Let's play the "Euclid Game". Let me kindly explain the game for you.
We start with two natural numbers. The first player subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative.The second player does the same with the two resulting numbers, and they go on like this alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0 and thereby wins.Now, let us play this game. I'm the one who goes first! and I'm choosing the numbers too.
The two numbers are:
Can you guess who's going to win? If you think I'll win, press the Computer button.If you think you'll win, press the Human button (Of course, under the assumption that both you and I are trying our best to win).
Stuck? Try to come up with an algorithm to determine the winner. As a matter of fact, this game was motivated by this problem from a programming competition :) If you cannot figure it out, I kindly prepared a tutorial for you here. But think before you click the link!