100 persons are standing in line, each facing the same way.  Each person is wearing a hat, either red or blue, but the hat color is not known to the person wearing the hat.  In fact, a person knows the hat color only of those persons standing ahead of him in line.

Starting from the back of the line (that is, with the person who can see the hat colors of all of other 99 persons), in order, and ending with the person at the head of the line (that is, with the person who can see the hat color of no one), each person exclaims either “red” or “blue”.  These exclamations can be heard by all.  Once everyone has spoken, a score is calculated, equal to the number of persons whose exclamation accurately describes their own hat color.

What strategy should the 100 persons use in order to get as high a score as possible, regardless of how the hat colors are assigned?  (That is, what strategy achieves the best worst-case score?)

For example, if everyone exclaims “red”, the worst-case score is 0.  If the first 99 persons exclaim the color of the hat of the person at the head of the line and the person at the head of the line then exclaims the color he has heard, the worst-case score is 1.  If every other person exclaims the hat color of the person immediate in front and that person then repeats the color he has just heard, then the worst-case score is 50.  Can you do better?

Hint: Instead of using just red and blue as the possible hat colors and exclamations, use N different colors.

You’re given a regular deck of 52 playing cards.  In the pile you’re given, 13 cards face up and the rest face down.  You are to separate the given cards into two piles, such that the number of face-up cards in each pile is the same.  In separating the cards, you’re allowed to flip cards over.  The catch:  you have to do this in a dark room where you cannot determine whether a card is face up or face down.

Warm-up:  You are given a box of matches and a piece of rope.  The rope burns at the rate of one rope per hour, but it may not burn uniformly.  For example, if you light the rope at one end, it will take exactly 60 minutes before the entire rope has burnt up, but it may be that the first 1/10 of the rope takes 50 minutes to burn and that the remaining 9/10 of the rope takes only 10 minutes to burn.  How can you measure a period of exactly 30 minutes?  You can choose the starting time.  More precisely, given the matches and the rope, you are to say the words “start” and “done” exactly 30 minutes apart.

The actual problem:  Given a box of matches and two such ropes, not necessarily identical, measure a period of 15 minutes.

Boris and Natasha live in different cities in a country with a corrupt postal service.  Every box sent by mail is opened by the postal service, the contents stolen, and the box never delivered. Except: if the box is locked, then the postal service won’t bother trying to open it (since there are so many other boxes whose contents are so much easier to steal) and the box is delivered unharmed.

Boris and Natasha each has a large supply of boxes of different sizes, each capable of being locked by padlocks.  Also, Boris and Natasha each has a large supply of padlocks with matching keys.  The padlocks have unique keys.  Finally, Boris has a ring that he would like to send to Natasha.  How can Boris send the ring to Natasha so that she can wear it (without either of them destroying any locks or boxes)?

Think of a positive integer, call it X.  Shuffle the decimal digits of X, call the resulting number Y.  Subtract the smaller of X,Y from the larger, call the difference D.  D has the following property:  Any non-zero decimal digit of D can be determined from the remaining digits.  That is, if you ask someone to hide any one of the non-zero digits in the decimal representation of D, then you can try to impress the other person by figuring out the hidden digit from the remaining digits.  How is this done?  Why does it work?

Two players are playing a game.  The game board is a circular table.  The players have access to an ample supply of equal-sized circular coins.  The players alternate turns, with each turn adding a single coin to the table.  The coins are not allowed to overlap.  Once a coin is placed on the table, it is not allowed to be moved. The player who has no place to put his next coin loses.  Develop a winning strategy for the player who starts.  (The table is large enough to accommodate at least one coin.)

Find two positive integers that together with 23 are the lengths of a right triangle.

Hint: There’s a simple technique that, given any odd positive integer, allows you to figure out the other two integer sides of a right triangle in your head (or with pen and paper if the numbers get too large).  Find this technique.

For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.

Hint:  Chebyshev proved that the following property (Bertrand’s Postulate) holds:  for any k > 1, there exists a prime number p in the range k < p < 2*k.