Welcome to the 2019 Qualifying Quiz!

What is the Quiz?

The Qualifying Quiz is the centerpiece of the Mathcamp application: it's a set of 5-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.

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 have 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.

The problems are roughly in increasing order of difficulty, but even the later problems often have some easier parts. 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 solve three or four problems and declare yourself done! The more problems you attempt, the better your chances. We strongly recommend that you try all the problems and send us the results of your efforts: partial solutions, conjectures, methods – everything counts. Also, if you come up with a solution that is messy and ugly, see if you can find a better way of thinking about the problem: elegance and clarity count too! 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 any problem, please contact us. You may not consult or get help from anyone else. You can 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! For further clarification, read more about our policy on getting help. Any deviation from these rules will be considered plagiarism and may permanently disqualify you from attending Mathcamp.

In a lot of contexts, we do mathematics collaboratively, and it's often more fun to work on math problems with friends. Even if you customarily do math with others, and even if the standard in your home community is to do problems together: that's not how the Quiz works. Because we are using it as an evaluative tool, it is really, really important to us that you do not talk with others about the problems until after application season is over. That means: don't talk with others about the problems; don't ask others how to solve them; don't share your own solutions with others; for goodness sake, don't post on internet forums asking other poeple to solve them for you. All of these are considered cheating.

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 2019 Quiz Problems

You may also be interested in the printable (PDF) format or the LaTeX source code. And perhaps the LaTeX Sample File for Solutions.

Note that we updated the primer on Combinatorial Game Theory on Feb 8th, so if you haven't seen the new version, take a look! We added a section on nimsum. Enjoy!

  1. If you take a scientific calculator, type in any number, and then alternate applying the operations ATAN and COS, then eventually you will reach a point where you run into a cycle: after every COS step, you will see a result of approximately 0.786 (and after every ATAN step, a result of approximately 0.666 radians, or 38.2 degrees).

    1. Find a formula for the number you get by starting with 0 and then applying the procedure "apply ATAN and then COS" n times. (You may give either an explicit formula or a recursive formula. In either case, you should try to make the formula as simple as possible.)
    2. Find an exact formula for the 0.786 number. (You do not need to prove that the formula that you found in part (a) converges to this number.)
  2. Susan and Eric are playing a dice game, with standard six-sided dice which have an equal probability of rolling each integer from 1 through 6. Each player takes turns scoring points as follows.

    On Susan's turn, she rolls a die. If it's a 1, she rolls two dice in its place, continuing to replace any 1s by two new dice. When finally no 1s are showing, Susan scores points equal to the sum of the remaining dice, and then her turn ends. (For example, suppose she rolls a 1. Then it gets replaced by two dice; if these are a 3 and a 1, the 3 remains and the 1 gets replaced by two more; if these are a 2 and a 4, then Susan stops and scores 3 + 2 + 4 = 9 points.)

    On Eric's turn, he rolls a die. If it's even, he replaces it with a roll of two dice; if the new total is even, he replaces it with a roll of three dice, etc. He continues to roll one more die than previously as long as his total is even. When he finally rolls an odd total, Eric scores that many points, and then his turn ends.

    On average, how many points do Susan and Eric each score on a turn?

  3. In the game of Flip Flop, players stand in a circle and take turns saying the numbers 1, 2, 3, etc., going clockwise.

    When they get to a multiple of 7, the player whose turn it is says FLIP instead, and the direction switches: if they were going clockwise before, they now go counterclockwise, or vice versa.

    When they get to a multiple if 8, the player whose turn it is says FLOP instead. The direction stays the same, but the next person is skipped over.

    For a number n that is a multiple of both 7 and 8, the player says FLIP FLOP. Direction reverses and you skip over the next person. This means n + 1 is said by the person who said n - 2.

    1. Show that no matter how many people are in the circle, eventually each person will get a turn to speak.
    2. Suppose we replace 7 and 8 by arbitrary integers K and M respectively. For what values of K, M is every player eventually guaranteed get a turn to speak (regardless of the number of players)?
  4. There is a puzzle with N2 pieces, each one shaped like a wedge that is 1/N of a disk. On the front of each piece, each of the two sides of the wedge is labeled with an integer between 1 and N, so that each of the N2 possible ordered pairs occurs exactly once. The goal of the puzzle is to form N full disks in such a way that the edges come together to have the same label. Below is an example of some pieces fitting together to form a full disk when N = 5.

    puzzle picture
    1. Show that the puzzle can be solved when N = 5.
    2. Show that the puzzle can be solved for any integer N ≥ 3. Partial credit will be awarded for a proof that the puzzle can be solved for infinitely many N.
  5. Every day at noon exactly, people submit orders of positive integer numbers of paninis at your panini store. It takes you 1 minute to make 1 panini.

    When Alice orders 2 paninis and Bob orders 100 paninis, you decide to make Alice's paninis first, because it results in less total customer wait time (104 vs. 202 minutes).

    • [Warm-up exercise: do not submit an answer] Show that for any set of orders, you achieve the smallest total wait time by processing the smaller orders first.

    When the town gets wind of your scheme, they hatch devious plans. Instead of ordering 100 paninis, Bob decides to submit 100 orders of 1 panini each under different names, so he gets processed first. Oh no.

    Call a panini-making scheme strategy-free if no customer, in any scenario, can strictly decrease their average wait time just by splitting their order up into several smaller (integer-size) orders.

    Assume your customers are aware of your scheme and will not split up their orders if the scheme is strategy-free.

    1. Show that the scheme "choose the sequence of orders uniformly at random" is strategy-free.
    2. Give an example of a strategy-free scheme that has a lower average wait time than the above scheme whenever the orders are not all the same size.
    3. Suppose you know that, on any given day, you will either receive (1) three orders for one panini each, or (2) one order for one panini and one order for two paninis. Give a strategy-free panini-making scheme such that in either scenario (1) or (2), the average total wait time is at most 25/24 the optimal total wait time.
  6. Jennifer and Serena are playing a game called Candy Split. They start with two piles of candy, one of size M and one of size K. On a player's turn, she eats one of the piles and splits the other pile into two (non-empty) piles any way she wants. Whoever can't make a legal move (i.e. is presented with two piles of one candy each) loses. Note that eating as much candy as possible is not the object of the game, though it may be a pleasant side effect.

    • [Warm-up exercise: do not submit an answer] Serena gets to decide whether to go first or second. What should she do when M = 2018 and K = 2019? What about for general values of M and K? (Hint: it's all about the parity of M and K.)

    The reason we're not asking you to submit an answer for the warm-up exercise is that it's a famous problem that can be found in many places on the internet. (Feel free to look it up if you can't figure out the answer.) What we are really interested is a harder problem:

    Suppose Jennifer and Serena have three different types of candy. The game is now played with six piles of candy, two piles of each type. On a player's turn, she chooses a type of candy, eats one of the piles of that type, and splits the other. Whoever can't move loses. If the numbers are (M1, K1), (M2, K2) and (M3, K3), is it better to go first or second, and what is the winning strategy?

    In order to solve this problem, you will need to learn a little bit of combinatorial game theory at this link: www.mathcamp.org/2019/cgt.pdf.

    1. Fill out the following table of nimvalues for Candy Split. The (M,K) entry of your table should show the nimvalue of the game with piles of size M and K.

      M\K12345678
      1
      2
      3
      4
      5
      6
      7
      8


    2. The game is (2,4), (1,8), and (3,5). It is Serena's turn. What should she do? Explain how to derive the answer from your table.
    3. Can you see a pattern in the table? If not, try enlarging the table some more until you see it. (Feel free to use a computer if you'd like, but you can certainly solve the problem without it.)

      Based on your conjectured pattern, write down a formula (or algorithm) for computing the nimvalue of (M, K) for all M and K. If you can, prove your formula!
    4. The game is (2,4), (1,8), and (2019, 2030). It is Serena's turn. What should she do? Explain how to derive the answer from your formula or pattern (even if you haven't proved it).

All problems were written by the Mathcamp staff.