Skip to content →

Tag: puzzle

The 15-puzzle groupoid (1)

Published June 17, 2007 by lievenlb

Before we go deeper into Conway’s M(13) puzzle, let us consider a more commonly known sliding puzzle: the 15-puzzle. A heated discussion went on a couple of years ago at sci-physics-research, starting with this message. Lubos Motl argued that group-theory is sufficient to analyze the problem and that there is no reason to resort to groupoids (‘The human(oids) who like groupoids…’ and other goodies, in pre-blog but vintage Motl-speak) whereas ‘Jason’ defended his viewpoint that a groupoid is the natural symmetry for this puzzle.

I’m mostly with Lubos on this. All relevant calculations are done in the symmetric group $S_{16} $ and (easy) grouptheoretic results such as the distinction between even and odd permutations or the generation of the alternating groups really crack the puzzle. At the same time, if one wants to present this example in class, one has to be pretty careful to avoid confusion between permutations encoding positions and those corresponding to slide-moves. In making such a careful analysis, one is bound to come up with a structure which isn’t a group, but is precisely what some people prefer to call a groupoid (if not a 2-group…).

Continue readingThe 15-puzzle groupoid (1)
One Comment

Conway’s puzzle M(13)

Published June 16, 2007 by lievenlb

Recently, I’ve been playing with the idea of writing a book for the general public. Its title is still unclear to me (though an idea might be “The disposable science”, better suggestions are of course wellcome) but I’ve fixed the subtitle as “Mathematics’ puzzling fall from grace”. The book’s concept is simple : I would consider the mathematical puzzles creating an hype over the last three centuries : the 14-15 puzzle for the 19th century, Rubik’s cube for the 20th century and, of course, Sudoku for the present century.

For each puzzle, I would describe its origin, the mathematics involved and how it can be used to solve the puzzle and, finally, what the differing quality of these puzzles tells us about mathematics’ changing standing in society over the period. Needless to say, the subtitle already gives away my point of view. The final part of the book would then be more optimistic. What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?

Continue readingConway’s puzzle M(13)
Leave a Comment

the secret life of numbers

Published January 11, 2007 by lievenlb

