Un alt exemplu de sarcină. Un alt exemplu de sarcină Petya și Vanya joacă următorul joc

În această sarcină, partea cea mai dificilă este să scrieți corect și logic soluția.

Deci, să începem prin a încerca să înțelegem starea.

1. Avem două mormane de pietre și doi jucători: primul (Petya) și al doilea (Vanya).
2. Jucătorii se fac pe rând.
3. În timpul unei mișcări, puteți fie să adăugați o piatră la oricare dintre grămezi, fie să dublați numărul de pietre din grămadă.
4. De îndată ce există 73 sau mai multe pietre în grămadă, jocul se termină.
5. Cel care a mers ultimul a câștigat.

Notite importante

1. Vom construi un arbore de petrecere în unele sarcini. Suntem obligați să facem acest lucru conform condiției numai din Sarcina 3. În Sarcina 2 noi nu este necesar construi un copac de petrecere.
2. În fiecare dintre sarcini, nu este suficient doar să spui cine are o strategie câștigătoare. De asemenea, este necesar să-l descrie și să indice numărul posibil de pași care vor fi necesari pentru a câștiga.
3. Nu este suficient să numești strategia câștigătoare. Nevoie dovedi că aceasta duce la o victorie. Chiar și afirmațiile evidente necesită dovezi.

Exercitiul 1.

Luați în considerare acum Sarcina 1. În grămezi - (6, 33) pietre (prima parte a Sarcinii 1) și (8, 32) pietre (a doua parte a Sarcinii 1). Trebuie să stabilim ce jucător are strategie învingătoare. Cu alte cuvinte, care dintre jucători jocul potrivit va câștiga cu siguranță indiferent de acțiunile adversarului.

Aici și mai jos, vom împărți soluția în două părți. În primul rând, va exista o explicație preliminară (nu este necesar să o scrieți în USE) și apoi - o „decizie formală”, adică ceea ce trebuie scris în formularul USE în sine.

Discuţie.

Să ne gândim: primul jucător, evident, nu poate câștiga într-o singură mișcare, pentru că indiferent ce face, nu vor fi în total 73. Cea mai „mare” acțiune pe care o poate face este să dubleze numărul de pietre din a doua grămadă, făcându-le 66. Dar (6, 66) sunt 72 de pietre, nu 73. Deci, prima dintr-o singură mișcare este în mod clar să câștigi poate. nu. Cu toate acestea, al doilea poate. Primul poate face patru lucruri: adăugați 1 la prima grămadă, dublați numărul de pietre din prima grămadă, adăugați 1 la a doua grămadă, dublați numărul de pietre din a doua grămadă. Să vedem unde duce asta:

• (6,33) -> (7,33). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Obținem (7, 66). În total - 73. Deci, al doilea câștigă.
• (6,33) -> (12, 33). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Obținem (12, 66). În total - 78. Deci, al doilea câștigă.
• (6,33) -> (6,34). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Obținem (6, 68). În total - 74. Deci, al doilea câștigă.
• (6,33) -> (6,66). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Obținem (6, 132). În total - 138. Deci, al doilea câștigă.

Total: indiferent de modul în care se comportă primul jucător, al doilea va câștiga într-o singură mișcare.

Se rezolvă în mod similar cu (8.32).

Rezolvarea formală a sarcinii 1.

Al doilea jucător are o strategie de câștig. Să demonstrăm și să arătăm această strategie. Pentru a face acest lucru, vom construi un arbore de petrecere pentru fiecare dintre pozițiile inițiale. În arborele de joc, vom indica starea ambelor grămezi în formatul (a,b), unde a este numărul de pietre din primul teanc, b este numărul de pietre din al doilea teanc. În timpul mișcării primului jucător, vom lua în considerare patru opțiuni posibile pentru comportamentul său: adăugați 1 la prima grămadă, dublați numărul de pietre din prima grămadă, adăugați 1 la a doua grămadă, dublați numărul de pietre din a doua. teanc. Pentru al doilea jucător, vom indica câte o mișcare fiecare, ceea ce duce la o victorie. Vom arăta mișcările sub formă de săgeți, lângă care scriem I în cazul primei mișcări și II în cazul celei de-a doua mișcări.

Arborele jocului pentru poziția de pornire (6, 33).

