Temel Sayısal Boggle
Gelen bu yazı , biz a üzerinde Sayısal Boggle oyuna tanıtıldı$6 \times 6$ kuralları aşağıdaki gibidir
- Her hücre tek bir rakam içermelidir $0$ -e $9$.
- Bir hücreden başlayarak, komşu hücrelere geçerken rakamları toplarsınız (8 yönün hepsinde). Rakamlar toplandıkça soldan sağa birleştirilerek tek bir sayı oluşturulur. Başlangıç basamağının da toplandığını ve hücreleri yeniden ziyaret edebileceğinizi unutmayın .
Daha sonra görev, böyle bir ızgara oluşturmaktı ( $6 \times 6$) öyle ki inşa edilemeyen en küçük pozitif sayı mümkün olduğu kadar büyük olur.
Açıkçası, bu oyun ve sonraki optimizasyon herhangi bir boyuttaki kare ızgaralara genelleştirilebilir, $n \times n$.
Dahası, kendimizi üs ile sınırlamamıza gerek yok$10$. Herhangi bir pozitif tam sayı verildiğinde$b$, her hücrenin tek bir rakam içermesi gerektiğine karar verebiliriz $0$ -e $b-1$ ve optimizasyonu bu yeni tabana göre ortaya koyar (yalnızca kullanan tekli hariç $1$).
Bu genellemeden motive olarak, soruna daha küçük bazlarda bakabiliriz.
Özellikle vakaya bakarsak$n=2$ ve $b=2$optimizasyon görevimiz aşağıdakine benzer bir şeyle sonuçlanabilir:
Görünüşe göre, bu ızgara için (veya aslında herhangi biri için) $2 \times 2$ iki ile ızgara $0$s ve iki $1$s) Her ikili sayıyı Numerical Boggle kurallarına göre oluşturmak mümkündür (kendiniz deneyin). Böyle bir ızgaranın tabanında sonsuz genişliğe sahip olduğunu söyleyeceğiz$b$.
Ayrıca, bir üs olduğunu söyleyeceğiz $b$ sonsuz büyüklükte bir ızgarayı kabul ediyor, sonlu boyutlu bir kare ızgara var mı ($n \times n$) temelde sonsuz genişliğe sahip olan $b$. Bu bizi bulmacamıza götürür.
En büyük pozitif tam sayı tabanı nedir $b$ sonsuz ölçüde sonlu bir kare ızgarayı kabul eden veya böyle bir $b$var olmak? Lütfen cevabınızın kanıtını sağlayın.
Yanıtlar
İşte alt sınırla eşleştiğini düşündüğüm diğer cevabın alt sınırına uyacak bir üst sınır var , ancak Boggle'ın kurallarını yanlış anladım:
Herhangi bir $k\times k$ tahta, uzunluk sayısı-$n$ yollar kabaca büyür $8^n$. Örneğin, aşağıdakilerle sınırlandırılmıştır:$k^2 \cdot 8^n$: sahibiz $k^2$ başlanacak yerler ve oradan her adım, $8$talimatlar. (Her yöndeki her adım her zaman mümkün değildir, ancak bu bir üst sınırdır.)
Ancak sayısı $n$Tabandaki basamaklı sayılar $b$ kabaca büyür $b^n$: bu $(b-1)b^{n-1}$. İçin böylece$b \ge 9$, olası uzunluk yollarının sayısı $n$ sonunda sayısından daha küçük olacak $n$-digit sayılar ve bulamadığımız bazı sayılar olacaktır. Tahtayı ne kadar büyük yaparsak, bu felaket o kadar geç gerçekleşecek, ama sonunda gerçekleşecek.
İçin hala bir boşluk var
$5 \le b \le 8$, bir çözümün var olabileceği ama biz onu bilmiyoruz.
Izgaramız sonlu olduğundan ve sonsuz uzunluktaki dizileri temsil edebilmemiz gerektiğinden, her basamağa bağlı olmayan bir karede ızgaraya X rakamını eklemenin çok az anlamı var gibi görünüyor: eğer böyle bir basamak, o zaman önceki adımda, kötü bağlanmış X aracılığıyla yapılamayan diziler için erişilebilir X'li başka bir kareye ihtiyaç olacaktır. Bu, sonsuz dallanmaya neden oluyor gibi görünüyor (mümkün olan her diziyi yerleştirmemiz gerektiğinden, varsayabiliriz Bizim için her zaman en sinir bozucu yolu seçen şeytani bir düşman vardır) ki bunu sınırlı bir oyun alanında yapamayız.
Yukarıdakilerin gerçekten doğru olup olmadığından emin değilim, ama öyle olduğunu varsayarsak, her rakamın tüm olası rakamlara bağlı olduğu bazı "güzelce bağlanmış" panolar oluşturmaya çalışalım, böylece gerekli "sonsuz kapsamı" kolayca sağlayalım.
Temel-3 basit görünüyor (gerçekten bir kare istiyorsanız rastgele rakamlarla doldurun):
0 1 1 0
0 2 2 0
veya mümkün olan minimum kareye sığan minimum olası basamak sayısı ile:
0 0 1 2 1 2
Base-4 biraz daha az önemsiz, ancak yine de oldukça yapılabilir:
0 0 1 2 3 1 1 3 2 1 0 0
Temel-5 bir zorluk arz eder:
üst satırdaki en soldaki "iyi bağlanmış" hane yalnızca altta ve sağda 5 komşu olamaz:
0 4 1 2 3
Elbette başka bir numara ekleyerek bunu düzeltebiliriz, ancak hala sorunumuz var
aynı anda
1. güzel bir şekilde bağlanmış (olası tüm rakamların yanında),
2. üst satırda ve
3. satırın en solunda bulunan bir rakam olamaz .
Dolayısıyla, ilk bölümdeki varsayımın herhangi bir değere sahip olduğunu varsayarsak (olduğundan hiç emin değilim), o zaman yapabileceğimiz en fazla şey
standart bir 4x4 boggle panosunun içine sığan base-4.
Misha Lavrov'un cevabında küçük bir gelişme.
Farklı uzunluk yollarının sayısı $nk$ bir izlenebilir $n\times n$ ızgara en fazla $n^2(8^n-3^n)^k$. Bunun nedeni, her grup$n$ ardışık hareketlerin tümü yukarı doğru gidemez, bu nedenle en fazla $8^n-3^n$ her grup için izin verilen yön dizileri.
$k$Bunun kökü $n^{2/k}(8^n-3^n)<8^n$ için $k$ yeterince büyük (açısından $n$). Böylece kesinlikle daha azını yapabilirsiniz$8^{nk}$ farklı uzunluk sayıları $nk$ bir değer için $k$yani durum $b=8$ da mümkün değil.
Maalesef bunun daha fazla zorlanabileceğini düşünmüyorum:
bir zarfın arkası hesaplaması, yeterince büyük $n$ gerçekten daha fazlası var $7^k$ farklı uzunluk yolları $k$ her biri için $k$rastgele bir yürüyüş $8$ tüm seçenekler ama $k-O(k/n)$ yüksek olasılıklı adımlar ve $8^{1-O(1/n)}>7$ büyük için $n$.
Sanırım Bass'ın cevabını destekleyen daha güçlü bir argümanım var.
1. Sonlu sayıda Boggle pano adası tüm dizileri birlikte oluşturabiliyorsa, en az bir ada tüm dizilerin sıfır olmayan oranını oluşturur.
2. Eğer bir ada tüm dizilerin sıfır olmayan oranını üretebiliyorsa, aslında tüm dizileri oluşturabilir (ve bu nedenle sonsuz kapsama sahiptir). Gerekçe: Belirli bir sonlu uzunluk dizisi üretemiyorsa$k$uzunluk için oluşturulan dizilerin oranı $\ell+1$ (kabaca) $1-1/2^k$ uzunluk için bunun katı $\ell$. Bu nedenle, herkes için oran$\ell \in [1, \infty)$sıfıra yakınsar. Çelişki.
3. Sonsuz genişliğe sahip sonlu bir tahta, kendisinden başlayarak tüm dizileri üretmeyen bir hücreye sahipse, bu hücre sonsuz boyuta zarar vermeden çıkarılabilir. Gerekçe: Sonucun yanlış olduğunu varsayın. Daha sonra bir dizi söz konusu hücreden geçmeye zorlanır ve varsayımla, pano tarafından üretilemeyen bir dizi oluşturabiliriz (bu, hücreye zorlama dizisi + hücreden üretilemeyen dizi) . Çelişki.
4. Tüm sonlu panolar $b \ge 5$en azından kendisinden başlayarak tüm dizileri üretemeyen bir hücre içerir. Bass'ın cevabında gözlemlendiği gibi bu önemsizdir, çünkü en soldaki hücre her zaman 4 veya daha düşük bir dış dereceye sahiptir.
5. 3 ve 4'ü birleştirerek, sonsuz genişliğe sahip sonlu bir tahta yoktur. $b \ge 5$.
Yukarıdaki iddialarda herhangi bir mantıksal boşluk olmadığını varsayarsak, cevap
Bass'ın bulduğu gibi , sonsuz genişlikte bir karta izin veren maksimum taban 4'tür .
Sonuç için 1. ve 2. adımların gerçekten gerekli olmadığını tahmin ediyorum (
Sonlu bir adalar koleksiyonu hala sonlu bir kuruldur
), ancak IMO ilginç gözlemler oldukları için onları tutmaya karar verdim.
B = 5 için bir çözümün taslağı (?). Bazı geri bildirimleri davet etmek için bitmemiş resmi gösteriyorum.
Genel fikir: u dönüşlü otoyol:
renk kodlu plan. Mavi arka plandır. beyaz çizgiler, her biri dört "şeride" sahip olan dört değişken yön şeridini ayırmak için görsel yardımcılardır. Bunun sadece genel düzeni gösterdiğini unutmayın; nihai çözüm daha uzun ve daha fazla şerit gerektirebilir.
Tek bir şerit içinde her karenin aynı şerit içinde gerekli tüm komşuları içerdiğine dikkat edin.
Öyleyse, bunu ortadan kaldırmanın tek yolu, hareketi bir yöne doğru yönlendirmektir. Komşu şeritlerin devreye girdiği yer burasıdır. Gerekirse onlara dönebilir ve geri dönebiliriz.
Peki bu her şeyi çözüyor mu?
% 100 emin değilim. İki sorun var: 1. Birçok yerde u-dönüş yapabiliriz ama her yerde değil. 2. Her zaman değiştirilecek şeridi seçemeyiz. Yani, prensipte, son şeride varabiliriz ve yolumuz bitebilir.
2. Muhtemelen gerçek bir sorun değildir, çünkü bunu zorlamak için aşağı yukarı her zaman çapraz hareketleri zorlamak (ortogonal hareketler neredeyse kesinlikle bize çok fazla kıpırdama alanı sağlar) ve uygun zamanlarda şerit değiştirmeye zorlamak gerekir. Muhtemelen ne zaman u-dönüş yapacağımız üzerinde bir miktar kontrole sahip olmaktan alıkoyulamayacağımızdan, bu ikinci gereksinimi uygulamak çok zor görünüyor.
İçimden gelen his, 1'in de ele alınabileceğidir (şu anda tüm davaları ele almaktan rahatsız olamam. Başka biri yapmak isterse, oy vermem garanti edilecektir)
Gözlemlenmesi gereken bir şey, bu düzeneğe karşı yalnızca ileriye dönük planlamayla yenilebilecek saldırılar olduğudur. Bir düşman bir sonraki rakama haber vermeden karar verirse bizi öldürebilir:
Örnek, aşağıdaki ayrıntılı stratejiye sahip yukarıdan saldırı 2'dir: sarı-> kırmızı-> açık turuncu-> mor-> koyu turuncu arasında bir u dönüşü zorlamak. U dönüşünden hemen sonra bir haneyi tekrarlayarak şerit değiştirmeye zorlayın, sadece seçenek bırakmayan bir rengi bekleyin. Baştan başlamak. Açıktır ki, şerit değişikliklerinin ne zaman planlandığını önceden bilirsek, tam olarak ne zaman u dönüşü yapacağımızı ve bu saldırıyı yeneceğimizi ayarlayabiliriz.