Soluţii corecte: Szabo Zoltan, Aurel Ionescu şi Claudiu Dragan (parţial)

Szabo Zoltan:

Cele două numere de obiecte din grămezi le vom numi configuraţii şi le vom nota ca o pereche de numere naturale (a,b). Orice configuraţie poate fi câştigătoare sau necâştigătoare, niciodată ambele deodată.

Observaţiile referitoare la configuraţiile necâşţigătoare le notăm cu n1), n2)… în timp ce observaţiile referitoare la configuraţiile câştigătoare le notăm cu c1), c2), …

În acest sens, prin metoda paşilor mărunţi avem următoarele observaţii c sau n, în funcţie că e vorba de configuraţii câştigătoare sau necâştigătoare:

c₀) Observăm că toate configuraţiile (0,k) (k,0) şi (k,k) sunt câştigătoare.

Dintre celelalte configuraţii va fi necâştigătoare aceea care prin orice mutare va aduce grămezile într-o configuraţie câştigătoare deja cunoscută (acceptată la un pas anterior). 

n₁) Astfel configuraţiile (1,2) şi (2,1) sunt necâştigătoare, pentru că orice mutare asupra lor va rezulta (0,2), (0,1), (1,1) sau (1,0) toate fiind configuraţii câştigătoare. 

c₁) Orice configuraţie diferită de cele descrise mai sus, care va conţine numerele 1 sau 2 sau are diferenţa 1 va fi câştigătoare, pentru că se va putea reduce la una din configuraţiile necâştigătoare (1,2) respectiv (2,1).

n₂) Configuraţia (3,5) nu s-a pomenit la paşii anteriori. Are diferenţa 2 şi este necâştigătoare pentru că orice mutare posibilă o va transforma într-o configuraţie câştigătoare: (2,5) (1,5) (0,5) (2,4) (1,3) (0,3) (3,4) (3,3) (3,2) (3,1) (3,0)

c₂) Orice configuraţie diferită de cele descrise mai sus, care va conţine numerele 3 sau 5 sau are diferenţa 2 va fi câştigătoare, pentru că se va putea reduce la una din configuraţiile necâştigătoare (3,5) respectiv (5,3)

Continuând raţionamentul observăm:

    1. Toate configuraţiile sunt simetrice. Adică orice pereche de configuraţii (a,b) şi (b,a) sunt în acelaşi timp ambele câştigătoare, sau ambele necâştigătoare.

    2. Nu pot exista două configuraţii (a,b), (c,d) ambele necâştigătoare cu a,b,c,d valori distincte şi diferenţă egală. Într-adevăr, dacă presupunem că ambele configuraţii sunt necâştigătoare cu b-a=d-c şi b<d. Atunci configuraţia (c,d) este câştigătoare pentru că scăzând câte d-b din ambele grămezi, iar diferenţa celor două grămezi este egală în cele două configuraţii. Astfel configuraţia (c,d) se va transforma în configuraţia necâştigătoare (a,b), deci configuraţia (c,d) este câştigătoare, ceea ce este contradicţie.

   3. Conform observaţiei 2. toate diferenţele 1,2,3, ... trebuie să apară câte o singură dată, perechea (x,y) trebuie să aibă valori minime posibile. În toate configuraţiile necâştigătoare, toate numerele naturale vor fi distincte două câte două.

Pentru generarea configuraţiilor necâştigătoare folosim următorul algoritm al cărui corectitudine se poate demonstra cu metoda inducţiei matematice complete:

Pasul 1. Configuraţia (1,2) este necâştigătoare cu diferenţa 1.

Pasul 2. Căutăm cel mai mic număr natural nefolosit a2 şi pentru diferenţa 2 avem perechea (a2,a2+2). Obţinem perechea (3,5).

Pasul 3. Căutăm cel mai mic număr natural nefolosit a3 şi pentru diferenţa 3 avem perechea (a3,a3+3). Obţinem perechea (4,7).

...

Pasul k. Căutăm cel mai mic număr natural nefolosit ak şi pentru diferenţa k avem perechea (ak,ak+k). Matematic se poate demonstra că nici numărul ak+k nu este printr-o altă configuraţie anterioară.

Prin metoda de mai sus am descris complet modul de generare al configuraţiilor necâştigătoare. Nu am găsit o formulă fixă între valorile configuraţiilor şi numărul lor de ordine de aceea voi enumera configuraţiile necâştigătoare cu primul termen <=100.