Arborele de joc pentru poziția de pornire (8, 32).

Conform arborelui de joc, indiferent de mutările primei, al doilea are întotdeauna o strategie câștigătoare care îi permite să câștige într-o singură mișcare, descrisă în arbori (sumele după mișcările lui Vanya sunt 73, 80, 74 și respectiv 136). , de la stanga la dreapta). În același timp, conform arborelui jocului, al doilea jucător poate câștiga într-o singură mișcare.

Sarcina 2

solutie formala

Luați în considerare poziția inițială (6,32). Rețineți că este aproape de (6.33) din Sarcina 1. În Sarcina 1, am aflat că în poziția (6, 33) al doilea câștigă și într-o singură mișcare. Aceasta conditie poate fi reformulata: in pozitia (6.33) cel care castiga intr-o miscare nu umblă (adică merge al doilea). Sau, cu alte cuvinte, cel care merge pierde într-o singură mișcare.

In pozitia (6,32) primul castiga in doua mutari. Să demonstrăm. La prima sa mutare, Petya adaugă +1 la a doua grămadă. Se obţine astfel poziţia (6.33). După cum am aflat mai devreme, în poziția (6.33) cel care se mișcă pierde. În cazul nostru, va fi mutarea Vaniei. Prin urmare, Vanya va pierde într-o singură mișcare. În acest caz, Petya va trebui să facă două mișcări în total: prima (adăugați 1 piatră la a doua grămadă) + a doua mutare în conformitate cu Arborele jocului din Sarcina 1, acționând conform strategiei Vanyei.

La fel în poziție (7, 32). Petya, la prima sa mutare, adaugă +1 piatră la prima grămadă, obținând poziția (8, 32). În această poziție, după același raționament, cel care se mișcă pierde. Va fi mutarea Vaniei, așa că Vanya va pierde. Strategia câștigătoare a lui Petya este următoarea: Petya adaugă +1 piatră la prima grămadă, apoi urmează strategia lui Vanya din Sarcina 1.

La fel în poziție (8, 31). Petya, la prima sa mutare, adaugă +1 piatră la a doua grămadă, obținând poziția (8, 32). În această poziție, după același raționament, cel care se mișcă pierde. Va fi mutarea Vaniei, așa că Vanya va pierde. Strategia câștigătoare a lui Petya este următoarea: Petya adaugă +1 piatră la a doua grămadă și apoi urmează strategia lui Vanya din Sarcina 1.

Sarcina 3

Discuţie

Rețineți că din situația (7, 31) este foarte ușor să ajungeți fie în situațiile (8, 31) și (7, 32), în care, conform Sarcinii anterioare, câștigă cel care se mișcă, fie în situația (14). , 31) și (7, 62), în care cel care se mișcă poate câștiga într-o singură mișcare dublând numărul de pietre din a doua grămadă. Astfel, se dovedește că Vanya trebuie să aibă o strategie câștigătoare. În același timp, poate câștiga atât în ​​2 mutări (primele două cazuri), cât și într-o singură mișcare (al doilea caz).

solutie formala

În poziția inițială (7, 31) Vanya câștigă în una sau două mișcări. Să demonstrăm. Pentru a face acest lucru, construim un arbore al tuturor părților.

Arborele tuturor jocurilor pentru poziția de pornire (7, 31).

Conform arborelui tuturor jocurilor, Vanya câștigă fie într-o singură mișcare (dacă Petya a dublat numărul de pietre din primul sau al doilea teanc), fie în două mișcări (dacă Petya a dublat numărul de pietre din primul sau al doilea teanc).

Astfel, în poziția inițială (7, 31), Vanya are o strategie câștigătoare, iar Vanya va câștiga în una sau două mișcări.

Evgheni Smirnov

Expert în IT, profesor de informatică

Problemă Doi jucători, Petya și Vanya, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se mișcă pe rând, Petya face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga una sau cinci pietre la grămadă sau poate tripla numărul de pietre din grămadă. De exemplu, având o grămadă de 15 pietre, într-o singură mișcare poți obține o grămadă de 16, 20 sau 45 de pietre. Fiecare jucător, pentru a face mișcări, are cantitate nelimitată pietre. Jocul se termină când teancul conține cel puțin 41. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 41 sau mai multe pietre. La momentul inițial, erau pietre S în grămadă; 1 S 40. Vom spune că un jucător are o strategie câștigătoare dacă poate câștiga pentru orice mișcare a adversarului. A descrie strategia unui jucător înseamnă a descrie ce mișcare ar trebui să facă în orice situație pe care o poate întâlni cu diferite jocuri ale adversarului. Finalizați următoarele sarcini. În toate cazurile, justificați răspunsul.

