15.10.2020

Otevíráme předplatné interaktivních simulátorů, abychom se připravili na USE 2016 v informatice

Každý, kdo má na svém mobilním telefonu peněženku Visa, MasterCard, Yandex.Money a dokonce i pozitivní zůstatek, si může objednat 60 jedinečných interaktivních animací, aby se připravil na USE 2016 v počítačové vědě, aniž by vstal ze svého počítače

Simulátor pro problém č. 26 demo verze USE 2015
v informatice a ICT metodou „Hills and Pits“

Nejjednodušší řešení problému 26 nebo staré C3
v informatice a ICT pomocí vizuální metody "Kopce a jámy"

Příklad řešení problému v případě zvětšení kamenů v hromadě dvěma způsoby „+1“ a „* 2“

Dva hráči, Petya a Vanya, hrají následující hru. Před hráči je hromada kamenů. Hráči se střídají, Petya dělá první tah. V jednom tahu může hráč přidat jeden kámen na hromádku nebo zdvojnásobit počet kamenů na hromádce. Například když máte hromadu 15 kamenů, můžete v jednom tahu získat hromadu 16 nebo 30 kamenů. Každý hráč má neomezený počet kamenů, aby mohl provádět tahy. Hra končí v okamžiku, kdy počet kamenů na hromádce dosáhne alespoň 22. Vítězem se stává hráč, který provedl poslední tah, tj. První, který obdrží hromádku, ve které bude 22 nebo více kamenů.
V počáteční chvíli byly na hromadě S kameny, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Dokončete následující úkoly. Ve všech případech svou odpověď zdůvodněte.

1. a) Uveďte všechny takové hodnoty čísla S, při kterých může Petya vyhrát jedním tahem. Zdůvodněte, že jste našli všechny požadované hodnoty S, a označte vítězný tah pro každou zadanou hodnotu S.
b) Uveďte hodnotu S, při které Petya nemůže vyhrát v jednom tahu, ale u jakéhokoli tahu může Petya vyhrát svým prvním tahem. Popište Vanyovu vítěznou strategii.

2. Uveďte dvě takové hodnoty S, pro které má Petya vítěznou strategii, a
- Petya nemůže vyhrát jediným tahem a
- Petya může vyhrát svým druhým tahem, bez ohledu na to, jak se pohybuje Vanya.
U každé zadané hodnoty S popište Petitovu vítěznou strategii.

3. Určete hodnotu S, při které:
- Vanya má vítěznou strategii, která mu umožňuje vyhrát v prvním nebo druhém tahu v jakékoli hře Petit a
- Váňa nemá strategii, která by mu umožnila vyhrát zaručeným prvním tahem.
Pro uvedenou hodnotu S popište Vanyinu vítěznou strategii.
Vytvořte si strom všech možných her s touto vítěznou strategií Vanya (ve formě obrázku nebo stolu). Na okrajích stromu uveďte, kdo provede tah, v uzlech - počet kamenů v haldě.

Otázka 1a.
Zpětným tahem z „vítězství“ definujeme hranice počáteční vítězné pozice: 22 – 1 = 21 a 22/2 = 11
Pro jakékoli číslo v tomto rozsahu je platná následující notace max0 * 2\u003e \u003d 22 nebo max0 * 2\u003e 21 (načrtneme tento rozsah shora a označíme jej jako max0, což bude znamenat počáteční vítěznou pozici nebo výhru v jednom tahu)

1a) Petya vyhrává prvním tahem v 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Otázka 1b. Chcete-li odpovědět na tuto otázku, musíte najít pozice, které jim podmíněně zavoláme min0 , ze kterého všechny možné tahy vedou na počáteční vítěznou pozici, kterou jsme označili jako max0 ... Při zpětném pohybu určujeme „podezřelé“ pozice min0 :
11/2=? není rozdělena úplně, proto takové postavení neexistuje. Pouze pozůstatky S \u003d 11-1=10
(ale zatím je to jen předpokladmin0 takže kreslíme "Jáma" dvě funkce, což bude znamenat - nezapomeňte na existenci 2 možných tahů, které je nutné zkontrolovat!)

