2014 Qualifying Quiz

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

  1. Imagine a chessboard that extends infinitely far in all directions. In the center of every square is a grasshopper.
    1. Show that it is possible for all the grasshoppers to jump simultaneously, so that after the jump there are exactly two grasshoppers in the center of every square. (A grasshopper can jump arbitrarily far; it can also jump straight up and land on the same spot it started on.)
    2. Now suppose the squares are 1 inch x 1 inch, and a grasshopper can jump at most 100 inches. Is it still possible to end up with two grasshoppers in the center of every square after one jump? If yes, show how it can be done. If no, prove your answer. (Note: Saying that your strategy from part (a) won't work is not a proof that it can't be done, because there might be a different strategy that does work.)
  2. Stephanie is an evil genius; she is building an army of robots and cyborgs. Every day, each of Stephanie's robots builds a copy of itself, while each of her cyborgs builds three new cyborgs and a robot. Once built, the cyborgs and robots never break or die.
    1. If Stephanie wants to double her army each successive day (i.e. to have exactly twice as many robots and twice as many cyborgs as the day before), what ratio of robots and cyborgs should she start with? What if she wants to quadruple her army each day?
    2. More generally, if Stephanie starts with R robots and C cyborgs on day 0, what will be the composition of her army after n days? Prove your answer. (One way to approach this problem is to use part (a), but you're welcome to do it any way you like.)
  3. Let Pn be a regular n-sided polygon inscribed in a circle of radius 1. What is the minimum number of circles of radius ½ required to cover Pn completely? (Both Pn and the circles in this problem include the boundary as well as the interior.) Note: in order to prove that something is the minimum, you need to prove both that it works and that nothing smaller works.
  4. Hannah is about to get into a swimming pool in which every lane already has one swimmer in it. Hannah wants to choose a lane in which she would have to encounter the other swimmer as infrequently as possible. All swimmers, including Hannah, swim back and forth at constant speeds, never pausing at the ends of the pool. Hannah swims at speed 1 (one pool length per minute).
    1. Say Hannah chooses a lane with a swimmer who swims at speed 0<s<1. Prove that, if they keep swimming long enough, eventually Hannah and the other swimmer will settle into a pattern where they pass each other (either in the same or in opposite directions, or at the edge of the pool) exactly N times every M minutes, where M and N are relatively prime integers. Find M and N. Do they depend on the other swimmer's speed and/or initial position when Hannah enters the pool?
    2. What if Hannah chooses a lane with a swimmer whose speed is s>1?
    3. From Hannah's point of view, what is the ideal nonzero speed that another swimmer can have? (Assume Hannah can time her entry into the pool with perfect precision, so she can make the other swimmer's initial position be whatever she wants.)
  5. Let p be a prime. For which integers n is it possible to split the set {1,2, … ,n} into p disjoint subsets such that the sum of the integers in each of the subsets is the same? Prove your answer.
  6. A path from the bottom left to the upper right corner of an m x n grid is called monotonic if on each step it goes either up (U) or to the right (R). Such a path has m + n steps, of which M are U's and n are R's. Thus the total number of monotonic paths is C(m+n, m) = C(m+n, n). (If you are not familiar with this kind of argument, or you are unfamiliar with this notation, see our background handout.)

    We define the area of a monotonic path to be the number of squares underneath it. The area can be anywhere between 0 and mn. We are interested in areas of monotonic paths modulo a prime q. (If you don't have much experience with modular arithmetic, you should again consult our background handout.)
    1. The forward shift of a monotonic path p is the path that results when we take the first step of p (either U or R) and move it to the end. For instance, the forward shift of URRURU would be RRURUU. Of course, once we perform m + n forward shifts, we get our original path back. Now suppose m + n = q, where q is prime. Let P0 be a monotonic path on an m x n grid, and let P1, P2,  … , Pq-1 be successive forward shifts of P0. Show that for each integer k = 0, 1, … , q-1, exactly one of P0, P1, … , Pq-1 has area congruent to k modulo q.
    2. Consider all monotonic paths on a q x q grid, where q is prime. For each integer k = 0, 1, … , q-1, how many of these C(2q, q) paths have area congruent to k modulo q? (Hint: use part (a). It may not seem relevant, but it is.)
    3. More generally, consider all monotonic paths on an mq x nq grid, where q is prime and M and n are arbitrary positive integers. For each integer k = 0, 1, … , q-1, how many of these paths have area congruent to k modulo q?
  7. A voting system is a way of combining the disparate preferences of many individual voters to arrive at a single decision for the group as a whole. When there are two candidates, there is only one reasonable voting system: the candidate who is preferred by the majority of voters wins. But with more than two candidates, things become much trickier. For instance, with three candidates A, B, and C, it is possible that a majority of voters prefers A to B, a majority prefers B to C, and a majority prefers C to A. (See "Voting Paradox" on Wikipedia.) So how should we decide on the winner? There are no easy answers to this question; in fact, you can even prove that, if voter preferences are allowed to be completely arbitrary, there are no good voting systems at all. (If you'd like to learn more about this, search under "voting theory" in Wikipedia - or come to Mathcamp and take a class on voting theory.)

    This problem is not about finding good voting systems; it's about how strange and inconsistent voter preferences in a group can be. An individual voter's preferences are given by "C1 > C2 >  …  > Cn", which means that candidate C1 is the voter's top choice, candidate C2 is her second choice, etc. We assume that each individual's preferences are transitive: if a voter prefers C1 to C2 and C2 to C3, then he will prefer C1 to C3. But, as the voting paradox shows, the preferences of the group as a whole might not have this property.
    1. If there are four candidates A, B, C, and D, show that it is possible to have a set of voter preferences such that a majority of voters prefers A to B, a majority prefers B to C, a majority prefers C to D, yet every single voter prefers D to A. (The simplest way to show such a thing is simply to write down a set of preferences satisfying these conditions.)
    2. Suppose there are n candidates C1, C2, … , Cn, and for every pair Ci, Cj (with i ≠ j ), I tell you which one should get a majority in a two-way election. Show that it is always possible to construct a set of voter preferences that satisfy these pairwise conditions.
    3. Extra credit: How many voters did you need in your proof in part (b)? Can you find a proof that uses fewer? For a given number n of candidates, what is the smallest number of voters that is guaranteed to work? (Note: We don't know the solution to this problem. We can get the number to be pretty small, but we can't prove that our solution is the smallest. Kudos to you if you can prove it -- or if you can prove us wrong by coming up with something even smaller!)

Problem #6 is due to Bill Kuszmaul, MC '12-'13; all other problems were written by the Mathcamp staff.