5. Zadatak

Na stolu su $42$ kamenčića. Dva igrača naizmjence odigravaju poteze. U svakom potezu igrač treba uzeti najmanje jedan kamenčić, ali ne više od polovine preostalih kamenčića. Pobjeđuje igrač nakon čijeg poteza na stolu ostane samo jedan kamenčić.

Koji igrač sigurno može pobijediti?

Prvo rješenje.

Prvi igrač može pobijediti sa sljedećom strategijom: ostavit će protivniku redom $31$ , $15$ , $7$ , $3$ i $1$ kamenčić.

U prvom potezu uzme $11$ kamenčića. Tada drugi igrač mora uzeti između $1$ i $15$ kamenčića, čime će na stolu ostati između $16$ i $30$ kamenčića. Koliko god da ih ostane, prvi igrač može uzeti dovoljno da ih na stolu nakon njegovog poteza ostane $15$ .

Kada je na stolu $15$ kamenčića, drugi igrač mora uzeti između $1$ i $7$ kamenčića, čime će na stolu ostati između $8$ i $14$ kamenčića. Koliko god da ih ostane, prvi igrač može uzeti dovoljno da ih na stolu nakon njegovog poteza ostane $7$ .

Kada je na stolu $7$ kamenčića, drugi igrač mora uzeti između $1$ i $3$ kamenčića, čime će na stolu ostati između $4$ i $6$ kamenčića. Koliko god da ih ostane, prvi igrač može uzeti dovoljno da ih na stolu nakon njegovog poteza ostane $3$ .

Kada su na stolu $3$ kamenčića, drugi igrač može uzeti samo točno $1$ kamenčić, čime na stolu ostaju $2$ kamenčića. Prvi igrač tada uzima $1$ kamenčić, ostavlja jedan na stolu i time pobjeđuje.

Drugo rješenje.

Sigurno može pobijediti prvi igrač.

Promotrimo situaciju u kojoj su na potezu nekog igrača na stolu $3$ kamenčića. Tada taj igrač smije uzeti samo točno $1$ kamenčić pa preostalom igraču ostaju na stolu $2$ kamenčića, od kojih on uzima točno jedan i pobjeđuje. Prema tome, igrač koji na svom potezu (prije uzimanja) ima $3$ kamenčića na stolu sigurno gubi.

Nadalje, promotrimo situaciju u kojoj je na potezu nekog igrača na stolu $7$ kamenčića. Tada taj igrač smije uzeti najmanje $1$ , a najviše $3$ kamenčića. U svakom od tih slučajeva, preostali igrač može uzeti točno onoliko kamenčića koliko je potrebno da ostavi $3$ kamenčića na stolu i, prema prethodnom, pobijedi. Prema tome, igrač koji na svom potezu (prije uzimanja) ima $7$ kamenčića na stolu sigurno gubi.

Slično, promotrimo situaciju u kojoj je na potezu nekog igrača na stolu $15$ kamenčića. Tada taj igrač smije uzeti najmanje $1$ , a najviše $7$ kamenčića. U svakom od tih slučajeva, preostali igrač može uzeti točno onoliko kamenčića koliko je potrebno da ostavi $7$ kamenčića na stolu i, prema prethodnom, pobijedi. Prema tome, igrač koji na svom potezu (prije uzimanja) ima $15$ kamenčića na stolu sigurno gubi.

Konačno, promotrimo situaciju u kojoj je na potezu nekog igrača na stolu $31$ kamenčić. Tada taj igrač smije uzeti najmanje $1$ , a najviše $15$ kamenčića. U svakom od tih slučajeva, preostali igrač može uzeti točno onoliko kamenčića koliko je potrebno da ostavi $15$ kamenčića na stolu i, prema prethodnom, pobijedi. Prema tome, igrač koji na svom potezu (prije uzimanja) ima $31$ kamenčić na stolu sigurno gubi.

Uočimo sada da prvi igrač u prvom potezu može uzeti najmanje $1$ , a najviše $21$ kamenčić. Posebno, prvi igrač može uzeti točno $11$ kamenčića i ostaviti drugom igraču $31$ kamenčić na stolu. Prema prethodno dokazanom, u tom slučaju drugi igrač sigurno gubi, a prvi igrač pobjeđuje.

Napomena: Gore navedena strategija je jedina pobjednička. Ako prvi igrač u bilo kojem potezu odstupi od te strategije, drugi igrač može preuzeti pobjedničku strategiju.