Zkontrolujte předpoklad pro S \u003d 10 při min0. Tato kontrola bude sloužit jako odpověď. k otázce 1b
S S \u003d 10 má Petya 2 tahy, které nemůže vyhrát v jednom tahu, ale u každého tahu může Petya Vanya vyhrát svým prvním tahem:
Jakýkoli pohyb Petit „10 + 1 \u003d 11“ nebo 10 * 2 \u003d 20 vede k počáteční vítězné pozici Vanyi, který po zdvojnásobení počtu kamenů v haldě obdrží 22 nebo 40, což je více než 21 a váňa vyhraje
Proto obrysujeme polohu S \u003d 10 zespodu plnou čarou ( nakreslit jámu) - min0 (počáteční ztráta nebo ztráta pro 1. tah):

Odpověď na otázku 1b. Může to být takto: S S \u003d 10 má Petya 2 tahy, které nemůže vyhrát, ale u každého tahu může Petya Vanya vyhrát svým prvním tahem. Jakýkoli pohyb Petya „10 + 1 \u003d 11“ nebo „10 * 2 \u003d 20“ vede Vanyu na počáteční vítěznou pozici, která po zdvojnásobení počtu kamenů v haldě získá 22 nebo 40, což je více než 21, a Vanya vyhraje

otázka 2... Aby mohla Petya zaručeně vyhrát na druhém tahu, tj. skončil na místě max0 , po Vanyově pohybu potřebuje jeho za prvé hýbat se " dejte Váňu do jámy". Je jasné, že takové pozice mohou být dva, jejichž hodnoty jsou uvedeny v opačném pořadí a musí být zkontrolovány ...
První podezřelá pozice „10-1 \u003d 9“

S \u003d 9. Pojďme zkontrolovat tuto pozici pro zaručené vítězství!
Kdyby Petya hrál prozradí, udělal by tah "9 * 2 \u003d 18",ale on potřebuje vyhrát, takže tento tah zahodíme. Pouze pozůstatky "9 + 1 \u003d 10",a Vanya je v „Pit“ - což vede Petyu k vítězství druhým tahem, bez ohledu na to, jak Vanya odejde!

Druhá „podezřelá pozice“ 10/2 = 5

S \u003d 5. Pojďme zkontrolovat tuto pozici pro zaručené vítězství! Mrtvice "5 + 1 \u003d 6",zpožďuje hru, takže ji nepovažujeme (zahodit)
Pouze pozůstatky "5 * 2 \u003d 10",a Vanya je v „Pit“ -což vede Petyu k vítězství druhým tahem, bez ohledu na to, jak Vanya odejde!

Odpověď 2 může vypadat takto:

Při S \u003d 5 a 9 nemůže Petya zvítězit prvním tahem, ale může vyhrát druhým tahem, a proto mu stačí provést tah „5 * 2 \u003d 10“ z pozice S \u003d 5, čímž pošle Váňu na počáteční pozici ztráty nebo z pozice S \u003d 9 poslat to na stejnou pozici s tahem "9 + 1 \u003d 10"

Otázka 3... Váňa musí vyhrát, proto musí být na špici max0, to znamená, že Petya určitě musí být min0, kde to je "Rostlina" Vanya z max1, anamovi zbývá najít takové pozice, ze kterých by Petya rozhodně spadl max1
Našli jsme „podezřelé“ pozice, které by Petyu mohly vést max1 pomocí stejného ústupku:
9-1=8
9/2 \u003d? 9 není dělitelné 2 - zmizí
5-1=4
5/2 \u003d? 5 x 2 není dělitelné - zmizí
Zjistili jsme, že takový "Podezřelý"existují pouze dvě polohy, ale stále je třeba je kontrolovat!

S \u003d 8. Pojďme zkontrolovat tuto pozici pro zaručenou ztrátu Petit!
Petitův tah je 8 + 1 \u003d 9 a Vanya vyhrává druhým tahem
Petitův tah je 8 * 2 \u003d 16 a Vanya vyhrává prvním tahem
S \u003d 4. Pojďme zkontrolovat tuto pozici kvůli zaručené ztrátě Petit!
Peťův tah 4 + 1 \u003d 5 a on by prohrál, ale z této pozice je Peťův tah 4 * 2 \u003d 8 ziskový, takže Vanya spadne do „díry“ a prohraje. Musíme ale najít Vanyovu vítěznou strategii, takže z kandidátů vyloučíme pozici S \u003d 4 a dostaneme finále "Obrázek":

