Blue-Empty Graph

I was going to post this puzzle tomorrow but I realized that leaving the inquisitive readers with just a solution to Langford’s problem would be very ill mannered. So here we go again! This one, like many others I will write about, comes from the late Martin Gardner’s prolific work as a puzzle writer:

Six Hollywood stars form a social group that has very special characteristics. Every two stars in the group either mutually love each other or mutually hate each other. There is no set of three individuals who mutually love one another. Prove that there is at least one set of three individuals who mutually hate each other. The problem leads into a fascinating field of graph theory, “blue-empty chromatic graphs”, the nature of which will be explained when the answer is given….on Wednesday, 12/29/2010.

Until then, enjoy the love triangle!

SOLUTION – Langford’s Problem

Merry Christmas everybody! On 12/23/2010 I wrote about a curious puzzle called Langford’s Problem. I asked the reader to try to arrange four pairs of different colored blocks such that one block was between a pair of blocks of color A, two blocks between a pair of blocks of color B, three blocks between a pair of blocks of color C, and finally four blocks between a pair of blocks of color D.

The unique solution is: DACABDCB.

There are 26 solutions to the 7 pair problem. Using numbers to represent block colors, here is one solution I came up with: 73625324765141.

Check out this link if you are interested in exploring the problem in greater detail:

http://legacy.lclark.edu/~miller/langford.html

Langford’s Problem

C. Dudley Langford, a Scottish mathematician, was watching his little boy play with colored blocks. There were two blocks of each color, and the child had piled six of them in a column in such a way that one block was between the red pair, two blocks were between the blue pair, and three were between the yellow pair. Substitute digits 1, 2, 3 for the colors and the sequence can be represented as 312132.

This is the unique answer (not counting its reversal as being different) to the problem of arranging the six digits so that there is one digit between the 1′s and there are two digits between the 2′s and three digits between the 3′s.

Langford tried the same task with four pairs of differently colored blocks and found that it too had a unique solution. Can you discover it? A convenient way to work on this easy problem is with eight playing cards: two aces, two deuces, two threes, and two fours. The object then is to place them in a row so that one card separates the aces, two cards separate the deuces, and so on.

There are no solutions to “Langford’s problem,” as it is now called, with five or six pairs of cards. There are 26 distinct solutions with seven pairs. The reader will find it a pleasant exercise to work out some of its solutions. No one knows how to determine the number of distinct solutions for a given number of pairs except by exhaustive trial-and-error methods, but perhaps you can discover a simple method of determining whether there is a solution.

I will post the solution to this problem on Christmas day. For those of you who might not have arrived at the solutions by then, you can count that as my Christmas present to you.

Cartoon Corner

The cartoon is by Randy Glasbergen.

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:

[SOLUTION]

References

1. 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?