Just read/glanced through another math-for-the-masses book : [The secret life of numbers](http://www.amazon.co.uk/Secret-Life-Numbers-Pieces-Mathematicians/dp/0309096588/sr=81/qid=1168541999/ref=sr_1_1/203-3776750-7074362?ie=UTF8&s=books) by [George G.
Szpiro](http://www.citebase.org/search?submit=1&author=Szpiro%2C+George+G.). The subtitle made me buy the book : **50 easy pieces on how
mathematicians work and think** Could be fun, I thought, certainly after
reading the Amazon-blurb :

Most of us picture
mathematicians laboring before a chalkboard, scribbling numbers and
obscure symbols as they mutter unintelligibly. This lighthearted (but
realistic) sneak-peak into the everyday world of mathematicians turns
that stereotype on its head. Most people have little idea what
mathematicians do or how they think. It’s often difficult to see how
their seemingly arcane and esoteric work applies to our own everyday
lives. But mathematics also holds a special allure for many people. We
are drawn to its inherent beauty and fascinated by its complexity – but
often intimidated by its presumed difficulty. \”The Secret Life of
Numbers\” opens our eyes to the joys of mathematics, introducing us to
the charming, often whimsical side, of the
discipline.

Please correct me when I’m wrong,
but I found just one out of 50 pieces which remotely fulfills this
promise : ‘Cozy Zurich’ ((on the awesome technical support a lecturer
in Zurich is rumoured to receive)). Still, there are some other pieces
worth reading, 1. ‘A puzzle by any other name’ ((On the
Collatz problem)) 2. ‘Twins, cousins and sexy primes’ ((How
reasearch into the twin primes problem led to the discovery of a
Pentium-bug)) 3. ‘Proving the proof’ ((On Kepler’s problem)) 4.
‘Has Poincare’s conjecture finally been solved’ ((Of course it has
been)) 5. ‘Late tribute to a tragic hero’ ((On Abel’s life and
prize)) 6. ‘God’s gift to science?’ ((Stephen Wolfram
bashing)) to single out a few, embedded in a soup made out of the
usual suspects (knots, chaos, RSA etc.). But, all in all, I fear the
book doesn’t fulfill its promises and once again it demonstrates how
little ‘math-substance’ one is able to put in a book for a general
audience. But let us end with a quote from the preface that I really
like :

Whenever a socialite shows off his flair
at a coctail party by reciting a stanza from an obscure poem, he is
considered well-read and full of wit. Not much ado can be made with the
recitation of a mathematical formula, however. At most, one may expect a
few pitying glances and the title ‘party’s most nerdy guest’. To the
concurring nods of the cocktail crowd, most bystanders will admit that
they are no good at math, never have been, and never will be.
Actually, this is quite astonishing. Imagine your lawyer
telling you that he is no good at spelling, your dentist proudly
proclaiming that she speaks n foreign language, and your financial
advisor admitting with glee that he always mixes up Voltaire with
Moliere. With ample reason one would consider such people as ignorant.
Not so with mathematics. Shortcomings in this intellectual discipline
are met with understanding by everyone.

Leave a Comment

coalgebras and non-geometry 3

Published September 11, 2006 by lievenlb

Last
time we saw that the _coalgebra of distributions_ of a
noncommutative manifold can be described as a coalgebra
Takeuchi-equivalent to the path coalgebra of a huge quiver. This
infinite quiver has as its vertices the isomorphism classes of finite
dimensional simple representations of the qurve A (the coordinate ring
of the noncommutative manifold) and there are as many directed arrows
between the vertices corresponding to the simples S and T as is the
dimension of $Ext^1_A(S,T) $.

The fact that this
coalgebra of distributions is equivalent to the path coalgebra of
_some_ quiver is in the Kontsevich-Soibelman
paper though it would have been nice if they had given reference for
this fact to the paper Wedge Products and
Cotensor Coalgebras in Monoidal Categories by Ardizzoni or to
previous work by P. Jara, D. Llena, L. Merino and D. Stefan,
“Hereditary and formally smooth coalgebras”, Algebr.
Represent. Theory 8 (2005), 363-374. In those papers it is shown that a
coalgebra with coseparable coradical is hereditary if and only if it
is formally smooth if and only if it is a cotensor coalgebra of some
bicomodule.

At first this looks just like the dual version of
the classical result that a finite dimensional hereditary algebra is
Morita equivalent to the path algebra of a quiver (which is indeed what
the proof does) but again the condition that the coradical is
coseparable does not require the coradical to be finite dimensional…
In our case, the coradical is indeed coseparable being the direct sum
over all matrix coalgebras corresponding to the simple representations.
Hence, we can again recover the _points_ of our noncommutative manifold
from the direct summands of the coradical. Fortunately, one can
compute this huge coalgebra of distributions from a small quiver, the
_one quiver to rule them all_, but as I’ve been babbling about all of
this here [numerous
times](http://www.neverendingbooks.org/?s=one+quiver) I’ll let the
interested find out for themselves how you use it (a) to get at the
isoclasses of all simples (hint : morally they are the smooth points of
the quotient varieties of n-dimensional representations and enough tools
have been developed recently to spot some fake simples, that is smooth
proper semi-simple points) and (b) to compute the _ragball_, that is the
huge quiver with vertex set the simples and arows as described
above. Over the years I’ve calculated several one-quivers for a
variety of qurves (such as amalgamated free products of finite groups
and smooth curves). If you are in for a puzzle, try to determine it for
the qurve $~(\mathbb{C}[x] \ast C_2) \ast_{\mathbb{C}
C_2} \mathbb{C} PSL_2(\mathbb{Z}) \ast_{\mathbb{C} C_3}
(\mathbb{C}[x] \ast C_3) $ The answer is a mysterious
hexagon

Leave a Comment

bivalue Sudoku graphs

Published December 27, 2005 by lievenlb

Here is
a ‘difficult but not unsolvable’ Sudoku from David Eppstein‘s paper Nonrepetitive paths and cycles
in graphs with application to Sudoku.

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. | |
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y1 $

As always I try to solve
Sudokus without having to use backtracking (that
is, making a guess and working from there on to a solution or a
contradiction in which case one uses the other option). Clearly, this is
not well defined. When one starts solving Sudokus one often resorts to
backtracking but after a while one discovers rules which seem to avoid
backtracking (but in a sense are still). For example, if two cells in a
same block (or row or column) can only be filled with two numbers one
can use this fact by forbidding other numbers to occupy those cells.
However, this is a mini-backtracking strategy. Still, I allow all such
rules. More precisely, any formal rule is non-backtracking in my
dictionary. In Eppstein’s paper there is a good summary of the rules
most people apply when starting a Sudoku. He calls them the ‘local
rules’. Here they are

  • If a digit x has only one remaining
    cell that it can be placed in, within some row, column, or square, then
    we place it in that cell. Any potential positions of x incompatible with
    that cell (because they lie in the same row, column, or square) are
    removed from future consideration.
  • If a cell has only one
    digit x that can be placed in it, we place x in that cell. Incompatible
    positions for x are removed from future consideration.
  • If
    some three cells, formed by intersecting a row or column with a square,
    have three digits whose only remaining positions within that row,
    column, or square are among those three cells, we prevent all other
    digits from being placed there. We also remove positions for those three
    forced digits outside the triple but within the row, column, or square
    containing it.
  • If the cells of a square that can contain a
    digit x all lie in a single row or column, we eliminate positions for x
    that are outside the square but inside that row or column. Similarly, if
    the cells that can contain x within a row or column all lie in a single
    square, we eliminate positions that are inside that square but outside
    the row or column.
  • If two digits x and y each share the same
    two cells as the only locations they may be placed within some row,
    column, or square, then all other digits must avoid those two cells.
  • If the placement of digit x in cell y can not be extended to a
    placement of nine copies of x covering each row and column of the grid
    exactly once, we eliminate cell y from consideration as a placement for
    x.
  • If the placement of a digit x in cell y within a single
    row, column, or square can not be extended to a complete solution of
    that row, column, or square, then we eliminate that placement from
    consideration.

But even if one manages to use all
these rules (and frankly I only use a subset) one might get stuck. I
don’t know how many cells you can fill in the above problem with these
local rules, I’m afraid I only managed $5 $… At such
moments, the bivalue Sudoku-graph may come in handy. Eppstein defines
this as follows

In this graph, we create a vertex
for each cell of the Sudoku grid that has not yet been filled in but for
which we have restricted the set of digits that can fill it to exactly
two digits. We connect two such vertices by an edge when the
corresponding two cells both lie in a single row, column, or square, and
can both be filled by the same digit; the label of the edge is the
digit they can both be filled by.

Eppstein then goes
on to define new rules (each of which is a mini-backtracking strategy)
which often help to crack the puzzle. Here are Eppstein’s ‘global
rules’

  • If an edge in the bivalue graph belongs to a
    nonrepetitive cycle, the digit labeling it must be placed at one of its
    two endpoints, and can be ruled out as a potential value for any other
    cell in the row, column, or square containing the edge.
  • If
    the bivalue graph has a cycle in which a single pair of consecutive
    edges has a repeated label, that label can not be placed at the cell
    shared by the two edges, so that cell must be filled by the other of its
    two possible values.
  • If the bivalue graph contains two
    paths, both starting with the same label from the same cell, both
    ending at cells in the same row, column, or square, and such that in the
    two ending squares the values not occurring on the incident edge labels
    are equal, then the cell at the start of the paths can not be filled by
    the start label of the paths, and must be filled by the other of its two
    possible values.

For example, in the above problem it
is not hard to verify that the indicated places X,Y and Z form a
nonrepetitive cycle in the bivalue graph so applying the first global
rule we have two choices of filling these places (one leading to a
solution, the other to a contradiction)

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |.
|X|Y|8|3| |9| |2|Z|. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| |
|1| | | | |3|. \end{sudoku-block}y2 $

In fact, it turns out
that making this choice is enough to solve the puzzle by simple local
rules. So, if I change the original puzzle by filling in the cell X

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. |6|
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y3 $

you will have no problem
solving the puzzle.

Leave a Comment

a 2006 chess puzzle anyone?

Published December 20, 2005 by lievenlb

Noam Elkies is one of
those persons I seem to bump into (figuratively speaking) wherever my
interests take me. At the moment I’m reading (long overdue, I
know, I know) the excellent book Notes on
Fermat’s Last Theorem by Alf Van der
Poorten. On page 48, Elkies figures as an innocent bystander in the
1994 April fools joke e-perpetrated by
Henri Darmon in the midst of all confusion about ‘the
gap’ in Wiles’ proof.

There has
been a really amazing development today on Fermat’s Last Theorem.
Noam Elkies has announced a counterexample, so that FLT is not true
after all! He spoke about this at the institute today. The solution to
Fermat that he constructs involves an incredibly large prime exponent
(larger than $10^{20}$), but it is constructive. The main idea seems to
be a kind of Heegner-point construction, combined with a really
ingenious descent for passing from the modular curves to the Fermat
curve. The really difficult part of the argument seems to be to show
that the field of definition of the solution (which, a priori, is some
ring class field of an imaginary quadratic field) actually descends to
$\\mathbb{Q}$. I wasn’t able to get all the details, which were
quite intricate…

Elkies is also an
excellent composer of chess problems. The next two problems he composed
as New Year’s greetings. The problem is : “How many shortest
sequences exists (with only white playing) to reach the given
position?”

$\\begin{position}
\\White(Kb5,Qd1,Rb1,Rh1,Nc3,Ne5,Bc1,Bf1,a2,b2,c4,d2,e2,f3,g3,h2)
\\end{position}{\\font\\mathbb{C}hess=chess10 \\showboard
}xc $

Here’s Elkies’ solution
:

There are 2004 sequences of the minimal length 12.
Each consists of the sin- gle move g3, the 3-move sequence
c4,Nc3,Rb1, and one of the three 8-move sequences
Nf3,Ne5,f3,Kf2,Ke3,Kd3(d4),Kc4(c5),Kb5. The move g3 may be played at
any point, and so contributes a factor of 12. If the King goes
through c5 then the 3- and 8-move sequences are independent, and can
be played in $\\binom{11}{3}$ orders. If the King goes through c4 then
the entire 8-move sequence must be played before the 3-move sequence
begins, so there are only two possibilities, depending on the choice
of Kd3 or Kd4. Hence the total count is $12(\\binom{11}{3}+2)=2004$ as
claimed.

A year later he composed the
problem

$\\begin{position}
\\White(Kh3,Qe4,Rc2,Rh1,Na4,Ng1,Bc1,Bf1,a2,b2,c3,d3,e2,f4,g2,h2)
\\end{position}{\\font\\mathbb{C}hess=chess10 \\showboard
}xd $

of which Elkies’ solution is
:

There are 2005 sequences of the minimal length 14.
This uses the happy coincidence $\\binom{14}{4}=1001$. Here White
plays the 4-move sequence f4,Kf2,Kg3,Kh3 and one of the five
sequences Nc3,Na4,c3,Qc2,Qe4,d3,Bd2(e3,f4,g5,h6),Rc1,Rc2,Bc1 of
length 10. If the Bishop goes to d2 or e3, the sequences are
independent, and can be played in $\\binom{14}{4}$ orders. Otherwise
the Bishop must return to c1 before White plays f4, so the entire
10-move sequence must be played before the 4-move sequence begins. Hence
the total count is $2 \\binom{14}{4}+3 =
2005$.

With just a few weeks remaining, anyone in for
a 2006 puzzle?

Leave a Comment

hints for micro-sudoku

Published October 27, 2005 by lievenlb

As a
quick reply to last posts comment :

Another
interesting question: How many clues (numbers allready in the grid) do
we need a Sudoku puzzle to have in the beginning in order to obtain a
unique solution? Comment by A.R.Ray

At
least one student proved that in micro-Sudoku (on a 4×4 grid)
one needs just 4 hints to get any unique solution (and that 4 is
minimal). It is an application of the fact that the micro-Sudoku group
acts on the set of all solutions with just two orbits so one needs to
check just these two solutions…

Leave a Comment

micro-sudoku

Published October 9, 2005 by lievenlb

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

sudoku mania (bis)

Published September 27, 2005 by lievenlb

Situation : my first class this year, about 20
fresh(wo)men, their second class this year.

Me : Okay, who
did some mathematics this vacation?

(No response
obviously, even if they did, it’s not a cool thing to
admit…)

Me : Sure, let me rephrase the question :
who thought about solving a puzzle or played a strategic game this
vacation?

(No response, or… is there?….. a
timid question :

‘Does Sudoku
count????’

Me : Well, not really but okay
let’s rephrase the question : Who solved at least 1 Sudoku this
vacation?

IMMEDIATE RESPONSE : about three quarters of all
students waving their arms!

Me :
Oof…….Oh…….Yes??? (to an even more timid
student raising his arm)

‘Does doing half a Sudoku
also counts?’

It’s going to be a tough
semester…

Leave a Comment