## Archive for **April 2009**

## Round 4: Problem 5 Solution

This is a nice tiling problem in disguise. Let’s ignore the letters and symbols for now and just work with a blank 5×8 board. The 3×1 rectangular pieces are like straight triominoes that we will use to try to tile the board.

Essentially, our problem now is the following: with 13 triomino(e)s, how many different places can we place a monomino on a 5×8 board.

Tricolor the board as shown. Note that we now have 13 red squares, 13 yellow squares, but 14 black squares. Therefore, the monomino must be placed on one of the black squares. However, the monomino cannot be placed on just any black square. A monomino can only be placed on a black square if there is no way to flip our coloring so that the square in our original coloring is no longer black. Flipping the coloring disqualifies every black square besides those 2 on the third row.

We can verify that in fact we may place a monomino on either of these two squares by showing a tiling (try it, it’s trivial). Therefore we conclude that a monomino can only appear on one of these 2 squares. Plugging in these 2 black squares into the original board / cake, we see that on these two squares are the **‘2’** and the **‘9’** of ‘2009.’ These are the only two possible remaining pieces.

## Round 4: Problem 2 Solution

Here’s a geometric construction proof:

- Extend and so that they intersect at an exterior point .
- Extend and in a similar fashion so they intersect at another exterior point, , forming quadrilateral .
- since each external angle is supplementary with the 60 degree internal angle.
- , so are equilateral triangles.
- in equilateral triangles.
- is a parallelogram (both pairs of opposite angles are congruent), so .
- , so by equilateral triangles as shown above.

## Round 4: Problem 5

At the prize ceremony for the 2009 CUNY Math Challenge there will be a cake that is decorated so the message to the right appears on top. Each letter, digit, and symbol of the message forms one square of a 5 x 8 rectangle. Each of the 13 second prize winners cuts and eats a 3 x 1 rectangular piece of cake leaving just one square for the grand prize winner. What letter, digit, or symbol could possibly be on the grand prize winner’s piece of cake? (You must identify all possibilities and prove that no others could occur.)

## Round 4: Problem 4

A square grid with 10 rows and 10 columns contains the numbers 1, 2,…, 100 in its squares, as shown to the right. The grid is to be divided into 50 rectangular pieces, each of which contains two squares. Each piece is given a value equal to the product of the numbers that are on it. What is the smallest possible sum of the values of the 50 pieces? (You should prove your answer is the minimum.)

## Round 4: Problem 3

Seven CUNY goatherds, each with one goat, wish to graze their goats in the Sheep Meadow of Central Park. Each goatherd hammers in a spike and attaches a rope to that spike and then ties the other end to his goat. In this way each goat is allowed to graze a circular region. The goatherds are shocked to see that all seven goats are soon fighting over an area common to all seven of the individual regions. Prove that at least one goat can chew on the spike of another goat. (A goatherd is like a shepherd but looks after goats instead of sheep. The lengths of the seven ropes are not necessarily the same.)

## Round 4: Problem 2

Each interior angle of a convex hexagon ABCDEF has a measure of 120 degrees. Prove that AB + BC = DE + EF.

## Round 4: Problem 1

Alice’s brother Bob won a math contest in 2007 by writing 2007 as a sum of positive integers that together used each of the digits 0, 1, 2,…, 9 exactly once. Bob’s sum was 2007 = 1907 + 84 + 2 + 3 + 5 + 6. Alice wants to prepare for the final round of the 2009 CUNY Math Challenge by writing 2009 as a sum of positive integers that together use each of the digits 0, 1, 2,…, 9 exactly once. Either give a sum of numbers that Alice could use, or prove that there is no such sum. (Of course, no positive integer can begin with the digit 0.)

## Round 4 is now open.

Round 4 problems are up on the CUNY site. I’ll post a mirror in just a bit. Stay tuned.

## Round 3: Problem 4 Solution

This is a rather easy problem as long as you’ve heard of using recurrence relations in basic combinatorics. You have right? Good.

Let’s examine our ID constraints and see how we can evade them to build a valid ID number.

We start with 50 ‘slots’ in which we can drop either a ‘1’ or a ‘0:’

Immediately we are forced to place a 1 in the first slot because IDs can start only with a 1:

What should be obvious is that we can (recursively) now continue the sequence in 2 and only 2 ways to avoid consecutive 1s and three consecutive zeros:

and that now we can continue to make the same 2 choices to complete the string to the end.

In general for an ID of length , we notice that the number of ways to build such a sequence is , since we can add either a string of ’01’ or ‘001’ each time, which decreases the length of the sequence by either 2 or 3.

To solve for our particular case, we need a few initial values for the sequence which are trivial:

Using this recurrence, we now can solve for our particular case of , for which we get an answer of **922111**.

## Round 3: Problem 3 Solution

It should be relatively easy to find a cycle of length 42 in the “castle.” There is one pictured at the left (or enlarged here), but try it out on a piece of paper and you’ll see it works out easily as long as you don’t make any poor choices.

What we need to prove, however, is that there is no cycle of greater length in the castle.

To do so, let us color the rooms of the castle black and white like a chessboard so that no two rooms that share an edge share a color. Let’s assume that there *is *a cycle that passes through more than 42 rooms. That longer cycle would need to look like this:

where each arrow represents moving from one room to another and the final move returns to the starting room. Since we colored the board in a checkerboard pattern so that no rooms of the same color share a common edge, such a cycle would need to alternate colors. However, if we count the number of white and black squares on the board, we see that there are 21 black squares and 24 white squares (or the reverse depending on which color you start with). Such a cycle, then, would not be able to touch 3 of the white squares because there are no black squares to alternate with. Therefore we can conclude that 42 is the longest cycle length on this board.