Soluţii corecte: Zoltan Szabo,  Aurel Ionescu,  Camelia Muşetescu,  Ştefan Gaţachiu. Soluţie parţială:  Cristian Balanoiu

1. Ştefan Gaţachiu:

Pe site-ul http://www.infoarena.ro/teoria-jocurilor/jocul-nim este demonstrată o teoremă care precizează condiția ca o anumită configurație a pieselor în grămezi să fie pierzătoare, și anume ca suma XOR a reprezentărilor binare ale numărului de piese din grămezi să fie 0.

De aici rezultă că o configurație este câștigătoare dacă această sumă este diferită de 0. Mai mult, dintr-o configurație pierzătoare jucătorul aflat la mutare nu poate muta astfel încât următoarea configurație să fie tot pierzătoare (adică suma XOR să fie 0, ar trebui să ia 0 piese, ceea ce nu se poate).

1) Avem 310=(011)2, 510=(101)2, 710=(111)2

(011)2 XOR  (101)2 XOR (111)2=(001)2=110

Deci trebuie luată o piesă. Cum toate cele 3 grămezi au mai mult de o piesă, aceasta poate fi luată din oricare din cele 3 grămezi.

După mutarea celui de al doilea jucător, primul jucător calculează din nou suma XOR și ia un număr de piese egal cu numărul obținut din sumă, reprezentat în baza 10 dintr-o grămadă disponibilă, ș.a.m.d.

2) 1110=(001011)2

2310=(010111)2

5710=(111001)2

6110=(111101)2

Suma XOR a celor 4 numere este (011000)2=2410.

Deci primul jucător trebuie să ia 24 de piese din grămada de 57 sau din grămada de 61 de piese.

Aurel Ionescu si Camelia Muşetescu au dat rezolvari similare.

 

2. Zoltan Szabo:

Scopul jucătorului este să îl aducă pe adversar în configurație pierzătoare.

Cea mai banală configurație pierzătoare este formată din două grămezi identice (n1,n1). Oricîte piese ar extrage primul jucător, al doilea îl va copia extrăgând același număr de piese din cealaltă grămadă, și astfel se va ajunge la o altă configurație (n2,n2), care se va rezolva la fel, astfel grămezile vor fi formate pe rând dintr-un număr de piese: n1>n2>n3>...>nk=0. La pasul k grămeyile se vor goli, și jucătorul a dilea câștigă.

O altă configurație pierzătoare este (1,2,3). Din orice grămadă extrage primul jucătorul, răspunsul celuilat jucător va fi o mutare care crează configurația (2,2) sau (1,1) și a treia grămadă vidă.

a.

Configurația (3,5,7) are trei variante pentru mutarea câștigătoare: primul jucător extrage o piesă din oricare grămadă.

 Configutațiile (2,5,7), (3,4,7) (3,5,6) toate sunt câștigătoare. 

Voi dezvolta mutările jocului pentru configurația (2,5,7). 

Variantele de mutare pentru jucătorul 2 și răspunsurile aferente din partea jucătorului 1:

(2,5,6) va fi urmat de  (2,4,6)    (configurație pierzătoare - vezi mai jos)

(2,5,5) va fi urmat de  (0,5,5)     (pierde jucătorul 2)

(2,5,4) va fi urmat de (1,5,4)    (configurație pierzătoare - vezi mai jos)

(2,5,3) va fi urmat de (2,1,3)     (pierde jucătorul 2)

(2,5,2) va fi urmat de (2,0,2)     (pierde jucătorul 2)

(2,5,1) va fi urmat de (2,3,1)     (pierde jucătorul 2)

(2,5,0) va fi urmat de (2,2,0)     (pierde jucătorul 2)

(2,4,7) va fi urmat de (2,4,6)    (configutație pierzătoare - vezi mai jos)

(2,3,7) va fi urmat de (2,3,1)     (pierde jucătorul 2)

