Mathcamp 2023 Quiz

2023 Qualifying Quiz

You have a funny calculator with only two buttons: +1 and ×2. The first button adds 1 to the current number, the second multiplies it by 2. For each nonnegative integer n, what is the shortest sequence of buttons that will get you from 0 to n? (As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof.)
Ordinarily, when an object bounces off of a surface — whether it's light reflecting from a mirror or a billiard ball bouncing off the side of a billiards table — its path makes the same angle with the surface before and after the bounce. However, a Bizarro Billiards table behaves differently.
The table is a rectangle with two horizontal and two vertical sides in the x–y plane. The rule that determines how balls bounce is:
- If the ball is moving up and right along a line with slope 1, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope −1/2.
- If the ball is moving up and right along a line with slope 2, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope −1.
- These two bounces are reversible: if the ball is moving up and left along a line with slope −1/2 or −1, it bounces off and continues moving down and left along a line with slope 1 or slope 2, respectively.
- When the ball is bouncing off another side of the table, the rule for bouncing is the same as it would be if you rotated the table to make that side the top side.
This rule is summarized in the diagram below.

Figure 1: Rule for bouncing.
1. Suppose that the ball starts in the top left corner (point B) moving down and right along a line with slope −1. If the ball hits side AD and bounces off, then hits side BC and bounces off, and then ends up at corner D, what must the proportions of the rectangle be?
2. Suppose that the ball starts in the bottom left corner (point A) moving up and right along a line with slope 1. If the ball hits side BC and bounces off, then hits side CD and bounces off, then hits side AD and bounces off, and then ends up at corner B, what must the proportions of the rectangle be?
3. Suppose that the rectangle has height AB = 3 and width BC = 5, and the ball starts in the bottom left corner (point A) moving up and right along a line with slope 1. Describe the trajectory that the ball takes.
You have 4046 identical-looking coins, but 2023 of them weigh 1 gram each, while the other 2023 coins weigh 2 grams each. You cannot distinguish these coins in any way manually. However, you have a partially-working scale, tuned to some unknown integer value X: when you weigh a set of coins, the scale reports if the weight is "less than X grams" or "at least X grams". You know that 1 < X < 6070.
1. Prove that you can eventually find a set of coins that weighs exactly X grams.
2. Prove that you can find such a set in at most 10000 weighings.
You are exploring the maze below. The red and blue doors are locked, but you know that there is a Red Key in a treasure chest in one of the rooms, and a Blue Key in a different treasure chest. Once you have the Red Key, you can open all of the red doors. Likewise, once you have the Blue Key, you can open all of the blue doors.

Figure 2: The maze.
1. If I chose two random treasure chests to put the keys in, most likely you will not be able to get to them. Suppose I choose randomly from only the valid assignments: those in which you can get to all of the treasure chests. What is the probability that the Red Key will be in the first treasure chest you open?
2. Suppose I choose a random key, and put it in a random treasure chest that you can get to. Then I repeat with the other key, but allow it to be placed in any other treasure chest that you can get to after picking up the first key I placed. What is the probability that the Red Key will be in the first treasure chest you open?
3. The two methods from (a) and (b) give different probabilities, but they're very close together. Can you draw a different map in which the method of (a) gives a probability of picking up the Red Key from the first chest you open of less than 1%, but the method of (b) gives a probability more than 99%? Your map may have any number of doors, treasure chests, and colors — but no other types of obstacle, and only one key of each color.
Narmada and Travis are playing a game in turns; Narmada goes first. Each player stands on their own number line, which has spaces numbered 1 through n for some integer n ≥ 3. Narmada starts at position 1 on her number line, and Travis starts at position n on his. On each player's turn, that player must move to another number on their number line. (The new number need not be adjacent to the old one.) But no repetitions are allowed in the pair of positions: if Narmada moves back to position 1, then Travis cannot move back to position n on his next move, because the ordered pair (1,n) has already occurred. The first player who cannot move loses. Assume both players play optimally.
1. For each n, who wins?
2. Now suppose they are on the same number line, and cannot simultaneously occupy the same spot. (So if Narmada is at 1 and Travis is at 3, Narmada can move to 2, 4, 5, …, n but not 1 or 3.) Furthermore, a position is considered the same if the same spots are occupied (so N=1, T=3 is a repetition of N=3, T=1). For each n, who wins?
3. Same as (b), but the players are considered distinct (so N=1, T=3 isn’t a repetition of N=3, T=1).
The first quadrant is lava. The rest of the plane (including the x and y axes) is safe. To traverse the lava, you can place a board, which is a line segment of length at most 1, between two safe endpoints. Once a board is placed, the line segment becomes safe, and points on it may be used as endpoints of a subsequent board. Your goal is to reach the point (2023, 2023).
1. Prove that one million boards aren't enough.
2. Give a specific number of boards with which you can reach (2023, 2023).
3. Prove that one billion boards aren't enough.

All 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

Does the answer need to be an explicit formula?

It doesn't have to be an explicit formula; you could give a procedure instead. As long as your answer clearly describes what the shortest sequence would be for any n, it's good!

Problem 2

In part (c), what do you mean by "describe the trajectory that the ball takes"? What information should an answer include?

We don’t have any specific requirements for the form of your description of the trajectory. From your description, we should be able to tell that you’ve figured out anything interesting there is to figure out about what the ball does (and proven it).

Was there a typo in the third rule?

Yes, it used to say "These two bounces are reversible: if the ball is moving up and left along a line with slope −1/2 or −1, it bounces off and continues moving down and right along a line with slope 1 or slope 2, respectively."

The correct phrasing is "These two bounces are reversible: if the ball is moving up and left along a line with slope −1/2 or −1, it bounces off and continues moving down and left along a line with slope 1 or slope 2, respectively."

Problem 3

Can I keep track of which coins I've used in previous weighings?

Yes! For example, you can number the coins with a marker if you want, and write down which sets of coins you've included in each weighing. The "cannot distinguish" part just means you can't manually tell which have weight 1 or 2.

Do I have to know that a specific set of coins weighs exactly X grams, or do I just have to put a set weighing exactly X on the scale at some point?

You must be able to identify a set of coins that you can prove has the correct weight; it's not enough to just happen to weigh such a set at some point.

Problem 4

In part (a), do both keys have to be in the starting room?

No; they could be, but you could also pick up one key and use it to get to another key in a different room.

In part (b), does the second key have to be somewhere you can get to only after picking up the first key?

No; it could be, but it could also be in the starting room.

Wait, then how are parts (a) and (b) different?

The difference is subtle! In part (a), you identify which key assignments are valid and choose one uniformly at random. In part (b), you place one key at a time, making sure that it can be reached using the keys that you have so far. Consequently, in part (b), different valid assignments may have different probabilities of being chosen.

How do I decide which chest in the starting room to open first? Is it random?

Because the keys are assigned randomly, it does not matter how you pick which chest to open first.

Does "picking up the Red Key first" mean "picking up the Red Key before any other keys" or "picking up the Red Key from the first chest you open?"

From the first chest you open. We've edited the Quiz to clarify this.

For part (c), what if a map has more keys than treasure chests?

If there are more keys than chests, then there are no valid assignments of keys to chests, so the probabilities are undefined. To satisfy part (c), your answer would need to be a map with at least one valid assignment--in particular, it would need at least as many chests as keys.

In part (b), is the second key placed after I pick up the first key (i.e. after some chests have already been opened)?

No; the key locations are all randomized before you start exploring the maze. When it says "after picking up the first key," it just means that the second key is placed somewhere that you will be able to get to once you have picked up the first key.

Problem 5

Can players only move to numbers which are integers?

Yes, all positions need to be integers.

Does a pair of positions occur every time either player moves, or only after they have both moved?

Whenever either player moves, that counts as a pair of positions. For example, if Narmada moves to 3 on her first move, Travis moves to 5, Narmada moves to 4, and Travis moves back to n, then all of the positions (1,n), (3,n), (3,5), (4,5), (4,n) have occurred. Narmada is not allowed to move to 1 or 3 on her next move because it would create a repetition.