[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
More information about the ringing-theory
mailing list