Skip to content →

Tag: symmetry

a Da Vinci chess problem

2005
was the year that the DaVinci code craze hit Belgium. (I started reading Dan Brown’s
Digital Fortress and Angels and Demons a year
before on the way back from a Warwick conference and when I read DVC a
few months later it was an anti-climax…). Anyway, what better way
to end 2005 than with a fitting chess problem, composed by Noam Elkies

The problem is to give an infinite sequence
of numbers, the n-th term of the sequence being the number of ways White
can force checkmate in exactly n moves. With the DVC-hint given, clearly
only one series can be the solution… To prove it, note that
White’s only non-checkmating moves are with the Bishop traveling
along the path (g1,h2,g3,h4) and use symmetry to prove that the number
of paths of length exactly k starting from h2 is the same as those
starting from g3…

If that one was too easy for you,
consider the same problem for the position

Here the solution are the 2-powers of those
of the first problem. The proof essentially is that White has now two
ways to deliver checkmate : Na6 and Nd7… For the solutions and
more interesting chess-problems consult Noam Elkies’ excellent
paper New directions in
enumerative chess problems
. Remains the problem which sequences can
arise on an $N \\times N$ board with an infinite supply of chess
pieces!

Leave a Comment

micro-sudoku

One
cannot fight fashion… Following ones own research interest is a
pretty frustrating activity. Not only does it take forever to get a
paper refereed but then you have to motivate why you do these things
and what their relevance is to other subjects. On the other hand,
following fashion seems to be motivation enough for most…
Sadly, the same begins to apply to teaching. In my Geometry 101 course I
have to give an introduction to graphs&groups&geometry. So,
rather than giving a standard intro to graph-theory I thought it would
be more fun to solve all sorts of classical graph-problems (Konigsberger
bridges
, Instant
Insanity
, Gas-
water-electricity
, and so on…) Sure, these first year
students are (still) very polite, but I get the distinct feeling that
they think “Why on earth should we be interested in these old
problems when there are much more exciting subjects such as fractals,
cryptography or string theory?” Besides, already on the first day
they made it pretty clear that the only puzzle they are interested in is
Sudoku.
Next week I’ll have to introduce groups and I was planning to do
this via the Rubik
cube
but I’ve learned my lesson. Instead, I’ll introduce
symmetry by considering micro-
sudoku
that is the baby 4×4 version of the regular 9×9
Sudoku. The first thing I’ll do is work out the number of
different solutions to micro-Sudoku. Remember that in regular Sudoku
this number is 6,670,903,752,021,072,936,960 (by a computer search
performed by Bertram
Felgenhauer
). For micro-Sudoku there is an interesting
(but ratther confused) thread on the
Sudoku forum
and after a lot of guess-work the consensus seems to be
that there are precisely 288 distinct solutions to micro-Sudoku. In
fact, this is easy to see and uses symmetry. The symmetric group $S_4$
acts on the set of all solutions by permuting the four numbers, so one
may assume that a solution is in the form where the upper-left 2×2
block is 12 and 34 and the lower right 2×2 block consists of the
rows ab and cd. One quickly sees that either this leeds to a
unique solution or so does the situation with the roles of b and c
changed. So in all there are $4! \\times \\frac{1}{2} 4!=24 \\times 12 =
288$ distinct solutions. Next, one can ask for the number of
_essentially_ different solutions. That is, consider the action
of the _Sudoku-symmetry group_ (including things such as
permuting rows and columns, reflections and rotations of the grid). In
normal 9×9 Sudoku this number was computed by Ed Russell
and Frazer Jarvis
to be 5,472,730,538 (again,heavily using the
computer). For micro-Sudoku the answer is that there are just 2
essentially different solutions and there is a short nice argument,
given by ‘Nick70′ at the end of the above mentioned thread. Looking a bit closer one verifies easily that the
two Sudoku-group orbits have different sizes. One contains 96 solutions,
the other 192 solutions. It will be interesting to find out how these
calculations will be received in class next week…

One Comment

quintominal dodecahedra


A _quintomino_ is a regular pentagon having all its sides
colored by five different colours. Two quintominoes are the same if they
can be transformed into each other by a symmetry of the pentagon (that
is, a cyclic rotation or a flip of the two faces). It is easy to see
that there are exactly 12 different quintominoes. On the other hand,
there are also exactly 12 pentagonal faces of a dodecahedron
whence the puzzling question whether the 12 quintominoes can be joined
together (colours mathching) into a dodecahedron.
According to
the Dictionnaire de
mathematiques recreatives
this can be done and John Conway found 3
basic solutions in 1959. These 3 solutions can be found from the
diagrams below, taken from page 921 of the reprinted Winning Ways for your Mathematical
Plays (volume 4)
where they are called _the_ three
quintominal dodecahedra giving the impression that there are just 3
solutions to the puzzle (up to symmetries of the dodecahedron). Here are
the 3 Conway solutions

One projects the dodecahedron down from the top face which is
supposed to be the quintomino where the five colours red (1), blue (2),
yellow (3), green (4) and black(5) are ordered to form the quintomino of
type A=12345. Using the other quintomino-codes it is then easy to work
out how the quintominoes fit together to form a coloured dodecahedron.

In preparing to explain this puzzle for my geometry-101 course I
spend a couple of hours working out a possible method to prove that
these are indeed the only three solutions. The method is simple : take
one or two of the bottom pentagons and fill then with mathching
quintominoes, then these more or less fix all the other sides and
usually one quickly runs into a contradiction.
However, along the
way I found one case (see top picture) which seems to be a _new_
quintominal dodecahedron. It can't be one of the three Conway-types
as the central quintomino is of type F. Possibly I did something wrong
(but what?) or there are just more solutions and Conway stopped after
finding the first three of them…
Update (with help from
Michel Van den Bergh
) Here is an elegant way to construct
'new' solutions from existing ones, take a permutation $\\sigma
\\in S_5$ permuting the five colours and look on the resulting colored
dodecahedron (which again is a solution) for the (new) face of type A
and project from it to get a new diagram. Probably the correct statement
of the quintominal-dodecahedron-problem is : find all solutions up to
symmetries of the dodecahedron _and_ permutations of the colours.
Likely, the 3 Conway solutions represent the different orbits under this
larger group action. Remains the problem : to which orbit belongs the
top picture??

Leave a Comment