Sarcina 1. a) Indicați toate aceste valori ale numărului S pentru care Petya poate câștiga într-o singură mișcare. Justificați că toate valorile necesare ale lui S sunt găsite și indicați mișcările câștigătoare. b) Indicați o valoare a lui S pentru care Petya nu poate câștiga într-o singură mișcare, dar pentru orice mișcare a lui Petya, Vanya poate câștiga cu prima sa mutare. Descrie strategia de câștig a Vanyei.

Sarcina 2. Indicați două valori ale lui S pentru care Petya are o strategie câștigătoare și două condiții sunt îndeplinite simultan: Petya nu poate câștiga într-o singură mișcare; Petya poate câștiga cu a doua sa mutare, indiferent de modul în care se mișcă Vanya. Pentru fiecare valoare dată a lui S, descrieți strategia câștigătoare a lui Petya.

Sarcina 3. Indicați valorile lui S, în care sunt îndeplinite simultan două condiții: Vanya are o strategie câștigătoare care îi permite să câștige la prima sau a doua mișcare în orice joc al lui Petya; Vanya nu are o strategie care să-i permită să câștige la prima mutare. Pentru valoarea dată a lui S, descrieți strategia câștigătoare a lui Vanya. Construiește un arbore cu toate jocurile posibile cu strategia câștigătoare a lui Vanya (sub forma unei figuri sau a unei mese). Pe marginile copacului indicați cine face mișcarea, la noduri - numărul de pietre în poziție.

1. a) S=14…40 pietre. După ce a triplat numărul de pietre, Petya va câștiga de la prima mutare, după ce a primit mai mult de 41 de pietre într-o grămadă. b) S=13 pietre. După prima mutare, Petya va avea 14 sau 18 sau 39 de pietre. Atunci Vanya va câștiga oricum cu prima lui mișcare. 1. a) S=14…40 pietre. După ce a triplat numărul de pietre, Petya va câștiga de la prima mutare, după ce a primit mai mult de 41 de pietre într-o grămadă. b) S=13 pietre. După prima mutare, Petya va avea 14 sau 18 sau 39 de pietre. Atunci Vanya va câștiga oricum cu prima lui mișcare.

Sarcina 2. Într-o singură mișcare, un jucător poate adăuga trei pietre la grămadă sau poate dubla numărul de pietre din grămadă. Jocul se termină când numărul de pietre din teanc devine cel puțin 33. La momentul inițial erau S pietre în teanc, 1 S Pentru care S: 1 a) Petya câștigă la prima mutare; 1 b) Câștigă Vanya la prima mutare? 2. Numiți două valori ale lui S pentru care Petya poate câștiga cu a doua sa mutare. 3. Pentru ce S câștigă Vanya cu prima sau a doua mutare?

A 26-a sarcină: „Teoria jocurilor, căutarea unei strategii câștigătoare”
Nivel de dificultate - ridicat,
Scorul maxim - 3,
Timpul de rulare estimat este de 30 de minute.

Analiza celei de-a 26-a sarcini a examenului unificat de stat în informatică 2017 FIPI opțiunea 5 (Krylov S.S., Churkina T.E.):

Doi jucători, Pasha și Valya, jocuri

mergi la jocul urmator. Există un morman de pietre în fața jucătorilor. Jucătorii se fac pe rând Pașa face prima mișcare unu de două ori. De exemplu, având un morman de 7 pietre, într-o singură mișcare poți obține un morman de 14 sau 8 pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face o mișcare.

Jocul se termină când numărul de pietre din grămadă devine cel puțin 28 . Dacă, în același timp, nu mai mult de 44 pietre, câștigătorul este jucătorul care a făcut ultima mișcare. În caz contrar, adversarul său devine câștigător. De exemplu, dacă erau 23 de pietre în grămadă, iar Pașa dublează numărul de pietre din grămadă, atunci jocul se va încheia și Valya va fi câștigătoare. La momentul inițial, erau pietre S în grămadă, 1≤S≤27.