3. Na pozici S \u003d 8 - Vanya nemá strategii, která by mu umožnila vyhrát v prvním tahu, protože jeho vítězství závisí na tahu Petya, takže Vanya má strategii vyhrát buď na prvním, nebo na druhém tahu: Pokud Petya zvolí „+1“ , na hromádce je 9 kamenů a Vanya vyhrává na tahu 2 (viz odpověď na otázku 2). Pokud Petya zvolí tah „* 2“, Vanya vyhraje prvním tahem, čímž zdvojnásobí počet kamenů v haldě.

Výkres, který jsme získali výše, lze snadno překreslit do herního stromu, když jsme dříve označili ztracené tahy červenými čarami (silná čára je „ krátký zdvih„nebo“ +1 ", A tenký -" dlouho„nebo“ *2 ») A zelená - vítězná. (červené silné čáry mohou být nakresleny na hrboly, což se bude shodovat se směrem „krátkých“ větví stromu hry)

Konečný strategický obrázek vítězství Petya může vypadat takto:

Další metody řešení problémů tohoto typu naleznete zde -

V tomto úkolu je nejobtížnější částí správně a logicky zapsat řešení.

Začněme tedy pokusem porozumět podmínce.

1. Máme dvě hromádky kamenů a dva hráče: první (Petya) a druhý (Vanya).
2. Hráči se střídají.
3. Během kola můžete buď přidat jeden kámen na libovolnou hromádku, nebo zdvojnásobit počet kamenů na hromádce.
4. Jakmile je na hromádce celkem 73 nebo více kamenů, hra končí.
5. Ten, kdo šel naposledy, vyhrál.

Důležité poznámky

1. V některých úkolech postavíme strom strany. Podle podmínky jsme povinni to udělat pouze v Úkolu 3. V Úkolu 2 jsme nemusím postavit strom stran.
2. V každém z úkolů nestačí jednoduše říci, kdo má vítěznou strategii. Je také nutné jej popsat a uvést možný počet kroků, které budou k vítězství nutné.
3. Nestačí nazvat vítěznou strategii. Potřebovat dokázatže to vede k výhře. I zjevná prohlášení vyžadují důkaz.

Cvičení 1.

Zvažte nyní úkol 1. V hromadách - (6, 33) kamenů (první část úkolu 1) a (8, 32) kamenů (druhá část úkolu 1). Musíme určit, který z hráčů má vítěznou strategii. Jinými slovy, který z hráčů, pokud bude hrán správně, jistě vyhraje, bez ohledu na akce soupeře.

Dále rozdělíme řešení na dvě části. Nejprve bude k dispozici předběžné vysvětlení (nemusíte jej psát ve Sjednocené státní zkoušce) a poté - „formální rozhodnutí“, tedy to, co musíte napsat ve Sjednocené státní zkoušce samotné.

Diskuse.

Uvažujme: první hráč zjevně nemůže vyhrát v jednom tahu, protože ať udělá cokoli, nebude jich celkem 73. „Největší“ akcí, kterou může udělat, je zdvojnásobení počtu kamenů na druhé hromádce, což z nich činí 66. Ale (6, 66) je 72 kamenů, ne 73. Takže první očividně vyhraje v jednom tahu nemůže. Druhý je však docela schopný. První může potenciálně dělat čtyři věci: přidat 1 na první hromádku, zdvojnásobit počet kamenů na první hromádce, přidat 1 na druhou hromádku a zdvojnásobit počet kamenů na druhé hromádce. Podívejme se, kam to vede:

• (6,33) -\u003e (7,33). V takovém případě může druhý hráč zdvojnásobit počet kamenů na druhé hromádce. Dostaneme (7, 66). Celkem - 73. Takže vyhrává druhá.
• (6,33) -\u003e (12, 33). V takovém případě může druhý hráč zdvojnásobit počet kamenů na druhé hromádce. Dostaneme (12, 66). Celkem - 78. Takže vyhrává druhá.
• (6,33) -\u003e (6,34). V takovém případě může druhý hráč zdvojnásobit počet kamenů na druhé hromádce. Dostaneme (6, 68). Celkem - 74. Takže vyhrává druhá.
• (6,33) -\u003e (6,66). V takovém případě může druhý hráč zdvojnásobit počet kamenů na druhé hromádce. Dostaneme (6, 132). Celkem - 138. Takže vyhrává druhá.

Celkem: bez ohledu na to, jak se chová první hráč, druhý vyhraje v jednom tahu.

Řešení s (8.32) je podobné.

Formální řešení problému 1.

Druhý hráč má vítěznou strategii. Pojďme to dokázat a ukázat tuto strategii. K tomu vytvoříme dávkový strom pro každou z počátečních pozic. Ve stromu stran označíme stav obou hromádek ve formátu (a, b), kde a je počet kamenů v první hromadě, b je počet kamenů ve druhé hromadě. V průběhu prvního hráče zvážíme čtyři možné možnosti jeho chování: přidat 1 na první hromádku, zdvojnásobit počet kamenů na první hromádce, přidat 1 na druhou hromádku a zdvojnásobit počet kamenů na druhé hromádce. U druhého hráče označíme jeden tah vedoucí k výhře. Tahy budou zobrazeny ve formě šipek, vedle kterých napíšeme I v případě prvního tahu a II v případě druhého tahu.

Dávkový strom pro výchozí pozici (6, 33).

Dávkový strom pro výchozí pozici (8, 32).

Podle stromu stran, bez ohledu na tahy prvního, má druhý vždy vítěznou strategii, která mu umožňuje vyhrát v jednom tahu popsaném ve stromech (součty po Vanyových tazích jsou 73, 80, 74 a 136, zleva doprava). Podle herního stromu navíc může druhý hráč vyhrát přesně v jednom tahu.

Zadání 2

Formální řešení

Zvažte výchozí pozici (6,32). Všimněte si, že je blízko k (6,33) z Úkolu 1. V Úkolu 1 jsme zjistili, že v pozici (6, 33) vyhrává druhý a to v jednom tahu. Tuto podmínku lze přeformulovat: na pozici (6.33) je vítězem v jednom tahu ten, kdo ne procházky (tj. procházky druhé). Jinými slovy, ten, kdo se hýbe, jedním tahem prohraje.

Na pozici (6,32) první vyhrává dvěma tahy. Pojďme to dokázat. Petya svým prvním tahem přidá +1 k druhé hromadě. Tím je získána poloha (6,33). Jak jsme již dříve zjistili, na pozici (6.33) ten, kdo se pohybuje, prohrává. V našem případě to bude tah Vanyi. Váňa proto prohraje jedním tahem. V tomto případě bude Petya muset provést celkem dva tahy: první (přidat 1 kámen na druhou hromádku) + druhý tah v souladu se stromem večírku v Úkolu 1, podle Vanyiny strategie.

Podobně v poloze (7, 32). Petya svým prvním tahem přidá k první hromádce +1 kámen a získá pozici (8, 32). V této pozici podle stejného uvažování ten, kdo chodí, prohrává. Bude tah Vanyi, takže Vanya prohraje. Petyina výherní strategie je následující: Petya přidá k první hromádce +1 kámen a poté sleduje Vanyinu strategii z Úkolu 1.

Podobně v poloze (8, 31). Petya svým prvním tahem přidá na druhou hromádku +1 kámen a získá pozici (8, 32). V této pozici podle stejného uvažování ten, kdo chodí, prohrává. Vanya bude mít tah, takže Vanya prohraje. Petyina vítězná strategie je následující: Petya přidá +1 kámen na druhou hromádku a poté sleduje Vanyinu strategii z Úkolu 1.

Přiřazení 3

Diskuse

