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