Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Are you following T. Ferguson's 'Game Theory' lecture notes? –  Ilya Sep 29 '11 at 9:52
    
@Gortaur: nopes, this is for a CS discreet Math course. –  user952949 Sep 29 '11 at 10:17

2 Answers 2

Induction isn’t the best idea. Use the fact that a position $p$ is a $P$-position if and only if every move from $p$ leaves an $N$-position, and $p$ is an $N$-position if and only if at least one move from $p$ leaves a $P$-position.

  1. Is it true that if $a$ and $b$ are both odd, every move from $(a,b)$ leaves a position in which at least one of $a$ and $b$ is even?
  2. Is it true that if at least one of $a$ and $b$ is even, you can always find a move from $(a,b)$ to some position $(c,d)$ in which $c$ and $d$ are both odd?

If you can prove that both answers are yes, you’ve shown that you’ve correctly identified the $P$- and $N$-positions. (This shouldn’t be too hard.)

share|improve this answer
    
Thanks a lot. I got rid of the induction and used this to prove it. –  user952949 Sep 29 '11 at 14:31

You don't need proof by induction. All you need to show is that:

  1. all moves from a P position result in an N position;
  2. every N position has a move that leads to a P position.

Given your characterisation of P positions as those containing two odd numbers, these are easy to show.

(For completeness, you should also point out that the game can't go on for ever, because each move decreases the total number of stones.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.