17
$\begingroup$

In this post, we were introduced to the game of Numerical Boggle on a $6 \times 6$ board, the rules of which are as follows

  • Each cell must contain a single digit from $0$ to $9$.
  • Starting in one cell you collect digits as you move to neighbouring cells (in all 8 directions). As the digits are collected they are concatenated left to right, to form a single number. Note that the starting digit is collected too and you can revisit cells.

The task then was to construct such a grid (of size $6 \times 6$) such that the smallest positive number that cannot be constructed is as large as possible.

Obviously, this game and subsequent optimisation can be generalised to square grids of any size, $n \times n$.
Moreover, we need not restrict ourselves to base $10$. Given any positive integer $b$, we can decree that each cell must contain a single digit from $0$ to $b-1$ and pose the optimisation with respect to this new base (with the exception of unary which only uses $1$).

Motivated by this generalisation, we can look at the problem in smaller bases.
In particular, if we look at the case $n=2$ and $b=2$, our optimisation task may result in something like the following

                                                                                enter image description here

It turns out that, for this grid (or indeed any $2 \times 2$ grid with two $0$s and two $1$s) it is possible to construct every binary number according to the rules of Numerical Boggle (try it yourself). We will say that such a grid has infinite extent in base $b$.

Furthermore, we will say that a base $b$ admits a grid of infinite extent is there is some square grid of finite size ($n \times n$) which has infinite extent in base $b$. This leads us to our puzzle.

What is the largest positive integer base $b$ which admits a finite square grid of infinite extent or does such a $b$ exist? Please provide proof of your answer.

$\endgroup$
  • 1
    $\begingroup$ Oooh I love this generalisation! Great idea. $\endgroup$ – Dmitry Kamenetsky Oct 13 at 13:58
  • $\begingroup$ Note the solution will be different if you are also allowed to stay in the same cell. $\endgroup$ – Dmitry Kamenetsky Oct 13 at 14:05
  • $\begingroup$ I've realised something that could be useful for someone. We are looking for a finite state automaton that accepts every number in base b. The nodes cannot have self edges and must have degree at most 8. $\endgroup$ – Dmitry Kamenetsky Oct 14 at 9:29
  • 1
    $\begingroup$ Copy of my own comment under Dmitry's answer: A Boggle board is basically an NFA having (number of boggle cells + 2) states, and it is practically impossible to prove that a specific board is universal using exhaustive search since the shortest rejecting word can be exponential in size (e.g. $2^{38}$ on a 6×6 board). So it is not helpful to post a random board that "looks like a solution" for some $n$, unless it is accompanied by a mathematical proof that it really is a solution. $\endgroup$ – Bubbler Oct 16 at 8:03
9
$\begingroup$

Here is an upper bound to match the lower bound of the other answer which I thought matched the lower bound, but I misunderstood the rules of Boggle:

On any $k\times k$ board, the number of length-$n$ paths grows roughly as $8^n$. For example, it is bounded by $k^2 \cdot 8^n$: we have $k^2$ places to start, and from there, each step goes in one of $8$ directions. (Not every step in every direction is always possible, but this is an upper bound.)

However, the number of $n$-digit numbers in base $b$ grows roughly as $b^n$: it is $(b-1)b^{n-1}$. So, for $b \ge 9$, the number of possible paths of length $n$ will eventually be smaller than the number of $n$-digit numbers, and there will be some numbers we can't find. The larger we make the board, the later this catastrophe will occur, but it will occur eventually.

There is still a gap for

$5 \le b \le 8$, where a solution might exist, but we don't know it.

| improve this answer | |
$\endgroup$
8
$\begingroup$

Since our grid is finite, and we need to be able to represent infinitely long sequences, there seems little point in adding any digit X to the grid at some square that isn't connected to every digit: if we were ever to use such a digit, then at the previous step there would also need to be another square with X accessible for the sequences that cannot be made through the badly connected X. This seems to cause infinite branching (since we have to accommodate every possible sequence, we can assume that there's an evil adversary always choosing the most annoying path for us), which we can't do on a finite playfield.

