Ispit iz informatike 26 zadataka riječi. Teorija igara. Pronalaženje pobjedničke strategije

U ovom zadatku najteži dio je ispravno i logično zapisati rješenje.

Dakle, hajde da počnemo pokušavajući da razumemo stanje.

  1. Imamo dvije gomile kamenja i dva igrača: prvog (Petya) i drugog (Vanya).
  2. Igrači se izmjenjuju.
  3. Tokom poteza, možete dodati jedan kamen na bilo koju gomilu ili udvostručiti broj kamenja u gomili.
  4. Čim se na hrpi nađu 73 ili više kamenčića, igra se završava.
  5. Pobijedio je onaj koji je posljednji otišao.

Važne napomene

  1. U nekim zadacima ćemo napraviti party drvo. To smo dužni da uradimo prema uslovu samo u zadatku 3. U zadatku 2 mi nije potrebno napravi party drvo.
  2. U svakom od zadataka nije dovoljno samo reći ko ima pobedničku strategiju. Također ga je potrebno opisati i navesti mogući broj koraka koji će biti potrebni za pobjedu.
  3. Strategiju nije dovoljno nazvati pobjedničkom. Treba dokazati da to vodi do pobede. Čak i očigledne izjave zahtijevaju dokaz.

Vježba 1.

Razmotrite sada zadatak 1. U hrpama - (6, 33) kamenje (prvi dio zadatka 1) i (8, 32) kamenje (drugi dio zadatka 1). Moramo odrediti koji igrač ima pobjedničku strategiju. Drugim riječima, ko će od igrača, ako se odigra korektno, sigurno pobijediti, bez obzira na postupke protivnika.

Ovdje i dolje ćemo rješenje podijeliti na dva dijela. Prvo će biti prethodno objašnjenje (nije potrebno pisati u USE), a zatim - "formalna odluka", odnosno šta treba napisati u samom obrascu USE.

Diskusija.

Zamislimo: prvi igrač očigledno ne može da pobedi u jednom potezu, jer šta god da uradi, neće ih biti ukupno 73. "Najveća" akcija koju može da uradi je da udvostruči broj kamenčića u drugoj hrpi, čineći ih 66. Ali (6, 66) je 72 kamena, a ne 73. Dakle, prvi u jednom potezu je očigledno da dobijete limenku ne. Međutim, drugi može. Prvi potencijalno može učiniti četiri stvari: dodati 1 prvoj hrpi, udvostručiti broj kamenja na prvoj hrpi, dodati 1 drugoj hrpi, udvostručiti broj kamenja na drugoj hrpi. Da vidimo kuda ovo vodi:

  • (6.33) -> (7.33). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (7, 66). Ukupno - 73. Dakle, drugi pobjeđuje.
  • (6.33) -> (12, 33). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (12, 66). Ukupno - 78. Dakle, drugi pobjeđuje.
  • (6.33) -> (6.34). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (6, 68). Ukupno - 74. Dakle, drugi pobjeđuje.
  • (6.33) -> (6.66). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (6, 132). Ukupno - 138. Dakle, drugi pobjeđuje.

Ukupno: bez obzira kako se prvi igrač ponaša, drugi će pobijediti u jednom potezu.

Slično se rješava sa (8.32).

Formalno rješenje zadatka 1.

Drugi igrač ima pobjedničku strategiju. Dokažimo to i pokažimo ovu strategiju. Da bismo to učinili, napravit ćemo partijsko stablo za svaku od početnih pozicija. U stablu igre ćemo naznačiti stanje obje gomile u formatu (a,b), gdje je a broj kamenčića u prvoj hrpi, b broj kamenčića u drugoj hrpi. Tokom poteza prvog igrača razmotrit ćemo četiri moguće opcije za njegovo ponašanje: dodati 1 na prvu hrpu, udvostručiti broj kamenčića u prvoj hrpi, dodati 1 na drugu hrpu, udvostručiti broj kamenčića u drugoj gomila. Za drugog igrača ćemo naznačiti po jedan potez, koji vodi do pobjede. Poteze ćemo prikazati u obliku strelica, pored kojih pišemo I u slučaju prvog poteza i II u slučaju drugog poteza.

Stablo igre za početnu poziciju (6, 33).

Stablo igre za početnu poziciju (8, 32).

Prema stablu igre, bez obzira na poteze prvog, drugi uvijek ima pobjedničku strategiju koja mu omogućava da pobijedi u jednom potezu, opisanom u stablima (zbirovi nakon Vanjinih poteza su 73, 80, 74 i 136, respektivno , s lijeva na desno). Istovremeno, prema stablu igre, drugi igrač može pobijediti u tačno jednom potezu.

Zadatak 2

formalna odluka

Razmotrimo početni položaj (6,32). Imajte na umu da je blizu (6.33) iz zadatka 1. U zadatku 1 smo saznali da na poziciji (6, 33) pobjeđuje drugi, i to u jednom potezu. Ovaj uslov se može preformulisati: u poziciji (6.33) onaj koji pobjeđuje u jednom potezu Ne hoda (odnosno hoda drugi). Ili, drugim riječima, onaj koji hoda gubi u jednom potezu.

U poziciji (6,32) prvi pobjeđuje u dva poteza. Dokažimo to. Na svom prvom potezu, Petya dodaje +1 na drugu gomilu. Tako se dobija pozicija (6.33). Kao što smo ranije saznali, u poziciji (6.33) gubi onaj koji se kreće. U našem slučaju, to će biti Vanjin potez. Stoga će Vanja izgubiti u jednom potezu. U ovom slučaju, Petya će morati napraviti ukupno dva poteza: prvi (dodati 1 kamen na drugu gomilu) + drugi potez u skladu sa Stablom igre u zadatku 1, djelujući prema Vanjinoj strategiji.

Slično u poziciji (7, 32). Petya, na svom prvom potezu, dodaje +1 kamen na prvu gomilu i dobija poziciju (8, 32). U ovoj poziciji, prema istom rezonovanju, gubi onaj koji se kreće. Biće Vanjinog poteza, pa će Vanja izgubiti. Petyina pobjednička strategija je sljedeća: Petya dodaje +1 kamen na prvu gomilu, a zatim slijedi Vanyinu strategiju iz zadatka 1.

Slično u poziciji (8, 31). Petya, u svom prvom potezu, dodaje +1 kamen na drugu gomilu i dobija poziciju (8, 32). U ovoj poziciji, prema istom rezonovanju, gubi onaj koji se kreće. Biće Vanjinog poteza, pa će Vanja izgubiti. Petyina pobjednička strategija je sljedeća: Petya dodaje +1 kamen na drugu gomilu, a zatim slijedi Vanyinu strategiju iz zadatka 1.

Zadatak 3

Diskusija

Imajte na umu da je iz situacije (7, 31) vrlo lako doći ili u situacije (8, 31) i (7, 32), u kojima, prema prethodnom zadatku, pobjeđuje onaj koji se kreće, ili u situaciju (14 , 31) i (7, 62), u kojima onaj koji se kreće može pobijediti u jednom potezu udvostručavajući broj kamenčića u drugoj hrpi. Tako se ispostavlja da Vanja mora imati pobjedničku strategiju. Istovremeno, može pobijediti i u 2 poteza (prva dva slučaja) i u jednom potezu (druga dva slučaja).

formalna odluka

Na početnoj poziciji (7, 31) Vanya pobjeđuje u jednom ili dva poteza. Dokažimo to. Da bismo to učinili, konstruiramo stablo svih strana.

Stablo svih igara za početnu poziciju (7, 31).

Prema stablu svih igara, Vanya pobjeđuje ili u jednom potezu (ako je Petya udvostručio broj kamenova u prvoj ili drugoj hrpi), ili u dva poteza (ako je Petya udvostručio broj kamenova u prvoj ili drugoj hrpi).

Tako na početnoj poziciji (7, 31) Vanja ima pobedničku strategiju, a Vanja će pobediti u jednom ili dva poteza.

Evgenij Smirnov

Stručnjak za informatiku, nastavnik informatike

Na času je razmatrana analiza 26. zadatka ispita iz informatike: dato detaljno objašnjenje i rješenje zadatka 2017


26. zadatak - "Teorija igara, potraga za pobedničkom strategijom" - karakteriše se kao zadatak visokog stepena složenosti, vreme izvođenja je oko 30 minuta, maksimalni rezultat je 3

* Neke slike i primjeri stranica preuzeti su iz prezentacijskih materijala K. Polyakova

Teorija igara. Pronalaženje pobjedničke strategije

Da biste riješili zadatak 26, morate zapamtiti sljedeće teme i koncepte:

    Pobjednička strategija

  • da bi se u jednostavnim igrama pronašla dobitna strategija, dovoljno je koristiti metod nabrajanja svih mogućih varijanti poteza igrača;
  • za rješavanje problema najčešće se za to koristi 26 zadataka način gradnje drveta;
  • ako od svakog čvora stabla odlaze dvije grane, tj. mogućim potezima, onda se takvo drvo zove binarni(ako postoje tri opcije za nastavak sa svake pozicije, stablo će biti ternarno).

    • Osvajanje i gubljenje pozicija

  • sve pozicije u jednostavne igre podijeljeni na dobitke i poraze;
  • pobednička pozicija- ovo je takva pozicija u kojoj će igrač koji napravi prvi potez sigurno pobijediti u bilo kojoj akciji protivnika, ako ne pogriješi; kaže se da ovaj igrač ima pobednička strategija- algoritam za odabir sljedećeg poteza, koji mu omogućava da pobijedi;
  • ako je igrač koji napravi prvi potez unutra gubljenje pozicije, onda će sigurno izgubiti ako njegov protivnik ne pogriješi; u ovom slučaju kažemo da ovaj igrač ima nema pobedničke strategije; dakle, opšta strategija igre je da se svojim potezom stvori izgubljena pozicija za protivnika;
  • Dobitne i izgubljene pozicije karakteriziraju se na sljedeći način:
  • pozicija iz koje svi mogući potezi vode do pobjedničkih pozicija gubljenje;
  • pozicija iz koje barem jedan od sljedećih mogućih poteza vodi u gubitnu poziciju - pobjeda, a strategija igrača je da pretvoriti igru ​​u ovaj gubitak(za protivnika) pozicija.

    • Ko pobjeđuje sa strateški ispravnom igrom?

  • da bi se utvrdilo ko će od igrača pobijediti u strateški ispravnoj igri, potrebno je odgovoriti na sljedeća pitanja:
  • Može li bilo koji igrač pobijediti, bez obzira na poteze drugih igrača?
  • Šta igrač sa pobedničkom strategijom treba da uradi na svom prvom potezu da bi mogao da pobedi, bez obzira na akcije poteza igrača?

Razmotrimo primjer:

Igra: ima 5 šibica na hrpi; igraju dva igrača, koji se naizmjenično vade šibice sa gomile; uslov: u jednom potezu možete ukloniti 1 ili 2 šibice; pobjeđuje onaj koji ostavi 1 šibicu na hrpi


Rješenje:

odgovor: sa pravilnom igrom (strategijom igre), prvi igrač će pobijediti; da bi to uradio, dovoljno je da prvim potezom ukloni jedan meč.

Rješavanje 26 USE zadataka iz informatike

Analiza 26. zadatka Jedinstvenog državnog ispita iz informatike 2017 FIPI opcija 5 (Krylov S.S., Churkina T.E.):

Dva igrača, Paša i Valja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju Paša pravi prvi potez jedan dvaput. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti gomilu od 14 ili 8 kamenčića. Svaki igrač ima neograničen broj kamenja da napravi potez.

Igra se završava kada broj kamenčića na hrpi postane najmanje 28 . Ako, u isto vrijeme, ne više od 44 kamenje, pobjednik je igrač koji je napravio posljednji potez. U suprotnom, njegov protivnik postaje pobjednik. Na primjer, ako je na hrpi bilo 23 kamena, a Pasha udvostruči broj kamenčića na hrpi, onda će se igra završiti i Valya će biti pobjednik. U početku je u gomili bilo S kamenja, 1≤S≤27.

Vježba 1
a) Za koje vrijednosti broja S Paša može da pobedi u jednom potezu? Navedite sve takve vrijednosti i odgovarajuće Pašine poteze.
b) Za koga od igrača ima pobjedničku strategiju S = 26, 25, 24? Opišite pobjedničke strategije za ove slučajeve.

Zadatak 2
S = 13, 12? Opišite relevantne pobjedničke strategije.

Zadatak 3
Za koga od igrača ima pobjedničku strategiju S=11? Konstruirajte stablo svih mogućih igara s ovom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima — broj kamenja na poziciji.


✍ Rješenje:

Za detaljno objašnjenje zadatka 26 ispita pogledajte video:

Analiza zadatka 26 Jedinstvenog državnog ispita iz informatike 2017 (jedna od opcija prema maturantu):

Petya i Vanya igraju igru: postoji skup riječi, morate uzastopno imenovati slova ovih riječi. Igrač koji imenuje posljednje slovo bilo koje riječi iz seta pobjeđuje. Petya ide prva.

Na primjer, postoji skup riječi (Vuk, Informatika, Strašno); za dati skup riječi, Petyin prvi potez može imenovati slovo IN, I ili WITH. Ako Petya odabere pismo IN, tada će Vanya pobijediti (sljedeći potezi: Petya - IN, Vania - O, Petar - L, Vania - TO).

Vježba 1
A) Date su 2 riječi (skup slova) ( IKLMNIKLMNH, NMLKINMLKI). Odredite dobitnu strategiju.

B) Date su 2 riječi ( TRI… TRI, RITARITARITARITA…RITA). U prvoj riječi 99 slova, u drugom 164 . Odredite dobitnu strategiju.

Zadatak 2
Potrebno je zamijeniti dva slova iz skupa tačaka 1A u riječi s najmanjom dužinom tako da drugi igrač ima pobjedničku strategiju. Objasnite pobjedničku strategiju.

Zadatak 3
S obzirom na skup riječi ( Vrana, Vuk, Wave, Derivat, Prokhor, Proso). Koji igrač ima pobjedničku strategiju? Obrazložite svoj odgovor i napišite stablo svih mogućih igara za pobjedničku strategiju.


✍ Rješenje:

* Za Vanju se prikazuju samo strateški potezi
**Crveni krug znači pobjedu

Za više informacija o rješavanju zadatka o riječima pogledajte video lekciju:

Odluka 26. Demo verzija ispita informatike 2018:

Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Petya pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan kamena ili povećati broj kamenja u gomili dvaput. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze.

Igra se završava kada se poveća broj kamenčića na hrpi najmanje 29. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio gomilu koja sadrži 29 ili više kamenja. U početku je u gomili bilo S kamenja, 1 ≤ S ≤ 28.

Reći ćemo da igrač ima pobjedničku strategiju ako može pobijediti za bilo koji potez protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u svakoj situaciji na koju može naići u različitim igrama protivnika. Na opis pobjedničke strategije ne radi to uključuju poteze igrača koji igra po ovoj strategiji, a koji za njega nisu bezuslovno dobitni, tj. ne pobjeđivati ​​bez obzira na igru ​​protivnika.

Vježba 1
A) Navedite takve vrijednosti broja S za koje Petya može pobijediti u jednom potezu.
b) Navedite vrijednost S za koju Petya ne može pobijediti u jednom potezu, ali za bilo koji Petyin potez Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

Zadatak 2
Navedite dvije takve vrijednosti S za koje Petya ima pobjedničku strategiju, štoviše:
- Petya ne može pobijediti u jednom potezu;
— Petya može pobijediti svojim drugim potezom, bez obzira na to kako se Vanja kreće.
Za naznačene vrijednosti S, opišite Petyinu pobjedničku strategiju.

Zadatak 3
Navedite vrijednost S na kojoj:
- Vanja ima pobedničku strategiju koja mu omogućava da pobedi u prvom ili drugom potezu u bilo kojoj Petjinoj igri;
- Vanja nema strategiju koja će mu omogućiti da pobedi uz garanciju na prvi potez.

Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara s ovom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima - broj kamenja u poziciji

Stablo ne bi trebalo da sadrži igre koje su nemoguće da pobednički igrač sprovede svoju pobedničku strategiju. Na primjer, kompletno stablo igre nije valjan odgovor za ovaj zadatak.


✍ Rješenje:
    Vježba 1.
  • a) Petya može pobijediti ako S = 15, ... 28
