Lecția 1: Poziții câștigătoare și pierzătoare

CE SUNT JOCURILE MATEMATICE?

Regulile generale

Jocurile pe care le considerăm sunt pentru doi jucători $A_1$ și $A_2$, care fac pe rând câte o mutare. Un jucător pierde când nu mai poate face nicio mutare.

Vom presupune că ambii jucători joacă fără greșeală — adică fac mereu cea mai bună alegere posibilă.

POZIȚII CÂȘTIGĂTOARE ȘI PIERZĂTOARE

Cheia rezolvării acestor probleme este să etichetăm fiecare situație din joc cu una din literele C sau P:

C = poziție Câștigătoare → jucătorul care urmează să mute câștigă (dacă joacă corect)

P = poziție Pierzătoare → jucătorul care urmează să mute pierde (dacă adversarul joacă corect)

Cum determinăm C sau P — cele 3 reguli

Poziția în care nu există nicio mutare posibilă este P (jucătorul care trebuie să mute nu poate și pierde).

O poziție este C dacă există cel puțin o mutare care duce la o poziție P.

O poziție este P dacă orice mutare duce la o poziție C.

Strategia câștigătoare: Dacă ești într-o poziție C, mută mereu într-o poziție P — adversarul va fi mereu în dezavantaj și în final vei câștiga tu.

Exemple rezolvate

E1) Jocul cu pietre — iei 1 sau 2

Pe masă sunt $n$ pietre. Cei doi jucători iau pe rând 1 sau 2 pietre. Cine ia ultima piatră câștigă. Cine câștigă dacă joacă primul $A_1$?

Analizăm de la mic la mare. $0$ pietre: nu poți lua nimic → P.

$1$ piatră: iei $1$ → adversarul rămâne cu $0$ (P) → tu câștigă → C.

$2$ pietre: iei $2$ → adversarul cu $0$ (P) → C.

$3$ pietre: iei $1$ → $2$ (C); iei $2$ → $1$ (C). Orice mutare duce în C → P.

$4$ pietre: iei $1$ → $3$ (P) → C. (Există o mutare bună.)

Pietre ($n$)	0	1	2	3	4	5	6	7	8	9
Poziție	P	C	C	P	C	C	P	C	C	P

Tipar: Pozițiile P sunt exact multiplii lui $3$: $0, 3, 6, 9, \ldots$

Concluzie: Dacă $n$ este multiplu al lui $3$, $A_1$ pierde. Altfel, $A_1$ câștigă luând astfel încât să lase adversarului un multiplu de $3$.

E2) Jocul numerelor — cine ajunge la 20?

Pornim de la numărul $0$. Pe rând, fiecare jucător adaugă $1$, $2$ sau $3$ la numărul curent. Cine ajunge exact la $20$ câștigă. Cine câștigă: $A_1$ sau $A_2$?

$20$ este poziția câștigătoare pentru cel care o atinge. Cel care este la $20$ a câștigat → situația înainte de $20$ (cel care „trimite" adversarul la $20$) câștigă.

Gândim invers: cine este forțat să nu atingă $20$ și să lase adversarul să o atingă?

Dacă ești la $17, 18$ sau $19$ — poți ajunge la $20$ în 1 mutare → poziție C. Dacă ești la $16$ — orice adaugi ($1, 2$ sau $3$) ajungi la $17, 18$ sau $19$ (C) → P.

Tiparul: P la $0, 4, 8, 12, 16, 20$... — multiplii lui $4$.

$0$ este multiplu al lui $4$ → $A_1$ pornește din poziție P → $A_2$ câștigă.

Strategia lui $A_2$: după fiecare mutare a lui $A_1$, $A_2$ adaugă cât trebuie pentru ca suma celor două mutări să fie $4$. (Dacă $A_1$ adaugă $1$, $A_2$ adaugă $3$; dacă $A_1$ adaugă $2$, $A_2$ adaugă $2$; etc.)

E3) Jocul cu pietre — iei 1 sau 2, dar ULTIMUL pierde