I'm not sure if the above is actually true, but assuming it is, let's try to construct some "nicely connected" boards where every digit is connected to all possible digits, thus easily providing the required "infinite extent".

Base-3 seems simple (pad with random digits if you really want a square):

0 1 1 0
0 2 2 0

or with the minimum possible number of digits, which fit inside the minimum possible square:

   0
 0 1 2
 1 2

Base-4 is a bit less trivial, but still quite doable:

    0 0
  1 2 3 1
  1 3 2 1
    0 0

Base-5 presents a difficulty:

the left-most "nicely connected" digit in the top row cannot have 5 neighbours on the bottom and right sides alone:

   0 4
 1 2 3
  

We can of course fix this by adding another number, but we still have the problem that

there cannot be a digit that is at the same time
1. nicely connected (next to all possible digits),
2. in the top row, and
3. the leftmost digit in its row.

So assuming that the conjecture in the first chapter is worth anything (I'm not at all sure it is), then the most we can do is

base-4, which fits inside a standard 4x4 boggle board.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I thought that every digit needs to be adjacent to every other digit as well, but it's not obviously a requirement. As long as each digit distinct from X is adjacent to some copy of X, it is not obvious how you would prove that you get stuck in one particular location. $\endgroup$ – Jeremy Dover Oct 13 at 17:55
  • 4
    $\begingroup$ @JeremyDover Yeah, I've tried to formulate a rigid argument for that, but it (along with a counterexample of a useful badly connected digit) seems quite elusive. As an extremely tangential but still shocking discovery: I tried to take a photo of this setup done with actual Boggle letters, but my entire Super Boggle set (the official Hasbro version with 25 dice) has exactly two instances of the letter B, and those are both on the same cube. So after "qi", the next shortest word one can never find in Boggle is very likely to be "ebb" :-) $\endgroup$ – Bass Oct 13 at 18:25
  • 1
    $\begingroup$ On a general graph, I think the conjecture is false. For example, in base 4, connect every $0$, $1$, $2$ to itself and to each other. Then add $3_{0,1}$, $3_{1,2}$, and $3_{0,2}$ where $3_{a,b}$ is connected to $a$, $b$, and itself. No $3$ needs to be connected to all three other digits. (But, I'm not sure if this can be realized on a Boggle board.) $\endgroup$ – tehtmi Oct 14 at 9:12
  • 2
    $\begingroup$ @tehtmi A good (counter)example was given by Retudin in a comment to Bubbler's answer. $\endgroup$ – Jaap Scherphuis Oct 14 at 11:36
4
$\begingroup$

A slight improvement to Misha Lavrov's answer.

The number of different paths of length $nk$ that can be traced out on an $n\times n$ grid is at most $n^2(8^n-3^n)^k$. This is because each group of $n$ consecutive moves cannot all go upwards, so there are at most $8^n-3^n$ permissible sequences of directions for each group.

The $k$th root of this is $n^{2/k}(8^n-3^n)<8^n$ for $k$ sufficiently large (in terms of $n$). Thus you can make strictly fewer than $8^{nk}$ different numbers of length $nk$ for some value of $k$, so the case $b=8$ is also not possible.

Unfortunately I don't think this can be pushed any further:

a back-of-an-envelope calculation suggests that for large enough $n$ there really are more than $7^k$ different paths of length $k$ for every $k$, since a random walk has $8$ choices at all but $k-O(k/n)$ steps with high probability, and $8^{1-O(1/n)}>7$ for large $n$.

| improve this answer | |
$\endgroup$
2
$\begingroup$

I think I have a stronger argument that supports Bass's answer.

1. If finitely many islands of Boggle boards can jointly generate all sequences, at least one island generates nonzero proportion of all sequences.

2. If an island can generate nonzero proportion of all sequences, it can actually generate all sequences (and thus it has infinite extent). Rationale: If it cannot generate a certain finite sequence of length $k$, the proportion of generated sequences for length $\ell+1$ is (roughly) $1-1/2^k$ times that for length $\ell$. Therefore, the proportion for all $\ell \in [1, \infty)$ converges to zero. Contradiction.

3. If a finite board with infinite extent has a cell that does not generate all sequences starting with itself, that cell can be removed without harming the infinite extent. Rationale: Assume the conclusion is false. Then some sequence is forced to go through the cell in question, and by assumption, we can construct a sequence that cannot be generated by the board (which is the sequence to force to the cell + the sequence that cannot be generated from the cell). Contradiction.

4. All finite boards for $b \ge 5$ contain at least a cell that cannot generate all sequences starting with itself. This is trivial as observed in Bass's answer, as the topmost leftmost cell always has an out-degree of 4 or lower.

5. Combining 3 and 4, there does not exist a finite board with infinite extent for $b \ge 5$.

Assuming there isn't any logical hole in the above claims, the answer is

The maximum base that allows a board of infinite extent is 4, as found by Bass.


I guess the steps 1 and 2 are not really needed for the conclusion (as

a finite collection of islands is still a finite board

), but I decided to keep them since IMO they're interesting observations.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I don't quite follow #3. If a cell is not removable, there is a finite sequence that is forced to pass through the cell. However, I don't see why there must be a sequence that is forced to end at that cell. Maybe the only way you are forced to use that cell depends on both what comes before and what comes after it, and what comes after it in such a forcing sequence might always be in the available set. If you change what's after it in the sequence to an unavailable one, you are no longer forced to go through the cell but along some other path. $\endgroup$ – Jaap Scherphuis Oct 14 at 8:41
  • 5
    $\begingroup$ counter example for #3. n=4, 5*5 board: 11311 13031 32103 13231 11311. The 1 in the middle is needed for 012 but not connected to a 1. $\endgroup$ – Retudin Oct 14 at 9:13
  • $\begingroup$ Hmm, so that doesn't work :( $\endgroup$ – Bubbler Oct 14 at 9:30
2
$\begingroup$

Sketch of a solution (?) for b=5. I'm showing the unfinished picture to invite some feedback.

General idea: highway with u-turns:

enter image description here

color coded blueprint. Blue is background. white lines are visual aides to separate four strips of alternating direction each having four "lanes". Note that this is just showing the general layout; the final solution may require longer and more strips.

Observe that within a single strip each square has all the neighbors required within the same strip.

So the only way to kill this is to bias the movement in one direction. Which is where the neighboring strips come into play. We can u-turn onto them and back if needed.

So does this solve everything?

Not 100% sure. There are two problems: 1. we can u-turn in many but not all places. 2. we cannot always choose the strip to change to. So, in principle, we may end up at the last strip and run out of road.

2. is probably no real problem because to force this would require to more or less always force diagonal moves (orthogonal moves almost certainly give us too much wiggle room) and force changing lane at the appropriate times. As we probably can't be kept from having some control over when to u-turn this second requirement looks too difficult to enforce.

My gut feeling is that 1 can be addressed, too (I just can't be bothered to bash all the cases right now. If anybody else wants to do it go ahead, my upvote will be guaranteed)

One thing to observe is that there are indeed attacks on this setup that can only be defeated by forward planning. If an adversary could decide the next digit without notice they could kill us:

The example is attack 2 from above with the following detailed strategy: cycle through yellow->red->light orange->purple->dark orange forcing a u-turn. quickly after the u-turn force a lane change by repeating one digit, just wait for a color that leaves no choice. Start over. It is clear, that if we know in advance when the lane changes are scheduled we can adapt when exactly to u-turn and defeat this attack.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Paul I think this is a great attempt - much better than mine. What happens when the number reaches one of the corner cells? Those cells only have 3 neighbours so an adversary will be able to exploit that. For this solution to work, we need to show that a number never reaches any corner cells. $\endgroup$ – Dmitry Kamenetsky Oct 18 at 1:26
  • 1
    $\begingroup$ @DmitryKamenetsky Ideally, it won't come to that because we have managed to u-turn before getting that far out. Adjacent strips are patterned in opposite direction, so as long as we can roughly control when to change between them we can always keep away from the ends. Showing this rigorously (if it is true) is the challenge. $\endgroup$ – Paul Panzer Oct 18 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.