Computer Science Unified State Exam 26 cuvinte atribuire. Teoria jocului. Găsirea unei strategii câștigătoare

Cea mai dificilă parte a acestei probleme este scrierea corectă și logică a soluției.

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

Avem două mormane de pietre și doi jucători: primul (Petya) și al doilea (Vanya).
Jucătorii se fac pe rând.
Î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ă.
De îndată ce există 73 sau mai multe pietre în grămadă, jocul se termină.
Ultimul care merge câștigă.

Notite importante

În unele sarcini vom construi un arbore de petreceri. Suntem obligați să facem acest lucru conform condiției numai din Sarcina 3. În Sarcina 2 noi nu obligat construi un copac de petrecere.
În fiecare dintre sarcini, nu este suficient să spunem pur și simplu cine are strategia câștigătoare. De asemenea, trebuie să o descrieți și să indicați numărul posibil de pași care vor fi necesari pentru a câștiga.
Nu este suficient să numești o strategie câștigătoare. Trebuie sa dovedi că duce la câștig. Chiar și declarațiile evidente necesită dovezi.

Exercitiul 1.

Să luăm acum în considerare Sarcina 1. Există (6, 33) pietre în grămezi (prima parte a Sarcinii 1) și (8, 32) pietre (a doua parte a Sarcinii 1). Trebuie să stabilim ce jucător are o strategie câștigătoare. Cu alte cuvinte, care jucător, dacă este jucat corect, va câștiga cu siguranță, indiferent de acțiunile adversarului.

Aici și mai departe vom împărți soluția în două părți. Mai întâi va exista o explicație preliminară (nu este nevoie să o scrieți în Examenul de stat unificat), apoi - o „decizie formală”, adică ceea ce trebuie scris pe formularul de examen de stat unificat în sine.

Discuţie.

Să ne gândim: primul jucător evident nu poate câștiga într-o singură mișcare, deoarece indiferent ce face, totalul nu va fi 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) este 72 de pietre, nu 73. Aceasta înseamnă că prima poate fi câștigată în mod clar într-o singură mișcare. nu poti. Cu toate acestea, al doilea este destul de capabil. Prima poate face patru acțiuni: 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). 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). 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). 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). 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.

Rezolvă în mod similar cu (8.32).

Soluție oficială la Sarcina 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. Când primul jucător se întoarce, vom lua în considerare patru opțiuni posibile pentru comportamentul său: adăugați 1 la primul teanc, dublați numărul de pietre din primul teanc, adăugați 1 la al doilea teanc, dublați numărul de pietre din al doilea teanc. Pentru cel de-al doilea jucător, vom indica câte o mișcare care duce la câștig. 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, de la stânga la dreapta, 73, 80). , 74 și, respectiv, 136). Mai mult, conform arborelui jocului, al doilea jucător poate câștiga într-o singură mișcare.

Sarcina 2

Soluție formală

Luați în considerare poziția inițială (6,32). Rețineți că este aproape de (6,33) din Task 1. În Task 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) se afla cel care castiga intr-o miscare Nu umblă (adică merge al doilea). Sau, cu alte cuvinte, cel care se mișcă pierde într-o singură mișcare.

Pe 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 mișcare în conformitate cu Arborele de petrecere din Sarcina 1, acționând conform strategiei Vanyei.

La fel în poziție (7, 32). Cu prima sa mutare, Petya 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 mișcarea 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). Cu prima sa mutare, Petya 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 mișcarea 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ă, 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. Mai mult, poate câștiga atât în 2 mutări (primele două cazuri), cât și într-o singură mișcare (al doilea caz).

Soluție formală

Î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, vom construi un copac al tuturor părților.

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

Conform arborelui tuturor jocurilor, Vanya câștigă fie într-o singură mișcare (dacă Petya a dublat numărul de pietre din prima sau a doua grămadă), fie în două mișcări (dacă Petya a crescut numărul de pietre din prima sau a doua grămadă cu 1) .

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 IT, profesor de informatică

Lecția a acoperit analiza sarcinii 26 a Examenului de stat unificat în informatică: dat explicatie detaliatași soluție la misiunea din 2017

A 26-a sarcină - „Teoria jocurilor, căutarea unei strategii câștigătoare” - este caracterizată ca o sarcină de un nivel ridicat de complexitate, timp de finalizare - aproximativ 30 de minute, scor maxim - 3

* Unele imagini și exemple de pagini sunt preluate din materialele de prezentare ale lui K. Polyakov

Teoria jocului. Găsirea unei strategii câștigătoare

Pentru a rezolva sarcina 26, trebuie să vă amintiți următoarele subiecte și concepte:

Strategia câștigătoare

pentru a găsi o strategie câștigătoare în jocurile simple, este suficient să folosiți metoda de enumerare a tuturor opțiunilor posibile pentru mișcările jucătorului;
pentru a rezolva probleme 26 de sarcini sunt cel mai des folosite pentru aceasta metoda de construire a copacilor;
dacă două ramuri se extind de la fiecare nod al arborelui, i.e. opțiuni posibile pentru mișcări, atunci se numește un astfel de arbore binar(dacă există trei opțiuni de continuare din fiecare poziție, arborele va fi ternar).

Câștigă și pierde poziții

