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.

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. Ultimul care merge câștigă.

Note importante

1. Î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.
2. Î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.
3. Nu este suficient să numești o strategie câștigătoare. Trebuie dovedi că duce la câștig. Chiar și declarațiile evidente necesită dovezi.

Sarcina 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 dintre jucători joc potrivit 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 pot. 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 jocului 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ă

Pentru o pregătire eficientă în informatică, pentru fiecare sarcină este oferit un scurt material teoretic pentru îndeplinirea sarcinii. Au fost selectate peste 10 sarcini de instruire cu analiză și răspunsuri, dezvoltate pe baza versiunii demo din anii precedenți.

Nu există modificări la examenul de stat unificat KIM 2020 în informatică și TIC.

Domenii în care vor fi testate cunoștințele:

• Programare;
• Algoritmizare;
• instrumente TIC;
• Activitati de informare;
• Procesele informaționale.

Acțiuni necesare când pregătire:

• Repetarea cursului teoretic;
• Soluţie testeîn informatică online;
• Cunoașterea limbajelor de programare;
• Îmbunătățiți matematica și logica matematică;
• Folosirea unei game mai largi de literatură - programa școlară pentru succes la examenul de stat unificat - nu este suficientă.

Structura examenului

Durata examenului este de 3 ore și 55 de minute (255 de minute), din care o oră și jumătate este recomandată a fi dedicată îndeplinirii sarcinilor din prima parte a KIM-urilor.

Sarcinile din bilete sunt împărțite în blocuri:

• Partea 1- 23 de sarcini cu răspuns scurt.
• Partea 2- 4 sarcini cu răspunsuri detaliate.

Din cele 23 de sarcini propuse pentru prima parte a lucrării de examen, 12 aparțin nivelului de bază al cunoștințelor de testare, 10 – complexității crescute, 1 – unui nivel ridicat de complexitate. Trei probleme din partea a doua nivel înalt complexitate, unul – crescut.

Atunci când luați o decizie, este necesar să înregistrați un răspuns detaliat (form liber).
În unele sarcini, textul condiției este prezentat în cinci limbaje de programare simultan - pentru confortul studenților.

Puncte pentru teme de informatică

1 punct - pentru 1-23 de sarcini
2 puncte - 25.
3 puncte - 24, 26.
4 puncte - 27.
Total: 35 de puncte.

Pentru a intra într-o universitate tehnică de nivel mediu, trebuie să obțineți cel puțin 62 de puncte. Pentru a intra la universitatea capitalei, numărul de puncte trebuie să corespundă cu 85-95.

Pentru a scrie cu succes o lucrare de examen, o cunoaștere clară a teorieși constantă practică în rezolvare sarcini.

Formula ta pentru succes

Lucrați + lucrați la greșeli + citiți cu atenție întrebarea de la început până la sfârșit pentru a evita greșelile = punctaj maxim la examenul de stat unificat în informatică.

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 animații interactive unice să te pregătești pentru examenul de stat unificat din 2016 în informatică fără să te ridici de pe computer

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ă, jucătorul 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. Indicaț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 poziții, să le numim 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 posibile mișcări 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Întrebarea 2 max0 . Pentru ca Petya să fie garantat că va câștiga la a doua sa mutare, adică. s-a trezit în poziție , după mutarea Vaniei, are nevoie de a lui primul muta" 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! 10/2 = 5

A doua „poziție suspectă” 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„9+1 = 10”, „5*2=10”,"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”. 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ă mergi „va întemnița” Vanya de la 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 "suspect" 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ă. Poza pe care am primit-o mai sus poate fi redesenată cu ușurință în arborele de joc, mai întâi marcând mișcările pierdute cu linii roșii (linia groasă este „ cursa scurta +1 " sau " ", și subțire - " cursa scurta *2 lung ") și verde - câștigătoare.

(liniile groase roșii pot fi trase 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: