Ask The Wizard #404

For the benefit of other readers, let me explain the rules of Tsyan Shizi.

1. The game starts with two unequal piles of stones.
2. The players will take turns.
3. Each turn will consist of removing any number of stones from either pile or the same number from both.
4. The player to remove the last stone WINS.

Consider the following table for my strategy.

For a longer table of up to differences of 89, please click the spoiler box below.

Here is my strategy, based on the table above.

1. Note the difference in stones between the two piles.
2. For difference of ten or less, consult the table above on what to play.
3. If both piles have enough stones to play according to the table above, then remove the same number of stones from both piles to achieve the state in the "play" column.
4. If both piles do NOT have enough stones to play according to the table above (for example with 6 and 11), then take stones from one pile to achieve any of the states in the table. For example, with 6 and 11, you would take 1 from the 11 pile to achieve a state of 10,6.
5. The only other possibility is you ARE in one of the states above. Then you are screwed if playing with a skilled player, as he will be able to force you onto another losing positions in the table no matter what you do. If not playing with a skilled player, I recommend taking just one stone from either pile, to give your opponent more opportunity to screw up.

Of course, it depends on the denomination and number of plays. The following table shows those probabilities.

This table was taken from my video poker appendix 2, where I show how often the player gets each total win in a large simulation.

Let's reduce this problem to one lillipad and then add one more at a time, to try to find a pattern.

If there were just one lillipad, then the answer is obviously 1.

If there were two lillipads, then the frog could either jump on the first pad on the way or over it, for a total of 2 sets.

If there were three lillipads, then the first jump could advance the frog either one or two pads. That will put him either 1 or 2 pads way. We have seen there is one way to advance one pad and two ways to advance two. Adding the choice of the first move, there are 1+2 = 3 sets.

If there were four lillipads, then the first jump could advance the frog either one or two pads. That will put him either 2 or 3 pads way. We have seen there is are 2 ways to advance 2 and 3 ways to advance 3. Adding the choice of the first move, there are 2+3 = 5 sets.

If there were five lillipads, then the first jump could advance the frog either one or two pads. That will put him either 3 or 4 pads way. We have seen there is are 3 ways to advance 3 and 5 ways to advance 4. Adding the choice of the first move, there are 3+5 = 8 sets.

This is following the Fibonacci sequence. The following list shows there are 89 ways to land on the 10th pad.

• 1 pad = 1 ways.
• 2 pads = 2 ways.
• 3 pads = 3 ways.
• 4 pads = 5 ways.
• 5 pads = 8 ways.
• 6 pads = 13 ways.
• 7 pads = 21 ways.
• 8 pads = 34 ways.
• 9 pads = 55 ways.
• 10 pads = 89 ways.