toate pozitiile in jocuri simpleîmpărțit în câștig și pierdere;
poziție câștigătoare– aceasta este o poziție în care jucătorul care face prima mutare va câștiga cu siguranță indiferent de ceea ce face adversarul, cu excepția cazului în care greșește; în același timp ei spun că acest jucător are strategie învingătoare– un algoritm de alegere a următoarei mișcări care îi permite să câștige;
dacă jucătorul care face prima mișcare este în pierderea poziţiei, atunci va pierde cu siguranță dacă adversarul său nu face o greșeală; în acest caz se spune că acest jucător are nici o strategie câștigătoare; Astfel, strategia generală a jocului este de a crea o poziție pierzătoare pentru adversarul tău cu mutarea ta;
pozițiile câștigătoare și pierdute sunt caracterizate după cum urmează:
o poziție din care toate mișcările posibile duc la poziții câștigătoare – pierzând;
o poziție din care cel puțin una dintre mișcările posibile ulterioare duce la o poziție pierdută - învingătoare, iar strategia jucătorului este să transformă jocul într-unul învins(pentru adversar) poziţie.

Cine va câștiga cu un joc corect strategic?

pentru a determina ce jucător va câștiga cu un joc corect strategic, este necesar să răspundeți la întrebările:
Poate orice jucător să câștige, indiferent de mișcările celorlalți jucători?
Ce trebuie să facă un jucător cu o strategie câștigătoare la prima sa mutare pentru a putea câștiga, indiferent de acțiunile mutărilor jucătorilor?

Să ne uităm la un exemplu:

Un joc: sunt 5 chibrituri într-o grămadă; jucat de doi jucători care scot pe rând chibriturile din grămadă; condiție: într-o singură mișcare poți elimina 1 sau 2 chibrituri; Câștigătorul este cel care lasă 1 meci în teanc

Soluţie:

Răspuns: cu jocul corect (strategia de joc), primul jucător va câștiga; Pentru a face acest lucru, trebuie să elimine doar un meci cu prima sa mutare.

Rezolvarea a 26 de sarcini Unified State Exam în informatică

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

Doi jucători, Pasha și Valya, 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 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 există 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) La ce valori ale numărului S Poate Pașa să câștige într-o singură mișcare? Enumerați toate aceste valori și mișcările corespunzătoare ale lui Pașa.
b) Ce jucător are o strategie câștigătoare când 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
Ce jucător are o strategie câștigătoare când S=11? Construiți un arbore cu toate jocurile posibile cu această strategie câștigătoare (sub forma unei imagini sau a unui tabel). Pe marginile copacului indicați cine face mișcarea; în noduri - numărul de pietre în poziție.

✍ Soluție:

Pentru o explicație detaliată a sarcinii 26 a examenului de stat unificat, urmăriți videoclipul:

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

Petya și Vanya joacă un joc: există un set de cuvinte, trebuie să denumești în mod constant literele acestor cuvinte. Câștigătorul este 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, Petya poate numi litera cu prima sa mișcare ÎN, ȘI sau CU. Dacă Petya alege litera ÎN, apoi Vanya va câștiga (următoarele mișcări: Petya - ÎN, Vania - DESPRE, Petru - L, Vania - LA).

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

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

Sarcina 2
Este necesar să schimbați două litere din setul de articole 1Aîn cuvântul cu lungimea cea mai scurtă astfel încât strategia câștigătoare să fie celălalt jucător. Explicați o strategie 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.

✍ Soluție:

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

Pentru mai multe detalii despre rezolvarea problemei cuvântului, urmăriți tutorialul video:

Soluția 26. Versiunea demonstrativă a computerului Unified State Exam 2018:

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ă în care vor fi 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 cu 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 jocuri diferite de la adversar. Descrierea strategiei câștigătoare nu o face includeți mișcările unui jucător care joacă în conformitate cu această strategie care nu sunt câștigătoare necondiționate pentru el, de ex. nu câștigă 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, astfel încât Petya să nu poată câștiga într-o singură mișcare, dar pentru orice mișcare pe care o face Petya, Vanya poate câștiga cu prima sa mutare. Descrie strategia de câștig a Vanyei.

Sarcina 2
Specificați două astfel de valori ale lui S pentru care Petya are o strategie câștigătoare și:
— 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 date ale lui S, descrieți strategia câștigătoare a lui Petit.

Sarcina 3
Specificați valoarea lui S la care:
— Vanya are o strategie de câștig care îi permite să câștige cu prima sau a doua mișcare în oricare dintre jocurile lui Petya;
— Vanya nu are o strategie care să-i permită să i se garanteze că va câștiga la prima sa 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 imagini 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 dacă jucătorul câștigător își implementează strategia câștigătoare. De exemplu, arborele complet al jocului nu este răspunsul corect la această sarcină.

✍ Soluție:

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 cu 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 cu prima sa 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 Vanya) nu poate câștiga, dar adversarul său (adică Petya) va câștiga la următoarea sa mutare.

