2013 Qualifying Quiz

You may also be interested in the printable (PDF) format or the LaTeX source code.

  1. A teacher asks 100 students to help her with a math contest that she's organizing: each student is supposed to come up with one or two problems to include in the contest. All 100 students do as requested, which takes the teacher by surprise: she actually needed only n problems, with n < 100, so now she has to decide which problems to use. She announces that she will call on the students one by one, at random, and collect all the problems from each student she calls on. Once she has n problems, she will stop. (If the last student wrote two problems and the teacher only needs one of them, she'll pick one at random.)
    1. Angela thought of one problem, Bill thought of two. Bill tells Angela, "Because I wrote more problems than you, I have a better chance of getting a problem on the contest." Angela says, "But the teacher is picking people completely at random! My chances of getting picked are as good as yours." Who is right? Does it depend on n? Does it depend on how many problems the other students came up with? (Be sure to explain any special cases.)
    2. Catherine only thought of one problem, but she overhears Bill talking to Angela and gets worried. She quickly composes another problem, just in case. Does this change her chances of having a problem on the contest? Does it change Bill's or Angela's chances, and if so, in what direction? (Note: you do not need to compute the exact probabilities.)
  2. The subscript ! sometimes indicates that a string of numbers is to be interpreted in factorial base: the i-th number from the right ranges from 0 to i and tells you what multiple of i! to add. For example,
    20301! = 2·5! + 0·4! + 3·3! + 0·2! + 1·1! = 240 + 18 + 1 = 259.
    1. Warm-up: show that a number is even if and only if its factorial base representation ends in 0. State and prove a similar condition for divisibility by 3.
    2. The number 27 has the property that its binary representation 110112 ends with its factorial base representation 1011!. Show that there are infinitely many numbers with this property.
  3. Charles and Lilly are playing a game. They start with an empty pot, to which a piece of candy is automatically added at the beginning of every turn. The player whose turn it is then has a choice: he/she can either take all the candy in the pot or pass. (For instance, if Lilly goes first and takes the pot on her first turn, she gets one piece of candy. If she passes and Charles takes the pot on the next turn, he gets two pieces, etc.) If a player decides to take the pot, he/she must pass on his/her next k turns. The winner is the first player to collect n pieces of candy.

    Charles unwisely offers Lilly the choice of going first or second. Which should she choose in order to be sure of winning, and how should she play? (Her choice may depend on n and/or k. You need to describe Lilly's strategy completely and prove that Charles cannot win against it, no matter what he does. We suggest you start with the case k = 1.)

    Note: This is a variant of the online game Reaper: http://www.artofproblemsolving.com/Edutainment/r2. Playing the original version of Reaper will not help you solve this problem, but you can check it out just for fun.
  4. A binary block is a rectangle whose side-lengths are powers of two.
    1. Show that any m x n rectangle can be chopped up into binary blocks no two of which are the same. For example, a 5x5 rectangle can be cut into binary blocks of dimensions 4x4, 4x1, 1x4, and 1x1. (Note that a 4x1 block is considered different from a 1x4 block: rotation is not allowed.)
    2. If m = 1 or m = 2, show that you get the same set of binary blocks from your m x n rectangle no matter how you arrange the cuts. (In other words, the set of blocks is uniquely determined by m and n in this case.)
    3. On the other hand, if m = n = 5, there is more than one set of binary blocks that works. Can you demonstrate this?
    4. Ideally, we'd like to find a set of rectangular blocks with integer sides (not necessarily powers of two) such that (i) every m x n rectangle can be cut into blocks from this set that are all different, and (ii) the blocks obtained in this way are uniquely determined by m and n. As we just saw, the set of binary blocks satisfies condition (i) but not (ii). Can you find a different set of blocks that satisfies both conditions?
    5. (Hard!) Our results in (b) and (c) raise the question: for what values of m and n is the set of binary blocks unique? Try to find a necessary and sufficient condition for uniqueness. (You'll need to prove that if m and n satisfy the condition, uniqueness is guaranteed, whereas if they don't satisfy it, there are at least two different sets of blocks that work. If the general version seems too hard, try for some partial results: are there classes of numbers m and n for which you can prove that there is only one set of binary blocks? Are there classes of numbers for which you can prove that there is more than one?)
  5. A farmer living on the xy-plane wants to fence off a rectangular field with sides parallel to the axes and area at least 1. A malicious king tries to stop the farmer by preemptively placing stakes at infinitely many points in the plane (thereby staking his own claim to those points). It's a constitutional monarchy, so the king can't just claim every point for himself: the law dictates that each point where he places a stake must have a circle of non-zero radius around it that contains no other stakes. (These unclaimed circles around each stake can be of different sizes and can be as small as the king likes.) Can the king place his stakes in such a way that the farmer can't find a rectangle of area 1 with no stakes anywhere in its interior or boundary?
  6. Isosceles triangle ABC has AB = AC and ∠BAC = α. The triangle is originally situated in the plane with A at (0,0) and midpoint M of side BC at (1,0). You are allowed to move the triangle by reflecting it across any of its edges. Your goal is to come up with a sequence of moves that switches A and M – that is, brings A to (1,0) and M to (0,0).
    1. Show that such a switch is impossible if α=60° or 90°.
    2. If α = 45°, show that such a switch is still impossible, but that the triangle can come close to its destination: we can simultaneously get A within distance 0.1 of (1,0) and M within distance 0.1 of (0,0). Can we get even closer? How close?
    3. Does there exist an angle α for which switching A and M is possible?
  7. Let f be a function on the nonnegative integers such that f (2n) = f ( f (n)) and f (2n+1) = f (2n)+1.
    1. If f (0) = 0, find a simple formula for f (n).
    2. Show that f (0) cannot equal 1. For what nonnegative integers k (if any) can f (0) equal 2k?
    3. For what nonnegative integers k (if any) can f (0) equal 2k+2?
    4. (Open question!) What else can you say about the possible values of f (0)? Are there values of f (0) for which more than one such function exists? If so, how many different functions are there? Partial results are welcome.

Problems 1, 2, and 7 were written by the Mathcamp staff. Problem 5 is folklore. The other problems are due to Mathcamp alumni: Charles Steinhardt, MC'96-'98, Lilly Chin, MC '10-'11 and Aaron Landesman, MC '10-'12 (#3); Billy Swartworth, MC '11-'12 (#4); and Zach Abel, MC '03-'04 (#6). Thanks to all!