Pe masă sunt $n$ pietre. Se iau pe rând $1$ sau $2$ pietre. Cine ia ultima piatră pierde (varianta inversă). Cine câștigă?

$1$ piatră: ești forțat să iei $1$ → tu iei ultima → tu pierzi → P.

$2$ pietre: iei $1$ → adversarul cu $1$ (P) → C.

$3$ pietre: iei $2$ → adversarul cu $1$ (P) → C.

$4$ pietre: iei $1$ → $3$ (C); iei $2$ → $2$ (C). Orice mutare → C → P.

Pietre ($n$)	1	2	3	4	5	6	7
Poziție	P	C	C	P	C	C	P

Tipar: Pozițiile P sunt $1, 4, 7, 10, \ldots$ — numerele de forma $3k+1$.

Dacă $n$ lasă rest $1$ la împărțirea cu $3$, $A_1$ pierde; altfel câștigă.

E4) Joc cu două grămezi

Avem două grămezi: una cu $5$ pietre și alta cu $3$ pietre. La fiecare pas, un jucător ia oricâte pietre dintr-o singură grămadă (cel puțin una). Cine ia ultima piatră câștigă. Cine câștigă: $A_1$ sau $A_2$?

Notăm starea cu $(a, b)$ = numărul de pietre din cele două grămezi.

$(0, 0)$: nu poți lua nimic → P.

$(n, 0)$ sau $(0, n)$ cu $n \geq 1$: iei toată grămada → adversarul cu $(0,0)$ (P) → C.

$(n, n)$ cu $n \geq 1$: orice muți dintr-o grămadă ajungi la $(n, k)$ cu $k \neq n$ sau $(k, n)$ → toate sunt C (poți egala grămezile din cealaltă) → P.

$(5, 3)$: grămezile sunt inegale → C. Strategia: fă grămezile egale! Ia $2$ din grămada cu $5$ → $(3, 3)$ (P pentru adversar).

Regula pentru jocul cu 2 grămezi: O stare $(a, b)$ este P când $a = b$ și C când $a \neq b$. Strategia câștigătoare: egalizează mereu grămezile.

La $(5, 3)$: $A_1$ ia $2$ din prima grămadă → $(3,3)$ → $A_1$ câștigă.

E5) Joc cu paritate — cine scrie un număr impar pierde

Se scriu pe tablă toate numerele naturale de la $1$ la $50$. Începând cu $A_1$, cei doi jucători șterg pe rând câte două numere și scriu în locul lor suma celor două numere șterse. Pierde primul jucător care nu poate scrie decât un număr impar (adică este forțat să scrie o sumă impară). Arătați că jocul are întotdeauna un învingător și determinați cine câștigă.

Câte mutări are jocul? Pornim cu $50$ de numere. Fiecare mutare înlocuiește $2$ numere cu $1$ număr → numărul total scade cu $1$. Deci după $49$ de mutări rămâne un singur număr și jocul se termină. Jocul are mereu exact $49$ de mutări → există mereu un învingător (nu există remiză).

Când ești forțat să scrii impar? Suma a două numere este impară numai dacă unul este par și celălalt impar. Ești forțat să scrii impar numai când pe tablă rămâne exact $1$ număr impar și toate celelalte sunt pare (nu poți alege două numere cu aceeași paritate).

Câte numere impare sunt la start? Din $1$ la $50$: numerele impare sunt $1, 3, 5, \ldots, 49$ → $\mathbf{25}$ numere impare.

Cum se modifică numărul de impare? O mutare sigură (scrie par) înseamnă: ori ștergem $2$ impare ($\text{impar}+\text{impar}=\text{par}$) → numărul de impare scade cu $\mathbf{2}$, ori ștergem $2$ pare ($\text{par}+\text{par}=\text{par}$) → numărul de impare nu se schimbă. Deci prin mutări sigure, numărul de impare rămâne mereu impar (pleacă de la $25$ și scade cu $0$ sau $2$).

Cine este forțat? Jocul ajunge inevitabil la situația cu $1$ impar și $1$ par pe tablă (2 numere) → mutarea $49$. Cel care face mutarea $49$ pierde. $A_1$ face mutările $1, 3, 5, \ldots, 49$ (cele cu număr impar). Mutarea $49$ o face $A_1$ → $A_1$ pierde → $A_2$ câștigă.

Strategia lui $A_2$: la fiecare rând, $A_2$ face o mutare sigură (scrie un număr par). Întrucât la start există $25$ numere impare (impar), numărul de impare rămâne mereu impar după orice secvență de mutări sigure — și $A_1$ va fi cel care ajunge la starea imposibilă.

$A_2$ câștigă dacă joacă fără greșeală. $\blacksquare$

Atenție!

Metoda C/P funcționează pentru orice joc finit în care nu există remiză. Cheia este să găsești tiparul pozițiilor P — de obicei legat de un invariant (paritate, rest la împărțire, egalitate) pe care îl menții dacă ești în C.

Temă (de realizat pe caietul de clasă)

Vă rog să scrieți și enunțul problemelor propuse spre rezolvare!

1. Pe masă sunt $12$ pietre. Se iau pe rând $1$, $2$ sau $3$ pietre. Cine ia ultima câștigă. Cine câștigă: $A_1$ sau $A_2$?

Indiciu: faceți tabelul C/P pentru $0, 1, 2, \ldots, 12$ pietre. Ce tipar observați?

2. Pornim de la $0$ și pe rând adăugăm $1$, $2$ sau $3$. Cine ajunge exact la $30$ câștigă. Cine câștigă?

Indiciu: care sunt pozițiile P? Cu câte se repetă tiparul?

3. Pe masă sunt $10$ pietre. Se iau pe rând $1$, $2$ sau $3$ pietre. Cine ia ultima piatră pierde. Cine câștigă?

Indiciu: faceți tabelul C/P. Atenție: regula de terminare este inversată față de E1!

4. Avem două grămezi: una cu $7$ pietre și alta cu $4$ pietre. Se ia oricât dintr-o singură grămadă. Cine ia ultima câștigă. Cine câștigă și cum?

Indiciu: folosiți regula din E4 — când sunt egale grămezile?

5. (Provocare) Se scriu pe tablă numerele de la $1$ la $100$. Jucătorii șterg pe rând câte două și scriu suma lor. Pierde cel forțat să scrie o sumă impară. Cine câștigă?

Indiciu: câte numere impare sunt? Câte mutări are jocul? Cine face ultima mutare?

Indicații pentru temă

1. Pozițiile P: $0, 4, 8, 12$ (multipli de $4$). $12$ este multiplu de $4$ → $A_1$ este în P → $A_2$ câștigă. Strategia $A_2$: după fiecare mutare a lui $A_1$, adaugă astfel încât suma să fie $4$.

2. Pozițiile P: $0, 4, 8, \ldots, 28$ (multipli de $4$). $0$ este P → $A_2$ câștigă. Strategia: după fiecare mutare a lui $A_1$, $A_2$ completează la un multiplu de $4$.

3. Pozițiile P (ultimul care ia pierde): $1, 5, 9$ (rest $1$ la împărțirea cu $4$). $10 = 4 \times 2 + 2$ → rest $2$ → poziție C → $A_1$ câștigă. Ia $1$ piatră → lasă $9$ (P).

4. $(7, 4)$: grămezile inegale → C. $A_1$ ia $3$ din prima → $(4, 4)$ (P). Orice face $A_2$, $A_1$ egalează din nou → $A_1$ câștigă.

5. De la $1$ la $100$: $50$ numere impare (par). Jocul are $99$ mutări. Mutarea $99$ (forțată, impară) o face $A_1$ (mutare cu număr impar). $A_2$ câștigă.

↑ Înapoi la Jocuri matematice

MateExamene

Lecția 1: Jocuri matematice — Poziții câștigătoare și pierzătoare