Exercitiul 1
a) Pentru ce valori ale numărului S Pașa poate câștiga într-o singură mișcare? Indicați toate aceste valori și mișcările corespunzătoare ale lui Pașa.
b) Pentru care dintre jucători are o strategie de câștig S = 26, 25, 24? Descrieți strategiile câștigătoare pentru aceste cazuri.

Sarcina 2
S = 13, 12? Descrieți strategiile de câștig relevante.

Sarcina 3
Pentru care dintre jucători are o strategie de câștig S=11? Construiți un arbore cu toate jocurile posibile cu această strategie câștigătoare (sub forma unei figuri sau a unui tabel). Pe marginile copacului indicați cine face mișcarea; în noduri — numărul de pietre în poziție.

✍ Afișați soluția:

Analiza sarcinii 26 a examenului unificat de stat în informatică 2017 (una dintre opțiunile în funcție de absolvent):

Petya și Vanya joacă un joc: există un set de cuvinte, trebuie să denumești secvenţial literele acestor cuvinte. Câștigă jucătorul care numește ultima literă a oricărui cuvânt din set. Petya merge prima.

De exemplu, există un set de cuvinte (Lupul, Informatica, Infricosator); pentru un anumit set de cuvinte, prima mișcare a lui Petya poate numi o literă LA, Și sau DIN. Dacă Petya alege o scrisoare LA, apoi Vanya va câștiga (următoarele mișcări: Petya - LA, Vania - O, Petya - L, Vania - La).

Exercitiul 1
A) Sunt date 2 cuvinte (un set de litere) ( IKLMNIKLMNH, NMLKINMLKI). Stabiliți o strategie câștigătoare.

B) Se dau 2 cuvinte ( TREI TREI...TREI, RITARITARITARITA…RITA). În primul cuvânt 99 litere, în a doua 164 . Stabiliți o strategie câștigătoare.

Sarcina 2
Trebuie să schimbați două litere din setul de puncte 1Aîn cuvântul cu lungimea cea mai mică, astfel încât celălalt jucător să aibă o strategie câștigătoare. Explicați strategia câștigătoare.

Sarcina 3
Dat un set de cuvinte ( Cioară, Lup, Val, Derivat, Prokhor, Mei). Care jucător are o strategie câștigătoare? Justificați-vă răspunsul și scrieți un arbore cu toate jocurile posibile pentru o strategie câștigătoare.

✍ Afișați soluția:

* Pentru Vanya, sunt afișate doar mișcările de strategie
**Cercul roșu înseamnă câștig

Decizia 26. Versiunea demo a examenului 2018 informatică:

Doi jucători, Petya și Vanya, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se mișcă pe rând, Petya face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga la grămadă unu piatra sau creste numarul de pietre din gramada de două ori. De exemplu, având o grămadă de 15 pietre, într-o singură mișcare poți obține o grămadă de 16 sau 30 de pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face mișcări.

Jocul se termină când numărul de pietre din grămadă devine cel putin 29. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 29 sau mai multe pietre. La momentul inițial, erau pietre S în grămadă, 1 ≤ S ≤ 28.

Vom spune că un jucător are o strategie câștigătoare dacă poate câștiga pentru orice mișcare a adversarului. A descrie strategia unui jucător înseamnă a descrie ce mișcare ar trebui să facă în orice situație pe care o poate întâlni cu diferite jocuri ale adversarului. La descrierea strategiei câștigătoare nu urmează includeți mișcările jucătorului care joacă în conformitate cu această strategie, care nu sunt necondiționat câștigătoare pentru el, de exemplu. nefiind câștigător indiferent de jocul adversarului.

Exercitiul 1
A) Indicați astfel de valori ale numărului S pentru care Petya poate câștiga într-o singură mișcare.
b) Indicați o valoare a lui S pentru care Petya nu poate câștiga într-o singură mișcare, dar pentru orice mișcare a lui Petya, Vanya poate câștiga cu prima sa mutare. Descrie strategia de câștig a Vanyei.

