2018 Qualifying Quiz

You may also be interested in the printable (PDF) format or the LaTeX source code.

  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.

    image: tetrahedron picture

    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.