Basic Numerical Boggle

Question

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

                                                                                

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.

Answer 4

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

General idea: highway with u-turns:

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.

Answer 5

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.