(2,2,7) va fi urmat de (2,2,0)     (pierde jucătorul 2)

(2,1,7) va fi urmat de (2,1,3)     (pierde jucătorul 2)

(2,0,7) va fi urmat de (2,0,2)     (pierde jucătorul 2)

(1,5,7) va fi urmat de (1,5,4)    (configutație pierzătoare - vezi mai jos)

(0,5,7) va fi urmat de (0,5,5)     (pierde jucătorul 2)

Trebuie să demonstrăm, că cele două configurații (1,5,4), respectiv (2,4,6) sunt pierzătoare.

Pentru configurația (1,5,4), jocul se va continua astfel:

(1,5,3) va fi urmat de (1,2,3)     (pierde jucătorul 2)

(1,5,2) va fi urmat de (1,3,2)     (pierde jucătorul 2)

(1,5,1) va fi urmat de (1,0,1)     (pierde jucătorul 2)

(1,5,0) va fi urmat de (1,1,0)     (pierde jucătorul 2)

(1,4,4) va fi urmat de (0,4,4)     (pierde jucătorul 2)

(1,3,4) va fi urmat de (1,3,2)     (pierde jucătorul 2)

(1,2,4) va fi urmat de (1,2,3)     (pierde jucătorul 2)

(1,1,4) va fi urmat de (1,1,0)     (pierde jucătorul 2)

(1,0,4) va fi urmat de (1,0,1)     (pierde jucătorul 2)

(0,5,4) va fi urmat de (0,4,4)     (pierde jucătorul 2)

Pentru configurația (2,4,6), jocul se va continua astfel:

(2,4,5) va fi urmat de (1,4,5)     (pierde jucătorul 2 – configurația tratată anterior)

(2,4,4) va fi urmat de (2,4,3)     (pierde jucătorul 2)

(2,4,3) va fi urmat de (2,1,3)     (pierde jucătorul 2)

(2,4,2) va fi urmat de (2,0,2)     (pierde jucătorul 2)

(2,4,1) va fi urmat de (2,3,1)     (pierde jucătorul 2)

(2,4,0) va fi urmat de (2,2,0)     (pierde jucătorul 2)

(2,3,6) va fi urmat de (2,3,1)     (pierde jucătorul 2)

(2,2,6) va fi urmat de (2,2,0)     (pierde jucătorul 2)

(2,1,6) va fi urmat de (2,1,3)     (pierde jucătorul 2)

(2,0,6) va fi urmat de (2,0,2)     (pierde jucătorul 2)

(1,4,6) va fi urmat de (1,4,5)     (pierde jucătorul 2 – configurația tratată anterior)

(0,4,6) va fi urmat de (0,4,4)     (pierde jucătorul 2)

Astfel am demonstrat despre configurația (3,5,7) că este câștigătoare și astfel jucătorul 1 îl poate forța pe adversarul său să mute numai din configurații pierzătoare.

 Generalizare

Folosim operația bitxor („sau exclusiv pe biți”), pe care o vom nota mai simplu cu „xor”. Această operație aplicăm peste toate numerele date. Dacă rezultatul este 0, înseamnă că în reprezentarea binară a tuturor numerelor, fiecare bit 1 rang k apare de număr par de ori, deci, configurația este pierzătoare. Orice mutare ar face jucătorul 1, xor-ul numerelor va fi diferit de 0, iar adversarul va alege acel număr cu care reface grămezile astfel ca să aibă xor-ul 0.

De aici vedem, că dacă se joacă optim, un jucător întotdeauna se străduiește să obțină 0 pentru xor-ul numerelor (el va fi câștigătorul), iar adversarul orice ar face, alegând un număr de piese din oricare grămadă, va strica „echilibrul” grămezilor obținând un xor diferit de 0.

 Putem verifica pe aplicația calculator al Windows-ului că 3 xor 5 xor 7=1. Deci configurația