2003 Qualifying Quiz

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

1.
Every day at Mathcamp, Frank and Lilian competed to see who could solve more problems in problem-solving class. Each day at least one of them was able to do more than half the problems. Of the days when Frank solved more than half the problems, he won twice as often as he lost. Of the days when Lilian solved more than half the problems, she won five times as often as she lost. There were 25 class days total. On how many days did Lilian win? (You can assume there were no ties.)

2.
Fifteen plates are placed evenly around a circular table, with name cards for fifteen guests. The guests fail to notice the cards until after they've sat down, at which point they discover that no one is in the correct seat. Show that the table can be rotated so that at least two of the guests are simultaneously correctly seated.

3.
An infinite sequence of "1"s and "2"s is determined by the following properties:
(i)
The sequence is built up by stringing together pieces of the form "12" and "112".
(ii)
If we replace each "12" piece with a "1" and each "112" piece with a "2" then we get back the same sequence.

(a)
Write down the first 30 digits in the sequence.

(b)
Without explicitly writing down any more digits, can you predict what the 409th digit in the sequence will be?

4.
Ten pirates, ranging in rank from captain (#1) to cabin boy (#10) have dug up a chest of gold coins. They start by splitting the treasure evenly, but the captain is not satisfied. He orders a vote to be taken on whether the cabin boy should be allowed to keep his part of the treasure. If more than half the pirates vote "no", the cabin boy's portion will be divided among the rest of the crew. Next, #9's portion will be put to a vote in the same way, then #8's, etc. In each round, the pirate whose fate is being decided gets a vote, but pirates who have already been dispossessed do not vote in successive rounds, and do not get a share of the redistributed treasure. Once one pirate is allowed to keep his share, the process stops.

(a)
Assuming each pirate acts totally rationally according to these rules, how many pirates will end up with a share of the gold?

(b)
Suppose there are 100 pirates to start with. How many will get a share of the gold?

5.
When Mark climbs a staircase, he ascends either 1, 2, or 3 stairsteps with each step of the foot, but in no particular pattern from one foot to the next. How many ways can Mark climb a staircase of 10 steps? (Note that he must finish on the top step.) Suppose that a spill has occurred on the 6th step and Mark wants to avoid it. How many ways can he climb the staircase without stepping on the 6th step?

6.
Three non-overlapping circles are drawn on the ground. Inside one of the circles are n pebbles, and there are no pebbles in the other two circles. Your goal is to transfer all of the pebbles from one circle to another, subject to the following rule: you may move exactly 2k pebbles from one circle (call it circle A) to another (call it circle B) provided that circle B begins with fewer than 2k pebbles, and that after the move circle A ends up with fewer than 2k pebbles. Further, you wish to complete this task in as few moves as possible. For what values of n less than or equal to 100 would the most moves be required?

7.
There are several cities in a certain kingdom. An obnoxious citizen is exiled from city A to city B, which is the furthest city in the kingdom from A. After a while, he is exiled from city B to the furthest city from it, which happens to be different from A. Prove that, if his exiles continue in the same way, he will never return to city A. You may assume that the distances between cities are all different.

8.
A king decides to build a large square plaza in front of his palace. He will position three of his trusted sentries at optimal points on the plaza, so that, in case of trouble, no point on the plaza is more than 50 feet from the nearest sentry. How large can the king make the plaza, and how should he position the sentries? (Kings are big on grandeur and mistrustful of mathematicians, so you need to explain carefully why your proposed arrangement of sentries is optimal. How do you know that there isn't an alternative arrangement that would enable the king to make his plaza even larger?)

9.
The repeat of a positive integer is the number obtained by writing the original number twice, so for example, the repeat of 364 is 364364. (All numbers are written in decimal with no leading zeros.) Is there a number whose repeat is a perfect square?

10.

(a)
Begin with a string of 10 A's, B's, and C's. For example: 
   A B C C B A B C B A

Underneath, form a new row, of length one letter shorter, as follows: between two letters that are different, write the third letter, and between two letters that are the same, write that same letter again. Continue this process, until you have only one letter in the new row. For example: 

   A B C C B A B C B A
    C A C A C C A A C
     B B B B C B A B
      B B B A A C C
       B B C A B C
        B A B C A
         C C A B
          C B C
           A A
            A

Prove that, no matter what string you start with, the letters at the corners of the resulting triangle are either all the same or all different.

(b)
To what other numbers could you change the 10 in part (a), and still have the assertion be true?

(Bonus)
In problem #3, let An denote the number of "1"s amongst the first n characters, and let Bn denote the number of "2"s amongst the first n characters, so that An + Bn = n. What happens to the ratio An/Bn as n grows large?