# CUNY Math Challenge Blog

Solutions, Resources, Further Information & Discussion

## 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:’

$\square\; \square\; \square\; \square\; \square\; \text{...}\;\square\; \square\; \square\; \square\; \square$

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

$1\; \square\; \square\; \square\; \square\; \text{...}\;\square\; \square\; \square\; \square\; \square$

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:

$1\; 0\; 1\; \square\; \square\; \text{...}\;\square\; \square\; \square\; \square\; \square$
$1\; 0\; 0\; 1\; \square\; \text{...}\;\square\; \square\; \square\; \square\; \square$

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 $n$, we notice that the number of ways to build such a sequence is $\alpha_n=\alpha_{n-2}+\alpha_{n-3}$, 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:

$\alpha_1=1$
$\alpha_2=1$
$\alpha_3=2$

Using this recurrence, we now can solve for our particular case of $\alpha_{50}$, for which we get an answer of 922111.

April 13, 2009 at 00:03

Posted in Round 3

## 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 $C'$ would need to look like this:

$C'=W\to B\to W\to B\to ... W\to B(\to W)$

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.

April 13, 2009 at 00:02

Posted in Round 3

Tagged with , , , , ,

## Round 3: Problem 2 Solution

Let’s call the maximum size a “sweet” set can have $n$, and let us try to find an upper bound for n.

Assume we have a set $S$ of size $n$ with distinct positive integer elements. Let’s construct a set, say $S'$, with the elements of $S \bmod 3$.

Note a few important points:

• All elements of $S'$ are either {0, 1, 2}.
• If $S'$ contains three of the same element, those three elements would sum to $0 \bmod 3$ which would mean that those three elements could not sum to a prime.
• If $S'$ contains one element each of {0, 1, 2}, then those three elements would sum to $0 \bmod3$.
• All elements of the original set $S$ sum to at least 6 because we can have only distinct positive integers in $S$.

Therefore, $S$ can contain at most 2 elements that are congruent mod 3 for at most 2 different possible remainders, meaning that our upper bound cannot be larger than 4 (otherwise at least one of the two conditions must fail). What is left is to see if there exists such a set of size 4, which indeed there are many, for example {1, 3, 7, 9}.

April 13, 2009 at 00:01

Posted in Round 3

Tagged with , ,

## Round 3: Problem 1 Solution

This is a famous old riddle that’s been “updated.” Kids these days… Anyhow, it’s not the best wording for the problem, but what we get is as follows: each person drinks $2\frac{2}{3}$ beers. Therefore, the first student who brought 3 beers has given up $\frac{1}{3}$ of a beer and the second student who brought 5 beers has given up $2\frac{1}{3}$ beers in order to provide the third student with his beers. We need to apply these ratios to the $8 of payment, so to do so we need to calculate what percentage of the third student’s beers were contributed by each of the first two students. $\frac{\frac{1}{3}}{\frac{8}{3}}=\frac{1}{8}$, so the first student has contributed $\frac{1}{8}$ of the third student’s beer and the second student has contributed $\frac{7}{8}$. Using this ratio, the first student should get$1 and the second student should get \$7.

April 13, 2009 at 00:00

Posted in Round 3

Tagged with , ,

## Round 3: Problem 5

with one comment

You are given 8 unit cubes such that 24 of the faces are painted blue and 24 of the faces are painted red. Prove that it is always possible to use these cubes to form a 2x2x2 cube that has the same number of blue and red unit squares on its surface.

Submissions for round 3 are due by Sunday, April 12 at 11:59 p.m. Solution will be posted (if we solve it) immediately after submissions are over.

March 30, 2009 at 00:55

Posted in Round 3

## Round 3: Problem 4

Each CUNY Math Challenge participant is allocated a 50-digit identification number. The I.D. number must start with a 1 and only use the digits 0 and 1. Moreover, it may not contain two consecutive 1s or three consecutive 0s. How many different identification numbers that meet these requirements are possible?

Submissions for round 3 are due by Sunday, April 12 at 11:59 p.m. Solution will be posted (if we solve it) immediately after submissions are over.

March 30, 2009 at 00:54

Posted in Round 3

## Round 3: Problem 3

Castle

The interior of a castle has the shape shown in the diagram to the right and consists of 45 square-shaped rooms.

There are doors between every two rooms that share a common wall. A tourist starts from one of the rooms and desires to visit as many of the castle’s rooms as possible so that he returns to his starting room but does not visit any (other) room more than once. What’s the largest number of rooms that he can visit?

Submissions for round 3 are due by Sunday, April 12 at 11:59 p.m. Solution will be posted (if we solve it) immediately after submissions are over.