PDA

View Full Version : Euclid's game.

InvariantLoop
01-31-2005, 03:53 PM
is it true that if you make the 1st move on this game you always win?

pianorain
01-31-2005, 04:03 PM
No. Consider 8 and 2.

InvariantLoop
01-31-2005, 04:12 PM
im confused lol im playing the game and trying to figure out a pattern but theres always something that breaks the pattern. how come the game depends on the orignal two numbers and not who makes the first move?

edit: you can play the game here http://www.cut-the-knot.org/blue/EuclidAlg.shtml

InvariantLoop
01-31-2005, 04:24 PM
i think i figured out the pattern. tell me if this is true.

if in the original 2 numbers, the bigger number is odd, whoever makes the 1st move wins!.

if in the original 2 numbers, the bigger number is even, whoever makes the 2nd move wins!

XSquared
01-31-2005, 05:13 PM
The way to figure out who goes first is by calculating n/gcd(n,m) where n and m are the two numbers, n>m. If n/gcd(n,m) is odd, the 1st player will win. If it is even, then the 2nd player will win.