Ejoc

Jocul se aseamana foarte tare cu algoritmul lui Euclid prin scaderi. Stim ca daca avem doua numere A si B si tot scadem din cel mai mare pe cel mai mic, pana cand numerele devin egale, numerele la sfarsit o sa fie egale cu cmmdc(A, B) (cel mai mare divizor comun). Aici cu siguranta se va ajunge la un moment dat sa se obtina cmmdc(A, B), si apoi acest cmmdc(A, B) va putea fi scazut in mod repetat din A sau din B. Cum jocul se termina cand nu se mai poate efectua nici o mutare se observa ca la sfarsit se vor obtine toti multiplii lui cmmdc(A, B) pana in A sau in B. Rezulta ca numarul de mutari nu conteaza de mutarile jucatorilor ci doar de A si B, si acesta este max(A, B) / cmmdc(A, B) - 2 (e un caz particular cand A = B dar acesta este usor de rezolvat). Castigatorul este deci determinat doar de paritatea numarului de mutari posibile.