RSS Feed
Precedenta
Următoarea

Problema 325

19 Februarie 2011

Jocul pietrei II


Vom defini un joc care se implică 2 jucători și 2 gramezi de pietre. Cand îi vine rândul, un jucător îndepărtează un anumit număr de pietre din grămada mai mare. Numărul de pietre care le îndepărtează trebuie să fie un multiplu pozitiv al numărului de pietre din grămada mai mică.

De exemplu, perechea ordonată (6, 14) descrie o configurație cu 6 pietre în grămada mică și 14 pietre în cea mare; în acest caz, primul jucător poate îndepărta 6 sau 12 pietre din grămada mare.

Jucătorul care ia toate pietrele dintr-o grămada câștigă jocul.

O configurație câștigătoare e una în care primul jucător poate forța un câștig. De exemplu, (1,5), (2,6) și (3,12) sunt configurații câștigătoare pentru că primul jucător poate, la prima mutare, să îndepărteze toate pietrele din grămada mică.

O configurație pierzătoare e una în care al doilea jucător poate forța un câștig, indiferent de mutarea primului jucător. De exemplu, (2,3) și (3,4) sunt configurații pierzătoare: orice mutare legală rezultă într-o configurație câștigătoare pentru al doilea jucător.

Fie S(N) suma (xi+yi) pentru toate configurațiile pierzătoare (xi,yi), 0 < xi < yiN. Se poate verifica că S(10) = 211 și S(104) = 230312207313.

Găsește S(1016) mod 710.


>> Vezi problema originală <<