Všimněte si, že ze situace (7, 31) je velmi snadné dostat se buď do situací (8, 31) a (7, 32), ve kterých podle předchozího úkolu vyhrává ten, kdo chodí, nebo do situace (14, 31) a (7, 62), ve kterých ten, kdo chodí, může vyhrát v jednom tahu zdvojnásobením počtu kamenů ve druhé hromádce. Ukazuje se tedy, že Vanya by měl mít vítěznou strategii. Kromě toho může vyhrát jak ve 2 tazích (první dva případy), tak v jednom tahu (druhé dva případy).

Formální řešení

Ve výchozí pozici (7, 31) Vanya vyhraje v jednom nebo dvou tazích. Pojďme to dokázat. K tomu vytvořme strom všech stran.

Strom všech stran pro výchozí pozici (7, 31).

Podle stromu všech her Vanya vyhrává buď v jednom tahu (pokud Petya zdvojnásobil počet kamenů v první nebo druhé hromádce), nebo ve dvou tazích (pokud Petya zvýšil počet kamenů v první nebo druhé hromádce o 1).

Na počáteční pozici (7, 31) má tedy Vanya vítěznou strategii, zatímco Vanya vyhraje v jednom nebo dvou tazích.

Evgeny Smirnov

IT expert, učitel informatiky

Dva hráči, Pasha a Vova, hrají následující hru. Před hráči je hromada kamenů. Hráči se střídají, Pasha dělá první tah. V jednom tahu může hráč přidat na hromádku 1 kámen nebo 10 kamenů. Například máte hromadu 7 kamenů, v jednom tahu můžete získat hromadu 8 nebo 17 kamenů. Každý hráč má neomezený počet kamenů k provádění tahů. Hra končí v okamžiku, kdy počet kamenů na hromádce dosáhne alespoň 31. Hráč, který provedl poslední tah, je považován za vítěze, tj. První hráč, který obdrží hromádku obsahující 31 nebo více kamenů.

V počátečním okamžiku byly na hromadě S kameny, 1 ≤ S ≤ 30.

Rozhodnutí.

1. a) Paša může vyhrát, pokud S \u003d 21, ..., 30. S menšími hodnotami S v jednom tahu je nemožné získat hromadu s více než 30 kameny. Pašovi stačí zvýšit počet kamenů o 10. S S 1. b) Vova může vyhrát prvním tahem (bez ohledu na to, jak Paša hraje), pokud zpočátku je v hromádce S \u003d 20 kamenů. Po prvním tahu Paši bude na hromadě 21 kamenů nebo 30 kamenů. V obou případech Vanya zvyšuje počet kamenů o 10 a vyhrává v jednom tahu.

2. Možné hodnoty S: 10, 19. V těchto případech Pasha očividně nemůže vyhrát prvním tahem. Může však získat hromadu 20 kamenů (při S \u003d 10 zvýší počet kamenů o 10; při S \u003d 19 přidá 1 kámen). Tato pozice je popsána v položce 1 b. V něm hráč, který se bude hýbat (nyní je to Vova), nemůže vyhrát a jeho protivník (tj. Pasha) vyhraje další tah.

3. Možná hodnota S: 18. Po prvním tahu Pashy bude na haldě 19 nebo 28 kamenů. Pokud je na hromádce 28 kamenů, Vova zvýší počet kamenů o 10 a vy hrajete se svým prvním tahem. Situace, kdy je na haldě 19 kamenů, byla vyřešena v kroku 2. V této situaci vyhrává hráč, který se bude hýbat (nyní je to Vova), druhým tahem.

host 26.05.2014 12:31

Bod 3. Ale co situace, když je v hromadě zpočátku 9 kamenů. Poté, co se Pašovy kameny stanou buď 10 nebo 19, Vasya skončí až 20 a dále podle odstavce 1.b.

Konstantin Lavrov

Ano, 9 je také správná odpověď. Stačí označit alespoň jednu správnou hodnotu.