Sarcina 2
Indicați două astfel de valori ale lui S pentru care Petya are o strategie câștigătoare, în plus:
- Petya nu poate câștiga într-o singură mișcare;
— Petya poate câștiga cu a doua sa mișcare, indiferent de modul în care se mișcă Vanya.
Pentru valorile indicate ale lui S, descrieți strategia câștigătoare a lui Petya.

Sarcina 3
Specificați valoarea lui S la care:
- Vanya are o strategie de câștig care îi permite să câștige la prima sau a doua mișcare în orice joc al lui Petya;
- Vanya nu are o strategie care să-i permită să câștige cu garanție la prima mutare.

Pentru valoarea dată a lui S, descrieți strategia câștigătoare a lui Vanya. Construiți un arbore cu toate jocurile posibile cu această strategie câștigătoare (sub forma unei figuri sau a unui tabel). Pe marginile copacului indicați cine face mișcarea; în noduri - numărul de pietre într-o poziție

Arborele nu trebuie să conțină jocuri care sunt imposibile pentru jucătorul câștigător să-și pună în aplicare strategia câștigătoare. De exemplu, arborele complet al jocului nu este un răspuns valid pentru această sarcină.

✍ Afișați soluția:

Exercitiul 1.
• a) Petya poate câștiga dacă S = 15, ... 28

15, ..., 28 - poziții câștigătoare de la prima mutare

b) Vanya poate câștiga la prima mutare (indiferent cum joacă Petya) dacă există S=14 pietre. Apoi, după prima mișcare a lui Petya, vor fi 15 sau 28 de pietre în grămadă. În ambele cazuri, Vanya dublează grămada și câștigă într-o singură mișcare.

S = 14 Petya: 14 + 1 = 15 poziție câștigătoare (vezi punctul a). Vanya Petya câștigă: 14 * 2 = 28 poziție câștigătoare (vezi punctul a). Vanya câștigă 14 - pierde poziția

Sarcina 2.

Valori posibile S: 7, 13. În aceste cazuri, Petya, evident, nu poate câștiga la prima mișcare. Cu toate acestea, poate obține un morman de 14 pietre: în primul caz prin dublare, în al doilea prin adăugarea unei pietre. Această poziție este discutată în paragraful 1b. În ea, jucătorul care se va muta (acum aceasta este Vanya) nu poate câștiga, iar adversarul său (adică Petya) va câștiga la următoarea mișcare.

S = 7 Petru: 7 * 2 = 14 este o poziție pierzătoare (vezi punctul 1 b). Petya câștigă S = 13 Petya: 13 + 1 = 14 pierzând poziția (vezi punctul 1 b). Petya câștigă 7, 13 - poziții câștigătoare din a doua mutare

Sarcina 3.

Valori posibile S: 12. După prima mișcare a lui Petya, vor fi 13 sau 24 de pietre în grămadă. Dacă există 24 de pietre în grămadă, Vanya va dubla numărul de pietre și va câștiga la prima mutare. Situația, când sunt 13 pietre într-o grămadă, este analizată în paragraful 2. În această situație, jucătorul care se va muta (acum este Vanya) câștigă cu a doua mutare.

S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 pierderea poziției (vezi punctul 1 b). Vanya câștigă al doilea mutare!

Tabelul arată arborele jocurilor posibile (și numai ele) pentru strategia descrisă de Vanya. Pozițiile finale (Vanya le câștigă) sunt subliniate. În figură, același arbore este prezentat grafic.


Arborele tuturor jocurilor posibile cu strategia lui Vanya:

* cerc roșu înseamnă câștig

Examen timpuriu în informatică 2018, opțiunea 1. Sarcina 26:

Doi jucători, Pașa și Vasya, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se fac pe rând Pașa face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga la grămadă unu sau patru piatră sau crește numărul de pietre din grămadă de cinci ori. Jocul se termină când numărul de pietre în grămada devine cel puțin 69.
Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 69 sau mai multe pietre. La momentul inițial, erau pietre S în grămadă, 1 ≤ S ≤ 68.

Exercitiul 1.
A) Indicați toate aceste valori ale numărului S pentru care Pașa poate câștiga într-o singură mișcare. Justificați că sunt găsite toate valorile necesare ale lui S și indicați mutarea câștigătoare pentru fiecare valoare specificată a lui S.

