Recently, I received a wonderful cookbook.  In an appendix, it shows a table that converts oven temperatures between Celsius and Fahrenheit.  (Side remark: Approximate oven temperatures are actually really simple to convert in your head–just double the number of degrees Celsius to get the number of degrees Fahrenheit.  For oven temperatures, this will be within 10 F of the exact answer.)

The table has a footnote that says “If your oven has a fan, reduce the recipe temperature by 68 F”.  I have a strong hunch that this footnote suffers from a translation error.  How many degrees Fahrenheit should it have said to reduce the temperature by?  (No knowledge of convection ovens required.)

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.

You are given a balance (that is, a weighing machine with two trays) and a positive integer N.  You are then to request a number of weights.  You pick which denominations of weights you want and how many of each you want.  After you receive the weights you requested, you are given a thing whose weight is an integer between 1 and N, inclusive.  Using the balance and the weights you requested, you must now determine the exact weight of the thing.

As a function of N, how few weights can you get by requesting?

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.

The harmonic series–that is, 1/1 + 1/2 + 1/3 + 1/4 + …–diverges.  That is, the sum is not finite.  This is in difference to, for example, a geometric series–like ½⁰ + ½¹ + ½² + ½³ + …–which converges, that is, has a finite sum.

Consider the harmonic series, but drop all terms whose denominator represented in decimal contains a 9.  For example, you’d drop terms like 1/9, 1/19, 1/90, 1/992, 1/529110.  Does the resulting series converge or diverge?

Hint: More generally, you may consider representing the denominator in the base of your choice and dropping terms that contain a certain digit of your choice.
Consider again the harmonic series, but drop a term only if the denominator represented in decimal contains two consecutive 9’s.  For example, you’d drop 1/99, 1/992, 1/299, but not 1/9 or 1/909.  Does this series converge or diverge?

You have 240 barrels of wine, one of which has been poisoned.  After drinking the poisoned wine, one dies within 24 hours.  You have 5 slaves whom you are willing to sacrifice in order to determine which barrel contains the poisoned wine.  How do you achieve this in 48 hours?

A ledge is 1 meter long.  On it are N lemmings.  Each lemming travels along the ledge at a constant speed of 1 meter/minute.  A lemming continues in the same direction until it either falls off the ledge or it collides with another lemming.  If two lemmings collide, they both immediately change their directions.  Initially, the lemmings have arbitrary starting positions and starting directions.  What is the longest time that may elapse before all lemmings have fallen off the ledge?

Hint: Suppose the ledge is not horizontal, but is leaning.  A lemming now travels up the ledge at a speed of 1 meter/minute and travels down the ledge at a speed of 2 meters/minute.  What is the longest time before all lemmings have fallen off?

Two witches each makes a nightly visit to an all-night coffee shop.  Each arrives at a random time between 0:00 and 1:00.  Each one of them stays for exactly 15 minutes.  On any one given night, what is the probability that the witches will meet at the coffee shop?

There are five holes arranged in a line.  A hermit hides in one of them.  Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right.  Once a day, you get to inspect one hole of your choice.  How do you make sure you eventually find the hermit?