[r-t] Crambo - mystery solved(?)
Richard Smith
richard at ex-parrot.com
Thu Sep 7 09:05:42 UTC 2006
Robert Johnson wrote:
> Here's a funny little question vaguely inspired by crambo
> (tho' crambo doesn't actually have this property). Can you
> constuct an extent on n which remains a legal touch if you
> strike out any row.
Other than the trivial solutions on 1 and 2 bells, it is not
possible for n < 6. The proof for n = 5 is quite involved
because of the number of steps involved and cases to be
considered. I hope I haven't overlooked any possibilities.
On three bells, it's clearly impossible -- there's one
extent and it doesn't have this property. On four, it's
also impossible: all extents contain 14 pns, and a 14 cannot
be combined with any other change to make another valid
change -- 14.12 and 14.34 are 3-cycles; 14.x is a 4-cycle.
In general, two changes can only be adjacent if they do not
have partially-overlapping swaps.
On five, this means the following changes are allowed next
to each other:
125 ----- 345 ----- 123 ----- 145
\ / \ / \ /
\ / \ / \ /
5 3 1
Each of the 3-loops on the graph correspond to round blocks,
so, for example the sequence 125.5.345 is round block and
therefore cannot be present in an extent. This means the
changes on either side of a double change must be the same:
3 3
| |
| |
125 ----- 345 ----- 123 ----- 145
| | | |
| | | |
5 5 1 1
Let's consider 125.5.125. According to the graph, this can
only be followed by a 345 or another 5. However it cannot
be followed by 345 as 5.125.345 at the end would form a
round block making the touch false, and it cannot be
followed by another 5 as 125.5 x2 is a round block. This
means we cannot have a 125.5.125, or (by symmetry) a
145.1.145 in an extent.
3 3
| |
| |
125 ----- 345 ----- 123 ----- 145
| |
| |
5 1
Similarly, 345.3.345 cannot be followed by 123 and 345.5.345
cannot be followed by a 125. This knowledge can be added
into the graph to give the following:
.................................. ..........
: : : :
: : : :
: 345 --- 125 --- 345 --- 123 --- 145 --- 123 :
: / \ / : : \ :
: / \ / : : \ :
: 3 X : : 3 :
: \ / \ : : / :
: \ / \ : : / :
: 345 ---- 5 ---- 345 --- 123 ---- 1 ---- 123 :
: : : :
:................................: :........:
Same pair of bells in 1-2 Same bells
in 1-2
As the 1 and 145 changes are the only ones that change
(rather than simply reordering) the bells in 1-2, the large
left-hand box on the graph has the same bells in 1-2
throughout, as does the smaller right-hand box. This means
that if a 345.3.345 block occurs, it must be in the middle
of a larger block of at least 10 rows with the same bells in
1-2 -- the shortest path from outside of the left-hand box
to the 3 and back is 9 changes long.
We know that it cannot be in a block of 11 rows with 1-2
fixed as there are no 10-change paths through the left-hand
box. Further, the only way that a 345.3.345 could occur in
a block of 12 rows (an 11-change path) is by taking a
9-change path and inserting a 2-change detour -- i.e. going
to a new vertex and back again. It's easy to verify that
all such detours are false as all involve a sequence of
changes x.y.x.y which (for all x,y in the graph) is false.
(This is by definition: if there is an edge betweeen x and
y, x.y is a change and has order 2; therefore x.y.x.y = 1.)
Therefore each 345.3.345 is in a block of precisely 10 rows
with a fixed pair of bells in 1-2, meaning that the other
two rows must be elsewhere in the extent. It's easy to see
that these rows must be consecutive: the only way to get an
isolated row with a given pair of bells in 1-2 is with a
1.145, but this is not a legal pair of consecutive changes.
And the only legal ways of getting two rows are with either
1.123.1 or 145.123.145, but in both cases the next change
must be a 123 meaning we are false (x.y.x.y again).
This means that 345.3.345 can never occur in an extent, nor,
by a similar argument for the bells in 4-5, can 123.3.123.
We can now delete the 3 pns from the graph together with the
adjacent 123s and 345s (which would, in the absense of the
3, necessarily by false).
...................
: :
: 125 :
: | :
: | :
: 345 :
: / \ :
: / \ :
1 ---- 123 123 --- 145
: \ / :
: \ / :
: 345 :
: | :
: | :
: 5 :
:.................:
(Again, the box is surrounding changes with the same pair of
bells in 1-2.)
With a little bit of experimentation, we can see that the
only length paths through the box (whether from one side to
the other, or in and out the same side) that do not have any
x.y.x.y sections are 4, 6 or 10 rows long. (Paths of 14
rows and longer are also possible, but these are clearly
false.) These are
Length 4: 123.345.123
Length 6: 123.345.[12]5.345.123
Length 10: 123.345.[12]5.345.123.345.[12]5.345.123
The length 10 section cannot occur as there are no length 2
sections for the remaining two rows with the same bells
fixed in 1-2 to occur in.
What about the length 6 sections? There are two variants of
this differing by their middle change (125 or 5):
125 5
12345 12345
12354 12354
21354 21354
21534 12534
12534 21534
12543 21543
Both of these blocks have one bell in 3rds for 3 blows, and
then a second bell in 3rds for 3 blows. This means that one
of the rows with each of these bells in 3rds is missing and
cannot be supplied by either of these blocks. (And we
cannot use a length 4 block to supply it as this would again
require a length 2 block for the last two rows.) Therefore
neither of these blocks can be present in an extent.
This has ruled out all possible uses of the 5 and 125
changes (the length 4 block contains neither), and (by
symmetry, or by a similar argument based on the work in 4-5)
we can eliminate all uses of the 1 and 145 changes. This,
however, leaves us with just two changes that can be present
in the extent -- 123 and 345 -- and the longest we can do
with these is an x.y.x.y round block.
Which means no 5-bell extent with these properties can
exist.
RAS
More information about the ringing-theory
mailing list