Mathcamp 2009 Qualifying Quiz

Instructions

We call it a quiz, but it's really a challenge: a chance for you to show us how you approach new problems and new concepts in mathematics. What matters to us are not only your final results, but your reasoning. Correct answers on their own will count for very little: you have to justify all your assertions and prove to us that your solution is correct. (For some tips on writing proofs, see www.mathcamp.org/proofs.php.) Sometimes it may take a while to find the right way of approaching a problem. Be patient: there is no time limit on this quiz.

The problems start out easier and get harder. (At least we think so — but you may disagree.) None of the problems requires a computer; you are welcome to use one if you’d like, but first read a word of warning at www.mathcamp.org/computers.php.

We don’t expect every applicant to solve every problem: in the past, we have sometimes admitted people who could do only half of them, occasionally even fewer. However, don’t just solve four or five problems and declare yourself done! The more problems you attempt, the better your chances. We strongly recommend that you try all the problems and send us the results of your efforts: partial solutions, conjectures, methods — everything counts.

If you need clarification on a problem, please contact us. You may not consult or get help from anyone else. You can use books or the Web to look up definitions, formulas, or standard techniques, but any information obtained in this way must be clearly referenced in your solution. Please do not try to look for the problems themselves: we want to see how well you can do math, not how well you can Google! Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp.

Good luck and have fun!

Problems

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.