15.10.2020

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. Vítězem se stává hráč, který provedl poslední tah, tj. První, 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. U menších hodnot S nelze v jednom tahu 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 je na hromadě zpočátku 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ů, zvýší Vova počet kamenů o 10 a vy budete hrát s prvním tahem. Situace, kdy je v 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 bodu 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ů k provádění tahů. Hra končí v okamžiku, kdy počet kamenů na hromádce dosáhne alespoň 41. Vítězem se stává hráč, který provedl poslední tah, 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 vyhrát 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 haldě.

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 očividně 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 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: 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 analyzována v kroku 2. V této situaci vyhrává hráč, který se bude hýbat (nyní je to Vova), druhým tahem.

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řijatelné).

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ů. Hra-ro-ki jde střídavě, 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 celkový počet kamenů ve dvou hromadách dosáhne alespoň 31. Pokud v okamžiku dokončení hry bude celkový počet kamenů počet kamenů ve 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. Ukazuje, ž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. Hráč vyhrává, po 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ý strom hry navržený ve formě tabulky, kde jsou do každé buňky zapsány 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é 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 zvítězit v některém z tahů 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) 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 každého tahu může Petya Vanya 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 zároveň Vanya nemá strategii, která mu umožní vyhrát v prvním tahu.

Pro uvedenou hodnotu S popište Vanyinu vítěznou strategii. Postavte strom všech možných her s touto vítěznou 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. Peťovi stačí pětkrát zvýšit 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 v 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 v haldě 19 kamenů, byla vyřešena v kroku 2. V této situaci vyhrává druhým tahem hráč, který se bude hýbat (nyní je to Vanya).

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ů

Analýza 26 úkolů USE 2017 v informatice z ukázky. Tento úkol je ze druhé části vysoké úrovně obtížnosti. Předpokládaný čas na dokončení úkolu je 30 minut. Maximální skóre za splnění úkolu je 3.

Zaškrtnuté položky obsahu:
- Schopnost postavit herní strom podle daného algoritmu a doložit vítěznou strategii.

Úkol 26

Dva hráči, Pasha a Valya, 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 jeden kámen nebo zvýšit počet kamenů v haldě dvakrát... Například když máte hromadu 15 kamenů, v jednom tahu můžete získat hromadu 16 nebo 30 kamenů. Každý hráč má neomezený počet kamenů k provádění tahů.
Hra končí v okamžiku, kdy počet kamenů v haldě dosáhne alespoň 20. Pokud v tomto případě není na hromádce více než 30 kamenů, pak se za vítěze považuje hráč, který provedl poslední tah. Jinak se jeho soupeř stává vítězem. Například pokud bylo v haldě 17 kamenů a Paša zdvojnásobil počet kamenů v haldě, pak hra skončí a Valya bude vítězem. V počáteční chvíli halda obsahovala S kameny, 1 ≤ S ≤ 19.

Říkáme, že hráč má vítězná strategiepokud může vyhrát na některém z tahů 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.
1.a) Pro jaké hodnoty čísla S Může Pasha vyhrát jedním tahem?
Uveďte všechny tyto hodnoty a odpovídající pašovy tahy.
b) Pro kterého hráče má vítěznou strategii S = 18, 17, 16?
Popište výherní strategie pro tyto případy.
2. Pro kterého hráče má vítěznou strategii S \u003d 9, 8? Popište vhodné výherní strategie.
3. Který hráč má vítěznou strategii S \u003d 7? Postavte si strom všech možných her s touto výherní strategií (ve formě obrázku nebo stolu). Uveďte, kdo provede pohyb na okrajích stromu; v uzlech - počet kamenů na pozici.

1.a) Paša může vyhrát, pokud S \u003d 19 nebo S \u003d 10, 11, 12, 13, 14, 15. Pro S \u003d 19 při prvním tahu musíte na hromádku přidat jeden kámen se zbývajícími uvedenými hodnotami S musíte zdvojnásobit počet kamenů.

b) Kdy S \u003d 16, 17 nebo 18 zdvojnásobení počtu kamenů nedává smysl, protože po takovém tahu nepřátel vyhrává. Můžeme tedy předpokládat, že jediným možným tahem je přidání jednoho kamene na hromádku.

Když S \u003d 18 po takovém tahu Paši bude v hromadě 19 kamenů. V této poloze vyhrává chodec (tj. Valya) (viz bod 1a): na S \u003d 18 Pasha (hráč, který by měl jít jako první) prohrává.

Vali má vítěznou strategii.

Když S \u003d 17, poté, co Pasha přidá jeden kámen při svém prvním tahu, bude na hromádce 18 kamenů. V této poloze ztrácí chodec (tj. Valya) (viz výše): na S \u003d 17 Pasha (hráč, který by měl jít jako první) vyhrává. Paša má vítěznou strategii.

Když S \u003d 16 Vali má vítěznou strategii. Ve skutečnosti, pokud Pasha zdvojnásobí počet kamenů v prvním tahu, pak je v haldě 32 kamenů a hra okamžitě končí vítězstvím Vali. Pokud paša přidá jeden kámen, pak se na hromadu stane 17 kamenů. Jak již víme, na této pozici vyhrává hráč, který se musí hýbat (tj. Valya).

Ve všech případech je zisk dosažen skutečností, že hráč s vítěznou strategií musí během svého tahu přidat na hromádku jeden kámen.

Pro zadané hodnoty můžete nakreslit stromy všech možných dávek S.
Další možností je (1) naznačit, že zdvojnásobení haldy nedává smysl, a (2) důsledně zmenšovat velikost případu S \u003d 18 k této příležitosti S \u003d 19, případ S \u003d 17 - příležitostně S \u003d 18 atd.

2. Kdy S \u003d 9 nebo 8 Pasha má vítěznou strategii. Spočívá ve zdvojnásobení počtu kamenů v hromadě a získání hromady obsahující 18, respektive 16 kamenů. V obou případech hráč, který provede tah (nyní Valya), prohrává (viz bod 1b).

3. Kdy S \u003d 7 Vali má vítěznou strategii. Po prvním tahu Pashy může být na hromádce 8 nebo 14 kamenů. Na obou těchto pozicích vyhrává hráč, který provede tah (nyní je to Valya). Happening S \u003d 8 přezkoumáno v odstavci 2, případ S \u003d 14 přezkoumáno v odstavci 1a.

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

Strom všech stran možný s Valininou strategií. \u003e\u003e označuje pozice, kde hra končí.

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 večírků.
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řeba 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áčů při správné hře rozhodně 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 je psát ve Sjednocené státní zkoušce) a poté - „formální rozhodnutí“, tedy to, co je třeba ve Sjednocené státní zkoušce napsat.

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ásobit počet 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 provádět potenciálně čtyři akce: přidat 1 na první hromádku, zdvojnásobit počet kamenů na první hromádce, přidat 1 na druhou hromádku, 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. Dostáváme (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. To znamená, že vyhrává druhá.

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

Vyřešeno podobným způsobem s (8.32).

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 budeme zvažovat č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.

Párty 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 (6,33) z Úkolu 1. V Úkolu 1 jsme zjistili, že na 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í ztrácí ten, kdo chodí. Vanya bude mít tah, 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. Současně 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 vyhrává jedním nebo dvěma tahy. 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 stran 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

Pro efektivní výcvik v informatice je ke každému úkolu uveden stručný teoretický materiál k dokončení úkolu. Vybráno více než 10 tréninkových úkolů s analýzou a odpověďmi vyvinutých na základě demo verze předchozích let.

V programu KIM USE 2020 v informatice a ICT nedochází ke změnám.

Oblasti, ve kterých bude testování znalostí probíhat:

• Programování;
• Algoritmizace;
• Nástroje ICT;
• Informační činnost;
• Informační procesy.

Akce, kterou je třeba podniknout, když připravuje se:

• Opakování teoretického kurzu;
• Rozhodnutí testy v informatice online;
• Znalost programovacích jazyků;
• Zdokonalit matematiku a matematickou logiku;
• Chcete-li použít širší škálu literatury - školní osnovy nestačí k úspěchu na zkoušce.

Struktura zkoušky

Délka zkoušky je 3 hodiny 55 minut (255 minut), z čehož se jeden a půl hodiny doporučuje věnovat úkolům první části CMM.

Úkoly v tiketech jsou rozděleny do bloků:

• Část 1- 23 úkolů s krátkou odpovědí.
• Část 2 - 4 problémy s podrobnou odpovědí.

Z navrhovaných 23 úkolů první části zkušební práce se 12 týká základní úrovně testování znalostí, 10 - zvýšené složitosti, 1 - vysoké úrovně složitosti. Tři úkoly druhé části s vysokou úrovní složitosti, jedním se zvýšenou úrovní.

Při rozhodování je povinné zaznamenat podrobnou odpověď (bezplatný formulář).
U některých úkolů je text podmínky prezentován v pěti programovacích jazycích najednou - pro pohodlí studentů.

Body za úkoly informatiky

1 bod - za 1-23 úkolů
2 body - 25.
3 body - 24, 26.
4 body - 27.
Celkem: 35 bodů.

Chcete-li vstoupit na technickou univerzitu střední úrovně, musíte získat alespoň 62 bodů. Pro vstup na univerzitu v hlavním městě musí počet bodů odpovídat 85-95.

Pro úspěšné napsání zkoušky musíte mít jasnou znalost teorie a konstantní praxe v řešení úkoly.

Váš vzorec pro úspěch

Práce + práce na chybách + pečlivě si přečtěte otázku od začátku do konce, abyste se vyhnuli chybám \u003d maximální skóre na zkoušce z informatiky.

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

Každý, kdo má na 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ů, v jednom tahu můžete získat hromadu 16 nebo 30 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ň 22. Hráč, který provedl poslední tah, je považován za vítěze, tj. První hráč, který obdrží hromádku obsahující 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, za které 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 každého tahu může Petya Vanya vyhrát svým prvním tahem. Popište Vanyovu vítěznou strategii.

2. Uveďte dvě 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 Vanya pohybuje.
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 při 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.
Postavte 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 od „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é bude nutné zkontrolovat!)

Zkontrolujte předpoklad pro S \u003d 10 při min0. Tato kontrola bude sloužit jako odpověď. k otázce 1b
Pokud S \u003d 10, Petya má 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 pozici S \u003d 10 dole 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: Pokud S \u003d 10, Petya má 2 tahy, které nemůže vyhrát, ale pro každý tah 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 bylo zaručeno, že Petya vyhraje na druhém tahu, tj. skončil na místě max0 , po Vanyově pohybu potřebuje jeho první 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 je třeba je zkontrolovat ...
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 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 vyhrát prvním tahem, ale může zvítězit 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í prohranou pozici 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 kvůli zaručené ztrátě 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 pro zaručenou ztrátu 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 zaručeným prvním tahem, protože jeho vítězství závisí na tahu Petya, takže Vanya má strategii vyhrát buď na první, nebo na druhý tah: 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 -