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.

Good luck and have fun!

## The 2018 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.

1. João and Kinga play a game with a fair n-sided die whose faces are numbered 1, 2, 3, …, n. In this game, João is assigned a value j and Kinga is assigned a value k, both also in the range 1, 2, 3,…, n. João and Kinga take turns rolling the die; João goes first.

If João rolls a number less than or equal to j, the game ends and he wins. If Kinga rolls a number less than or equal to k, the game ends and she wins. The game continues until one player wins.

1. Show that if j = k, then João always has an advantage.
2. If n = 6, find all possible values of j and k which make the game fair. (That is, João and Kinga have equal 50% chances of winning.)
3. If n = 101, show that no values of j and k will make the game fair.
2. The pirates of the Cartesian sail an infinite flat sea, with a small island at coordinates (x, y) for every integer x and y.

1. A pirate’s ship has two sails. Every day, the pirate raises one of the sails and travels for the whole day without stopping. With the first sail raised, a pirate at (x, y) can travel to (x + 3, y + 5) in a single day, or in the reverse direction to (x - 3, y - 5). With the second sail raised, a pirate at (x, y) can travel to (x + 4, y + 6) in a single day, or in the reverse direction to (x - 4, y - 6).

Which islands can a pirate reach from the island at (0, 0), after traveling for any number of days?
2. The Dread Pirate Riemann replaces the second sail on his ship by a sail that lets him travel from (x, y) to either (x + a, y + b) or (x - a, y - b) in a single day, where a and b are integers. (The first sail stays the same as in part (a).) For which values of a and b will the Dread Pirate Riemann be able to reach any island in the Cartesian sea?
3. Can you generalize the result in (b) to two arbitrary sails?
3. For any positive integer n, its list of divisors contains all integers between 1 and n, including 1 and n itself, that divide n with no remainder; they are always listed in increasing order. For example, if n = 20, its list of divisors is 1, 2, 4, 5, 10, 20.

In a fill-in-the-blank puzzle, we take the list of divisors, erase some of them and replace them with blanks, and ask what the original number was.

1. For example, suppose we have the list

1 , 2 , __ , __ , __ , 8 , __ , __ .

Prove that there is only one way to fill in the blanks to get the list of divisors of a number n, and find n.
2. Does there exist a fill-in-the-blank puzzle that has exactly 2018 solutions?
3. For each value of n, the very hard puzzle for n is the one that leaves only the next-to-last divisor, replacing all the others with blanks. For example, the very hard puzzle for 10 is  __ , __ , 5 , __ . It has two solutions: 10 and 15.

For which values of n does the very hard puzzle for n have no solutions other than n?

4. A flock of 3k crows hold a speed-flying competition. All crows have different speeds, and each crow’s speed remains the same throughout the competition. Because crows love secrecy, they don’t want to be distinctive and recognizable, so instead of trying to find the fastest or slowest crow, they want to be as medium as possible.

1. The crows split into groups of 3 at random and then race. In each group of 3, the crow that finishes second wins, so there are 3k - 1 winners.

The 3k - 1 winners repeat this process. In each round, a third of the crows win, and move on to the next round. The crow left after k rounds is declared the most medium crow.

How many of the crows have a chance (depending on which groups of 3 compete together) of being declared the most medium?

2. If there are n crows, where n is not a power of 3, this process has to be modified. In a round where the crows cannot be evenly divided into groups of 3, one or two crows are randomly chosen to sit out: they automatically move on to the next round. After the last round, there will either be one crow left, in which case it is declared the most medium, or two crows, in which case there is a tie. (If there are more than two crows, they can continue with another round.)

For which values of n will a single crow be declared the most medium? When this happens, which of the crows can it be?
5. Take a unit tetrahedron: a 3-dimensional solid with four vertices A, B, C, D all at distance one from each other. We can cut the tetrahedron along a plane that’s equidistant from and parallel to edge AB and edge CD. If we do, the cross-section is a square with side length 1/2, as shown in the diagram below.

Now take a unit 5-cell, which is the 4-dimensional analog of the tetrahedron: a 4-dimensional solid with five vertices A, B, C, D, E all at distance one from each other. We can cut the 5-cell along a 3-dimensional surface (a hyperplane) that’s equidistant from and parallel to edge AB and plane CDE. If we do, what (3-dimensional) cross-section do we get?

6. Max finds a large sphere with 2018 rubber bands wrapped around it. Each rubber band is stretched in the shape of a circle. Max notices that any two rubber bands cross each other in two points, and that no three rubber bands cross at the same point.

By the nature of rubber bands, whenever two cross, one is on top of the other. Max has a magic wand that, when tapped on a crossing, switches which rubber band is on top at that crossing. He may use the magic wand any number of times.

Prove that Max can make it so that if he follows each rubber band around the sphere, no rubber band is ever the top band at two consecutive crossings.

7. A tribble is a creature with unusual powers of reproduction. Tribbles come in positive integer sizes. Every night, a tribble grows in size by 1, and every day, any tribble of even size can split into two tribbles of half its size (possibly multiple times), if it wants to. For example, if we started with a tribble of size 6 on Tuesday, here is one possible way it could grow:

• Tuesday: Two tribbles of size 3 (the tribble decides to split).
• Tuesday night: Two tribbles of size 4 (both tribbles grow).
• Wednesday: One tribble of size 4, one tribble of size 2, and two tribbles of size 1 (one of the tribbles of size 4 splits, and one of the tribbles it produced also splits).
• Wednesday night: One tribble of size 5, one tribble of size 3, and two tribbles of size 2.
• Thursday: One tribble of size 5, one tribble of size 3, and two tribbles of size 2 (the tribbles choose not to split).
1. Suppose that we start with a single tribble of size n. (We start in the morning, so if n is even, the tribble has a chance to split before it grows.) What is the fastest way in which it could split fully into tribbles of size 1? How many tribbles of size 1 would there be?
2. Suppose that we start with a single tribble of size 1. Let T(k) be the number of different possibilities for what we could see after k days (in the evening, after the tribbles have had a chance to split). For example, T(1)=2, because after 1 day we could see either a tribble of size 2, or two tribbles of size 1.

What are the best upper and lower bounds you can give on T(k), in terms of k?
(In particular, how does it compare to simple functions like k2 or 2k or 22k?
We’re less interested in the difference between k2 and 10k2, or 2k and 2k + k.)

3. (EXTRA CREDIT) Given a tribble population such as “Ten tribbles of size 3", it can be difficult to tell whether it can ever be reached, if we start from a single tribble of size 1. Can you come up with any simple conditions that tell us that a population can definitely be reached, or that it definitely cannot be reached?

The question probably does not have a general answer, so partial results are welcome. You might, for example, consider populations with only a small number of tribbles, or only a small number of distinct sizes.

Problem #1 is due to Stephen Newman, MC '16–'17. The author of problem #4 wishes to remain anonymous. Problem #6 is due to Max Jiang, MC '16. Problem #7 is due to Drake Thomas, MC '14–'17. Problems #2, #3, and #5 were written by the Mathcamp staff.