Welcome to the Qualifying Quiz!

The Qualifying Quiz is the centerpiece of the Mathcamp application: it's a set of 7-10 problems, designed to be fun, challenging, and thought-provoking for you, and to give us a good read on how you think about math. We assume no background outside of the standard high-school curriculum, but the problems are anything but standard: you'll have to think hard to solve them. If the problems stick with you, nag you in the shower, and make you want to learn more, then that's a good indication that Mathcamp's classes will be fun for you.

The 2015 Qualifying Quiz is not yet available; it will be posted in January. It will be similar in format and difficulty to previous Mathcamp Qualifying Quizzes, so we invite you to check out the 2014 Quiz (below).

Instructions

We call it a Quiz, but it's really a challenge: a chance for you to show us how you approach new problems and new concepts in mathematics. What matters to us are not just your final results, but your reasoning. Correct answers on their own will count for very little: you need to justify all your assertions and prove to us that your solution is correct. (For some general tips on writing proofs, see proof tips, or take a look at examples of solutions to past QQ problems.) Sometimes it may take a while to find the right way of approaching a problem. Be patient: there is no time limit on this quiz.

We don't expect every applicant to solve every problem: in the past, we have sometimes admitted people who could do only half of them, occasionally even fewer. However, don't just do four or five problems and declare yourself done! The more problems you attempt, the better your chances. The problems are roughly in increasing order of difficulty, but the later problems often have some easier parts. We strongly recommend that you try all the problems and send us the results of your efforts: partial solutions, conjectures, methods -- everything counts. None of the problems require a computer; you are welcome to use one if you'd like, but first read a word of warning about computers.

If you need clarification on a problem, please contact us. You may not consult or get help from anyone else. You may use books or the Web to look up definitions, formulas, or standard techniques, but any information obtained in this way must be clearly referenced in your solution. Please do not try to look for the problems themselves: we want to see how well you can do math, not how well you can use Google. Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp. Read more about our policy on getting help.

You may handwrite or type your Quiz. For those interested in typing mathematics beautifully, we also offer you the LaTeX source file for the Qualifying Quiz. Please don't let it distract you from solving the problems, though! For more information on LaTeX, take a look at our LaTeX tutorial for The QQ. No matter how you write up your solutions, we require that you upload them with your application as PDF files; visit our PDF tutorial if you need help.

Finally: don't write your name on your Quiz. (Really!) Instead, write your applicant ID number on your Quiz. (You will receive an applicant ID number when you start your online application, on the welcome page.) Why not your name? When we grade Quizzes, we want to be thinking just about the math. So we're doing an experiment in which we evaluate all applicants just by ID number and then uncover the names later. We appreciate your help with the experiment.

Good luck and have fun!

The 2014 Quiz Problems

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.