b) Indicați o valoare a lui S pentru care Pașa nu poate câștiga într-o singură mișcare, dar Vasya poate câștiga cu prima sa mutare în orice mișcare a lui Pașa. Descrieți strategia câștigătoare a lui Vasya.

Sarcina 2. Indicați 2 valori ale lui S pentru care Pașa are o strategie câștigătoare, iar Pașa nu poate câștiga într-o singură mișcare și poate câștiga la a doua mutare, indiferent de modul în care se mișcă Vasya. Pentru fiecare valoare dată a lui S, descrieți strategia de câștig a lui Pașa.

Sarcina 3. Indicați cel puțin o valoare a lui S pentru care Vasya are o strategie câștigătoare care îi permite să câștige la prima sau a doua mutare ori de câte ori joacă Pașa, iar Vasya nu are o strategie care să îi permită să câștige la prima mutare. Pentru valoarea dată a lui S, descrieți strategia câștigătoare a lui Vasya. Construiește un arbore cu toate jocurile posibile cu această strategie câștigătoare a lui Vasya (sub forma unei figuri sau a unei mese).

✍ Afișați soluția:

1.
A) S ≥ 14. Dacă numărul de pietre din grămadă este de 14 sau mai mult, Pașa trebuie să-și mărească numărul de cinci ori, obținând astfel 70 sau mai multe pietre.

S ≥ 14 poziții câștigătoare

b) S=13. Pașa poate face 14, 17 sau 65 de pietre la prima sa mișcare, după care Vasya crește numărul de cinci ori, obținând 70, 85 sau 325 de pietre într-o grămadă.

S = 13 Pașa 1 mutare: 13 + 1 = 14 Pașa 1 mutare: 13 + 4 = 17 Pașa 1 mutare: 13 * 5 = 65 Vanya 1 mutare: * 5 = S ≥ 14 Vanya câștigă 13 - pierde poziția

2. S = 9, 12. În aceste cazuri, Pașa trebuie să adauge 4 pietre la o grămadă de 9 pietre sau 1 piatră la o grămadă de 12 și să obțină o grămadă de 13 pietre.
După aceea, jocul se reduce la strategia descrisă în paragraf 1b.

S = 13 Pașa 1 mutare: 9 + 4 = 13 Pașa câștigă Pașa 1 mutare: 12 + 1 = 13 Pașa câștigă 9, 12 - poziții câștigătoare din a doua mutare

3. S=8. La prima sa mutare, Pașa poate face numărul de pietre din teancul 9, 12 sau 40. Dacă Pașa crește numărul de cinci ori, atunci Vasya câștigă la prima sa mișcare, mărind numărul de pietre de cinci ori.
Pentru cazul pietrelor 9 și 12, Vasya folosește strategia indicată în punctul 2.

S = 8 Pașa 1 mutare: 8 + 1 = 9 Vanya Câștigă (vezi elementul 2) Pașa 1 mutare: 8 + 4 = 12 Vanya câștigă (vezi articolul 2) Pașa 1 mutare: 8 * 5 = 40

USE simulator în informatică 2018, opțiunea de control 1. Sarcina 26 (Krylov S., Ushakov D.):

o piatră sau . Jocul se termină când numărul total de pietre din grămezi devine cel putin 73.
Câștigătorul este jucătorul care a făcut ultima mutare, adică. primul care a obținut o astfel de poziție încât să fie un total de 73 de pietre sau mai mult în grămezi.

Exercitiul 1.
(6, 33), (8, 32) indicați care dintre jucători are o strategie câștigătoare. În fiecare caz, descrieți strategia câștigătoare; explicați de ce această strategie duce la o victorie și indicați numărul maxim de mișcări pe care câștigătorul le poate face pentru a câștiga cu această strategie.

Sarcina 2.
Pentru fiecare dintre pozițiile inițiale (6, 32), (7, 32), (8, 31) indicați care dintre jucători are o strategie câștigătoare.

Sarcina 3.
Pentru pozitia de pornire (7, 31) indicați care dintre jucători are o strategie câștigătoare. Construiește un arbore cu toate jocurile posibile cu strategia câștigătoare pe care ai specificat-o. Prezentați copacul sub forma unei imagini sau a unui tabel.

✍ Afișați soluția:

Analiza sarcinii 26 de pe site-ul lui K. Polyakov (nr. 31):

