2009 Qualifying Quiz

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

1. A group of Mathcampers went on a 3.5-hour hike on Mt. Rainier. In any consecutive one-hour period during their hike, they covered exactly 2 miles. Does it follow that they hiked exactly 7 miles total? If not, what are the minimum and maximum distances they could have walked? Prove your answer.

2. Consider the following coloring problem:

  1. You wish to color each of the integers 0, 1, 2, ... , n red or blue, in such a way that
    • both colors are used, and
    • integers that differ by 7 or 11 have the same color.
    Can you do this for all n? If not, what is the largest value of n for which it is possible? Prove your answer.
  2. How does the answer in (a) change if we replace the numbers 7 and 11 with arbitrary integers m and k? If you can't figure out the solution for the most general case, try it for some special cases - e.g., for a fixed value of k or for some specific relationship between m and k. Include your most interesting/general proofs in your solution.

3. Let S be a set of numbers. We'll call S autonomous if the number of elements in S is itself an element of S. For example, the set {2, 5} is autonomous, as is the set {2, 3, 7}, but the set {3, 4} is not. Find, with proof, the number of autonomous subsets of {1, 2, 3, ... , n}.

4. Suppose you start with the number 1 and go through a series of steps, where at each step you add a (positive integer) divisor of your current number to the number itself, to get a new number. For instance, the first step is forced: you have to take 1 + 1, so your new number is 2. Now you have two choices; the next number could be 2 + 1 = 3 or 2 + 2 = 4. If you choose 4, the next step after that can take you to 5, 6, or 8.

  1. Show that if N is less than or equal to 2n+1, then you can always reach N using 2n steps or fewer.
  2. Show that if N is larger than 2n and you can reach N in n+1 steps, then N is a sum of two powers of two.

5. Three real numbers are chosen at random between 0 and 1. What is the probability that they form the side lengths of a triangle? Prove your answer.

6. Nathan and Abi are playing a game. Abi always goes first. The players take turns changing a positive integer to a smaller one and then passing the smaller number back to their opponent. On each move, a player may either subtract one from the integer or halve it, rounding down if necessary. Thus, from 28 the legal moves are to 27 or to 14; from 27, the legal moves are to 26 or to 13. The game ends when the integer reaches 0. The player who makes the last move wins. For example, if the starting integer is 15, Abi might move to 7, Nathan to 6, Abi to 3, Nathan to 2, Abi to 1, and now Nathan moves to 0 and wins. (However, in this sample game Abi could have played better!)

  1. Assuming both Nathan and Abi play according to the best possible strategy, who will win if the starting integer is 1000? 2000? Prove your answer.
  2. As you might expect, for some starting integers Abi will win and for others Nathan will win. If we pick a starting integer at random from all the integers from 1 to n inclusive, we can consider the probability of Nathan winning. This probability will fluctuate as n increases, but what is its limit as n tends to infinity? Prove your answer.

7. Consider the sequence of positive real numbers:

         4, 1/3, 4/3, 4/9, 16/27, 64/243, . . . ,

in which each term (after the first two) is the product of the two previous terms. Note that for this particular sequence, the first and third terms are greater than one while the second and fourth terms are less than one. However, after that the "alternating" pattern fails: the fifth and all subsequent terms are less than one. Do there exist sequences of positive real numbers in which each term is the product of the two previous ones and for which all odd-numbered terms are greater than one, while all even numbered terms are less than one? If so, find, with proof, all such sequences. If not, prove that no such sequences exist.

8. On the x, y coordinate plane, there is a finite set of line segments. Each line segment lies completely in the square bounded by (0, 0), (0, 1), (1, 0), and (1, 1), and the sum of the lengths of all the line segments is 18. Prove that there exists a straight line in the plane that crosses at least 10 of the segments.

Problems 6 and 7 copyright Mark Krusemeyer.