Welcome to the 2010 Qualifying Quiz!

You can find the 2010 Quiz below in HTML and PDF formats. For those interested in typing mathematics beautifully, we also offer you the LaTeX source file for the Qualifying Quiz. Please don't let it distract you from solving the problems, though! For more information on LaTeX, take a look at our LaTeX tutorial for The QQ. LaTeX is freely available for Linux, Mac OS X and Windows operating systems, among others.

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 proof tips.) 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 about computers.

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!

2010 Problems

  1. This problem is a variation of the famous Tower of Hanoi problem. If you don't know the original problem and its solution, check out http://mathforum.org/library/drmath/view/55956.html.

    Suppose now that the three pegs are arranged in order --- A, B, and C --- and on a single move you can only move rings between A and B or between B and C. A ring can move from A to C or vice versa only in two moves (and then only provided that there isn't a smaller ring on B).

    1. What is the minimum number of moves required to move a stack of n rings from A to C? Prove your answer.
    2. What is the minimum number of moves required to move a stack of n rings from A to B? Prove your answer.

  2. Consider the following two-player game. Starting with the number 0, players take turns adding to the current sum; on your turn, you can add either 4 or 7. If on your turn you can make the new sum end in two zeros (i.e., if your turn leaves a multiple of 100), you win.

    Assuming best play, is there a winning strategy for either player, or will the game go on indefinitely? If there is a winning strategy, should you move first or second, and how do you play from there?

  3. Suppose r and s are positive integers. Let F be a function from the set of all positive integers {1,2,3,…} to itself with the following properties:

    • F is one-to-one and onto. (If you don't know these terms, look them up online.)
    • For every positive integer n, either F(n) = n + r or F(n) = n − s.

    1. If r = 5 and s = 8, what is F(2010)?
    2. Find, with proof, the smallest positive integer k such that the k-fold composition of F with itself is the identity function; that is, F(F(…F(n))) = n for all n (where there are k copies of F on the left-hand side). The answer will depend on r and s.
  4. For some positive integer n, the numbers 2n and 5n begin with the same 10 digits when written in base 10. What are these digits? You do not need to show that such an n exists, but you do need to prove that, assuming such an n exists, your answer is the only possible one. Extra: Do you have any ideas about how to prove that such an n exists?

  5. Let an be the number of strings of length n that can be formed from the symbols X and O, with the restriction that a string may not consist entirely of multiple copies of one string of shorter length. For example, for n = 4, the string XXOX is allowed, while the strings XXXX and XOXO are not allowed. It is not hard to check that a4 = 12.

    Here is a table showing an and approximate values of the ratio an+1 / an for different values of n.

    n 1 2 3 4 5 6 7 8
    an 2 2 6 12 30 54 126 240
    an+1 / an 1 3 2 2.5 1.8 2.333 1.905 2.1

    The table suggests two conjectures:

    1. For any n > 2, the number an is divisible by 6,
    2. \displaystyle \lim_{n\to\infty} a_{n+1} / a_n = 2

    Prove or disprove each of these conjectures.

  6. For 0 ≤ x ≤ 1, let T(x) = x if x ≤ ½, and T(x) = 1 − x if x ≥ ½. In other words, T(x) is the distance from x to the nearest integer. Let:

    f(x) = \sum_{n=1}^\infty T(x^n).

    Does there exist a value of x (still between 0 and 1) such that f(x) = 2010? Find all such values or show that none exist.

  7. For what values of M and N can an M × N chessboard be covered by an equal number of horizontal and vertical dominoes? (A domino always covers two adjacent squares on the board.)

  8. If we tile the plane with black and white squares in a regular checkerboard pattern, then every square has an equal number (four) of black and white neighbors. (Two squares are considered neighbors if they are not the same but have at least one common point; squares that touch just at a vertex count as neighbors.) But if we try the analogous pattern of cubes in 3-dimensional space, it no longer works this way.

    1. How many neighbors of each color does a white cube have?
    2. Find a coloring pattern for a grid of cubes in 3-dimensional space so that every cube, whether black or white, has an equal number of black and white neighbors.
    3. What happens in n-dimensional space for n>3? Is it still possible to find a color pattern for a grid of hypercubes, so that every hypercube, whether black or white, has an equal number of black and white neighbors?

Problems 2, 3, 5, 6, and 8 copyright Mark Krusemeyer.