Doi jucători, Petya și Vanya, joacă următorul joc. În fața jucătorilor sunt două mormane de pietre. Jucătorii se mișcă pe rând, Petya face prima mișcare. Într-o singură tură, jucătorul poate adăuga la una dintre grămezi (la alegere) două pietre sau dublează numărul de pietre din grămadă. Pentru a face mișcări, fiecare jucător are un număr nelimitat de pietre. Jocul se termină când numărul total de pietre din grămezi devine cel putin 44.
Câștigătorul este jucătorul care a făcut ultima mutare, adică. primul care obține o astfel de poziție încât să fie un total de 44 sau mai multe pietre în grămezi.

La momentul inițial, primul morman a conținut 5 pietre, în a doua grămadă - S pietre; 1 ≤ S ≤ 38.
Exercitiul 1.
La ce S: 1a) Petya câștigă la prima mutare; 1b) Vanya câștigă la prima mutare?

Sarcina 2.
Numiți o singură valoare S, sub care Petya poate câștiga la a doua sa mutare.

Sarcina 3.
Numiți valoarea lui S la care Vanya câștigă cu prima sau a doua mutare.

Afișați soluția:

5 + 20*2 = 45 (>44) * 5 - numărul de pietre din prima grămadă, nu se modifică în funcție de stare

În consecință, toate valorile mare 20 va avea ca rezultat un număr mai mare 44 . Să-l punem în tabel. + înseamnă o poziție câștigătoare de la prima mutare:

Raspuns 1 a): S= (La examen, explicați mișcările, de exemplu: (5; 20) -> (Mișcarea lui Petit) -> (5; 40); 40 + 5 = 45)

Sarcina 1 b):

Deoarece Vanya se va muta pe al doilea, este necesar să se schimbe numărul de pietre din prima grămadă. Deci, să luăm în considerare situațiile în care Petya s-ar putea muta la prima mișcare (7;S) si in (10;S). Să indicăm dacă aceste poziții vor fi câștigătoare dintr-o singură mișcare: de exemplu (7;19) poziție câștigătoare, pentru că jucătorul va face o mișcare (7;38) și câștigă (7 + 38 = 45). În consecință, toate pozițiile sunt câștigătoare (7; peste 19). Să analizăm tabelul, crescând numărul de pietre din prima grămadă și căutând poziții câștigătoare într-o singură mișcare:

Următoarea logică a raționamentului: Vanya poate câștiga cu prima sa mișcare, când Petya, cu prima sa mutare, poate trece doar în pozițiile câștigătoare de la prima mutare (la +). Marcăm astfel de poziții, având în vedere că aceasta este prima mișcare a lui Petya, iar numărul de pietre din prima grămadă ar trebui să fie de 5. Pozițiile găsite vor fi poziții pierdere (-):

Găsim singura astfel de valoare - (5; 19). Acestea. S = 19.

Răspunsul 1 b): S=19 (La examen, explicați mișcările, de exemplu: (5; 19) -> (Mișcările lui Petya): (5; 21), (5; 28); (7; 19); (7; 28). Vanya va câștigă peste tot cu următoarea mișcare, vezi punctul anterior)

Sarcina 2:

Vă rugăm să rețineți că în tabel, toate „colțurile” formate sunt poziții care pierde (de la prima mutare): adică, dacă un jucător se găsește într-o astfel de poziție, atunci el poate trece doar în pozițiile câștigătoare (adică adversarul va câștigă la următoarea mișcare):

Logica de raționament: Petya va putea câștiga cu a doua sa mutare atunci când va ajunge într-o poziție pierzătoare cu prima sa mutare, de exemplu. va pune adversarul într-o situație de pierdere. Astfel de valori: S = 16, 17 sau 18. Să numim aceste poziții câștigătoare din a doua mutare (2+):

Raspunsul 2: S = 16, 17 sau 18

Sarcina 3:

De asemenea, indicăm în tabel pozițiile care sunt câștigătoare din a n-a mișcare: când jucătorul poate transfera adversarul într-o poziție pierzătoare:

Indicăm, de asemenea, pozițiile pierdute din a doua mișcare: jucătorul care se găsește într-o astfel de poziție poate trece doar în pozițiile câștigătoare (atunci adversarul va câștiga):

