Hilbert's Grand Hotel

We talked over dinner about Hilbert's Grand Hotel (follow the link for a good description). The hotel has an infinite number of rooms, all full, and a new guest arrives. To make room for a new guest, for all i the guest in room i is moved to room i+1.

My 12-year-old daughter argued that the hotel is too expensive to build. I postulated that room i+1 costs only half as much as room i, and that the guests shrink as they are moved to higher numbered rooms. She conceded that such a hotel could exist.

My 15-year-old daughter argued that the moving of guests fails. For example, what happens to the guest in room number infinity? I said "there is no room numbered infinity". She responded, "then what number is it?", and the whole family felt that she won.

String of Pearls

Two friends found a necklace (a loop) of pearls. There are some black pearls and some white pearls, all otherwise indistinguishable. They want to cut the necklace into two parts (with two cuts) so that the number of black pearls on each side match, and the number of white pearls match. They cannot cut the pearls themselves, but instead cut the necklace between the pearls. There are an even number of black pearls, and an even number of white pearls. Prove that you can always do it, or else find a case where it cannot be done. After arguing and working on it for a 15 minutes, they came up with an argument. But afterwards Lizzy said she didn't like it much (compared for example to Sunday's freecell problem). This problem comes from one of Charles Leiserson's papers (I don't remember which) on VLSI layout.

Freecell Solitaire: What Are Open Slots Worth?

Today we analysed part of Freecell solitaire. In Freecell there are

• 4 reserve slots which can hold one card, and
• 8 tableau slots which can hold a stack of cards.

A stack is a set of cards of alternating colors, of increasing ordinality. E.g., a red 3 on a black 4 on a red 5 is a stack of 3 cards.

How big a stack can you move, given some open reserve and tableau slots?

• If you have no open reserves, you can move a stack of size 1. (One card only.)
• If you have one open reserve, you can move a stack of 2. (Given a red 3 on a black 4: you can move the red 3 to the open reserve, then move the black 4 to its destination, then move the red 3 onto the black 4.)
• What if you have 2 open reserves? (A stack of 3 can be moved.)
• What if you have r open reserves? (A stack of r+1 can move.)
• What if you have 1 open tableau and 0 open reserves?
• What if you have t open tableaux and r open reserves?

To analyse this, we define a function S(t,r) that says how big a stack can be moved when there are t open tableau and r open reserves. S satisfies this recurrence relation:

• S(0,r) = r+1, and
• S(t,r) = 2S(t-1,r), for t>0.

The first case where t=0 is known. In the second case I can use t-1 open tableaux and r open reserves to move S(t-1, r) cards to one of the free tableaux. Now I have t-1 open tableaux and r open reserves to move the next S(t-1, r) cards in the same stack to its final destination. Then I can move the first S(t-1, r) to form another stack.

Here's a solution to the recurrence for S:

• S(t,r) = 2^t(r+1)

Discussion: Computer scientists see a recurrence like the one shown above, and tend to think it's a reasonable way to define a function. Mathematicians don't like defining a function in terms of itself, because you might get "definitions" that read like

• g(x) = 0, if g(x)=0, and
• g(x) = 1, otherwise.

• f(x) = 0, if f(x)=1, and
• f(x) = 1, otherwise.

The fix to this is to say that a recurrence is equation that is true of the function we are talking about, and ask what functions solve that equation. In the case of S on the nonnegative integers, there is a unique solution. For f there are no solutions, and for g there are many solutions. For S defined on the real numbers, there are many solutions.