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

*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?

*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*) = 2*S(t-*1,*r*), for*t>*0.

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

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

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

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

## No comments:

## Post a Comment