S = 7 Petya: 7 * 2 = 14 pierdere poziție (vezi punctul 1 b). Petya câștigă S = 13 Petya: 13 + 1 = 14 pierde poziție (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ă sunt 24 dintre ele în grămada, Vanya va dubla numărul de pietre și va câștiga la prima ei mișcare. Situația în care există 13 pietre în grămadă este tratată în paragraful 2. În această situație, jucătorul care se va muta (acum aceasta 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în mișcare!

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

Arborele tuturor jocurilor posibile cu strategia lui Vanya:

*cercul 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ă tură, un jucător poate adăuga la grămadă unu sau patru piatră sau măriți de cinci ori numărul de pietre dintr-o grămadă. Jocul se termină când numărul de pietre 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 valorile numărului S pentru care Pașa poate câștiga într-o singură mișcare. Justificați că toate valorile necesare ale lui S au fost găsite și indicați mutarea câștigătoare pentru fiecare valoare specificată a lui S.

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

Sarcina 2. Specificați 2 astfel de 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 cu a doua mutare, indiferent de modul în care se mișcă Vasya. Pentru fiecare valoare a lui S dată, 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 cu prima sau a doua mutare în orice joc de Pașa, iar Vasya nu are o strategie care să îi permită să câștige cu prima mutare. Pentru valoarea specificată 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 imagini sau a unui tabel).

✍ Soluție:

S ≥ 14

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 în grămadă.

S = 13 Pașa 1-a mutare: 13 + 1 = 14 Pașa 1-a mutare: 13 + 4 = 17 Pașa 1-a mutare: 13 * 5 = 65 Vanya 1-a 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ă care jocul se reduce la strategia descrisă în paragraful 1b.

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

3. S=8. Cu 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ă cu 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 clauza 2.

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

Urmăriți videoclipul pentru soluția sarcinii 26:

Simulator de examen de stat unificat în informatică 2018, versiunea de testare 1. Sarcina 26 (Krylov S., Ushakov D.):

o piatră sau . Jocul se termină în momentul în care 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 primit o astfel de poziție încât grămezii să conțină 73 de pietre sau mai mult.

Exercitiul 1.
(6, 33), (8, 32) indicați ce jucător 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 cel mai mare număr de mișcări pe care un câștigător ar putea avea nevoie pentru a câștiga cu această strategie.

Sarcina 2.
Pentru fiecare dintre pozițiile de start (6, 32), (7, 32), (8, 31) indicați ce jucător are o strategie câștigătoare.

Sarcina 3.
Pentru pozitia de pornire (7, 31) indicați ce jucător are o strategie câștigătoare. Construiește un arbore cu toate jocurile posibile cu strategia câștigătoare pe care ai specificat-o. Imaginați-vă copacul ca pe o imagine sau o masă.

✍ Soluție:

Soluție video pentru sarcina 26 cu două grămezi:

26_6: 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ă grămezi de pietre. Jucătorii se pe rând, Petya face prima mișcare. Într-o singură tură, un jucător 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ă în momentul în care numărul total de pietre din grămezi devine cel putin 44.
Câștigătorul este jucătorul care a făcut ultima mișcare, adică. primul care a obținut o astfel de poziție încât grămezii să conțină 44 sau mai multe pietre.

La momentul inițial, în prima grămadă a existat 5 pietre, în a doua grămadă - S pietre; 1 ≤ S ≤ 38.
Exercitiul 1.
La ce S: 1a) Petya câștigă cu prima sa mișcare; 1b) Vanya câștigă cu prima lui mișcare?

Sarcina 2.
Denumiți orice valoare S, în care Petya poate câștiga cu a doua sa mutare.

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

✍ Soluție:

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

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

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

Sarcina 1 b):

Deoarece Vanya va merge pe locul al doilea, este necesar să schimbați numărul de pietre din prima grămadă. Deci, să luăm în considerare situațiile în care Petya ar putea face prima mutare (7;S) si in (10;S). Să indicăm dacă aceste poziții vor fi câștigătoare într-o singură mișcare: de exemplu (7;19) poziție câștigătoare pentru că jucătorul va face o mutare (7;38) și va câștiga (7 + 38 = 45). În consecință, toate pozițiile sunt câștigătoare (7;mai mult de 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 mutare, în timp ce Petya cu prima sa mutare se poate muta în poziții câștigătoare doar de la prima mutare (în +). Să marchem aceste poziții, ținând cont de faptul că aceasta este prima mișcare a lui Petya, iar numărul de pietre din prima grămadă ar trebui să fie 5. Pozițiile găsite vor fi poziții în pierdere (-):

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

Răspunsul 1 b): S=19 (La examenul de stat unificat, 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âștiga peste tot cu următoarea mișcare, vezi paragraful anterior)

Sarcina 2:

Vă rugăm să rețineți că în tabel, toate „colțurile” rezultate sunt poziții pierdute (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âștiga la următoarea mișcare):

Logica raționamentului: Petya va putea câștiga cu a doua sa mutare atunci când cu prima sa mutare va ajunge într-o poziție pierzătoare, adică. va pune adversarul într-o situație de pierdere. Aceste valori sunt: 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:

Să indicăm, de asemenea, în tabel, pozițiile care sunt câștigătoare de la a n-a mutare: când un jucător poate transfera adversarul într-o poziție pierzătoare:

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

Logica raționamentului: Vanya poate câștiga cu prima sau a doua mișcare, când Petya poate lovi cu prima sa mutare 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 a n-a mutare (2+). Aceasta este poziția la S = 14:

Raspunsul 3: S=14 (La examenul de stat unificat, explicați mișcările, referindu-vă la explicațiile din paragrafele anterioare)

