[seqfan] Re: « King-walking » integers in a square box

[franktaw at netscape.net]

I can now settle the cases base 5 and base 9.

For base 5, consider the arrangement:

.012.
24304
31.13
02324
.410.

The dots can be anything. Every digit in this arrangement is next to 
every other base 5 digit, and so every sequence of base 5 digits can be 
obtained without leaving the specified digits.

On the other hand, for base 9 it is not possible to get arbitrarily 
large numbers from a single arrangement. Given a box of base 9 digits, 
we will construct a sequence of digits d_1 d_2 ... d_k which cannot be 
obtained. We use two associated sequences b_1 ... b_k and c_1 ... c_k. 
For each d_1 ... d_i, there is a set S_1 of the digits in the box which 
can be the end point of this sequence. b_i is the number of elements in 
this set, and c_i is the minimum distance from any element of the set 
to an edge (0 for an edge or corner). We can take d_1 arbitrarily; S_1 
will be all instances of d_1 in the box.

Each successive d_(i+1) will be chosen so that, if possible, b_(i+1) < 
b_i. If this is not possible, then the b_i digits have 8b_i neighbors, 
which must then be the 8 other digits each occurring b_i times. In 
particular, all elements of S_i must have 8 neighbors, and thus not be 
on an edge. We can then choose an element of S_i which is as close as 
possible to the edge, and take a neighbor of it that is closer to the 
edge; the value in that position will be d_(i+1). Now we will have 
b_(i+1) = b_i, and c_(i+1) < c_i. So by induction over omega^2, we will 
eventually get b_i = 0, and that sequence will not be obtainable. QED

Franklin T. Adams-Watters

-----Original Message-----
From: franktaw at netscape.net

There was considerable discussion about this some months ago. 
 
I got to thinking, what about other bases? 
 
Obviously, for b = 4 (or less), the 2x2 square: 
 
0 1 
2 3 
 
produces all non-negative integers. 
 
On the other end, the number of walks of length m on a kxk square is 
bounded by k^2 * 9^n, so for base 10 or more, there are always numbers 
that cannot be obtained. 
 
So what about the intermediate cases, bases 5 through 9? In particular, 
can anyone come up with a box, of any size, which generates all base 5 
integers? 
 
(I will be very surprised if a base 9 solution is possible, but about 
bases 5, 6, 7, and 8 I'm very much in doubt.) 
 
Franklin T. Adams-Watters 
 
> ----------------original message----------------- 
> From: "Eric Angelini" Eric.Angelini at kntv.be 
> To: "Sequence Fanatics Discussion list" seqfan at list.seqfan.eu 
> Date: Fri, 23 Jul 2010 16:50:20 +0200 
> ------------------------------------------------- 
> 
> 
>> 
>> Hello SeqFans, 
>> In this 4x5 box one can read all 
>> consecutive integers from 0 to 158 
>> (included): 
>> 5 8 0 7 3 
>> 9 6 5 1 8 
>> 1 3 2 4 2 
>> 4 0 9 7 6 
>> (grid submitted by James Dow Allen 
>> on rec.puzzles two days ago) 
>> 
>> The rules are: 
>> - an integer is there if it's digits 
>> can be walked on by a chess King 
>> (one step in 8 directions: 
>> 4 straightly, 4 diagonally) 
>> - two identical digits (or more) can 
>> follow each other (as if the King 
>> was jumping on the same square). 
>> 
>> Example: 
>> - the integers 58073, 13997 and 13887 
>> are visible below, 
>> - the integer 159 is not: 
>> 5 8 0 7 3 
>> 9 6 5 1 8 
>> 1 3 2 4 2 
>> 4 0 9 7 6 
>> It seems impossible to find such a 
>> 4x5 box showing all consecutive in- 
>> tegers from 0 to 'n' with 'n' > 158. 
>> 
>> Here is Giovanni Resta's 158 solution 
>> for the same box: 
>> 0 3 6 4 2 
>> 1 7 5 1 3 
>> 4 0 2 8 9 
>> 8 9 6 5 7 
>> (published on rec.puzzles yesterday) 
>> 
>> Question: 
>> Using the same rules, what would be 
>> the highest reachable integer in the 
>> successive square boxes 1x1, 2x2, 3x3, 
>> 4x4, 5x5, ... 
>> This might constitute a seq S for Neil. 
>> [S starts 0, 3, 8, ...] 
 
_______________________________________________ 
 
Seqfan Mailing list - http://list.seqfan.eu/