Take a checkerboard, and remove two squares at opposite corners. Is it then possible to find an exact and complete cover of the remaining board using dominoes (two are shown in orange), without overlap and overhang?
There is a surprisingly simple and elegant proof for the negative answer to this question. I've just learned it this afternoon, in a great public talk by mathematician Günter Ziegler, coauthor of "Proofs from the book", current president of the German Association of Mathematicians, and main organiser of the "Year of Mathematics 2008" in Germany.
Starting with the "Year of Physics" in 2000, the German Federal Ministry of Science and Education has dedicated each year since to one particular discipline, and following the humanities in 2007, this year is all about math. As Ziegler writes in the March 2008 issue of the Notices of the American Mathematical Society, "The entire year 2008 has been officially declared Mathematics Year in Germany. This has created an unprecedented opportunity to work on the public's view of the subject."
And he used the opportunity, in a talk this afternoon on the occasion of the opening of the Mathematics Year for Frankfurt. He discussed the role of proof in mathematics, and then gave examples of actual elegant proofs of geometrical problems using colorations of the plane. The checkerboard riddle was just the first of them - he ended explaining the steps of a quite surprising proof that a square can not be decomposed into an odd number of triangles of equal area. I was amazed to see how I was guided by him through the steps and the idea of the proof - it's exciting to follow a talk like this! And my impression was that the 300 or so people in the audience have felt the same. Most of them, however, were faces I knew from the math department, or students and teachers. It would be great if such an event will attract even more people from the interested public.
Have a nice weekend - and if you want to solve the checkerboard riddle by yourself, don't read the comments - I'm convinced the answer will be there pretty soon!
Unfortunately, the slides of the talk are not online. Here are, roughly, the steps of the proof of the impossibility to decompose the square into an odd number of triangles of equal area: Start by colouring the rational points of the unit square in three different colours, using a scheme depending on the enumerator and denominator of the coordinates of the point. Then, convince yourself that each decomposition of the square into triangles (with corners in the rational points) contains at least one triangle with three different colours for the three corners. It comes out that this triangle, because of the rules chosen for colouring, has an area with an even denominator. Hence, in a decomposition into triangles with equal area, it cannot be part of a decomposition into an odd number of triangles. Use some heavy machinery to promote this proof from rational corner points to any corner points of the triangles, and you're done. If you find an error in this description, it's probably my fault - you may consult the original papers, "A Dissection Problem" by John Thomas, Mathematics Magazine 41 No. 4 (Sep. 1968), 187-190 (via JSTOR; subscription required), and "On Dividing a Square Into Triangles" by Paul Monsky, The American Mathematical Monthly 77 No. 2 (Feb. 1970) 161-164 (via JSTOR, subscription required).
Tag: Mathematics Year
Hah! An invitation to point out that counting white and black squares proves the impossibility.
ReplyDeleteWhich reminds me, at the local chess club, a game was discussed where white ended up with two white square bishops. The discussers concluded that there had been a mistake in the play as no pawns had been promoted.
So this raises the question. Is it possible to change a white square bishop into a black square bishop by using an other than finite number of moves? Perhaps if one makes enough moves, the board will suffer a quantum transformation and the color of some of its squares will change...
Parity check! Parity might falsify General Relativity and string theory - parity Eötvös experiment opposing single crystal alpha-quartz enantiomorphs, parity calorimetry experiment opposing single crystal benzil enantiomorphs.
ReplyDeletePhysics routinely chokes on parity - right hand rule, gyroscope precession, spacetime torsion... and that little Christmas 1956 experimental embarrassment.
Hi Uncle Al,
ReplyDelete“Physics routinely chokes on parity - right hand rule, gyroscope precession, spacetime torsion... and that little Christmas 1956 experimental embarrassment.”
Yes, not only parity yet more importantly symmetry. That is our world is not simply that of the other side of the mirror and therefore just simply a different perspective of reality. For me it has always served to indicate that reality is thus not a special case of the possible, yet what is the possible is rather a special case of what we call reality. The other way to put it is, if Alice had stepped through the looking glass, she wouldn’t have found that all was simply strange, yet rather impossible and therefore non existent. The implications of breaking symmetry are one thing, while the disregard of it is another. I feel this to must form to be part of the consideration and explanation.
Best,
Phil
Stefan,
ReplyDeleteMaybe I misunderstand something, but isn't there a much simpler proof by noting that the two removed squares are both black? Since every domino covers exactly one black and one white square, they can't cover 32 white and 30 black squares.
Hi Stefan,
ReplyDeleteNice post and again I find yours’ and Bees access at times both to be wondrous and yet at the same time a little envious. Yet, when I think about it I am grateful that you bring in part some of this experience to life within this blog. The puzzle you present I also find interesting, as to the fact that a proof can be discovered and presented. What I find interesting to considerer is that this proof is obviously discoverable since the spaces presented do have finite limit. The question that this then has one wonder about is if the answers that are sought within physics have the same and if not does this then form to be an obstacle that can or cannot be overcome? This I would understand to be something that first must be dealt with within the confines of mathematics and thus physics must in this sense wait for the judgment, unless it can demonstrate that the first limit is all that is to be considered.
Best,
Phil
Dear Stefan,
ReplyDeleteInteresting post. I vaguely remember I came across this triangle proof elsewhere previously but can't recall where. Regarding the dominoes, what Oleg says above sounds good to me, what do you think?
Best,
B.
Hi Carl, Oleg, dear Bee,
ReplyDeleteyes, the answer is indeed as simple as that - there are 32 white squares and 30 black squares, and each domino covers exactly one white and one black square - hence no complete covering is possible.
I didn't know the riddle before, neither this answer. Günter Ziegler in his talk had presented the problem first for a board without the black and white coloration of the fields. The key step is to introduce this coloration, which then makes the counting argument quite obvious. When he explained this reasoning, I had a very surprised and pleasant "Aha" effect, which is, in my eyes, hallmark of an elegant proof. And Ziegler then went on applying similar surprising coloration arguments to more complicated and less obvious problems, like that of the decomposition of the square into triangles of equal area.
Best, Stefan
Parity check! Every domino is 01 or 10. Remove two squares of the same color to give 00 or 11 residual. No domino can cover it.
ReplyDeleteOrder of rotations of a sphere; current, magnetic field, force; Weak Interaction; Cartesian coordinates... Physics assumes isotropic, commutative, abelian conditions then adds exceptions. Perhaps symmetry "breakings" were never unbroken.
Gravitation is defined immune to symmetry breakings (General Relativity and spacetime curvature) or not (teleparallel gravitation and spacetime torsion transforming like EM Lorentz force). Parity Eötvös and parity calorimetry experiments answer the question. Somebody should look.
Sylvester-Gallai also has, IMO, an elegant proof.
ReplyDelete"The Sylvester–Gallai theorem asserts that given a finite number of points in the plane, either
1. All the points are collinear; or
2. There is a line which contains exactly two of the points."
It remained open from 1893 to 1944. You might want to try your hand at it before looking at the answer (no, I didn't get it).
Hint: proof by contradiction.