Analiza sarcinii 26 a examenului de stat unificat 2017 în informatică din versiunea demo. Aceasta este o sarcină din a doua parte a unui nivel ridicat de dificultate. Timpul aproximativ pentru finalizarea sarcinii este de 30 de minute. Punctajul maxim pentru îndeplinirea sarcinii este 3.

Elemente de conținut verificate:
— Abilitatea de a construi un arbore de joc conform unui algoritm dat și de a justifica o strategie câștigătoare.

Sarcina 26

Doi jucători, Pasha și Valya, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se pe rând, Pașa face prima mișcare. Într-o singură tură, un jucător 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ă în momentul în care numărul de pietre din teanc devine cel puțin 20. Dacă în același timp nu sunt mai mult de 30 de pietre în teanc, atunci jucătorul care a făcut ultima mutare este considerat câștigător. În caz contrar, adversarul său devine câștigător. De exemplu, dacă erau 17 pietre în grămadă și 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 era în grămada S pietre, 1 ≤ S ≤ 19.

Vom spune că jucătorul are strategie învingătoare, dacă poate câștiga cu 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 jocuri diferite de la adversar.

Finalizați următoarele sarcini.
1. a) La ce valori ale numărului S Poate Pașa să câștige într-o singură mișcare?
Enumerați toate aceste valori și mișcările corespunzătoare ale lui Pașa.
b) Ce jucător are o strategie câștigătoare când S = 18, 17, 16?
Descrieți strategiile câștigătoare pentru aceste cazuri.
2. Ce jucător are o strategie câștigătoare când S= 9,8? Descrieți strategiile de câștig relevante.
3. Ce jucător are o strategie câștigătoare când S= 7? Construiți un arbore cu toate jocurile posibile cu această strategie câștigătoare (sub forma unei imagini sau a unui tabel). Pe marginile copacului indicați cine face mișcarea; în noduri – numărul de pietre în poziție.

1. a) Pașa poate câștiga dacă S= 19 sau S= 10, 11, 12, 13, 14, 15. Când S= 19 prima mutare este să adăugați o piatră la grămadă, cu valorile rămase indicate S trebuie să dublezi numărul de pietre.

b) Când S= 16, 17 sau 18, dublarea numărului de pietre nu are sens, deoarece după o astfel de mutare adversarul câștigă. Prin urmare, putem presupune că singura mișcare posibilă este să adăugați o piatră la grămadă.

La S= 18 după o astfel de mutare a lui Pașa vor fi 19 pietre în grămadă. În această poziție, cel care merge (adică Valya) câștigă (a se vedea punctul 1a): la S= 18 Pașa (jucătorul care trebuie să meargă primul) pierde.

Valya are o strategie câștigătoare.

La S= 17, după ce Pașa adaugă o piatră cu prima sa mișcare, vor fi 18 pietre în grămadă. În această poziție, jucătorul (adică Valya) pierde (Vezi deasupra): la S= 17 Pașa (jucătorul care trebuie să meargă primul) câștigă. Pașa are o strategie câștigătoare.

La S= 16 Valya are o strategie câștigătoare. Într-adevăr, dacă Pașa dublează numărul de pietre la prima sa mișcare, atunci teancul devine 32 de pietre, iar jocul se termină imediat cu Vali câștigând. Dacă Pașa adaugă o piatră, atunci grămada devine 17 pietre. După cum știm deja, în această poziție jucătorul care trebuie să se miște (adică Valya) câștigă.

În toate cazurile, câștigul este obținut prin faptul că în timpul mutării sale, jucătorul cu o strategie câștigătoare trebuie să adauge o piatră la grămadă.

Este posibil să desenați arbori pentru toate părțile posibile pentru valorile specificate S.
O altă posibilitate este să (1) să subliniezi că dublarea grămezii nu are sens și (2) să reducă cazul secvenţial S= 18 per caz S= 19, caz S= 17 – la ocazie S= 18 etc.

2. Când S= 9 sau 8 Pașa are o strategie câștigătoare. Constă în dublarea numărului de pietre din grămadă și obținerea unui morman care va avea 18 sau, respectiv, 16 pietre. În ambele cazuri, jucătorul care face mutarea (acum Valya) pierde (a se vedea punctul 1b).

3. Când S= 7 Valya are o strategie câștigătoare. După prima mișcare a lui Pașa, grămada poate avea fie 8, fie 14 pietre. În ambele poziții, jucătorul care face mutarea (acum Valya) câștigă. Se întâmplă S= 8 considerate la punctul 2, caz S= 14 recenzate la punctul 1a.

Tabelul arată arborele de jocuri posibile pentru strategia descrisă de Vali. Pozițiile finale (Valya câștigă în ele) sunt subliniate. În figură, același copac este reprezentat grafic (ambele moduri de a reprezenta un copac sunt acceptabile).

Arborele tuturor jocurilor posibile în strategia lui Valya. Semnul >> indică pozițiile în care se termină jocul.

Doi jucători, Pasha și Vova, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se pe rând, Pașa face prima mișcare. Într-o singură tură, un jucător poate adăuga 1 piatră sau 10 pietre la grămadă. De exemplu, având o grămadă de 7 pietre, într-o singură mișcare poți obține o grămadă de 8 sau 17 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 teanc devine cel puțin 31. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 31 sau mai multe pietre.

La momentul inițial erau pietre S în grămadă, 1 ≤ S ≤ 30.

Soluţie.

1. a) Pașa poate câștiga dacă S = 21, ..., 30. Cu valori mai mici ale lui S, într-o singură mișcare este imposibil să obții o grămadă cu mai mult de 30 de pietre. Pașa trebuie doar să mărească numărul de pietre cu 10. Pentru S 1. b) Vova poate câștiga la prima mișcare (indiferent cum joacă Pașa) dacă grămada conține inițial S = 20 de pietre. Apoi, după prima mișcare a lui Pașa, vor fi 21 de pietre sau 30 de pietre în grămadă. În ambele cazuri, Vanya crește numărul de pietre cu 10 și câștigă într-o singură mișcare.

2. Valori posibile ale lui S: 10, 19. În aceste cazuri, Pașa, evident, nu poate câștiga cu prima sa mutare. Cu toate acestea, poate obține o grămadă de 20 de pietre (la S=10 crește numărul de pietre cu 10; la S=19 adaugă 1 piatră). Această poziție este discutată în paragraful 1 b. În ea, jucătorul care se va muta (acum acesta este Vova) nu poate câștiga, dar adversarul său (adică Pașa) va câștiga la următoarea mutare.

3. Valoarea posibilă a lui S: 18. După prima mișcare a lui Pașa, vor fi 19 sau 28 de pietre în grămadă. Dacă sunt 28 de pietre în grămadă, Vova va crește numărul de pietre cu 10 și te joci cu prima ta mișcare. Situația în care există 19 pietre într-o grămadă este tratată în paragraful 2. În această situație, jucătorul care se va muta (acum acesta este Vova) câștigă cu a doua mutare.

Oaspete 26.05.2014 12:31

Punctul 3. Dar cum rămâne cu situația când inițial sunt 9 pietre în grămadă. După mutarea lui Pașa, pietrele devin fie 10, fie 19, Vasya termină până la 20 și mai departe conform punctului 1.b.

Constantin Lavrov

Da, 9 este și răspunsul corect. Este suficient să indicați cel puțin o valoare corectă.

Doi jucători, Pasha și Vova, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se pe rând, Pașa face prima mișcare. Într-o singură tură, un jucător poate adăuga 1 piatră sau 10 pietre la grămadă. De exemplu, având o grămadă de 7 pietre, într-o singură mișcare poți obține o grămadă de 8 sau 17 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 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.

Finalizați următoarele sarcini. În toate cazurile, justificați răspunsul.

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ă toate valorile necesare ale lui S au fost găsite și indicați mișcările câștigătoare.

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

2. Indicați două 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, dar poate câștiga cu a doua mutare, indiferent de modul în care se mișcă Vova. Pentru valorile date ale lui S, descrieți strategia de câștig a lui Pasha.

3. Indicați valoarea lui S la care Vova are o strategie câștigătoare care îi permite să câștige cu prima sau a doua mutare în orice joc de Pașa, dar Vova nu are o strategie care să îi permită să câștige cu prima mutare. Pentru valoarea specificată a lui S, descrieți strategia câștigătoare a lui Vova. Construiește un arbore cu toate jocurile posibile cu această strategie câștigătoare a Vova (sub formă de imagine sau tabel). Pe marginile copacului indicați cine face mișcarea, iar la noduri - numărul de pietre din grămadă.

Soluţie.

1. a) Pașa poate câștiga dacă S = 31, ..., 40. Cu valori mai mici ale lui S, într-o singură mișcare este imposibil să obții o grămadă cu mai mult de 40 de pietre. Pașa trebuie doar să mărească numărul de pietre cu 10. Cu S b) Vova poate câștiga la prima mișcare (indiferent cum joacă Pașa) dacă teancul conține inițial S = 30 de pietre. Apoi, după prima mișcare a lui Pașa, vor fi 31 de pietre sau 40 de pietre în grămadă. În ambele cazuri, Vanya crește numărul de pietre cu 10 și câștigă într-o singură mișcare.

2. Valori posibile ale lui S: 20, 29. În aceste cazuri, Pașa, evident, nu poate câștiga cu prima sa mutare. Cu toate acestea, poate obține o grămadă de 30 de pietre (pentru S = 20 crește numărul de pietre cu 10; pentru S = 29 adaugă 1 piatră). Această poziție este discutată în paragraful 1. b). În ea, jucătorul care se va muta (acum acesta este Vova) nu poate câștiga, dar adversarul său (adică Pașa) va câștiga la următoarea mutare.

3. Valoarea posibilă a lui S: 28. După prima mișcare a lui Pașa, vor fi 29 sau 38 de pietre în grămadă. Dacă grămada ajunge la 38 de pietre, Vova va crește numărul de pietre cu 10 și te joci cu prima ta mișcare. Situația în care există 29 de pietre într-o grămadă este tratată în paragraful 2. În această situație, jucătorul care se va muta (acum acesta este Vova) câștigă cu a doua mutare.

Tabelul arată arborele de jocuri posibile pentru strategia lui Vova descrisă mai sus. Pozițiile finale (Vova câștigă în ele) sunt subliniate. În figură, același copac este reprezentat grafic (ambele moduri de a reprezenta un copac sunt acceptabile).

