Grundlegendes numerisches Boggle
In diesem Beitrag wurden wir in das Spiel Numerical Boggle on a eingeführt$6 \times 6$ Vorstand, dessen Regeln wie folgt sind
- Jede Zelle muss eine einzelne Ziffer von enthalten $0$ zu $9$.
- Beginnend in einer Zelle sammeln Sie Ziffern, wenn Sie zu benachbarten Zellen (in alle 8 Richtungen) wechseln. Wenn die Ziffern gesammelt werden, werden sie von links nach rechts verkettet, um eine einzelne Zahl zu bilden. Beachten Sie, dass auch die Startziffer erfasst wird und Sie die Zellen erneut aufrufen können.
Die Aufgabe bestand dann darin, ein solches Gitter (von Größe) zu konstruieren $6 \times 6$) so, dass die kleinste positive Zahl, die nicht konstruiert werden kann, so groß wie möglich ist.
Offensichtlich kann dieses Spiel und die anschließende Optimierung auf quadratische Gitter jeder Größe verallgemeinert werden. $n \times n$.
Darüber hinaus müssen wir uns nicht auf die Basis beschränken$10$. Bei jeder positiven ganzen Zahl$b$können wir festlegen, dass jede Zelle eine einzelne Ziffer von enthalten muss $0$ zu $b-1$ und stellen Sie die Optimierung in Bezug auf diese neue Basis (mit Ausnahme von unary, die nur verwendet $1$).
Motiviert durch diese Verallgemeinerung können wir das Problem in kleineren Basen betrachten.
Insbesondere, wenn wir uns den Fall ansehen$n=2$ und $b=2$kann unsere Optimierungsaufgabe zu folgenden Ergebnissen führen
Es stellt sich heraus, dass für dieses Gitter (oder in der Tat jedes $2 \times 2$ Gitter mit zwei $0$s und zwei $1$s) Es ist möglich, jede Binärzahl nach den Regeln von Numerical Boggle zu konstruieren (probieren Sie es selbst aus). Wir werden sagen, dass ein solches Gitter eine unendliche Ausdehnung in der Basis hat$b$.
Darüber hinaus werden wir sagen, dass eine Basis $b$ gibt ein Gitter von unendlicher Ausdehnung zu, wenn es ein quadratisches Gitter von endlicher Größe gibt ($n \times n$) die unendliche Ausdehnung in der Basis hat $b$. Dies führt uns zu unserem Rätsel.
Was ist die größte positive Ganzzahlbasis? $b$ das ein endliches quadratisches Gitter von unendlicher Ausdehnung zulässt oder ein solches tut $b$existieren? Bitte beweisen Sie Ihre Antwort.
Antworten
Hier ist eine Obergrenze, die mit der Untergrenze der anderen Antwort übereinstimmt, von der ich dachte, dass sie mit der Untergrenze übereinstimmt, aber ich habe die Regeln von Boggle falsch verstanden:
Auf jedem $k\times k$ Brett, die Anzahl der Länge-$n$ Pfade wachsen ungefähr so $8^n$. Zum Beispiel ist es begrenzt durch$k^2 \cdot 8^n$: wir haben $k^2$ Orte zu beginnen, und von dort geht jeder Schritt in einen von $8$Richtungen. (Nicht jeder Schritt in jede Richtung ist immer möglich, aber dies ist eine Obergrenze.)
Die Anzahl der $n$-stellige Zahlen in der Basis $b$ wächst ungefähr so $b^n$: es ist $(b-1)b^{n-1}$. So für$b \ge 9$, die Anzahl der möglichen Längenpfade $n$ wird schließlich kleiner als die Anzahl von $n$-stellige Zahlen, und es wird einige Zahlen geben, die wir nicht finden können. Je größer wir das Board machen, desto später wird diese Katastrophe eintreten, aber sie wird irgendwann eintreten.
Es gibt noch eine Lücke für
$5 \le b \le 8$, wo eine Lösung existieren könnte, aber wir wissen es nicht.
Da unser Gitter endlich ist und wir in der Lage sein müssen, unendlich lange Sequenzen darzustellen, scheint es wenig sinnvoll, dem Gitter an einem Quadrat, das nicht mit jeder Ziffer verbunden ist, eine Ziffer X hinzuzufügen: Wenn wir jemals eine solche verwenden würden Ziffer, dann müsste im vorherigen Schritt auch ein anderes Quadrat mit X für die Sequenzen zugänglich sein, die nicht durch das schlecht verbundene X hergestellt werden können. Dies scheint eine unendliche Verzweigung zu verursachen (da wir jede mögliche Sequenz berücksichtigen müssen, können wir annehmen dass es einen bösen Gegner gibt, der immer den nervigsten Weg für uns wählt), was wir auf einem endlichen Spielfeld nicht tun können.
Ich bin mir nicht sicher, ob das oben Gesagte tatsächlich zutrifft, aber unter der Annahme, dass dies der Fall ist, versuchen wir, einige "gut verbundene" Karten zu konstruieren, bei denen jede Ziffer mit allen möglichen Ziffern verbunden ist, um so leicht das erforderliche "unendliche Ausmaß" bereitzustellen.
Base-3 scheint einfach zu sein (Pad mit zufälligen Ziffern, wenn Sie wirklich ein Quadrat wollen):
0 1 1 0
0 2 2 0
oder mit der minimal möglichen Anzahl von Ziffern, die in das minimal mögliche Quadrat passen:
0 0 1 2 1 2
Base-4 ist etwas weniger trivial, aber dennoch durchaus machbar:
0 0 1 2 3 1 1 3 2 1 0 0
Base-5 stellt eine Schwierigkeit dar:
Die am weitesten links stehende "gut verbundene" Ziffer in der oberen Reihe kann nicht allein 5 Nachbarn auf der unteren und rechten Seite haben:
0 4 1 2 3
Wir können dies natürlich beheben, indem wir eine weitere Nummer hinzufügen, aber wir haben immer noch das Problem, dass
Es kann keine Ziffer geben, die gleichzeitig
1. gut verbunden ist (neben allen möglichen Ziffern),
2. in der oberen Reihe und
3. die am weitesten links stehende Ziffer in ihrer Reihe.
Unter der Annahme, dass die Vermutung im ersten Kapitel etwas wert ist (ich bin mir überhaupt nicht sicher), können wir höchstens etwas tun
base-4, passt in ein Standard 4x4 Boggle Board.
Eine leichte Verbesserung der Antwort von Mischa Lawrow.
Die Anzahl der verschiedenen Längenpfade $nk$ das kann auf einem verfolgt werden $n\times n$ Gitter ist höchstens $n^2(8^n-3^n)^k$. Dies liegt daran, dass jede Gruppe von$n$ aufeinanderfolgende Züge können nicht alle nach oben gehen, es gibt also höchstens $8^n-3^n$ zulässige Richtungsfolgen für jede Gruppe.
Das $k$Die Wurzel davon ist $n^{2/k}(8^n-3^n)<8^n$ zum $k$ ausreichend groß (in Bezug auf $n$). Somit können Sie streng weniger als machen$8^{nk}$ unterschiedliche Längenzahlen $nk$ für einen Wert von $k$, so der Fall $b=8$ ist auch nicht möglich.
Leider glaube ich nicht, dass dies weiter vorangetrieben werden kann:
Eine Berechnung auf der Rückseite eines Umschlags legt nahe, dass dies groß genug ist $n$ es gibt wirklich mehr als $7^k$ verschiedene Längenwege $k$ für jeden $k$, da ein zufälliger Spaziergang hat $8$ Auswahl überhaupt aber $k-O(k/n)$ Schritte mit hoher Wahrscheinlichkeit und $8^{1-O(1/n)}>7$ für große $n$.
Ich glaube, ich habe ein stärkeres Argument, das Bass 'Antwort unterstützt.
1. Wenn endlich viele Inseln von Boggle-Brettern gemeinsam alle Sequenzen erzeugen können, erzeugt mindestens eine Insel einen Anteil ungleich Null aller Sequenzen.
2. Wenn eine Insel einen Anteil aller Sequenzen ungleich Null erzeugen kann, kann sie tatsächlich alle Sequenzen erzeugen (und hat somit eine unendliche Ausdehnung). Begründung: Wenn es keine bestimmte endliche Längenfolge erzeugen kann$k$, der Anteil der erzeugten Sequenzen an der Länge $\ell+1$ ist (ungefähr) $1-1/2^k$ mal das für die Länge $\ell$. Daher der Anteil für alle$\ell \in [1, \infty)$konvergiert gegen Null. Widerspruch.
3. Wenn eine endliche Tafel mit unendlicher Ausdehnung eine Zelle hat, die nicht alle Sequenzen erzeugt, die mit sich selbst beginnen, kann diese Zelle entfernt werden, ohne die unendliche Ausdehnung zu beeinträchtigen. Begründung: Angenommen, die Schlussfolgerung ist falsch. Dann wird eine Sequenz gezwungen, die fragliche Zelle zu durchlaufen, und unter der Annahme können wir eine Sequenz konstruieren, die nicht von der Karte erzeugt werden kann (dies ist die Sequenz, die in die Zelle erzwungen werden muss + die Sequenz, die nicht aus der Zelle erzeugt werden kann). . Widerspruch.
4. Alle endlichen Bretter für $b \ge 5$mindestens eine Zelle enthalten, die nicht alle Sequenzen generieren kann, die mit sich selbst beginnen. Dies ist trivial, wie in Bass 'Antwort zu sehen ist, da die Zelle ganz oben links immer einen Out-Grad von 4 oder weniger hat.
5. Wenn man 3 und 4 kombiniert, gibt es keine endliche Tafel mit unendlicher Ausdehnung für $b \ge 5$.
Angenommen, die obigen Behauptungen enthalten keine logische Lücke, lautet die Antwort
Die maximale Basis, die ein Board mit unendlicher Ausdehnung zulässt, ist 4 , wie von Bass gefunden.
Ich denke, die Schritte 1 und 2 werden für den Abschluss nicht wirklich benötigt (as
Eine endliche Ansammlung von Inseln ist immer noch eine endliche Tafel
), aber ich habe beschlossen, sie zu behalten, da IMO sie interessante Beobachtungen sind.
Skizze einer Lösung (?) Für b = 5. Ich zeige das unvollendete Bild, um Feedback zu erhalten.
Allgemeine Idee: Autobahn mit Kehrtwende:
farbcodierte Blaupause. Blau ist Hintergrund. weiße Linien sind visuelle Hilfsmittel, um vier Streifen mit wechselnder Richtung zu trennen, die jeweils vier "Spuren" aufweisen. Beachten Sie, dass hier nur das allgemeine Layout angezeigt wird. Die endgültige Lösung erfordert möglicherweise längere und mehr Streifen.
Beachten Sie, dass innerhalb eines einzelnen Streifens jedes Quadrat alle Nachbarn hat, die innerhalb desselben Streifens benötigt werden.
Die einzige Möglichkeit, dies zu töten, besteht darin, die Bewegung in eine Richtung zu lenken. Hier kommen die benachbarten Streifen ins Spiel. Wir können sie bei Bedarf auf und zurück drehen.
Löst das also alles?
Nicht 100% sicher. Es gibt zwei Probleme: 1. Wir können an vielen, aber nicht an allen Orten umkehren. 2. Wir können nicht immer den Streifen auswählen, zu dem wir wechseln möchten. Im Prinzip könnten wir also am letzten Streifen landen und keine Straße mehr haben.
2. ist wahrscheinlich kein wirkliches Problem, denn um dies zu erzwingen, müssten mehr oder weniger immer diagonale Bewegungen erzwungen werden (orthogonale Bewegungen geben uns mit ziemlicher Sicherheit zu viel Spielraum) und der Spurwechsel zu den entsprechenden Zeiten erzwungen werden. Da wir wahrscheinlich nicht davon abgehalten werden können, die Kontrolle darüber zu haben, wann diese zweite Anforderung umgedreht werden muss, scheint es zu schwierig, sie durchzusetzen.
Mein Bauchgefühl ist, dass ich auch angesprochen werden kann (ich kann mir gerade nicht die Mühe machen, alle Fälle zu verprügeln. Wenn jemand anderes dies tun möchte, ist meine Gegenstimme garantiert).
Eine Sache zu beachten ist, dass es tatsächlich Angriffe auf dieses Setup gibt, die nur durch Vorausplanung besiegt werden können. Wenn ein Gegner ohne Vorankündigung die nächste Ziffer bestimmen könnte, könnte er uns töten:
Das Beispiel ist Angriff 2 von oben mit der folgenden detaillierten Strategie: Durchlaufen von Gelb-> Rot-> Hellorange-> Lila-> Dunkelorange, um eine Kehrtwende zu erzwingen. Warten Sie kurz nach der Kehrtwende einen Spurwechsel, indem Sie eine Ziffer wiederholen. Warten Sie einfach auf eine Farbe, die keine andere Wahl lässt. Von vorn anfangen. Es ist klar, dass wir, wenn wir im Voraus wissen, wann die Spurwechsel geplant sind, uns anpassen können, wann genau umgedreht und dieser Angriff besiegt werden muss.