2021 Qualifying Quiz
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:
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.
- 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".)
- 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?
- 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?
- 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?
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.
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.
- 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?
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).
- Suppose the blue die starts with 4 sides. What is the probability that Kai wins?
- Suppose the blue die starts with N sides. 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.
- 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?
- 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?
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.
- What is the minimal number of gardens if n = 6?
- Prove that the number of gardens must be at least (1/5)(n−2)2.
- Prove that it is possible to construct an apartment complex with no more than (1/5)n2 gardens for any n.
- 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?
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.
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.
- Show that there can be at most 14 abundant circles.
- Can there be 14 abundant circles? If not, what is the maximum number possible?
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.
- 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.)
- 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.
- 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?
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 (A1, A2, …, An) such that the campers are standing in the infinite row in that order, not necessarily consecutively. (A1 is to the left of A2, who is to the left of A3, and so on.)
- You must schedule CHS games between the campers to find a subsequence (A1, A2, A3) of three campers such that either A1 ≺ A2 ≺ A3 or A1 ≻ A2 ≻ A3. 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.
- Now, suppose you want to find either a subsequence (A1, A2, A3) such that A1 ≺ A2 ≺ A3, or a subsequence (A1, A2, …, An) such that A1 ≻ A2 ≻ … ≻ An.
Show that you can always do this in less than 10n games. (As a challenge, how much can you improve this bound?)
- 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 (A1, A2, …, An) such that whenever i < j, we have Ai ≺ Aj. 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.
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!
What about compound statements?
Questions and statements can be compound (using, e.g., 'and', 'or', 'if'), but an answer will still only have a single truth value. For example, if you asked, "Is Mathcamp awesome, and is the sky green?", the answer would be "no" because only one of the two parts connected by "and" is true.
Does the die have to be 3-dimensional? That is, what numbers of sides, N, are allowed?
Any whole number of sides N > 0 is allowed; the geometry is not relevant. In particular, can you have a die with just two sides (or even one)? Yes, you can, even though this doesn't really make sense physically (they are magic after all!).
Problem 3(c) asks for a maximum, but aren't you allowed to have, say, n2-1 gardens and 1 apartment? (Even though, at that point, it becomes more of a garden complex than an apartment one :) )
You could have a garden in every lot, and you're right that that would be more than (1/5)n2 gardens. But the question is saying the apartment complex can be constructed with no more than (1/5)n2. It wants you to prove that no matter what n is, it is always possible to build an apartment complex with at most that many gardens, while still giving all apartments a scenic view. (As several of you who asked this question have pointed out, it is also possible to build one with many more gardens!)
Do the samples in parts (b) and (c) still have at most 32 people, or may they vary in size?
Yes, the 32 sample limit applies to all parts of the problem. You can have smaller pooled samples but not larger ones.
In parts b and c, does the restriction that only 16 tests are available for the entire town still apply?
No, the 16 test limit is just for part a. (The second paragraph of problem 5 applies to all parts, though: in particular, the at-most-32-samples-per-pooled-sample limit is still true in b and c.)
The problem says: "not only do you not know who is sick, but even how many of the 10 are." Is it saying that we don't know who is sick and we DON'T know how many of the 10 are, or is it saying that we do know who is sick and we DO know how many of the 10 are?
You DON'T know how many of the 10 are. Maybe one of them is sick, or maybe seven are; either way the test result will just say "positive" and you get no further information.
Can two players have the same skill level, so their game is a tie?
No, there cannot be ties. Either A ≺ B or B ≺ A.
In part (b), is the question correct as it is, or should both sequences be of length n?
Yup, it's supposed to be as written: an increasing subsequence of length 3 or a decreasing subsequence of length n.