# [r-t] Crambo - mystery solved(?)

Richard Smith richard at ex-parrot.com
Fri Sep 8 17:17:26 UTC 2006

```Robert Johnson wrote:

> > More generally what is the largest k(n) for which there
> > exists an extent on n which remains a legal touch if you
> > strike out any k consecutive rows. (The fact that you
> > can't have more than 2^{n/2} rows with any two differing
> > by a legal change (proof an exercise to the reader)
> > shows that k=2^{n/2} - 1 is an upper bound for k.)

First of all, let's look at n=6.  Ander's already shown that
k(6) >= 1.  We can show that k(6) = 1.

The graph of changes that are allowed next to each other
(based purely on whether they would allow the removal of a
single row) is as follows:

..........................
:                        :
:        34     x        :
:  12                56  :
:          1256          :
:                        :
14 --:-- 1234          3456 --:-- 36
:     |            |     :
:.....|............|.....:
|            |
|            |
14 ----- 1456 -------- 1236 ----- 36
|            |
|            |
16          16

There are additionally edges between each of { x, 12,
34, 56, 1234, 1256, 3456 }, none of which are included on
the above graph.  The box contains all the changes that just
swap the bells in 1-2, 3-4 and 5-6 without mixing between
these positions.  Clearly an extent must use some changes
outside the box.

Consider a 14.1234 block.

123456
132465
132456

The next change must be from the box -- a 1456 is false, and
as a 14 could only be followed by a 1234, it can be ruled
out too.  If we want to allow two consectutive rows to be
removed (i.e. if k >= 2) we cannot swap the bells in 1-2 or
3-4.  However 1234 is the only change with this property
and, as that was the previous change, that will be false.
This means a 14.1234 block cannot exist if k >= 2.

Similarly, a 1456.1234 block cannot be followed by 14 (it is
false) or anything from the box meaning it can only be
followed by another 1456.  However, what can come after
that?  A 1234 would be come round, a 16 or 1236 would
introduce a jump change if two rows were removed.  This
means a 1456.1234 block can only be followed by a
1456.14.1456 block, however this is a round block.  This
means that 1234 (and by symmetry) 3456 cannot occur.

14 ----- 1456 -------- 1236 ----- 36
|            |
|            |
16            16

Now consider a 1456.1236 block.  This cannot be followed by
a 16 as this is a round block, nor can it be followed by a
36 as this produces a jump change when two rows are omitted.
This splits the graph in two:

14 ----- 1456 ----- 1236        1456 ----- 1236 ----- 36
|                                |
|                                |
16                                16

Neither of these can produce the extent as the left-hand
graph fixes the bell in 1sts place and the right-hand graph
fixes the bell in 6ths place.

And therefore k(6) = 1.

I think that this ought to generalise into a improved upper
bound on k:  k < 2^{n/2 - 2}.  I'll see if I can prove that
over the weekend.

RAS

```