Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Puzzles where both players play optimally

  1. Nov 7, 2012 #1
    Puzzles like the following(they are actually programming questions) :-
    How do you solve such puzzles?
    Since they say that both play optimally does that mean given the conditions in the game(here lets say number N is given) we already know who will be the winner?
  2. jcsd
  3. Dec 18, 2012 #2
    Playing optimally means that both players will have insight into all possible next moves and will play in such a way to maximize their chance of winning without making a mistake. However, if all moves lead to the other player winning, then this player still has to play, and any move would be equivalent.

    In the first puzzle, a player loses when their number is 1. This means that the player at 2 can force their opponent to lose by subtracting 1, and a player at 3 will lose since they can only subtract 1. Similarly, a player at 4 can win by subtracting 1, and a player at 5 will lose.

    Note that all odd numbers only have odd factors, so a player at an odd number can only get to an even number since he or she can only subtract an odd number from odd. A player at an even number can then subtract 1 to force the opponent to get to an odd number.

    Thus if the game begins on an even number, Alice wins. If the game begins on an odd number, Bob wins.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook