0

Consider the following two-player game: starting with the single number 123, two players alternately subtract numbers from the set {1; 2; 3} from this value. The player who first gets this sum to 0 wins. If you want to win this game, should you go first or second? Prove that your chosen player has a winning strategy.

I struggle to solve this. Could someone help me with this?

Joker
  • 49

3 Answers3

1

The first step should probably be to figure out what you want to prove; then you can try to prove it by induction. For the first step, forget about starting with 123 and think systematically about what happens when the game starts with very small numbers. If it starts with 1 or 2 or 3, then the first player wins immediately by subtracting 1 or 2 or 3, respectively. But if it starts with 4, then the first player can't win instantly and, in fact, must leave a remainder of 3 (if he subtracts 1) or 2 (if he subtracts 2) or 1 (if he subtracts 3), so the other player will win on the next move. Now think about what happens if the game starts with 5, or with 6, etc. By the time you get up to about 10 (if not sooner), you'll see a pattern: The first player wins if and only if the starting number has [a fairly simple property that you'll detect].

Then try to prove, by (strong) induction that the pattern you found continues to hold for arbitrarily large numbers. Finally, once your pattern has become a theorem, apply it to the starting number 123.

Andreas Blass
  • 71,833
  • It seems I was too optimistic in saying "you'll see a pattern." Two other answers have been given since then, and only one of the two (by WW1) got the pattern right. – Andreas Blass Aug 14 '18 at 17:04
1

You can play in such a way that the sum of your opponent's move and your next move is equal to 4.

So if you go first and leave your opponent a multiple of 4, you are certain to win.

Whenever You start with a multiple of 4, go second and you will win

If you start with $4n+a$ with $a \in \{1,2,3\}$ then go first and subtract $a$ on your first move

WW1
  • 10,497
0

Go first. Whenever it is your turn and the number to subtract from is more than $4$, play so as to leave $1$ more than a multiple of $3.$ Eventually, the number to subtract from is $4, $ on your opponent's turn. Whatever value $x$ he subtracts, you subtract $4-x$ on your next move and win.

For a formal proof, let $S(n)$ be the statement that if the remainder is $n$ and it is your opponent's turn then you have a winning strategy. First show that $S(4)$ is true. Show that $S(n)\implies S(n+3)$ for any $n>0.$ Then by induction you have $S(1+3m)$ for all $m>0.$

DanielWainfleet
  • 57,985