Logica de raționament: Vanya va putea câștiga cu prima sau a doua sa mutare, când Petya cu prima sa mutare poate lovi numai fie la o poziție câștigătoare de la prima mutare (+), fie la o poziție câștigătoare de la a doua mutare sau la a n-a mutare (2+). Aceasta este poziția la S = 14:

Raspunsul 3: S=14 (La examen, explicați mișcările, referindu-vă la explicațiile din paragrafele precedente)

Sarcina #26 a fost nouă. Această sarcină aparține clasei (C3) - nivel înalt. Mai jos este textul temei:

P-08. Doi jucători, Petya și Vanya, joacă următorul joc. Este dat un anumit set de lanțuri simbolice („cuvinte”), în care niciunul dintre cuvinte nu este începutul altuia (condiția Fano este îndeplinită). Jocul începe cu o linie goală, la sfârșitul căreia jucătorii adaugă pe rând litere, câte o literă pe tură, astfel încât lanțul rezultat la fiecare pas să fie începutul unuia dintre cuvintele date. Petya face prima mișcare. Prima persoană care formează un cuvânt dintr-un set dat câștigă.

Exemplu. Lasă cuvintele (MAC, SAPUN, CADRU, CANCER) să fie date. La prima mișcare, Petya poate scrie litera M sau R. Lasă-l să scrie litera M. Ca răspuns, Vanya poate scrie A sau Y. În primul caz, se obține MA, iar Petya, după ce a adăugat litera K, primește cuvântul MAC din setul dat și câștigă. În al doilea caz, se dovedește WE, Petya este forțată să adauge L și Vanya va câștiga la a doua mutare, adăugând O și obținând cuvântul SOAP.

Exercitiul 1.

a) Determinați care dintre jucători are o strategie câștigătoare pentru tastarea cuvintelor (JAM, COW). Descrieți această strategie. Determinați câte jocuri diferite pot fi jucate cu această strategie și ce cuvânt va fi obținut în fiecare caz.

b) Determinați care dintre jucători are o strategie câștigătoare pentru tastarea cuvintelor (NUBNUB ... NUB, PUMAPUMA ... PUMA ). Primul cuvânt repetă de 55 de ori cuvântul NUB, iar al doilea cuvânt repetă de 32 de ori cuvântul PUMA. Descrieți această strategie. Determinați câte jocuri diferite pot fi jucate cu această strategie și ce cuvânt va fi obținut în fiecare caz.

Sarcina 2

În setul de cuvinte din sarcina 1a, schimbați două litere în orice cuvânt, astfel încât celălalt jucător să aibă o strategie câștigătoare. Descrieți această strategie. Determinați câte jocuri diferite pot fi jucate cu această strategie și ce cuvânt va fi obținut în fiecare caz.

Sarcina 3

Se dă un set de cuvinte (MOROKA, MORS, FROST, PLAHA, DRESS, SIGIL). Care jucător are o strategie câștigătoare? Dați sub forma unei figuri sau a unui tabel un arbore cu toate jocurile posibile cu această strategie.

1)Să presupunem mai întâi că există un cuvânt în set. Dacă jucătorii adaugă o literă de fiecare dată, atunci este evident că primul dintre ei (Petya) va adăuga toate literele impare, iar al doilea (Vanya) va adăuga toate literele pare. Astfel, dacă cuvântul are un număr impar de litere, Petya va câștiga, iar dacă există un număr par, Vanya va câștiga.

2)Dacă există mai multe cuvinte, atunci strategia lui Petya este să aleagă întotdeauna o astfel de continuare, în care, ca urmare, se va obține un cuvânt cu un număr impar de litere, iar Vanya, dimpotrivă, ar trebui să încerce să sară la un cuvânt. cu un număr par de litere.

3)Sarcina 1a. Cuvântul JAM are 7 litere (un număr impar, Petya va câștiga), iar cuvântul COW are 6 litere (un număr par, Vanya va câștiga). Petya merge prima și poate scrie litera B. Deoarece cuvântul COW începe cu o altă literă, Vanya va fi forțată să „meargă” conform cuvântului JAM și să piardă. Această opțiune este singura, adică este posibil un singur joc, în care Petya își urmează strategia, se termină cu cuvântul JAM.