SOLUTION – Polyominoes
On Jan 11 I briefly introduced Polyominoes and posed some interesting problems to delight our readers. If you haven’t read the post introducing this fantastic topic, I highly encourage you to do so before proceeding to read the solutions to the puzzles presented in that post.
- In the first problem it was asked if a checkerboard has a pair of diagonally opposite corner squares deleted then would it be possible to cover this “mutilated” checkerboard with dominoes. Recall that a domino covers exactly 2 squares in the checkerboard. It turns out that the “mutilated” checkerboard cannot be covered with dominoes and the proof is oh so elegant! The standard checkerboard contains 64 alternating dark and light colored squares. On this board, each domino will cover one light square and one dark square. Thus n dominoes will cover n light squares and n dark squares. However, the defective board has 32 squares of one color and 30 squares of another color and thus cannot be covered by dominoes. How beautiful was that?
- In this second problem it was asked if the reader could show a construction where 21 right trominoes and 1 monomino covers an 8X8 checkerboard. Moreover, the reader was asked to prove the remarkable fact that no matter where a monomino is placed on the checkerboard, the remaining squares can always be covered with 21 right trominoes. I will furnish a proof of this fact thus simultaneously answering the question about constructing such a covering. Below is an 8X8 board:
Consider the 2X2 section of this checkerboard. For the sake concreteness, let us pick the 2X2 area at the top left of the checkerboard above. Essentially this area is 2X2 checkerboard in itself. Notice that no matter where you place a monomino on this 2X2 board, you can cover the other 3 squares with a right tromino.
Next let us consider a 4X4 area of the board above. Divide it into quarters, each of which is a 2X2 board. Now consider the upper left 2X2 board. Clearly we can place a monomino and right tromino and cover this 2X2 area. Now considering the upper right 2X2 board, we can leave the lower left square empty and cover the other 3 squares with a right tromino. In the lower left 2X2 board, we can leave the upper right square empty and cover the other 3 squares with a right tromino. And finally, in the lower right 2X2 board, we can leave the upper left square empty and cover the other 3 squares with a right tromino. Notice that we left 3 squares blank and these 3 squares nicely congregate at the center of the 4X4 checkerboard and can be convered with a right tromino. Thus we have shown how to cover the 4X4 checkerboard with 1 monomino and 5 right trominoes! Ah, we are making some big progress!
It is now plain to see that 8X8 checkerboard can be divided into 4 quadrants of 4X4 boards and we can apply the same technique we used to cover the 4X4 board! In fact, by mathematical induction it is true that we can cover any (2^n)X(2^n) board, where n = 1, 2, 3, …, with 1 monomino and several right trominoes only. At a later time I will write a post about mathematical induction as a way of proof.
These problems barely scratch the surface of the theory of Polyominoes. Stay tuned for more truly mind bending puzzles about the arrangement of these simple figures!
An Introduction to Polyominoes
In this post I will briefly introduce the fascinating subject of Polyominoes and pose some elementary problems that are sure to puzzle the incredible pattern matching machines in your skulls. Those of you who are familiar with Polyominoes might know that they inspired the very popular video game Tetris.
Polyominoes are shapes made by connecting certain number of equal-sized squares, each joined together with at least one other square along an edge. To make the definition clear, here are some examples of simple polyominoes composed of fewer than 5 connected squares:
From the figure above, you can see that a Monomino is composed of a single square and it is clear that there is just one such shape. A Domino is made of 2 connected squares and has only one shape, a rectangle. A Tromino is made of 3 connected squares and the figure above shows that there are only 2 distinct trominoes (straight tromino and right tromino) if we discount rotations and reflections. Similarly, a Tetromino is composed of 4 connected squares and there are 5 distinct tetromino shapes (straight, square, T, L and skew tetrominoes). The most popular type of polyomino that has inspired many games and puzzles are the 12 distinct Pentominoes:
Simple looking critters aren’t they? Simple as they might look, these shapes can be mixed together to form patterns and tessellations that are anything but simple. Polyomino patterns are actually examples of Combinatorial Geometry, that branch of Mathematics dealing with the ways in which geometrical shapes can be combined.
So that is it for this lecture on these simple looking shapes we call Polyominoes. For now! Let’s roll up our sleeves and get into some interesting problems in Combinatorial Geometry shall we?
- The first problem, with which some readers may be familiar, concerns dominoes: Given a checkerboard with a pair of diagonally opposite corner squares deleted (see figure below) and a box of dominoes, each of which covers exactly 2 squares, is it possible to cover this board completely with dominoes (allowing no vacant squares and no overlaps)? Explain your answer.
- It is impossible to cover an 8X8 board entirely with trominoes because 64 is not divisible by 3. However, it is a well known fact that the 8X8 board can be covered with 21 right trominoes and 1 monomino. Can you come up with a construction? What is more remarkable is that it can be proved that no matter where on the checkerboard a monomino is placed, the remaining squares always can be covered with 21 right trominoes. Can you come up with a proof? I realize that submitting a solution to this problem via the comments section would be problematic due to the geometric nature of the solution but I highly encourage you to try your hand at this remarkable problem. I know this is a stretch, but for those of you who would like to submit your geometric solution, you can email a file (an image or some other type of document) containing your geometric solution to yooklidean@gmail.com.
I will post the solution to these puzzles on thursday, 01/14/2010. Until then, happy pattern matching!
UPDATE:
References
- Golomb W., Solomon. Polyominoes.
Help the merchant’s wife!
A rich merchant had collected many gold coins. He did not want anybody to know about them. One day, his wife asked,“How many gold coins do we have?” After pausing a moment, he replied, “Well! If I divide the coins into two unequal numbers, then 36 times the difference between the two numbers equals the difference between the squares of the two numbers, “The wife looked puzzled. Can you help the merchant’s wife by finding out how many gold coins they have?
Easy Picking
In a certain bank the positions of the cashier, manager, and tellers are held by Brown, Jones and Smith, though not necessarily respectively.
The teller, who was an only child, earns the least.
Smith, who married Brown’s sister, earns more than the manager.
What position does each man fill?
Ten Commandments of Mathematics
King James Version
1. Thou shalt read Thy problem.
2. Whatsoever Thou doest to one side of ye equation, Do ye also to the other.
3. Thou must use Thy “Common Sense”, else Thou wilt have flagpoles 9,000 feet in height, yea … even fathers younger than sons.
4. Thou shalt ignore the teachings of false prophets to do work in Thy head.
5. When Thou knowest not, Thou shalt look it up, and if Thy search still elude Thee, Then Thou shalt ask the all-knowing teacher.
6. Thou shalt master each step before putting Thy heavy foot down on the next.
7. Thy correct answer does not prove that Thou hast worked Thy problem correctly. This argument convincest none, least of all, Thy teacher.
8. Thou shalt first see that Thou hast copied Thy problem correctly before bearing false witness that the answer book lieth.
9. Thou shalt look back even unto Thy youth and remember Thy arithmetic.
10. Thou shalt learn, speak, write, and listen correctly in the language of mathematics, and verily A’s and B’s shall follow Thee even unto graduation.
-Author Unknown
SOLUTION – Military Tactics Puzzle
The solution described below pertains to the Military Tactics Puzzle, which I wrote about on 12/07/2009. If you have not attempted to match your wits against this puzzle, I highly encourage you to stop reading this post any further and attempting the puzzle.
The puzzle asked to show how a rook at the initial starting point of H6 will visit all 64 squares where one of the moves must be D5:D4 (or D4:D5) and end at H5. This must be done by making the fewest possible number of turns and no square can be visited more than once:
Here the green point is the starting position (H6), the yellow point is the ending postion (H5) and the blue line segment is the triumphant arch (D4:D5). In this solution there are 15 turns and my intuition says that this is minimal, however, I am not able to rigorously prove it. Might one of our readers be able to prove that 15 turns is the minimum or that there is a solution with fewer than 15 turns?
SOLUTION- The Trouble with Barbers
The solution described below pertains to The Trouble with Barbers, which I wrote about on 12/02/2009. If you have not attempted to match your wits against this puzzle, I highly encourage you to stop reading this post any further and attempting the puzzle.
So, is there a way out of this paradox?
In the real world, yes. There are plenty. You could question the existence of such towns or the existence of such barbers. In Mathematics though, a more carefully stated version called the Barber’s Paradox usually attributed to the 20 th century British mathematician and poly-math Bertrand Russell, lead to one of the deepest pitfalls in mathematical Logic. It showed the limitations of logic and the trouble with building the whole edifice of Mathematics on the logical properties of Sets. The barber paradox did not stop with just forcing mathematicians to revise their views on certain topics but went on to question their way of thinking about mathematics itself. The Barber Paradox belongs to the self-contradictory category of Logical Paradoxes, the simplest and the most troublesome ones in the business. “This sentence is a lie.” is probably one of the simplest and most baffling of them all. Trouble, indeed.
Bertrand Russell
References
1. Stewart, Ian. Professor Stewart’s Cabinet of Mathematical Curiosities.
2. Russell, Bertrand. Principles of Mathematics.
Military Tactics Puzzle
Here is another pretty puzzle from the inimitable Sam Loyd. In his day, much sensation was created by General Winfield Scott‘s scathing criticism of the Union soldiers during the American Civil War. General Scott remarked to then Secretary of War Edwin Stanton,
“While we have scores of commanders who could march a division of soldiers into a park, not one of them knows enough about military tactics to get them out again!”
Knowing that General Scott was a skillful Chess player, Sam Loyd built an interesting puzzle concerning the military tactics of a division of soldiers passing through a public park:
The public park is marked off into squares which resemble a chessboard and the puzzle itself requires no knowledge of chess other than the movement of a rook piece. Quite simply the rook moves horizontally or vertically, forward or backward, through any number of squares. However, for this puzzle it is assumed that this rook can only go to an adjacent square in a single move. The riddle is to show how a military division should enter gate No. 1, march through all of the squares, under the triumphant arch, and out through gate No. 2, making the fewest possible number of turns. All moves must be like a chess rook’s, and no square can be visited more than once.
More rigorously stated, given the following chessboard with algebraic notation:
Show how a rook at the initial starting point of H6 will visit all 64 squares where one of the moves must be D5:D4 (or D4:D5) and end at H5. This must be done by making the fewest possible number of turns and no square can be visited more than once. Remember that the rook can only go to an adjacent square in a single move.
According to Sam Loyd:
“It is safe to say you will make several attempts before you get the shortest possible answer, which is so pretty that you will know when you have guessed it”
Ah, nothing like that moment of eureka when you stumble upon an elegant and simple solution to a seemingly intractable problem. I will post my own solution on Thursday, 12/10/2009. In the meantime, I would love to read solutions from our clever readers in the comments or in emails. If you decide to email your solution to yooklidean@gmail.com, please label the subject with “Military Tactics Puzzle”. Happy Strategizing!
UPDATE:
References
SOLUTION – The Boxer’s Puzzle
The solution described below pertains to The Boxer’s Puzzle, which I wrote about on 11/30/2009. If you have not attempted to match your wits against this puzzle, I highly encourage you to stop reading this post any further and attempting the puzzle.
Lets call the maiden sitting down, Player A, and the maiden standing up, Player B. It is Player A’s turn and we are asked to find the best possible move for her. The best move for Player A is to connect G to H which will earn her a victory with a score of 7 boxes over Player B’s score of 2 boxes. This assumes that both players play rationally after Player A has connected G to H. To see why, let us investigate some of the available moves for Player A:
1) Player A connects D to H or H to L. Here it is easy to see that Player B can be guaranteed a victory by connecting the dots that will complete a line from D to L. As stated in the problem itself, player B can then score all 9 boxes regardless of what move Player A makes. So clearly this move is out.
2) Clearly Player A should not connect G to K since Player B can score 3 boxes in one run by closing J-K, K-O, and L-P and place her fourth move anywhere she wishes.
3) J to K is out of the question since Player B can score 3 boxes by completing G-K, K-O, and L-P and play a waiting move by connecting D to H.
4) Similarly K-O or L-P are bad moves for player A since Player B can score 3 boxes in a single run and play a waiting move by connecting D to H.
So, by process of elimination, G to H is the best move for player A. It is plain to see that player B’s best possible response would be to connect J to K to which player A responds with scoring 2 boxes by connecting K-O and L-P and placing a waiting move by connecting H to L. Player B would then score 2 boxes by connecting G to K and relinquish the other 5 boxes to Player A thus giving her the match!
This delightful topological game called “Dots and Boxes” offers a pleasant challenge on square board sizes of order 4 or greater. A winning strategy for the first or second player is not known for boards of order n > 4, which makes it all the more addicting. Interestingly, the game can also be played on triangular and hexagonal grids.
