[r-t] Crambo - mystery solved(?)
Richard Smith
richard at ex-parrot.com
Tue Sep 5 16:23:59 UTC 2006
I've just been working through the details of Robert's proof
of the 'Crambo Theorem' thinking about how it might
generalise. I haven't managed to achieve anything, and I'm
starting to think that this is just an oddity that only
applies on five bells, but I thought I'd post my musings
here in case they help anyone else see how it might
generalise.
I've started by interjecting some comments and diagrams
into Robert's proof making a few of the steps more explict.
(Most of these points are obvious in the five bell case but
are not obviously true in generalisations.)
Robert Johnson wrote:
> As requested by the Ander here is a short proof of the
> Crambo Theorem (every in-course half extent of doubles
> admits a crambo).
>
> Given an in-course half extent on 5 make a bipartite graph
> G by listing the "slots" (ie pairs of adjacent rows) on
> the left and the out-of-course rows on the right and
> joining a slot to a row if inserting that row in that slot
> gives a legal touch. We'd like to find a perfect mathcing
> in this (that is a set of edges which pairs up everything
> on the left with everything on the right). Obviously
> every slot has degree 2 (it sees 2 rows) and the averagre
> degree of an ooc row is 2.
Each slot has degree 2 because the only ways in which a the
effect of a double change can be achieved in two
single changes is doing one swap in one change and the
second swap in the next change. (Which one is done first
makes no difference.)
1 = 123.145 = 145.123
3 = 123.345 = 345.123
5 = 125.345 = 345.125
> If all the ooc rows have degree 2 then we are happy as the
> graph is just a disjoint union of even cycles so certainly
> has a perfect matching. If not then some rows have degree
> 1.
To be rigorous, we need also to show that there are no ooc
rows with degree 0. As these correspond to rows that cannot
be present in the crambo, and the crambo (by definition)
includes the whole extent, an ooc row with degree 0 means
the crambo cannot exist.
Suppose abcde has degree 0. The graph of double changes
'near' to abcde looks as follows. This shows all the
potential slots for abcde (which are marked with asterisks)
and all rows that might go next to the slot.
\ /
\ /
cadbe
\ 5 / /
\ / /
cabed ----- acbde baecd
/ 3 \ / \
/ *1* \ / 5 \
abced
|
*3* |
|
bacde
\ *5* / \ 1 /
\ 3 / \ /
badec ----- abdce bcaed
/ \ \
/ 1 \ \
adbec
/ \
/ \
For abcde to have degree 0, none of the slots (the starred
marked edges) can be present in the half-extent. Once these
are removed, abced and bacde are only connected by one edge
and so can't be part of the half-extent.
\ /
\ /
cadbe
\ 5 / /
\ / /
cabed ----- acbde baecd
/ 3 / \
/ / 5 \
abced
bacde
\ \ 1 /
\ 3 \ /
badec ----- abdce bcaed
/ \ \
/ 1 \ \
adbec
/ \
/ \
As the initial premise was that we had a half-extent (which,
by definition, includes all rows including abced and bacde),
we have a contradiction and therefore no ooc rows of degree
0 exist.
We can see this more simply by just drawing the graph of
slots to be removed:
1 3 5
acbde ----- abced ----- bacde ----- abdce
[145] [123] [345] [125]
and as, in the whole graph, each row has degree 3 (there are
three double changes), once two edges are removed, only one
remains, precluding a half-extent.
> If abcde has degree 1 then the touch must contain the
> block
>
> baecd
> abced
> bacde
> bcaed
>
> (This is because we must have a slot which is adjacent to
> abcde next to both abced and bacde so these must be
> consecutive in the touch, and we are now not allowed a 1
> pn next to abced or a 5 pn next to bacde.)
This is readily apparent from the graphs above. If abcde is
a 'dangler' then only one of the starred edges -- the slots
-- can be present in the half-extent. If *1* is left, and
*3* and *5* removed, then bacde is problematic as it only
has one remaining edge (the 1 pn to bcaed):
1 3 5
acbde abced ----- bacde ----- abdce
[ --- = edges to be removed ]
By similar logic *5* cannot be the only slot present in the
extent. This leaves *3* to investigate:
1 3 5
acbde ----- abced bacde ----- abdce
[ --- = edges to be removed ]
Once these are remove, abced now only has two edges -- the 5
pn to baecd and the remaining *3* slot to bacde, and bacde
is connected to bcaed via a 1 pn:
baecd
5
abced
3
bacde
1
bcaed
> Now if we pair up every degree 1 vertex (the prof calls
> these danglers) with the unique slot it is adjacent to and
> remove these slots and rows from the graph we get a
> bipartite graph in which every degree is 2.
>
> This is because the row baced (ie the other neiighbour of
> the slot which is deleted) has degree 3 in the graph.
>
> A matching in this graph finishes the job.
>
>
> This also gives an algorithm for finding all the cramboes.
> Locate the danglers (this is easy just look for the 1.3.5
> or 5.3.1 pns in the touch). Make an arbitrary choice of
> one edge in each compnent of the rest and everything else
> is forced. The number of cramboes will be 2^{number of
> components of G}
>
> I have no idea how to do any of this, or even what a
> sensible crambo conjecture would be, on more than 5.
One possible generalisation might be that every double-
change half-extent on any number of bells has at least one
single-change crambo. (I don't believe this to be true.)
As with the five-bell proof, each slot has degree 2, and the
average degree of the ooc rows is 2. Next, we'd like to
prove that there are no ooc rows of degree 0. And this
appears to be a sticking point.
On five bells, we considered the graph whose vertices were
in-course rows and edges were double changes, removed all
the edges between pairs of rows that are both a single
change away from some particular ooc row (abcdef), and
demonstrated that the graph was no longer Hamiltonian --
that a half-extent was not possible without using the
removed slots.
On six, the graph is that much more complicated. The graph
of slots for the ooc row abcdef looks as follows:
[1256]
abdcef
12 / \ 56
/ \
/ 34 \
[1234] abcdfe ------ bacdef [3456]
| |
| 14 36 |
| |
[1456] acbdef ------ abcedf [1236]
16
And the whole in-course graph of changes has degree 6 (for
the six double changes). If we remove the six edges above
from the graph, all of the in-course rows still have at
least degree 3 so there is no reason to suppose a
half-extent like this cannot exist. Unless we can prove
that no such half-extents exist, our proof falls down at the
first hurdle. (And I expect that there will be examples of
half-extents that do avoid these six edges.)
So no luck there.
Another possible generalisation might be that every
even-change (i.e. even parity changes only) half-extent on
any number of bells has at least one odd-change crambo.
Let's consider six bells again. One six, all even changes
are double changes, but odd changes may be either single
changes or the cross change. This means that in addition to
splitting a double change into its two component single
changes, we can *sometimes* also split it into a cross and
its complementary single change:
12 = 1234.1256 = 1256.1234 = x.3456 = 3456.x
14 = 1234.1456 = 1456.1234
16 = 1236.1456 = 1456.1236
34 = 1234.3456 = 3456.1234 = x.1256 = 1256.x
36 = 1236.3456 = 3456.1236
56 = 1256.3456 = 3456.1256 = x.1234 = 1234.x
This means that instead of six possible slots for a given
ooc row, abcdef, we have nine:
[1256]
abdcef
/ | \
/ | \
/ | 34 \
/ [x] | \
12 / badcfe \ 56
/ / \ \
/ / \ \
/ / 56 12 \ \
/ / \ \
[1234] abcdfe -------------- bacdef [3456]
| 34 |
| 14 36 |
| |
[1456] acbdef -------------- abcedf [1236]
16
But unfortunately, as the graph of even changes has degree
6, and we remove at most four edges from a given in-course
row, there is still the possibility that abcdef is an
unreachable ooc row -- i.e. in Robert's graph, G, (the
bipartite graph of slots and ooc rows) it has degree 0.
(Any hopes that the two sections forced by the removal of
four edges might form a closed loop can be easily
dispelled.)
A little closer, but still no joy.
(Incidentally, if we were to disallow any one of 14, 36 and
16, then we can at least clear the first hurdle, but
that seems too contrived to be of interest.)
So as I said at the start of the email, I haven't actually
achieved anything, but with any luck it might help someone
else to get somewhere.
RAS
More information about the ringing-theory
mailing list