Dva hráči, Pasha a Vova, hrají následující hru. Před hráči je hromada kamenů. Hráči se střídají, Pasha dělá první tah. V jednom tahu může hráč přidat na hromádku 1 kámen nebo 10 kamenů. Například máte hromadu 7 kamenů, v jednom tahu můžete získat hromadu 8 nebo 17 kamenů. Každý hráč má neomezený počet kamenů, aby mohl provádět tahy. Hra končí v okamžiku, kdy počet kamenů na hromádce dosáhne alespoň 41. Hráč, který provedl poslední tah, je považován za vítěze, tj. První hráč, který obdrží hromádku obsahující 41 nebo více kamenů.

V počátečním okamžiku byly na hromadě S kameny, 1 ≤ S ≤ 40.

Řekneme, že hráč má vítěznou strategii, pokud může zvítězit jakýmkoli pohybem soupeře. Popsat strategii hráče znamená popsat, jaký pohyb by měl provést v jakékoli situaci, na kterou může narazit v jiné hře soupeře.

Dokončete následující úkoly. Ve všech případech svou odpověď zdůvodněte.

1. a) Uveďte všechny takové hodnoty čísla S, ve kterých může Pasha vyhrát jedním tahem. Zdůvodněte, že byly nalezeny všechny požadované hodnoty S, a uveďte vítězné tahy.

b) Uveďte hodnotu S., při které Paša nemůže zvítězit v jednom tahu, ale u kteréhokoli z Pašových tahů může Vova vyhrát svým prvním tahem. Popište vítěznou strategii společnosti Vova.

2. Uveďte dvě hodnoty S, pro které má Pasha vítěznou strategii, a Pasha nemůže vyhrát v jednom tahu, ale může vyhrát svým druhým tahem, bez ohledu na to, jak se pohybuje Vova. U daných hodnot S popište Pashovu vítěznou strategii.

3. Uveďte hodnotu S, při které má Vova vítěznou strategii, která mu umožňuje vyhrát v prvním nebo druhém tahu v jakékoli hře Pasha, ale Vova nemá strategii, která by mu umožnila vyhrát v prvním tahu. U uvedené hodnoty S popište vítěznou strategii společnosti Vova. Vytvořte si strom všech možných her s touto výherní strategií Vova (ve formě obrázku nebo stolu). Na okrajích stromu uveďte, kdo provede tah, v uzlech - počet kamenů v hromadě.

Rozhodnutí.

1. a) Paša může vyhrát, pokud S \u003d 31, ..., 40. S menšími hodnotami S v jednom tahu nemůžete získat hromadu obsahující více než 40 kamenů. Pašovi stačí zvýšit počet kamenů o 10. Pokud S b) Vova může vyhrát prvním tahem (bez ohledu na to, jak Paša hraje), pokud je na hromadě zpočátku S \u003d 30 kamenů. Poté, po prvním tahu Paši, bude na hromadě 31 kamenů nebo 40 kamenů. V obou případech Vanya zvyšuje počet kamenů o 10 a vyhrává v jednom tahu.

2. Možné hodnoty S: 20, 29. V těchto případech Pasha samozřejmě nemůže vyhrát prvním tahem. Může však získat spoustu 30 kamenů (při S \u003d 20 zvýší počet kamenů o 10; při S \u003d 29 přidá 1 kámen). Tato pozice je popsána v bodě 1. b). V něm hráč, který se pohne (nyní je to Vova), nemůže vyhrát a jeho soupeř (tj. Pasha) vyhraje další tah.

3. Možná hodnota S: 28. Po prvním tahu Pashy bude na haldě 29 nebo 38 kamenů. Pokud je na hromádce 38 kamenů, Vova zvýší počet kamenů o 10 a vy budete hrát s prvním tahem. Situace, kdy je na hromádce 29 kamenů, je vyřešena v kroku 2. V této situaci vyhrává druhým tahem hráč, který se bude hýbat (nyní je to Vova).

Tabulka ukazuje strom možných her pro popsanou strategii Vova. Konečné pozice (ve kterých vyhrává Vova) jsou podtrženy. Obrázek ukazuje stejný strom v grafické podobě (oba způsoby zobrazení stromu jsou přípustné).