Doi jucători, Petya și Vanya, joacă următorul joc. În fața lor se află două grămezi de pietre, dintre care primul conține 2, iar al doilea - 3 pietre. Fiecare joc are o mulțime de pietre. Jucătorii se pe rând, Petya făcând prima mișcare. Mutarea constă în faptul că jucătorul fie scoate numărul de pietre dintr-o grămadă, fie adaugă 4 pietre la o grămadă. Jocul se termină în momentul în care numărul total de pietre din două grămezi este de cel puțin 31. Dacă în momentul în care jocul se termină, numărul total de pietre din două grămezi este de cel puțin 40, atunci Petya a câștigat, în caz contrar Vanya a câștigat. Cu cine joci când ambii jucători joacă fără eroare? Care ar trebui să fie prima mișcare a jocului tău? Explicați răspunsul.

Soluţie.

Vanya câștigă.

Pentru a demonstra acest lucru, luați în considerare un arbore de joc incomplet, conceput sub forma unui tabel, în care fiecare celulă conține perechi de numere separate prin virgulă. Aceste numere corespund numărului de pietre din fiecare etapă a jocului din primul și, respectiv, al doilea teanc.

Tabelul conține toate mișcările posibile ale primului jucător. Arată că pentru orice mutare a primului jucător, al doilea are o mutare care duce la victorie.

Doi jucători, Petya și Vasya, joacă următorul joc. În fața lor se află două grămezi de pietre, dintre care primul conține 2, iar al doilea - 1 piatră. Fiecare jucător are un număr nelimitat de pietre. Jucătorii se pe rând, Petya merge prima. Mișcarea este că jucătorul fie crește numărul de pietre dintr-o grămadă de 3 ori, fie adaugă 3 pietre la o grămadă. Câștigă jucătorul, după a cărui mișcare există cel puțin 24 de pietre într-una dintre grămezi. Cine câștigă când joacă fără erori? Care ar trebui să fie prima mutare a jucătorului câștigător?

Justificati raspunsul.

Soluţie.

Petya câștigă; cu prima sa mișcare trebuie să tripleze numărul de pietre din a doua grămadă. Pentru a demonstra acest lucru, luați în considerare un arbore de joc incomplet, conceput sub forma unui tabel, în care fiecare celulă conține perechi de numere separate prin virgulă. Aceste numere corespund numărului de pietre din fiecare etapă a jocului din primul și, respectiv, al doilea teanc.

Tabelul conține toate opțiunile posibile pentru mișcările lui Vasya. Arată că, cu orice răspuns, Petya are o mișcare care duce la victorie.

Jocul se termină în momentul în care numărul de pietre din grămadă devine mai mare de 100. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 101 sau mai multe pietre.

La momentul inițial erau pietre S în grămadă, 1 ≤ S ≤ 100.

Se spune că un jucător are o strategie câștigătoare dacă poate câștiga cu oricare dintre mișcările adversarului său. 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 inamicului.

Finalizați următoarele sarcini. În toate cazurile, justificați răspunsul.

1. a) Pentru ce valori ale numărului S poate câștiga Petya cu prima sa mutare? Enumeră toate aceste valori și mișcarea câștigătoare a lui Petit.

b) Indicați o valoare a lui S astfel încât Petya să nu poată câștiga într-o singură mișcare, dar pentru orice mișcare pe care o face Petya, Vanya poate câștiga cu prima sa mutare. Descrie strategia de câștig a Vanyei.

2. Specificați două valori ale lui S pentru care Petya are o strategie câștigătoare, iar Petya nu poate câștiga cu prima sa mutare, dar Petya poate câștiga cu a doua mutare, indiferent de modul în care se mișcă Vanya. Pentru valorile date ale lui S, descrieți strategia câștigătoare a lui Petit.

3. Indicați o valoare a lui S, astfel încât Vanya să aibă o strategie câștigătoare care îi permite să câștige cu prima sau a doua mișcare în orice joc Petya și, în același timp, Vanya nu are o strategie care să îi permită să câștige cu prima mișcare.

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. Prezentați-l sub forma unei imagini sau a unui tabel. Pentru fiecare margine a copacului, indicați cine face mișcarea; pentru fiecare nod, indicați numărul de pietre în poziție.

Soluţie.

1. a) Petya poate câștiga dacă S = 21, ..., 100. Cu valori mai mici ale lui S, într-o singură mișcare este imposibil să obții o grămadă cu mai mult de 100 de pietre. Pentru Petya, este suficient să crești numărul de pietre de 5 ori. Când S 1. b) Vanya poate câștiga cu prima mutare (indiferent cum joacă Petya), dacă inițial există S = 20 de pietre în grămadă. Apoi, după prima mișcare a lui Petya, vor fi 21 de pietre sau 100 de pietre în grămadă. În ambele cazuri, Vanya crește numărul de pietre de 5 ori și câștigă într-o singură mișcare.

2. Valori posibile ale lui S: 4, 19. În aceste cazuri, Petya, evident, nu poate câștiga cu prima sa mutare. Cu toate acestea, poate obține o grămadă de 20 de pietre (cu S = 4, el crește numărul de pietre de 5 ori; cu S = 19, adaugă 1 piatră). Această poziție este discutată în paragraful 1 b). În ea, jucătorul care se va muta (acum Vanya) nu poate câștiga, dar adversarul său (adică Petya) va câștiga la următoarea sa mutare.