15, ..., 28 - dobitne pozicije iz prvog poteza
  • b) Vanya može pobijediti na prvi potez (bez obzira kako Petya igra) ako ih ima S=14 kamenje. Tada će nakon Petjinog prvog poteza na hrpi biti 15 ili 28 kamenčića. U oba slučaja Vanya udvostručuje gomilu i pobjeđuje u jednom potezu.
    • S = 14 Petya: 14 + 1 = 15 pobjednička pozicija (vidi tačku a). Vanya Petya osvaja: 14 * 2 = 28 pobjedničkih pozicija (vidi tačku a). Vanya osvaja 14 - gubi poziciju

    Zadatak 2.

  • Moguće vrijednosti S: 7, 13. U ovim slučajevima Petya očito ne može pobijediti na prvi potez. Međutim, može dobiti gomilu od 14 kamenčića: u prvom slučaju udvostručavanjem, u drugom dodavanjem jednog kamena. Ovaj stav je razmatran u paragrafu 1b. U njemu igrač koji će se pomaknuti (sada je to Vanya) ne može pobijediti, a njegov protivnik (to jest, Petya) će pobijediti na sljedećem potezu.
    • S = 7 Petar: 7 * 2 = 14 je gubitna pozicija (vidi tačku 1 b). Petya osvaja S = 13 Petya: 13 + 1 = 14 gubi poziciju (vidi tačku 1 b). Petya osvaja 7, 13 - osvajanje pozicija iz drugog poteza

    Zadatak 3.

  • Moguće vrijednosti S: 12. Nakon Petjinog prvog poteza, na hrpi će biti 13 ili 24 kamena. Ako se na hrpi nalaze 24 kamena, Vanya će udvostručiti broj kamenčića i pobijediti prvim potezom. Situacija kada je 13 kamenčića na hrpi analizirana je u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vanja) pobjeđuje svojim drugim potezom.
    • S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 gubi poziciju (vidi tačku 1 b). Vanya pobjeđuje sekunda pokret!

    Tabela prikazuje stablo mogućih igara (i samo njih) za Vanjinu opisanu strategiju. Konačne pozicije (Vanya ih osvaja) su podvučene. Na slici je isto stablo grafički prikazano.


    Stablo svih mogućih igara sa Vanjinom strategijom:

    * crveni krug znači pobjedu

    Rani ispit iz informatike 2018, opcija 1. Zadatak 26:

    Dva igrača, Paša i Vasja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju Paša pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan ili četiri kamen ili povećati broj kamenja u gomili za pet puta. Igra završava kada se broj kamenčića u hrpi postaje najmanje 69.
    Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio gomilu koja sadrži 69 ili više kamenčića. U početku je u gomili bilo S kamenja, 1 ≤ S ≤ 68.

    Vježba 1.
    A) Navedite sve takve vrijednosti broja S za koje Pasha može pobijediti u jednom potezu. Objasnite da su sve tražene vrijednosti S pronađene i označite pobjednički potez za svaku određenu vrijednost S.

    b) Navedite vrijednost S za koju Pasha ne može pobijediti u jednom potezu, ali Vasya može pobijediti svojim prvim potezom u bilo kojem Pašinom potezu. Opišite Vasjinu pobjedničku strategiju.

    Zadatak 2. Navedite 2 vrijednosti S za koje Pasha ima pobjedničku strategiju, a Pasha ne može pobijediti u jednom potezu i može pobijediti u svom drugom potezu bez obzira na to kako se Vasya kreće. Za svaku datu vrijednost S opišite Pašinu pobjedničku strategiju.

    Zadatak 3. Navedite barem jednu vrijednost S za koju Vasya ima pobjedničku strategiju koja mu omogućava da pobijedi u prvom ili drugom potezu kad god Pasha igra, a Vasya nema strategiju koja će mu omogućiti pobjedu u prvom potezu. Za datu vrijednost S, opišite Vasjinu pobjedničku strategiju. Napravite stablo svih mogućih igara sa ovom pobedničkom Vasjinom strategijom (u obliku figure ili tabele).


    ✍ Rješenje:
      1.
      A) S ≥ 14. Ako je broj kamenčića u gomili 14 ili više, Paša treba da poveća njihov broj pet puta i tako dobije 70 ili više kamenčića.
    S ≥ 14 pobjedničkih pozicija

    b) S=13. Pasha može napraviti 14, 17 ili 65 kamenčića na svom prvom potezu, nakon čega Vasya povećava broj pet puta, dobijajući 70, 85 ili 325 kamenčića na gomili.

    S = 13 Pasha 1 potez: 13 + 1 = 14 Pasha 1 potez: 13 + 4 = 17 Pasha 1 potez: 13 * 5 = 65 Vanja 1 potez: * 5 = S ≥ 14 Vanja osvaja 13 - gubi poziciju

    2. S = 9, 12. Za ove slučajeve, paša treba dodati 4 kamena na gomilu od 9 kamenova, ili 1 kamen na gomilu od 12, i dobiti gomilu od 13 kamenčića.
    Nakon toga, igra se svodi na strategiju opisanu u paragrafu 1b.

    S = 13 Pasha 1 potez: 9 + 4 = 13 Pasha osvaja Pasha 1 potez: 12 + 1 = 13 Pasha pobjeđuje 9, 12 - pobjedničke pozicije iz drugog poteza

    3. S=8. Na svom prvom potezu, Pasha može napraviti broj kamenčića u gomili 9, 12 ili 40. Ako Pasha poveća broj pet puta, tada Vasja pobjeđuje prvim potezom, povećavajući broj kamenčića pet puta.
    Za slučaj kamenja 9 i 12, Vasya koristi strategiju naznačenu u tačka 2.

    S = 8 Pasha 1 potez: 8 + 1 = 9 Vanya pobjeda (vidi tačku 2) Pasha 1 potez: 8 + 4 = 12 Vanya pobjeda (vidi tačku 2) Pasha 1 potez: 8 * 5 = 40

    Pogledajte video za rješenje zadatka 26:

    UPOTREBA simulatora u informatici 2018, kontrolna opcija 1. Zadatak 26 (Krylov S., Ushakov D.):

    jedan kamen ili . Igra se završava kada ukupan broj kamenja u hrpama postane najmanje 73.
    Pobjednik je igrač koji je napravio posljednji potez, tj. prvi koji će dobiti takav položaj da će u gomilama biti ukupno 73 kamena ili više.

    Vježba 1.
    (6, 33), (8, 32) naznačiti koji od igrača ima pobjedničku strategiju. U svakom slučaju, opišite pobjedničku strategiju; objasni zašto ova strategija vodi do pobjede i naznači maksimalan broj poteza koje pobjednik može poduzeti da pobijedi ovom strategijom.

    Zadatak 2.
    Za svaku od početnih pozicija (6, 32), (7, 32), (8, 31) naznačiti koji od igrača ima pobjedničku strategiju.

    Zadatak 3.
    Za početnu poziciju (7, 31) naznačiti koji od igrača ima pobjedničku strategiju. Napravite stablo svih mogućih igara sa pobjedničkom strategijom koju ste naveli. Predstavite drvo u obliku slike ili tabele.


    ✍ Rješenje:

    Video rješavanja 26 zadataka sa dvije gomile:


    26_6: Analiza zadatka 26 sa sajta K. Polyakova (br. 31):

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača su dvije gomile kamenja. Igrači se kreću redom, Petya pravi prvi potez. U jednom potezu, igrač može dodati na jednu od gomila (po svom izboru) dva kamena ili udvostručiti broj kamenja u gomili. Da bi napravio poteze, svaki igrač ima neograničen broj kamenčića. Igra se završava kada ukupan broj kamenja u hrpama postane najmanje 44.
    Pobjednik je igrač koji je napravio posljednji potez, tj. prvi koji će dobiti takav položaj da će u gomilama biti ukupno 44 ili više kamena.

    U početnom trenutku, prva gomila je imala 5 kamena, u drugoj hrpi - S kamenje; 1 ≤ S ≤ 38.
    Vježba 1.
    Na čemu S: 1a) Petya pobjeđuje prvim potezom; 1b) Vanja pobjeđuje prvim potezom?

    Zadatak 2.
    Navedite jednu vrijednost S, pod kojim Petya može pobijediti svojim drugim potezom.

    Zadatak 3.
    Navedite vrijednost S na kojoj Vanya pobjeđuje svojim prvim ili drugim potezom.


    ✍ Rješenje:

    5 + 20*2 = 45 (>44) * 5 - broj kamenja u prvoj hrpi, ne mijenja se u skladu sa uslovom

  • Shodno tome, sve vrijednosti veliki 20 rezultirat će većim brojem 44 . Stavimo to u tabelu. + znači dobitnu poziciju od prvog poteza:


    • Odgovor 1 a): S= (Na ispitu objasnite poteze, na primjer: (5; 20) -> (Petitov potez) -> (5; 40); 40 + 5 = 45)

    Zadatak 1 b):

  • Budući da će Vanya krenuti drugi, potrebno je promijeniti broj kamenja u prvoj hrpi. Dakle, razmotrimo situacije u koje bi Petya mogla krenuti na prvi potez (7;S) i u (10;S). Naznačimo da li će ove pozicije biti osvajane jednim potezom: na primjer (7;19) pobjedničku poziciju, jer igrač će napraviti potez (7;38) i pobijediti (7 + 38 = 45). Shodno tome, sve pozicije su dobitne (7; preko 19). Analizirajmo tabelu, povećavajući broj kamenčića u prvoj hrpi i tražeći pobjedničke pozicije u jednom potezu:

  • Sljedeća logika rasuđivanja: Vanja može pobijediti svojim prvim potezom, dok Petya svojim prvim potezom može samo od prvog poteza (do +) da pređe na pobjedničke pozicije. Takve pozicije označavamo, s obzirom da je ovo Petyin prvi potez, a broj kamenja u prvoj hrpi trebao bi biti 5. Pronađene pozicije će gubiti pozicije (-):

  • Nalazimo jedinu takvu vrijednost - (5; 19). One. S = 19.

    • Odgovor 1 b): S=19 (Na ispitu objasnite poteze, na primjer: (5; 19) -> (Petini potezi): (5; 21), (5; 28); (7; 19); (7; 28). Vanja će pobijediti svuda sljedećim potezom, vidi prethodnu tačku)

    Zadatak 2:

  • Napominjemo da su u tabeli svi formirani "uglovi" gubitničke pozicije (od 1. poteza): odnosno, ako se igrač nađe u takvoj poziciji, onda može preći samo na pobjedničke pozicije (odnosno, protivnik će osvojite sljedeći potez):

  • Logika rasuđivanja: Petya će moći pobijediti svojim drugim potezom kada prvim potezom dođe u gubitnu poziciju, tj. će dovesti protivnika u situaciju gubitka. Takve vrijednosti: S = 16, 17 ili 18. Nazovimo ove pozicije dobitnim iz drugog poteza (2+):

    • Odgovor 2: S = 16, 17 ili 18

    Zadatak 3:

  • U tabeli takođe navodimo pozicije koje su dobitne iz n-tog poteza: kada igrač može prebaciti protivnika u izgubljenu poziciju:

  • Naznačavamo i izgubljene pozicije iz drugog poteza: igrač koji se nađe u takvoj poziciji može preći samo na pobjedničke pozicije (tada će protivnik pobijediti):

  • Logika obrazloženja: Vanja će moći da pobedi svojim prvim ili drugim potezom, kada Petja svojim prvim potezom može da pogodi samo bilo na pobjedničku poziciju iz prvog poteza (+), ili na pobjedničku poziciju iz drugog poteza ili n-tog poteza (2+). Ovo je pozicija na S = 14:


    • Odgovor 3: S=14 (Na ispitu objasniti poteze, pozivajući se na objašnjenja iz prethodnih paragrafa)

    Analiza 26 zadatka USE 2017 iz informatike iz demonstracije. Ovo je zadatak iz drugog dijela visokog nivoa težine. Predviđeno vrijeme za završetak zadatka je 30 minuta. Maksimalan broj bodova za izvršenje zadatka je 3.

    Provjereni elementi sadržaja:
    — Sposobnost da se napravi stablo igre prema datom algoritmu i opravda pobjednička strategija.

    Zadatak 26

    Dva igrača, Paša i Valja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan kamena ili povećati broj kamenja u gomili dvaput. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze.
    Igra se završava u trenutku kada broj kamenčića na hrpi postane najmanje 20. Ako istovremeno nema više od 30 kamenčića u gomili, tada se igrač koji je napravio posljednji potez smatra pobjednikom. U suprotnom, njegov protivnik postaje pobjednik. Na primjer, ako je na hrpi bilo 17 kamenčića, a Pasha udvostruči broj kamenčića na hrpi, onda će se igra završiti i Valya će biti pobjednik. U početnom trenutku, gomila je imala S kamenje, 1 ≤ S ≤ 19.

    Reći ćemo da igrač ima pobednička strategija, ako može pobijediti bilo kojim potezom protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u svakoj situaciji na koju može naići u različitim igrama protivnika.

    Dovršite sljedeće zadatke.
    1. a) Za koje vrijednosti broja S Paša može da pobedi u jednom potezu?
    Navedite sve takve vrijednosti i odgovarajuće Pašine poteze.
    b) Za koga od igrača ima pobjedničku strategiju S = 18, 17, 16?
    Opišite pobjedničke strategije za ove slučajeve.
    2. Ko od igrača kada ima pobjedničku strategiju S= 9, 8? Opišite relevantne pobjedničke strategije.
    3. Ko od igrača kada ima pobjedničku strategiju S= 7? Konstruirajte stablo svih mogućih igara s ovom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima - broj kamenja na poziciji.

    1. a) Paša može pobijediti ako S= 19 ili S= 10, 11, 12, 13, 14, 15. Sa S= 19 U prvom potezu, jedan kamen se mora dodati na gomilu, sa naznačenim preostalim vrijednostima S potrebno je udvostručiti broj kamenja.

    b) Kada S= 16, 17 ili 18 udvostručavanje broja kamenova nema smisla, jer nakon takvog poteza protivnik pobjeđuje. Stoga možemo pretpostaviti da je jedini mogući potez dodavanje jednog kamena na gomilu.

    At S= 18 nakon takvog Pašinog poteza, na gomili će biti 19 kamena. U ovoj poziciji pobjeđuje hodač (tj. Valya). (vidi tačku 1a): at S= 18 Pasha (igrač koji mora ići prvi) gubi.

    Vali ima pobjedničku strategiju.

    At S= 17, nakon što Paša doda jedan kamen na svom prvom potezu, na gomili će biti 18 kamenčića. U ovoj poziciji, hodač (tj. Valya) gubi (vidi gore): at S= 17 Pasha (igrač koji mora prvi krenuti) pobjeđuje. Paša ima pobedničku strategiju.

    At S= 16 Vali ima dobitnu strategiju. Zaista, ako Pasha udvostruči broj kamenčića u svom prvom potezu, tada se na hrpi nalaze 32 kamena, a igra se odmah završava pobjedom Valje. Ako Paša doda jedan kamen, onda je u gomili 17 kamenčića. Kao što već znamo, u ovoj poziciji pobjeđuje igrač koji se mora pomaknuti (tj. Valya).

    U svim slučajevima pobjeda se postiže činjenicom da prilikom svog poteza igrač sa pobjedničkom strategijom mora dodati jedan kamen na gomilu.

    Moguće je nacrtati stabla svih mogućih serija za navedene vrijednosti S.
    Druga mogućnost je (1) istaći da udvostručavanje hrpe nema smisla i (2) sukcesivno smanjivanje slučaja S= 18 po slučaju S= 19, slučaj S= 17 - na slučaj S= 18 itd.

    2. Kada S= 9 ili 8 Pasha ima pobedničku strategiju. Sastoji se od udvostručavanja broja kamenja u gomili i dobijanja gomile koja sadrži 18 odnosno 16 kamenova. U oba slučaja, igrač koji će napraviti potez (sada je to Valya) gubi (vidi tačku 1b).

    3. Kada S= 7 Vali ima pobjedničku strategiju. Nakon Pašinog prvog poteza, gomila može sadržavati 8 ili 14 kamenčića. Na obje ove pozicije, igrač koji će napraviti potez pobjeđuje (sada je to Valya). Dešava se S= 8 razmatrano u stavu 2, slučaj S= 14 razmatrano u stavu 1a.

    Tabela prikazuje stablo mogućih igara za opisanu Wali strategiju. Konačne pozicije (Valja ih osvaja) su podvučene. Na slici je isto stablo prikazano grafički (oba načina predstavljanja stabla su prihvatljiva).

    Stablo svih mogućih igara sa Valjinom strategijom. Znak >> označava pozicije na kojima igra završava.

    Dva igrača, Paša i Vova, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati 1 kamen ili 10 kamenčića na gomilu. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti hrpu od 8 ili 17 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića na hrpi postane najmanje 31. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio hrpu koja sadrži 31 ili više kamenčića.

    U početnom trenutku u gomili je bilo S kamenja, 1 ≤ S ≤ 30.

    Rješenje.

    1. a) Paša može pobijediti ako je S = 21, ..., 30. Sa manjim vrijednostima S, ne može se dobiti hrpa koja sadrži više od 30 kamenčića u jednom potezu. Dovoljno je da Paša poveća broj kamenčića za 10. Sa S 1. b) Vova može pobijediti na prvi potez (bez obzira kako Pasha igra) ako u početku ima S = 20 kamenčića u gomili. Zatim, nakon prvog Pašinog poteza, na gomili će biti 21 kamen ili 30 kamenčića. U oba slučaja, Vanya povećava broj kamenova za 10 i pobjeđuje u jednom potezu.

    2.  Moguće vrijednosti S: 10, 19. U ovim slučajevima Paša očigledno ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 20 kamenčića (na S=10 povećava broj kamenčića za 10; na S=19 dodaje 1 kamen). Ovaj stav je razmatran u stavu 1 b. U njemu igrač koji će krenuti (sada je to Vova) ne može pobijediti, a njegov protivnik (to jest, Pasha) će pobijediti na sljedećem potezu.

    3. Moguća vrijednost S: 18. Nakon Pašinog prvog poteza, na hrpi će biti 19 ili 28 kamenčića. Ako je na hrpi 28 kamenčića, Vova će povećati broj kamenčića za 10 i igrate na prvi potez. Situacija, kada je 19 kamenčića na gomili, govori se u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vova) pobjeđuje svojim drugim potezom.

    Gost 26.05.2014 12:31

    Tačka 3. Ali šta je sa situacijom kada je u početku 9 kamenja na gomili. Nakon Pašinog poteza, kamenčići postaju ili 10 ili 19, Vasja završava do 20 i dalje prema stavu 1.b.

    Konstantin Lavrov

    Da, 9 je takođe tačan odgovor. Dovoljno je navesti barem jednu tačnu vrijednost.

    Dva igrača, Paša i Vova, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati 1 kamen ili 10 kamenčića na gomilu. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti hrpu od 8 ili 17 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića na hrpi postane najmanje 41. Pobjednik je igrač koji je napravio posljednji potez, odnosno prvi koji je dobio hrpu koja sadrži 41 ili više kamenčića.

    U početnom trenutku u gomili je bilo S kamenja, 1 ≤ S ≤ 40.

    Reći ćemo da igrač ima pobjedničku strategiju ako može pobijediti za bilo koji potez protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u bilo kojoj situaciji na koju može naići s različitom igrom protivnika.

    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Navedite sve takve vrijednosti broja S za koje Paša može pobijediti u jednom potezu. Opravdajte da su sve tražene vrijednosti S pronađene i označite pobjedničke poteze.

    b) Navedite vrijednost S. za koju Paša ne može pobijediti u jednom potezu, ali za bilo koji Pašin potez Vova može pobijediti svojim prvim potezom. Opišite Vovinu pobjedničku strategiju.

    2. Navedite dvije vrijednosti S za koje Pasha ima dobitnu strategiju, a Pasha ne može pobijediti u jednom potezu, ali može pobijediti u svom drugom potezu bez obzira kako se Vova kreće. Za date vrijednosti S, opišite Pašinu pobjedničku strategiju.

    3. Navedite vrijednost S za koju Vova ima pobjedničku strategiju koja mu omogućava da pobijedi u prvom ili drugom potezu kad god Pasha igra, ali Vova nema strategiju koja će mu omogućiti pobjedu u prvom potezu. Za datu vrijednost S, opišite Vovinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara ovom Vovinom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće, na čvorovima - broj kamenja u hrpi.

    Rješenje.

    1. a) Paša može pobijediti ako je S = 31, ..., 40. Sa manjim vrijednostima S ne može se dobiti hrpa sa više od 40 kamenčića u jednom potezu. Dovoljno je da Paša poveća broj kamenčića za 10. Sa S b) Vova može pobijediti na prvi potez (bez obzira kako Pasha igra) ako u početku ima S = 30 kamenčića u gomili. Zatim, nakon prvog Pašinog poteza, na gomili će biti 31 kamen ili 40 kamenčića. U oba slučaja, Vanya povećava broj kamenova za 10 i pobjeđuje u jednom potezu.

    2.  Moguće vrijednosti S: 20, 29. U ovim slučajevima Paša očigledno ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 30 kamenčića (pri S = 20 povećava broj kamenčića za 10; pri S = 29 dodaje 1 kamen). Ovaj stav je razmatran u stavu 1. b). U njemu igrač koji će krenuti (sada je to Vova) ne može pobijediti, a njegov protivnik (to jest, Pasha) će pobijediti na sljedećem potezu.

    3. Moguća vrijednost S: 28. Nakon Pašinog prvog poteza, na hrpi će biti 29 ili 38 kamenčića. Ako je na hrpi 38 kamenčića, Vova će povećati broj kamenčića za 10 i igrate na prvi potez. Situacija, kada je 29 kamenčića na gomili, govori se u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vova) pobjeđuje svojim drugim potezom.

    Tabela prikazuje stablo mogućih igara za opisanu Vovinu strategiju. Konačne pozicije (Vova ih osvaja) su podvučene. Na slici je isto stablo prikazano grafički (oba načina predstavljanja stabla su prihvatljiva).

    Dva igrača, Petya i Vanya, igraju sljedeću utakmicu. Ispred njih su dvije gomile kamenja, od kojih se u prvoj nalaze 2, au drugoj - 3 kamena. Svaka igra-ro-ka nema-ogran-no-chen-ali puno kamenja. Igrači hodaju oko-re-di, prvi potez je de-la-et Petya. Pokret se sastoji u tome da igrač ili am-i-bio broj kamenčića u nekoj gomili, ili dodaje 4 kamena na neku gomilu. Igra je završena u trenutku kada ukupan broj kamenčića u dvije hrpe postane najmanje 31. Ako je u trenutku završetka igre ukupan broj kamenčića u dvije hrpe najmanje 40, onda je Petya igrao, u suprotan slučaj - Vanja. Ko si ti-ig-ry-va-et u nedostatku greške-boch-noy igre obje igre-ro-kov? Koji bi trebao biti prvi potez vas-ig-ry-va-yu-sche-go-ro-ka? Obrazložite odgovor.

    Rješenje.

    Vanya pobjeđuje.

    Da biste to dokazali, razmotrite nepotpuno stablo igre, dizajnirano kao tabela, gdje svaka ćelija sadrži parove brojeva odvojenih zarezom. Ovi brojevi odgovaraju broju kamenčića u svakoj fazi igre u prvoj i drugoj hrpi, respektivno.

    Tabela sadrži sve moguće poteze za prvog igrača. To pokazuje da za bilo koji potez prvog igrača, drugi ima potez koji vodi do pobjede.

    Dva igrača, Petya i Vasya, igraju sljedeću igru. Ispred njih su dvije gomile kamenja, od kojih prva ima 2, a druga - 1 kamen. Svaki igrač ima neograničen broj kamenja. Igrači se kreću redom, Petya ide prvi. Pokret se sastoji u tome da igrač ili poveća broj kamenčića na nekoj hrpi za 3 puta, ili doda 3 kamena na neku gomilu. Pobjeđuje igrač nakon čijeg okreta ima najmanje 24 kamena u jednoj od hrpa. Ko pobjeđuje kada igra besprijekorno? Koji bi trebao biti prvi potez pobjedničkog igrača?

    Obrazložite odgovor.

    Rješenje.

    Petya pobjeđuje, svojim prvim potezom mora utrostručiti broj kamenčića u drugoj hrpi. Da biste to dokazali, razmotrite nepotpuno stablo igre, dizajnirano kao tabela, gdje svaka ćelija sadrži parove brojeva odvojenih zarezom. Ovi brojevi odgovaraju broju kamenčića u svakoj fazi igre u prvoj i drugoj hrpi, respektivno.

    Tabela sadrži sve moguće opcije za Vasyine poteze. Iz toga se vidi da sa bilo kojim svojim odgovorom Petya ima potez koji vodi do pobjede.

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Petya pravi prvi potez. U jednom potezu, igrač može dodati jedan kamen na gomilu ili povećati broj kamenčića u gomili pet puta. Na primjer, ako imate gomilu od 10 kamenčića, možete dobiti gomilu od 11 ili 50 kamenčića u jednom potezu. Svaki igrač ima neograničen broj kamenja za poteze.

    Igra se završava kada broj kamenčića na hrpi postane veći od 100. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio hrpu koja sadrži 101 ili više kamenčića.

    U početnom trenutku u gomili je bilo S kamenja, 1 ≤ S ≤ 100.

    Za igrača se kaže da ima pobjedničku strategiju ako može pobijediti za bilo koji od protivničkih poteza. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u bilo kojoj situaciji na koju može naići s različitom igrom protivnika.

    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Za koje vrijednosti broja S Petya može pobijediti na prvi potez? Navedite sve takve vrijednosti i Petyin pobjednički potez.

    b) Navedite vrijednost S za koju Petya ne može pobijediti u jednom potezu, ali za bilo koji Petyin potez, Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

    2. Navedite dvije vrijednosti S za koje Petya ima pobjedničku strategiju, a Petya ne može pobijediti u prvom potezu, ali Petya može pobijediti u svom drugom potezu bez obzira na to kako se Vanja kreće. Za naznačene vrijednosti S, opišite Petyinu pobjedničku strategiju.

    3. Navedite vrijednost S za koju Vanja ima pobjedničku strategiju koja mu omogućava da pobijedi u prvom ili drugom potezu za bilo koju igru ​​Petye, a istovremeno Vanya nema strategiju koja će mu omogućiti pobjedu na prvi potez.

    Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara s Vanjinom pobjedničkom strategijom. Predstavite ga u obliku figure ili tabele. Za svaki rub stabla naznačite ko čini potez, za svaki čvor, broj kamenja na poziciji.

    Rješenje.

    1. a) Petya može pobijediti ako je S = 21, ..., 100. Za manje vrijednosti S, ne može se dobiti hrpa koja sadrži više od 100 kamenčića u jednom potezu. Dovoljno je da Petya poveća broj kamenja za 5 puta. Sa S 1. b) Vanya može pobijediti u prvom potezu (bez obzira kako Petya igra) ako u početku ima S = 20 kamenčića u gomili. Tada će nakon Petjinog prvog poteza biti 21 kamen ili 100 kamenčića u gomili. U oba slučaja, Vanya povećava broj kamenova za 5 puta i pobjeđuje u jednom potezu.

    2.  Moguće vrijednosti S: 4, 19. U ovim slučajevima Petya očigledno ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 20 kamenčića (sa S = 4, povećava broj kamenčića za 5; sa S = 19, dodaje 1 kamen). Ovaj stav je razmatran u stavu 1 b). U njemu igrač koji će se pomaknuti (sada je to Vanya) ne može pobijediti, a njegov protivnik (to jest, Petya) će pobijediti na sljedećem potezu.

    3. Moguća vrijednost S: 18. Nakon Petjinog prvog poteza, na hrpi će biti 19 ili 90 kamenčića. Ako na hrpi ima 90 kamenčića, Vanya će povećati broj kamenčića za 5 puta i pobijediti prvim potezom. Situacija, kada je 19 kamenčića na gomili, govori se u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vanya) pobjeđuje svojim drugim potezom.

    Tabela prikazuje stablo mogućih igara za Vanjinu opisanu strategiju. Konačne pozicije (Vanya ih osvaja) su podvučene. Na slici je isto stablo prikazano grafički (oba prikaza su prihvatljiva).


    Uradite test za ove zadatke

    Otvaramo pretplatu na interaktivne simulatore za pripremu za USE 2016 iz informatike

    Svako sa novčanikom Visa, MasterCard, Yandes.Money, pa čak i sa pozitivnim stanjem na svom mobilnom telefonu, može naručiti 60 jedinstvenih interaktivnih animacija za pripremu za Jedinstveni državni ispit 2016. iz informatike bez ustajanja od kompjutera

    Simulator za zadatak br. 26 demo verzije USE 2015
    Informatika i IKT metodom "Brda i rupe".

    Najjednostavnije rješenje za problem 26 ili stari C3
    iz informatike i IKT vizualnom metodom "Brda i rupe"

    Primjer rješavanja problema u slučaju povećanja kamenja u hrpi na dva načina "+1" i "*2"

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Petya pravi prvi potez. U jednom potezu, igrač može dodati jedan kamen na gomilu ili udvostručiti broj kamenčića na hrpi. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića na hrpi postane najmanje 22. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio hrpu koja sadrži 22 ili više kamenčića.
    U početnom trenutku u gomili je bilo S kamenja, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Navedite sve takve vrijednosti broja S za koje Petya može pobijediti u jednom potezu. Objasnite da su sve tražene vrijednosti S pronađene i označite pobjednički potez za svaku određenu vrijednost S.
    b) Navedite vrijednost S za koju Petya ne može pobijediti u jednom potezu, ali za bilo koji Petyin potez, Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

    2. Navedite dvije takve vrijednosti S za koje Petya ima pobjedničku strategiju, i
    – Petja ne može da pobedi u jednom potezu, i
    – Petya može pobijediti svojim drugim potezom, bez obzira kako se Vanja kreće.
    Za svaku datu vrijednost S, opišite Petyinu pobjedničku strategiju.

    3. Navedite vrijednost S, pri kojoj:
    – Vanja ima pobedničku strategiju koja mu omogućava da pobedi u prvom ili drugom potezu u bilo kojoj Petjinoj igri, i
    – Vanja nema strategiju koja će mu omogućiti da pobedi na prvi potez.
    Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju.
    Konstruirajte stablo svih mogućih igara s Vanjinom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće, na čvorovima - broj kamenja u hrpi.

    Pitanje 1a.
    Obrnutim potezom od "pobjede" određujemo granice početne pobjedničke pozicije: 22 – 1 = 21 I 22/2 = 11
    Za bilo koji broj koji leži unutar granica ovog raspona, sljedeći unos je istinit max0*2>= 22 ili max0*2 > 21 (zaokružite ovaj raspon odozgo i označite ga kao max0, što bi značilo početnu dobitnu poziciju ili pobjedu u jednom potezu)

    1a) Petya pobjeđuje u prvom potezu sa 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

    Pitanje 1b. Da biste odgovorili na ovo pitanje, morate pronaći pozicije, mi ćemo ih uslovno nazvati min0 , iz koje svi mogući potezi vode do početne pobjedničke pozicije, koju smo označili kao max0 . Obrnuto, određujemo “sumnjive” pozicije na min0 :
    11/2=? nije potpuno podijeljena, dakle, takva pozicija ne postoji. Ostaje samo S= 11-1=10
    (ali za sada je ovo samo nagađanje)min0 , pa crtamo "jama" dvije karakteristike, što će značiti - ne zaboravite na postojanje 2 moguća poteza koje ćete morati provjeriti!)

    Provjeravamo pretpostavku za S = 10 na min0. Ova provjera će biti odgovor. na pitanje 1b
    Sa S = 10, Petya ima 2 poteza koje ne može osvojiti u jednom potezu, ali sa bilo kojim Petjinim potezom, Vanja može pobijediti svojim prvim potezom:
    Svaki Petjin potez "10+1=11" ili 10*2=20 vodi do početne pobedničke pozicije Vanje, koji, udvostručivši broj kamenčića u gomili, dobija 22 ili 40, što je više od 21 i Van će pobediti
    Stoga zaokružujemo poziciju S = 10 odozdo punom linijom ( nacrtati rupu) - min0 (početni gubitak ili gubitak za 1. potez):

    Odgovor na pitanje 1b. može biti ovako: Sa S = 10, Petya ima 2 poteza koje ne može dobiti, ali za bilo koji Petyin potez, Vanja može pobijediti svojim prvim potezom. Svaki Petjin potez "10+1=11" ili "10*2=20" vodi do početne pobedničke pozicije Vanje, koji udvostručavanjem broja kamenčića u gomili dobija 22 ili 40, što je više od 21 i Vanya pobjeđuje

    Pitanje 2. Da bi Petya pobijedila u drugom potezu, tj. bio na poziciji max0 , nakon Vanjinog poteza, treba mu njegov prvo premjestiti" stavi Vanju u rupu". Jasno je da takve pozicije mogu biti dva, čije vrijednosti nalazimo obrnuto i moraju se provjeriti...
    Prva sumnjiva pozicija "10-1=9"

    S=9. Provjerimo ovu poziciju za zagarantovanu pobjedu!
    Da je Petya igrao davanje, napravio bi potez "9 * 2 \u003d 18", ali on treba da pobijedi, tako da odbacujemo ovaj potez. Ostaje samo "9+1 = 10", Ivanya je unutra "jama" - koja dovodi Petju do pobede u drugom potezu, bez obzira kako Vanja ide!

    Druga "sumnjiva pozicija" 10/2 = 5

    S=5. Provjerimo ovu poziciju za zagarantovanu pobjedu! pokret "5+1=6", odugovlači igru, tako da je ne uzimamo u obzir (odbaciti)
    Ostaje samo "5*2=10", Ivanya je unutra "jama" -što dovodi Petya do pobjede u drugom potezu, bez obzira kako Vanya ide!

    Odgovor 2 može biti:

    Sa S = 5 i 9, Petya ne može pobijediti u prvom potezu, ali može pobijediti u drugom potezu, a za to mu je dovoljno da napravi potez "5*2 = 10" sa pozicije S = 5, čime se Vanja šalje u početnu gubitnu poziciju ili iz pozicije S=9 šalje ga u istu poziciju potezom "9+1=10"

    Pitanje 3. Vanya mora pobijediti, dakle, mora biti na vrhu max0, to znači da Petya sigurno mora biti unutra min0, gdje je "biljka" Vanja iz max1, ostaje da se pronađu takve pozicije sa kojih bi Petja nedvosmisleno upao max1
    Nalazimo "sumnjive" položaje do kojih Petya može dovesti max1 sa istim pozadinom:
    9-1=8
    9/2=? 9 nije deljivo sa 2 - nestaje
    5-1=4
    5/2=? 5 sa 2 nije deljivo - nestaje
    Nalazimo da je takvo "sumnjivo" Postoje samo dvije pozicije, ali ih još uvijek treba provjeriti!

    S=8. Hajde da proverimo ovu poziciju da vidimo da li će Petya sigurno izgubiti!
    Petyin potez je 8+1=9 i Vanja pobjeđuje u drugom potezu
    Petyin potez 8*2=16 i Vanja pobjeđuje u prvom potezu
    S=4. Hajde da proverimo ovu poziciju da vidimo da li će Petya sigurno izgubiti!
    Petin potez je 4+1=5 i on bi izgubio, ali sa ove pozicije je koristan Petin potez 4*2=8, tako da Vanja pada u "jamu" i gubi. Ali moramo pronaći Vanjinu pobjedničku strategiju, pa isključimo poziciju S=4 iz kandidata i dobijemo finale "slika":

    3. Na poziciji S = 8 – Vanja nema strategiju koja će mu omogućiti da dobije prvim potezom, pošto njegova pobeda zavisi od Petjinog poteza, tako da Vanja ima strategiju da pobedi ili prvim ili drugim potezom: Ako Petja odabere potez “+1” , na hrpi je 9 kamenčića i Vanya pobjeđuje u 2. potezu (vidi odgovor na pitanje 2). Ako Petya odabere potez "*2", Vanya pobjeđuje prvim potezom, udvostručavajući broj kamenčića u gomili.

    Slika koju smo dobili iznad može se lako precrtati u stablo igre, nakon što se izgubljeni potezi označavaju crvenim linijama (debela linija - " kratki udar" ili " +1 ", i tanko -" dugo" ili " *2 ”) i zelena - pobjednička. (crvene debele linije mogu se povući s grbama prema gore, koje će se poklapati sa smjerom "kratkih" grana stabla divljači)

    Konačna strateška slika Petyine pobjede može izgledati ovako:

    Ostale metode za rješavanje problema ove vrste možete pronaći ovdje -