Další hráči hrají dva hráči, Petya a Vanya. Před nimi jsou dvě hromady kamenů, v první z nich jsou 2 a ve druhé - 3 kameny. Každá hra ro-ka není omezená, ale hodně kamenů. Game-ro-ki jde zase, první tah je de-la-et Petya. Tah je v tom, že hráč buď am-and-wa-je počet kamenů v nějaké hromadě, nebo přidá 4 kameny k nějaké hromadě. Hra je dokončena v tom okamžiku, kdy je celkový počet kamenů ve dvou hromadách alespoň 31. Pokud je v okamžiku dokončení hry celkový počet kamenů na dvou hromadách není menší než 40, pak jste hráli Petya, jinak - Vanya. Kdo jste-hra-ry-va-e, když oba hráči hrají bez chyb? Jaký by měl být první krok hry you-game-ry-va-yu-shch-go? Odůvodněte odpověď.

Rozhodnutí.

Vanya vyhrává.

Pro důkaz zvažte neúplný herní strom navržený ve formě tabulky, kde každá buňka obsahuje dvojice čísel oddělené čárkou. Tato čísla odpovídají počtu kamenů v každé fázi hry na první a druhé hromádce.

Tabulka obsahuje všechny možné možnosti tahů prvního hráče. Z toho je patrné, že u jakéhokoli tahu prvního hráče má druhý tah, který vede k vítězství.

Dva hráči, Peťa a Vasya, hrají následující hru. Před nimi jsou dvě hromady kamenů, v první z nich jsou 2 a ve druhé - 1 kámen. Každý hráč má neomezený počet kamenů. Hráči se střídají, Petya jde první. Tah spočívá ve skutečnosti, že hráč buď zvýší trojnásobný počet kamenů na nějaké hromádce, nebo přidá 3 kameny na hromádku. Vítězem je hráč, na jehož tahu je na jedné z hromádek alespoň 24 kamenů. Kdo vyhrává při hraní bez chyb? Jaký by měl být první tah vítězného hráče?

Odůvodněte odpověď.

Rozhodnutí.

Petya vyhrává, se svým prvním tahem musí ztrojnásobit počet kamenů ve druhé hromadě. Pro důkaz zvažte neúplný herní strom navržený ve formě tabulky, kde každá buňka obsahuje dvojice čísel oddělené čárkou. Tato čísla odpovídají počtu kamenů v jednotlivých fázích hry na první a druhé hromádce.

Tabulka obsahuje všechny možné varianty Vasyiných pohybů. Z toho je patrné, že u každé z jeho odpovědí má Petya tah vedoucí k vítězství.

Dva hráči, Petya a Vanya, hrají následující hru. Před hráči je hromada kamenů. Hráči se střídají, Petya dělá první tah. Jedním tahem může hráč přidat jeden kámen na hromádku nebo pětkrát zvýšit počet kamenů na hromádce. Například máte hromadu 10 kamenů, v jednom tahu můžete získat hromadu 11 nebo 50 kamenů. Každý hráč má neomezený počet kamenů k provádění tahů.

Hra končí v okamžiku, kdy počet kamenů v hromádce dosáhne více než 100. Vítězem se stává hráč, který provedl poslední tah, tj. První hráč, který obdrží hromádku obsahující 101 nebo více kamenů.

V počátečním okamžiku byly na hromadě S kameny, 1 ≤ S ≤ 100.

Říká se, že hráč má vítěznou strategii, pokud může vyhrát na jakýchkoli protivníkových tazích. Popsat strategii hráče znamená popsat, jaký pohyb by měl provést v jakékoli situaci, na kterou může narazit v jiné hře soupeře.

Dokončete následující úkoly. Ve všech případech svou odpověď zdůvodněte.

1. a) Na jakých hodnotách S může Petya vyhrát prvním tahem? Uveďte všechny tyto hodnoty a Petitův vítězný tah.

b) Uveďte hodnotu S, při které Petya nemůže vyhrát v jednom tahu, ale u jakéhokoli tahu může Petya vyhrát svým prvním tahem. Popište Vanyovu vítěznou strategii.

2. Uveďte dvě hodnoty S, pro které má Peťa vítěznou strategii, a Peťa nemůže vyhrát svým prvním tahem, ale Peťa může vyhrát svým druhým tahem, bez ohledu na to, jak se Vanya pohybuje. U uvedených hodnot S popište Petitovu vítěznou strategii.

