Consider a game that you play against an opponent.  In front of you are an even number of coins of possibly different denominations.  The coins are arranged in a line.  You and your opponent take turns selecting coins.  Each player takes one coin per turn and must take it from an end of the line, that is, the current leftmost coin or the current rightmost coin.  When all coins have been removed, add the value of the coins collected by each player.  It is possible that you and your opponent end up with the same value (for example, if all coins have the same denomination).  Develop a strategy where you take the first turn and where your final value is at least that of your opponent (that is, don’t let your opponent end up with coins worth more than your coins).

A spy is located on a one-dimensional line.  At time 0, the spy is at location A.  With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left).  A and B are fixed integers, but they are unknown to you.  You are to catch the spy.  The means by which you can attempt to do that is:  at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location.  That is, you will ask a question like “Is the spy currently at location 27?” and you will get a yes/no answer.  Devise an algorithm that will eventually find the spy.

Consider the following array operations.  Init(N,d) initializes an array of N elements so that each element has value d.  Once Init has been called, the following two operations can be applied:  For any i such that 0 <= i < N, Get(i) returns the array element at position i and Set(i,v) sets the array element at position i to the value v.

Given any amount of memory you want, implement the three operations so that each operation has an O(1) time complexity.

100 prisoners agree on a strategy before playing the following game:  One at a time (in some unspecified order), each of the prisoners is taken to a courtyard where there is a line of 100 boxes.  The prisoner gets to make choices to open 50 of the boxes.  When a box is opened, it reveals the name of a prisoner (the prisoners have distinct names).  The names written in the boxes are in 1-to-1 correspondence with the prisoners; that is, each name is found in exactly one box.  If after opening 50 boxes, the prisoner has not found his own name, the game is over and all the prisoners lose.  But if the prisoner does find the box that contains his name among the 50 boxes he opens, then the prisoner is taken to the other side of the courtyard where he cannot communicate with the others, the boxes are once again closed, and the next prisoner is brought out into the courtyard.  If all prisoners make it to the other side of the courtyard, they win.

One possible strategy is for each prisoner to randomly select 50 boxes and open them.  This gives the prisoners 1 chance out of 2¹⁰⁰ to win–a slim chance, indeed.  But the prisoners can do better, using a strategy that for a random configuration of the boxes will give them a larger chance of winning.  How good a strategy can you develop?

A park contains paths that intersect at various places.  The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each other.  The one exception is an intersection where there is a restaurant.  The restaurant is reachable from everywhere in the park.  Your task is to find your way to the restaurant.

The park has strict littering regulations, so you are not allowed to modify the paths or intersections (for example, you are not allowed to leave a note an intersection saying you have been there).  However, you are allowed to do some bookkeeping on a pad of paper that you bring with you at all times (in the computer-science parlance, you are allowed some state).  How can you find the restaurant?

You may assume that once you enter an intersection, you can continue to the left, continue to the right, or return to where you just came from.

Given is a (possibly enormous) rectangular chocolate bar, divided into small squares in the usual way. The chocolate holds a high quality standard, except for the square in the lower left-hand corner, which is poisonous. Two players take turns eating from the chocolate in the following manner: The player whose turn it is points to any one of the remaining squares, and then eats the selected square and all squares positioned above the selected square, to the right of the selected square, or both above and to the right of the selected square. Note, although the board starts off rectangular, it may take on non-rectangular shapes during game play. The object of the game is to avoid the poisonous square. Assuming the initial chocolate bar is larger than 1×1, prove that the player who starts has a winning strategy.

Hint: To my knowledge, no efficient strategy for winning the game is known. That is, to decide on the best next move, a player may need to consider all possible continuations of the game. Thus, you probably want to find a non-constructive proof. That is, to prove that the player who starts has a winning strategy, prove just the existence of such a strategy; in particular, steer away from proofs that would construct a winning strategy for the initial player.