[seqfan] Re: « King-walking » integers in a square box
franktaw at netscape.net
franktaw at netscape.net
Sat Feb 26 15:13:50 CET 2011
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/
More information about the SeqFan
mailing list