I have to find the P and N positions for the following combinatorial game:
There are two pots which are initially filled with a and b stones respectively, with a and b greater than or equal to 1. Use the notation (a, b) to represent the number of stones in each pot.
In each turn, a player chooses a pot that has more than 1 stone and empties the other pot. He then divides up the stones from the pot he chose among the two pots, in any way he likes as long as he puts at least one stone in each pot. The terminal state of the game is (1, 1) (i.e., exactly one stone in each pot).
Example 1: Say we begin with (1, 4). Since pot a contains 1, we must chose pot b, and empty pot a. Now, we can divide up the 4 stones between the two pots in any of the following ways: (1, 3); (2, 2)
Note that this is a normal game.
So I need to find the N and P positions for this game.
By using the recursive definition of P and N positions and drawing game trees, I have reached the conclusion that:
P positions are those where a and b are both ODD numbers
N positions are where out of (a,b), one is an odd number and the other is a even number; or out of (a,b), both are even numbers
I need to prove this though. I was going about on doing a proof by induction.
I thought to show that for each case (both odd; both even; one odd and one even) I will show that we end up with the respective P and N positions.
This is my induction hypothesis:
For some (c,d), where c is less than a, and d is less than b, assume that the following is true:
The P positions are those when (c,d) are both odd numbers
The N positions are those when: in (c,d), c is odd number and d is even number, or in (c,d), are both even numbers
I know, it looks terrible. I don't know what other thing to come up with.
What I wanted to ask is:
Is proof by induction the correct strategy?
If yes, then I am confused as to what the induction hypothesis should be.
If no, then what other proof strategy is good?