2021 Qualifying Quiz

1. People at Mathcamp can be in one of three categories: campers, JCs, and mentors. There is a universal rule about what happens when they talk:
   • Mentors always lie to campers. (They say all sorts of bizarre things about so-called "imaginary numbers" and "sizes of infinity".)
   • Campers always lie to JCs. (They say things like "yes, of course I've called my parents today".)
   • JCs always lie to mentors. (They say things like "of course, I will definitely bring you some chalk".)
   Except for these three cases, everyone always tells the truth. The information in this problem is common knowledge at Mathcamp; you can also assume that whenever anyone makes a statement to anyone else, they know the category of the person they're talking to.
   1. Sachi and Yuval have a conversation. Sachi says to Yuval, "At least one of us is a mentor." Yuval replies to Sachi, "At least one of us is a camper." What can you deduce about Yuval?
   2. You are a camper and you meet someone named Miranda at camp. What question can you ask Miranda about herself to determine whether she is a JC?
   3. Don and Viv are having a conversation as you pass by. Is there a single statement you can overhear from that conversation from which you can deduce that Don and Viv are both in the same group of people (both campers, or both JCs, or both mentors) without giving you any additional information about which group it is?
2. Kai has a collection of magic, shape-changing dice.
   
   When he rolls a blue die, it changes shape to have a number of sides equal to the number rolled minus one. For example, if a blue die starts out with 12 sides, then Kai has an equal probability of rolling any of the twelve integers from 1 through 12. If he rolls an 8, then the blue die changes shape to have 7 sides, and the next roll will have an equal probability of rolling any of the seven integers from 1 through 7. After rolling the same blue die over and over, eventually Kai will roll a 1, at which point the die will disappear.
   1. Suppose the blue die starts with 4 sides (and so it has an equal probability of rolling any of the four integers from 1 through 4). How many rolls, on average, will it take for the die to disappear?
   Now Kai is playing a game with Helena. Kai rolls a blue die first (causing it to change shape), then Helena rolls the same blue die (which changes shape again), and then they continue to take turns rolling the same die until one of them rolls a 1. Whoever rolls the 1 loses.
   2. Suppose the blue die starts with 4 sides. What is the probability that Kai wins?
   3. Suppose the blue die starts with N sides. What is the probability that Kai wins?
   Kai also has green dice, which work slightly differently from blue dice. When he rolls a green die, it changes shape to have a number of sides equal to the number rolled (so if Kai rolls the maximum possible value, the green die doesn't change shape at all).
   4. He plays the same game with Helena, but now with an N-sided green die; the first player to roll a 1 still loses. What is the probability that Kai wins?
   5. Suppose now that Kai and Helena modify their game: the first person to roll one of the numbers 1, 2, …, k loses. If they start with an N-sided green die, what is the probability that Kai wins?
   In parts (c)–(e), write your answer as a function of N and possibly k, in closed form: a recurrence relation or a summation is a good start, but not the final answer.
3. A construction company is designing a new apartment complex. They have an n×n lot in which each 1×1 square can either occupy an apartment or a garden.
   
   The apartments must all have a scenic view: if an apartment is not on the edge of the apartment complex, then one of the 4 adjacent lots must have a garden. For reference, consider the first two diagrams below: diagram (i) shows a valid design, while the design in diagram (ii) has one apartment without a scenic view.
   1. What is the minimal number of gardens if n = 6?
   2. Prove that the number of gardens must be at least (1/5)(n−2)².
   3. Prove that it is possible to construct an apartment complex with no more than (1/5)n² gardens for any n.
   4. Now suppose that gardens have very tall trees that provide a scenic view to up to 20 nearby lots. Specifically, if a garden is placed at the center of a 5×5 square, then every apartment in that square except the four 1×1 corners will have a scenic view of the garden. An example of this is shown in diagram (iii) above.
      
      What upper and lower bounds can you prove on the number of gardens needed?
4. Let S be a set of 8 points in the plane. Call a circle abundant if it passes through at least 4 points of S.
   1. Show that there can be at most 14 abundant circles.
   2. Can there be 14 abundant circles? If not, what is the maximum number possible?
   If you find it hard to think about 14 circles at once, there's a trick. A technique called circle inversion can transform circles and lines into other circles and lines; if applied carefully, it can simplify difficult geometry problems. If you have not encountered this technique before, you may find our handout on inversion (PDF) helpful.
5. A small town has 192 people who want to know whether they have COVID-19. Fortunately, only 2 of them are actually sick. Unfortunately, the town only has enough resources to run 16 tests.
   
   The ambitious scientists of the town have realized that they can combine as many as 32 samples into a single "pooled sample", which will return a positive result if any of the people in the sample are positive, and will return a negative result if nobody in that sample has COVID-19. For example, pooling 10 people together will clear all 10 if the result is negative, but if the result is positive, not only do you not know who is sick, but even how many of the 10 are.
   1. Can you figure out a way to help them determine which 2 people to quarantine while avoiding quarantining anybody who is healthy? (The tests you do can depend on the results of earlier tests.)
   2. A nearby, larger town of 1,000 people wants your help with testing. They also have 2 sick people, and will send over some pooled samples for you to test. However, because they don't have a testing center of their own, they'll need to prepare all the pooled samples at the same time. (The tests you do have to be planned ahead of time, and can't depend on the results of earlier tests.)
      
      Find the minimum number of pooled samples needed to identify who is sick, to within a factor of 2. That is, find an n-sample strategy, and prove that n/2 samples are not enough, for some value of n.
   3. A large city hears about your success and wants your help as well. They want to test 10,000 people per day, and each person has about a 5% chance of testing positive, although you don't know the exact number on any given day. (They can do their own testing, and don't need to send samples over, so you can base each test on previous results.)
      
      Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, about how many tests will be required?
6. Infinitely many campers line up in a row for a Competitive Hanabi Set (CHS) tournament. Each camper has an unknown, numerical skill level in playing CHS. A more skilled player will always beat a less skilled one, but the game is very subtle; it is impossible to compare skill levels, except in a one-on-one match. We will write A ≺ B if camper A loses to camper B in CHS (which means that A's skill level is a lower number than B's).
   
   A subsequence of n campers is an n-tuple of campers (A₁, A₂, …, A_n) such that the campers are standing in the infinite row in that order, not necessarily consecutively. (A₁ is to the left of A₂, who is to the left of A₃, and so on.)
   1. You must schedule CHS games between the campers to find a subsequence (A₁, A₂, A₃) of three campers such that either A₁ ≺ A₂ ≺ A₃ or A₁ ≻ A₂ ≻ A₃. You can use the results of each game to schedule the next.
      
      How can you minimize the number of games required in the worst case? Prove that your answer is optimal.
   2. Now, suppose you want to find either a subsequence (A₁, A₂, A₃) such that A₁ ≺ A₂ ≺ A₃, or a subsequence (A₁, A₂, …, A_n) such that A₁ ≻ A₂ ≻ … ≻ A_n.
      
      Show that you can always do this in less than 10n games. (As a challenge, how much can you improve this bound?)
   3. Next, the campers come together in an unorganized crowd, and decide to hold a Two-Player Castlefall (TPC) competition. TPC is a highly strategic and complex game, so it cannot be reduced to a single skill level: in TPC, it is possible that A ≺ B and B ≺ C, but A ≻ C.
      
      You want to find n campers (A₁, A₂, …, A_n) such that whenever i < j, we have A_i ≺ A_j. How can you minimize the number of TPC games required in the worst case?
      
      We don't know the optimal answer here, so you don't have to prove that your answer is optimal. You should prove that your strategy gives the bound you claim, and you should try to make the bound as small as possible.

Problem #5 is due to Charles Steinhardt, MC '96–'98. All other problems were written by the Mathcamp staff.

FAQ Answers

Many applicants asked us questions to clarify the statements of Quiz problems via our QQ helpline. Here are some of the questions and our answers; you might find them helpful!

Problem 1

Problem 2

Problem 3

Problem 5

Problem 6