3. Valoarea posibilă a lui S: 18. După prima mișcare a lui Petya, vor fi 19 sau 90 de pietre în grămadă. Dacă există 90 de pietre în grămadă, Vanya va crește numărul de pietre de 5 ori și va câștiga cu prima sa mișcare. Situația în care există 19 pietre în grămadă este tratată în paragraful 2. În această situație, jucătorul care se va muta (acum aceasta este Vanya) câștigă cu a doua mutare.

Tabelul arată arborele de jocuri posibile pentru strategia lui Vanya descrisă mai sus. Pozițiile finale (Vanya câștigă în ele) sunt subliniate. În figură, același arbore este reprezentat grafic (ambele metode de reprezentare sunt acceptabile).

Faceți teste pentru aceste sarcini

Deschidem un abonament la simulatoare interactive pentru pregătirea pentru examenul de stat unificat 2016 în informatică

Oricine are un portofel Visa, MasterCard, Yandex.Money și chiar și un sold pozitiv pe telefonul mobil poate comanda 60 de animații interactive unice pentru a se pregăti pentru examenul de stat unificat 2016 în informatică fără a părăsi computerul.

Simulator pentru sarcina nr. 26 a versiunii demo a examenului de stat unificat 2015.
în informatică și TIC folosind metoda „Hills and Holes”.

Cea mai simplă soluție la problema 26 sau vechiul C3
în informatică și TIC folosind metoda vizuală „Hills and Holes”.

Un exemplu de rezolvare a unei probleme în cazul creșterii pietrelor într-o grămadă în două moduri: „+1” și „*2”

Doi jucători, Petya și Vanya, joacă următorul joc. Există un morman de pietre în fața jucătorilor. Jucătorii se pe rând, Petya face prima mișcare. Într-o singură tură, un jucător poate adăuga o piatră la grămadă sau poate dubla 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 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 teanc devine cel puțin 22. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește o grămadă care conține 22 sau mai multe pietre.
La momentul inițial erau pietre S în grămadă, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Finalizați următoarele sarcini. În toate cazurile, justificați răspunsul.

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 au fost găsite și indicați mutarea câștigătoare pentru fiecare valoare specificată a lui S.
b) Indicați o valoare a lui S astfel încât Petya să nu poată câștiga într-o singură mișcare, dar pentru orice mișcare pe care o face Petya, Vanya poate câștiga cu prima sa mutare. Descrie strategia de câștig a Vanyei.

2. Specificați două astfel de valori ale lui S pentru care Petya are o strategie câștigătoare și
– Petya nu poate câștiga într-o singură mișcare și
– Petya poate câștiga cu a doua sa mișcare, indiferent de modul în care se mișcă Vanya.
Pentru fiecare valoare dată a lui S, descrieți strategia câștigătoare a lui Petit.

3. Specificați valoarea lui S la care:
– Vanya are o strategie de câștig care îi permite să câștige cu prima sau a doua mișcare în oricare dintre jocurile lui Petya și
– Vanya nu are o strategie care să-i permită să i se garanteze că va câștiga 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 această strategie câștigătoare a lui Vanya (sub forma unei imagini sau a unui tabel). Pe marginile copacului, indicați cine face mișcarea; la noduri, indicați numărul de pietre din grămadă.

Întrebarea 1a.
Lucrând înapoi de la „victorie”, determinăm limitele poziției inițiale câștigătoare: 22 – 1 = 21 Și 22/2 = 11
Pentru orice număr care se află în acest interval, următoarea intrare este valabilă: max0*2>= 22 sau max0*2 > 21 (încercuiește acest interval în partea de sus și notează-l ca max0, ceea ce va însemna poziția inițială de câștig sau câștig dintr-o singură mișcare)

1a) Petya câștigă cu prima sa mutare la 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Întrebarea 1b. Pentru a răspunde la această întrebare, trebuie să găsiți posturi, să le sunăm min0 , dintre care toate mișcările posibile duc la poziția inițială câștigătoare, marcată de noi ca max0 . În sens invers, determinăm pozițiile „suspectate” pe min0 :
11/2=? nu este complet divizat, prin urmare, nu există o astfel de poziție. Tot ce rămâne este S= 11-1=10
(dar deocamdată acest lucru este doar speculativmin0 , așa că hai să desenăm "groapă" două caracteristici, ceea ce va însemna - nu uitați de existența a 2 mișcări posibile care vor trebui verificate!)

Verificăm ipoteza pentru S = 10 la min0. Această verificare va servi drept răspuns la întrebarea 1b
Când S = 10, Petya are 2 mișcări cu care nu poate câștiga într-o singură mișcare, dar cu orice mutare a lui Petya, Vanya poate câștiga cu prima sa mutare:
Orice mutare a lui Petya „10+1=11” sau 10*2=20 duce la poziția inițială câștigătoare a Vaniei, care, după ce a dublat numărul de pietre din grămadă, obține 22 sau 40, care este mai mult de 21 și Vanya va câștiga
Prin urmare, conturăm poziția S = 10 de mai jos cu o linie continuă ( trage o gaură) - min0 (pierderea inițială sau pierderea pentru prima tură):

Răspuns la întrebarea 1b. poate fi așa: Cu S = 10, Petya are 2 mișcări cu care nu poate câștiga, dar cu orice mutare a lui Petya, Vanya poate câștiga cu prima sa mutare. Orice mutare a lui Petya „10+1=11” sau „10*2=20” o duce pe Vanya în poziția inițială de câștig, care, dublând numărul de pietre din grămadă, obține 22 sau 40, care este mai mult de 21 și Vanya învinge

