In a finite, undirected, connected graph, an integer variable v(n) is associated with each node n.  One node is distinguished as the anchor.  An operation OP(n) is defined on nodes:

OP(n):
if node n is the anchor, then do nothing,
else set v(n) to the value 1 + min{v(m)}, where m ranges over all neighbors of n that are distinct from n.

An infinite sequence of operations <OP(n),OP(m), …> is executed, the node arguments n, m, … for the operations being chosen arbitrarily and not necessarily fairly.  Show that eventually all v(n) stabilize.  That is, that after some finite prefix of the infinite sequence of operations, no further operation changes v(n) for any node n.

A square table has a coin at each corner.  Design an execution sequence, each of whose steps consists of one of the following operations:

• ONE:  The operation chooses a coin (possibly a different one with each execution of the operation) and flips it.
• SIDE:  The operation chooses a side of the table and flips the two coins along that side.
• DIAG:  The operation chooses a diagonal of the table and flips the two coins along that diagonal.

such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.

N prisoners get together to decide on a strategy.  Then, each prisoner is taken to his own isolated cell.  A prison guard goes to a cell and takes its prisoner to a room where there is a switch.  The switch can either be up or down.  The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.  The prisoner is then taken back to his cell.  The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners.  That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”.  If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.  What strategy should the prisoners use to ensure their eventual freedom?

(Just in case there’s any confusion:  The initial state of the switch is unknown to the prisoners.  The state of the switch is changed only by the prisoners.)

As a warm-up, you may consider the same problem but with a known initial state of the switch.

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.)