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

[Richard Smith]

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