3. Uveďte hodnotu S, při které má Vanya vítěznou strategii, která mu umožňuje vyhrát v prvním nebo druhém tahu v jakékoli hře Petya, a současně Vanya nemá strategii, která mu umožní vyhrát v prvním tahu.

Pro uvedenou hodnotu S popište Vanyovu vítěznou strategii. Vytvořte si strom všech možných her s touto výherní strategií od Vanyi. Prezentujte jej ve formě obrázku nebo tabulky. U každého okraje stromu uveďte, kdo provede tah, u každého uzlu - počet kamenů v pozici.

Rozhodnutí.

1. a) Petya může vyhrát, pokud S \u003d 21, ..., 100. U menších hodnot S je jedním tahem nemožné získat hromadu s více než 100 kameny. Pete dost na to, abyste 5krát zvýšili počet kamenů. S S 1. b) Vanya může vyhrát prvním tahem (bez ohledu na to, jak Petya hraje), pokud je na hromadě zpočátku S \u003d 20 kamenů. Po prvním tahu Petit bude na hromádce 21 kamenů nebo 100 kamenů. V obou případech Vanya zvýší počet kamenů pětkrát a vyhraje jedním tahem.

2. Možné hodnoty S: 4, 19. V těchto případech Petya očividně nemůže vyhrát prvním tahem. Může však získat hromadu 20 kamenů (při S \u003d 4 zvýší počet kamenů 5krát; při S \u003d 19 přidá 1 kámen). Tato pozice je popsána v bodě 1 písm. B). V něm hráč, který se bude hýbat (nyní je to Vanya), nemůže vyhrát a jeho soupeř (tj. Petya) vyhraje další tah.

3. Možná hodnota S: 18. Po Petitově prvním tahu bude na haldě 19 nebo 90 kamenů. Pokud je na hromádce 90 kamenů, Vanya zvýší počet kamenů 5krát a vyhraje na svůj první tah. Situace, kdy je na haldě 19 kamenů, byla vyřešena v kroku 2. V této situaci vyhrává hráč, který se bude hýbat (nyní je to Vanya), druhým tahem.

Tabulka ukazuje strom možných her pro popsanou strategii Vanyi. Konečné pozice (ve kterých Vanya vyhrává) jsou podtrženy. Na obrázku je graficky zobrazen stejný strom (jsou povoleny oba způsoby jeho zobrazení).

Proveďte test těchto úkolů

Složitost : vysoký.
Odhadovaná doba řešení : 20 minut
Téma: Matematické základy programování. Algoritmy.
Podtéma: Hry a strategie
Co se kontroluje: Znalost základních pojmů souvisejících s analýzou her s úplnými informacemi. Schopnost identifikovat vítězné a prohrávající pozice.
Jak může úkol vypadat? Například takto: Je uveden popis hry dvou hráčů s úplnými informacemi. Je nutné určit pozice, ve kterých má hráč uvedený v podmínce výherní strategii, která mu umožňuje zaručeně vyhrávat ve stanoveném počtu tahů.

Jak analyzovat problém.
Dobrou analýzu provedl K.Yu. Polyakov v článku „Unified State Exam: New Strategies (Task C3)“ [1. září. Informatika. 2013, leden. P. 22-27]. Článek obsahuje mnoho úkolů pro nezávislé řešení. V článku je pouze jedna nepřesnost: strom zobrazený na stránce 25 se nazývá strom „možných herních možností“. V kontextu článku je jasné, o co jde. Ale při analýze článku se studenty je lepší objasnit: strom možných možností pro hru se zvolenou strategií Vanyi. Strom možných variant hry (nebo jednoduše strom hry) se obvykle nazývá strom představující všechny možné hry. To znamená, že jsou brány v úvahu všechny možné tahy Ványi, nejen tahy odpovídající určité strategii.

Komentář. Úkol C3-2013 kombinuje myšlenky úkolů C3-2011 a C3-2012. Kontinuita od C3-2012 je patrná z analýzy K.Yu.Polyakova. Viz také rozpis C3-2012