2004 Qualifying Quiz
You may also be interested in the printable (PDF) format or the LaTeX source code.
Problems
1. Feng and Simona are playing a game in which they take turns breaking up a rectangular bar of chocolate, six squares wide by eight squares long. Each break must be in a straight line along the divisions between the squares, and must go all the way across. Once the bar breaks into several pieces, the players continue taking turns choosing one piece and breaking it, until only the individual squares remain. The player who makes the last break wins the game (and the chocolate). If Feng goes first, who will win? Is there a strategy that this player has to follow? Be sure you explain why she can be assured of her victory, no matter what moves her opponent makes.
2. Find the smallest positive integer n such that n/2 is the square of an integer, n/3 is the cube of an integer, n/5 is the fifth power of an integer, and n/11 is the 11th power of an integer.
3. Mark is drawing up the Mathcamp schedule, doing his best to make it possible for everyone to attend the classes of their choice. 70% of the campers want to take Alice's class on set theory, 75% of the campers want to go to Brenda's class on projective geometry, 80% of the campers say they're interested in Chris's class on group theory, and 85% of the campers want to take Dave's number theory class. What's the smallest possible percentage of campers that want to go to all four classes?
4. On a regular dodecagon (12-sided polygon), number the vertices 1 through 12 in order, as on the face of a clock. Connect 11 to 3, 8 to 12, and 10 to 1. Do these three lines meet in a single point? Be sure to prove your answer.
5. Three bugs are crawling on the coordinate plane. They move
one at a time, and each bug will only crawl in a direction parallel to
the line joining the other two.
(a) If the bugs start out at (0,0), (3,0), and (0,3), is it possible that
after some time the first bug will end up back where it started, while the
other two bugs switch places?
(b) Can the three bugs end up at (1,2), (2,5), and (-2,3)?
6. Nineteen Mathcamp students have signed up for a ping-pong tournament in
which each participant is to play exactly 10 games, and no one should play
the same opponent twice.
(a) Show that it is possible to arrange such a tournament.
(b) Show that any two players who play one another have at least one
common opponent.
(c) Is it possible to arrange the tournament so that any two players who
play one another have exactly one common opponent?
7. The Rainbow Game is played by a team of seven. Each player gets a hat, which can be any one of the seven colors red, orange, yellow, green, blue, indigo, and violet. The colors of the hats are independent of each other and repetitions are allowed: for instance, it may happen that all the hats are green. Each player can see only the colors of the six hats worn by the rest of the team; no player can see the color of his or her own hat. The players are to guess the colors of their own hats, and if at least one player guesses correctly then the team as a whole wins.
The players may not communicate in any fashion during the game, and they must all announce their guesses simultaneously. They are, however, allowed to plan out a strategy in advance. Is there a strategy for choosing their guesses that will allow the team to win 100% of the time? (As a warm-up, try it with two players and two colors).
8. The sequence a0 = 0, a1 = 1, a2 = 4, a3 = 15, ... is defined via the recursion an = 4 an-1 - an-2 for n >= 2. Show that the triple of numbers (an-1, 2 an, an+1) has the property that the product of any two of the numbers is one less than a perfect square.
9. The number 1089 has the property that to multiply it by 9 you just reverse the digits, i.e. 9 x 1089 = 9801. How many n-digit numbers are there with this property?
10. Parity High School has n students. The school rules allow the students to form clubs, but dictate that each club must have an odd number of members, and that any two clubs must have an even number of members in common. What is the largest possible number of clubs? Be sure to prove your answer.
For those who happen to know advanced linear algebra, there is a very short and elegant solution to this problem. We suspect that there is an elementary solution as well, but we have not been able to find it. We are hoping that one of you can--consider this our final challenge to you!
