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.

Today our professor presented us with a puzzle of interest called The 'eating apple' problem (I have no idea what is it called formally though). The rules are

  • There are three compartments, containing 3, 5, and 7 apples respectively.
  • Two players, or 'eaters', will eat n apples in turns, until all apples are eaten. (n>0, n not necessarily 1)
  • The last player to empty the compartments will be declared the loser.
  • Each player can eat from at most one compartment at a time.

After trial and error with my friends, I have discovered that the person who starts the game will have an advantage, if not even a total dominance over the other player, but how can I prove this? As a cs student, I'm not a math geek at all, so a little help to where I can start would be appreciated.

share|improve this question
    
Have you tried thinking about what would happen if you had one compartment? Then two? Then maybe one apple in the third compartment etc –  Mark Bennet Apr 10 '12 at 6:12
    
Related: math.stackexchange.com/questions/52130/the-game-of-nim and math.stackexchange.com/questions/33468/a-nim-game-variant. The first is not exact dupe, but can be considered minor variant, I suppose. The second is just related. –  Aryabhata Apr 10 '12 at 6:16

2 Answers 2

up vote 3 down vote accepted

This is the classic game/variant of NIM. The wiki has a good description on the winning strategies.

share|improve this answer

As a general idea with any of these games, you want to look at winning and losing positions. A winning position is one where player A has some move which leads to a losing position for player B. A losing position for player B is one where every move leads to a winning position for player A. As a cs student you will recognise an obvious recursion here. If you can find some property which is preserved for all winning positions then you have an easy way to identify a win. Otherwise you may need to brute force it.

For this game the simplest winning position is no apples in any compartment, which means that the previous player ate the last one and lost. The simplest losing position is one apple, since the only possible move leads to the previous winning position.

The next winning positions are just those where there is some move which puts the game into one of the losing positions. Either have one compartment with more than one apple and eat all but one; or two compartments, where one has exactly one apple and you take everything from the other.

What are the next losing positions? Two apples in each of two compartments, or one apple in each of three compartments.

Repeat this process until you get to the case that you are interested in.

On the way, you will find that some patterns emerge. For example, equal numbers (>1) in two compartments is a losing position because you have three choices.

  1. Eat all apples in one compartment. Opponent takes all but one from the other.
  2. Eat all but one. Opponent eats all apples from the other.
  3. Anything else. Opponent eats the same number as you, leaving two compartments with the same number in each, which is the same scenario you started from.

Once you have played with this strategy, then read up on nim, as others have suggested, since the universal strategy is unlikely to be apparent.

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.