Solution to MP66
February 2007

The problem:
Sophie and Sally each got puzzles for Christmas.  Sophie's puzzle was a 10 10 grid to be filled by a certain number of 1×4 tiles and a certain number of 2×2 tiles, with no tiles left over.  Sally's puzzle was also a 10×10 grid to be filled by a certain number of 1×4 tiles and a certain number of 2×2 tiles, with no tiles left over.  Sophie could complete her puzzle in 2 minutes and 30 seconds, and Sally could complete hers in 4 minutes.  Then, they switched, and Sophie completed Sally's puzzle in 4 minutes and 20 seconds while Sally completed Sophie's puzzle in 3 minutes and 12 seconds.  Then, they switched back to their own puzzle, but Sophie gave Sally one of her 1×4 tiles, and Sally gave Sophie one of her 2×2 tiles.  Our problem: How long will each take to complete her puzzle now? 

Correct solutions came from

Solution.  The puzzle cannot be solved after the exchange of tiles.  There was some disagreement about how long it would take for Sophie and Sally to realize it, but most thought they would give up after a finite amount of time.
            Our February problem has been adapted from a problem in Chapter 2 ("Coloring Proofs") of Problem Solving Strategies by Arthur Engel, (Problem Books in Mathematics. Springer-Verlag, New York, 1998.)  We thank Matthieu Dufour for introducing us to the problem..  In a somewhat mischievous mood, we neglected to say that Sophie and Sally are not really little girls, but, rather, they are the neighbor's cats.

Moreover, we (perhaps unwisely) formulated the problem to suggest that even a cat could complete the puzzle after the exchange of pieces.  We apologize to all those who spent an afternoon in futile computations.  Indeed, if you color the 10 10 board as in the accompanying figure,

Figure 2

you can easily convince yourself that the puzzle can be completed only if there are an odd number of 2 2 pieces: Each 2 2 piece will cover exactly one red square when placed on the board, while each 1 4 piece will cover either 0 or 2 red squares; since 25 pieces are required to cover the board, there must be an odd number of those covering one red square.  Since we were told that the puzzle had been completed by both Sophie and Sally, we know that the number of 2 2 pieces was odd.  After the exchange, they each had an even number of 2 2 pieces, so it was no longer possible to complete either puzzle. 

            Amghibech and Cairoli sent us the solution presented above.  Other correspondents sent us a variety of clever soolutions.  Here are two more.  Yet others can be found on our French page.

Color the board Billion's way.
Take a completed puzzle and color the (vertical) columns alternately white and red.  Remove all 2 2 tiles and those 1 4 tiles that were placed horizontally.  These pieces will have an equal number of squares of each color, whence the remaining pieces will have an equal number of squares of each color.  But the 1 4 tiles that remain will have all squares colored red, or all colored white, so that there must be an even number of vertically placed 1 4 tiles.  In the same way we see that the number of horizontally placed 1 4 tiles must be even.  We conclude that a completed puzzle will necessarily have an even number of 1 4 tiles; therefore, the puzzle could not be completed using one extra 1 4 tile, or one fewer.

Provide a combinatorial argument.  Here is one example of this type of solution.
Tiefenbach's solution:
Assume the puzzle is solved with the appropriate number of 1 4's and 2 2's.  Let s(j) be the number of squares in row j (from the top) covered by vertical 1 4's.  Each s(j) must be even, since horizontal 1 4's and 2 2's cover 4 and 2 squares, respectively, of a particular row, and that row has ten squares.  Let t(j) be the number of vertical 1 4's whose top is in row j.  t(1) = s(1), and so t(1) is even.  Moreover, by recursion every t(j) is even: