The 2023 Quiz Problems

Don't forget to start with the instructions. (In particular, a reminder: your solutions must be entirely your own work, and you may not consult with others. Do not ever post these problems in online forums, or ask others how to solve them.) Good luck and have fun!

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

  1. 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.)
  2. 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.
    image: rule for bouncing
    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.
  3. 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.
  4. 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.
    image: the maze
    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.
      4. (To generalize the method from (b), I place the keys in random order, and place the kth key in an empty treasure chest you can get to if you have the first k-1 keys. If all the treasure chests you can get to are full when I try to place the kth key, I take back all the keys placed and start over, once again randomly choosing an order for the keys.)
  5. 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).
  6. 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.