2011 Qualifying Quiz

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

  1. A betting company offers the possibility to bet on any of the n contestants in a race, with odds a1,...,an, respectively. This means that if you bet X dollars on contestant j (where X is any positive real number), then:

    • If contestant j loses, you lose your X dollars.
    • If contestant j wins, you get your X dollars back, together with a profit of aj X dollars.

    If the company does not choose the odds wisely, it may be possible to bet on all of the contestants in a manner that guarantees a profit no matter what. For instance, if there are 3 contestants with odds 2, 2, and 10, you could bet $1 on each of the first two and $0.50 on the the third one, guaranteeing a profit no matter who wins the race.

    1. What relation do the real numbers a1,...,an need to satisfy so that it is impossible to guarantee a profit in this way?
    2. What is the largest profit that you can guarantee on a total bet of $1 if the relation is NOT satisfied?

  2. The function f is defined on the positive integers by the formulas

    f(1) = 1,
    f(2n) = 2f(n)+2n,
    nf(2n+1) = (2n+1)f(n)
    for all n ≥ 1.

    1. Prove that f(n) is always an integer.
    2. For what values of n does the equality f(n) = n hold? (Be sure to prove that no other value works.)

  3. (Proposed by Michael Wu, a student at Mathcamp 2009 & 2010.) There are n children equally spaced around a merry-go-round with n seats, waiting to get on. The children climb onto the merry-go-round one by one (but not necessarily going in order around the circle), always using the seat in front of them and only taking a seat if it is empty. After one child climbs on and takes a seat, the merry-go-round rotates 360/n degrees counterclockwise so that each remaining child is again lined up with a seat. For what values of n is it possible for the children to climb on, in some order, so that everyone gets a seat? (Do remember to prove both that it's possible for the values you claim and that it's impossible for all other values.)

  4. A country has n airports served by k airlines. Not every pair of airports is connected by a direct flight, but if you don't mind stopovers, you can get from any airport to any other. Also, if a direct flight between a pair of cities exists, you can travel on it in either direction.

    1. To connect n airports, you need to have at least n-1 direct flights. (You may assume this without proof.) Unfortunately, airlines in this country often go bankrupt. The airlines are required to coordinate their routes so that if any one of the airlines goes bankrupt, a traveler can still get from any airport to any other. What is the smallest number of direct flights that could be offered by all the airlines together? (Note: whenever you are asked to find the smallest number with a certain property, you need to prove both that your number has the required property and that no smaller number works.)
    2. Suppose n=7, k=5, and you want to be able to get from any airport to any other even if any two airlines go bankrupt. What is the smallest number of direct flights needed in this scenario?

  5. Bianca and Yuval are playing a game. Yuval thinks of an integer greater than or equal to 1000, but does not reveal it to Bianca. Then Bianca names an integer greater than 1. If Yuval's number is divisible by Bianca's, Bianca wins. Otherwise, Yuval subtracts Bianca's number from his own; the resulting difference is his new number. The game continues, with Bianca naming a different integer each time (no repeats allowed!) and Yuval subtracting each integer she names, until either Yuval's number is divisible by Bianca's (in which case Bianca wins) or Yuval's number becomes negative (in which case Yuval wins).

    1. Obviously, Yuval does not have a winning strategy in this game. (Whatever number he picks, Bianca might get lucky.) Does Bianca have one?
    2. Suppose we replace the number 1000 in the problem by a different positive integer N. For which values of N, if any, does Bianca have a winning strategy?

  6. Three numbers are arranged around a circle; at time t=0, the numbers are 0, 1, 2, reading counterclockwise. Thereafter, the numbers are adjusted each unit of time, as follows: If the two neighbors of a number m are equal, then that number m will stay the same for the next unit of time. If the counterclockwise neighbor of a number m is less than its clockwise neighbor, then the number m will be raised by 1. If the counterclockwise neighbor of a number m is greater than its clockwise neighbor, then the number m will be reduced by 1. The first few steps of this process yield the following:

    t=0 0, 1, 2
    t=1 1, 0, 3
    t=2 2, -1, 2
    t=3 3, -1, 1
    t=4 4, 0, 0
    t=5 4, 1, -1

    Including t=0, what is the 2011th time that at least one of the three numbers is zero?

  7. (Proposed by Josh Frisch, a student at Mathcamp 2010.) Consider the interval (0,1], which is the set of real numbers x with 0 < x ≤ 1. A subset S of the interval (0,1] is called evil if, for each positive integer n:

    • Its reciprocal 1/n is in S.
    • If X is in S then so is the average of X and 1/n.

    Must an evil set contain every rational number in the interval (0,1]?

  8. There are N cyclists riding counterclockwise around a circular track, each one at a different constant speed. The track is very narrow: there is only one point on it where passing is possible (but at this point, the track is wide enough that any number of bicycles can pass there simultaneously). Somehow the cyclists have arranged it so that they can keep going as long as they want, always passing each other at exactly this point.

    1. (Warm-up) For N=2, what condition must the speeds of the two cyclists satisfy?
    2. For what values of N is this situation possible?