intrebarea 2. Pentru ca Petya să fie garantat că va câștiga la a doua sa mutare, adică. s-a trezit în poziție max0 , după mutarea Vaniei, are nevoie de a lui primul mișcare " pune Vanya într-o gaură" Este clar că pot exista astfel de poziții Două, ale căror valori le găsim invers și asigurați-vă că le verificăm...
Prima poziție suspectă „10-1=9”

S=9. Să verificăm această poziție pentru a asigura victoria!
Dacă Petya ar fi jucat un giveaway, ar fi făcut o mișcare „9*2 = 18” , dar el trebuie să câștige, așa că renunțăm la această mișcare. Tot ce rămâne este „9+1 = 10”, iar Vanya se găsește în „groapă” - ceea ce îl face pe Petya să câștige la a doua sa mișcare, indiferent de cum iese Vanya!

A doua „poziție suspectă” 10/2 = 5

S=5. Să verificăm această poziție pentru a asigura victoria! Mișcare „5+1=6” ,întârzie jocul, așa că nu îl luăm în considerare (renunțați-l)
Tot ce rămâne este „5*2=10”, iar Vanya se găsește în "groapa" - ceea ce îl face pe Petya să câștige la a doua sa mișcare, indiferent de cum merge Vanya!

Răspunsul 2 ar putea fi:

Cu S = 5 și 9, Petya nu poate câștiga cu prima mutare, dar poate câștiga cu a doua mișcare, iar pentru aceasta trebuie doar să facă mutarea „5*2 = 10” din poziția S = 5, trimițând astfel Vanya în poziția inițială pierzătoare sau din poziția S = 9 trimite-l în aceeași poziție cu mutarea „9+1=10”

Întrebarea 3. Vanya trebuie să câștige, prin urmare el trebuie să fie în vârf max0, asta înseamnă că Petya trebuie să ajungă cu siguranță în min0, unde să mergem „va întemnița” Vanya din max1, Tot ce trebuie să facem este să găsim poziții în care Petya ar intra cu siguranță max1
Găsim poziții „suspecte” care l-ar putea conduce pe Petya max1 folosind același revers:
9-1=8
9/2=? 9 nu este divizibil cu 2 - dispare
5-1=4
5/2=? 5 nu este divizibil cu 2 - dispare
Găsim că așa "suspicios" Sunt doar două poziții, dar mai trebuie verificate!

S=8. Să verificăm această poziție pentru a vedea dacă Petya este garantat să piardă!
Mișcarea lui Petya este 8+1=9 și Vanya câștigă cu a doua mutare
Mișcarea lui Petya este 8*2=16 și Vanya câștigă cu prima sa mutare
S=4. Să verificăm această poziție pentru a vedea dacă Petya este garantat să piardă!
Mișcarea lui Petya este 4+1=5 și ar fi pierdut, dar din această poziție Petya beneficiază de mutarea 4*2=8, astfel Vanya cade în „gaura” și pierde. Dar trebuie să găsim strategia câștigătoare a lui Vanya, așa că excludem poziția S=4 din candidați și obținem finala "imagine":

3. În poziția S = 8 – Vanya nu are o strategie care să îi permită să câștige cu prima mutare, deoarece victoria lui depinde de mutarea lui Petya, așa că Vanya are o strategie pentru a câștiga fie cu prima, fie cu a doua mutare: Dacă Petya alege mutarea „+1”, grămada devine 9 pietre și Vanya câștigă la a 2-a mutare (vezi răspunsul la întrebarea 2). Dacă Petya alege mișcarea „*2”, Vanya câștigă cu prima sa mutare, dublând numărul de pietre din grămadă.

Imaginea pe care am primit-o mai sus poate fi redesenată cu ușurință în arborele jocului, marcând mai întâi mișcările pierdute cu linii roșii (linia groasă este „ cursă scurtă" sau " +1 ", și slab - " lung" sau " *2 ") și verde - câștigătoare. (pot fi trasate linii groase roșii cu cocoașe în sus, care vor coincide cu direcția ramurilor „scurte” ale arborelui de joc)

Imaginea strategică finală a victoriei lui Petit poate arăta astfel:

Alte metode de rezolvare a problemelor de acest tip pot fi găsite aici -

Computer Science Unified State Exam 26 cuvinte atribuire. Teoria jocului. Găsirea unei strategii câștigătoare

Exercitiul 1.

Sarcina 2

Sarcina 3

Teoria jocului. Găsirea unei strategii câștigătoare

Rezolvarea a 26 de sarcini Unified State Exam în informatică

Sarcina 26

Simulator pentru sarcina nr. 26 a versiunii demo a examenului de stat unificat 2015. în informatică și TIC folosind metoda „Hills and Holes”.

Cea mai simplă soluție la problema 26 sau vechiul C3 în informatică și TIC folosind metoda vizuală „Hills and Holes”.

Un exemplu de rezolvare a unei probleme în cazul creșterii pietrelor într-o grămadă în două moduri: „+1” și „*2”

Simulator pentru sarcina nr. 26 a versiunii demo a examenului de stat unificat 2015.
în informatică și TIC folosind metoda „Hills and Holes”.

Cea mai simplă soluție la problema 26 sau vechiul C3
în informatică și TIC folosind metoda vizuală „Hills and Holes”.