Ігри двох осіб
Вчитель-методист
Хмельницького ліцею №17,
Поташнік О. А.
В останній час на багатьох математичних олімпіадах почали
з’являтись задачі на ігри двох осіб. В усіх іграх такого типу спочатку є деякий
набір елементів – фішок, камінців і т.д. Гравці по черзі роблять «ходи» -
переміщують фішки по дошці, беруть камінці з купок. При цьому для кожної гри є
свої правила. Оскільки число елементів на дошці чи в купці з кожним ходом
зменшується, то гра повинна закінчитися, при цьому жоден хід не може бути
випадковим; кожен гравець володіє «повною інформацією» в тому розумінні, що
йому відомі усі дії суперника. Порівняйте гру в шахи і яку не будь відому вам гру в карти. У першому
випадку на будь-якій стадії розгортання партії кожний із суперників має повне
уявлення про позицію, що склалася. Ця позиція просто перед очима. Вона вичерпно
визначається розміщення фігур на шахівниці та черговість ходу: дивись, аналізуй
, оцінюй, прогнозуй. Якість кожного наступного ходу в партії залежить тільки
від уміння, інтелекту, врівноваженості, загалом – від особистих якостей гравця.
Натомість при грі в карти гравець не знає, які карти має суперник (чи
суперники), а які ще не введені в гру. Отже, плануючи свій наступний хід, він
принципово не може передбачити його можливі наслідки, бо не володіє повною
інформацією про ситуацію в грі ( розподіл карт) на момент ходу. Результат
конкретної партії залежить не тільки від уміння гравців, але також від багатьох
випадкових обставин.
Гра повинна бути «рівноправною» тобто, можливі ходи
обумовлені виключно розміщенням елементів, яке виникло перед даним ходом, а не
тим чия в даний момент черга ходити, чи тим, які були попередні ходи. Правилом
гри передбачено як слід тлумачити результат зіграної партії (заключну позицію):
хто з гравців виграв, а хто програв ( у деяких іграх можливий нічийний
варіант).
Ігри цього типу називають скінченними іграми двох осіб із
повною інформацією.
В гру вступають не для того, щоб програти. Перший хід
попереду, віра в успіх безперечна, а можливості невичерпні. Але партнер –
гідний суперник. Потрібно відгадати його задуми. З чого ж почати гру?
Чи існує в ній гарантований виграш?
Ось коло
питань, які хвилюють гравців перед початком партії.
Розглянемо таку гру. Є
дві купки сірників. Два гравці по черзі беруть сірники з купок. За своїм ходом
дозволяється з однієї купки взяти довільну кількість сірників, але не менше
одного. Переможцем вважається той гравець, хто забрав останні сірники.
Якщо Вам не доводилось чути про цю гру раніше, то зараз
самий час відкласти читання і подумати над проблемою: якої стратегії слід
дотримуватись у цій грі, щоб завжди вигравати. Гучне слово «стратегія» означає
тут цілком зрозумілу річ. Йдеться про певну лінію поведінки, дотримування
певних принципів. Оскільки нас цікавить виграшна стратегія, то йдеться про
пошук універсального правила, дотримуючись якого при виборі своїх ходів, ми
виграватимемо у будь-якого, як би добре він не грав. Ви, певне, відразу
помітили, що останнє речення висловлює думку, суперечливу собі. Справді, якщо таке універсальне правило
існує, то що трапиться, коли ним володітимемо не тільки ми, але й і наш
суперник?
Звичайно ж, суперечливість відразу усувається, якщо ми
дещо обмежимо наші претензії завжди
вигравати, а натомість визнаємо за суперником таку силу інтелекту і
обізнаності, на яку претендуємо самі, тобто розглядатимемо гру як повністю
симетричну щодо обох учасників. Якщо обидва гравці діятимуть безпомилково, то
результат гри залежатиме зовсім не від них, а від початкової позиції (по
скільки сірників лежить у купках перед початком гри) та від черги першого ходу.
Назвемо позицію виграшною, якщо в ній можна зробити хід,
що вее до виграшу партії незалежно від того, як відповідатиме суперник. Решта
позицій – програшні. Це позиції, в яких не можна зробити добрий хід, бо кожний
з них віддає виграш суперникові, якщо тільки той уде грати як найкраще.
Пошуки виграшної стратегії багатьох ігор – це захоплюючі
і повчальні математичні дослідження, які містять у мініатюрі всі фази наукового
відкриття.
Виграшна стратегія в даній грі полягає у зрівнюванні
сірників у купках. Розглянута гра належить до так званих нім-ігор. Гра значно
ускладнюється, якщо правила гри залишити незмінними, але збільшити кількість
купок (навіть до трьох). В давні часи
така гра була поширена в Китаї і зветься по-китайськи фан-тан.
Перевірка на парність. Якими міркуваннями керується гравець, вибираючи
стратегію? Які орієнтири він знаходить для побудови своїх планів? Одним з них
може стати поняття парності. Суть його полягає в тому, що головне стратегічне
рішення приймається з урахуванням того, чи парно число деяких елементів
(наприклад: ходів, клітин ігрового поля і т. д.), які фігурують в грі. Більш
докладно ці ситуації ми розберемо на прикладах.
Приклад 1.
Двоє по черзі розламують шоколадну плитку 6 ×8. За один хід
дозволяється зробити прямолінійний розлом будь-якого зі шматків вздовж
заглиблення. Програє той, хто не зможе зробити наступного ходу. У кого з
гравців є виграшна стратегія?
Розв’язання. При кожному розламуванні кількість шматків
збільшується на 1. Спочатку був 1 шматок. В кінці гри, коли не можна зробити
жодного ходу, таких шматків 48. Отже, гра триватиме рівно 47 ходів. Оскільки
при цьому кожний непарний хід робить гравець, який розпочинає гру, то він
зроить і останній 47-й хід. Тому перший гравець переможе, незалежно від того,
як буде грати він сам та його суперник.
До речі, в даній задачі число 47 було інваріантом.
Приклад 2. На
дошці записано 10 одиниць та 10 двійок. За один хід дозволяється стирати
будь-які дві цифри і, якщо вони були однаковими, записати двійку, а якщо
різними – одиницю. Якщо остання цифра, що залишилась на дошці, - одиниця, то
виграє перший гравець, якщо ж двійка – то другий. У кого з гравців є виграшна
стратегія?
Розв’язання. При кожному ході кількість одиниць або не
змінюється, або зменшується на 2. Оскільки спочатку було парне число одиниць,
то одиниця залишатися не може. Отже,
незалежно від гри суперників, виграє другий гравець.
Розглянутий прийом має назву «перевірка на парність».
Звичайно його використовують як простий і ефективний засіб довести неможливість
того чи іншого факту.
Симетрична стратегія. Для ігор, в яких
гравці кладуть фішки на дошку чи з’єднують точки вірізками тощо, існує так
звана симетрична стратегія. В її основі лежить нехитра ідея копіювати ходи
суперника. При цьому роздуми 2-го гравця (після 1-го ходу починаючого)
зводяться приблизно до наступних.
Залучаючи геометричні міркування, він старається знайти
вісь симетрії, яка ділила б початкову
конфігурацію елементів на дві рівні області так, щоб хід починаючого повністю
опинився в одній з них. Вісь знайдена. Тоді 2-й гравець робить свій 1-й хід
симетрично 1-му ходу починаючого. Він повністю опинився в другій області. Якщо
починаючий і далі ходить в свою область, то в силу симетрії у 2-го гравця
завжди знайдеться хід у відповідь в своїй області. Якщо ж починаючий на якомусь
ході змінить свою область, те ж зробить і 2-й гравець. Зрозуміло, що по
закінченню можливих ходів переможцем опиниться 2-й гравець.
З першого ходу може здаватись, що роль починаючого в
подібних іграх пасивна і у всіх випадках він приречений на поразку. Але це не
так. Наступна задача доводить, що переможцем в іграх такого роду може бути як
другий, так і перший гравець.
Приклад 3. В
таблиці n× n квадратиків воє грають в
таку гру:за своїм ходом (їх роблять почергово) кожний з гравців зафарбовує одну
клітинку в чорний колір. Перемагає той, хто зафарбовує останню клітинку. При
яких n перемагає перший або другий гравець.
Розв’язання. При
парному n перемагає другий гравець.
Так як таблиця є квадратом, її центр симетрії знаходиться в точці перетину
діагоналей. В даному випадку центр симетрії знаходиться у вузлі квадратиків, з
яких складається таблиця. Тоді, якби не зробив хід перший гравець, другий
завжди знайде не зафарбовану клітинку, яка симетрична даній.
При непарному n перемагає
перший гравець. В даному випадку центр симетрії знаходиться в точці перетину
діагоналей центрального квадратика. Тоді, перший гравець зафарбовує центральний
квадратик, і далі діє симетрично другому гравцю.
Парна стратегія. Симетричну стратегію можна рахувати
частковим випадком більш загальної парної стратегії. Її назва підкреслює, що
вся гра як би розбивається на парні ходи. А оптимальність стратегії припускає,
що якщо один з гравців зробив якийсь хід, то хід суперника (не обов’язково симетричний) повинен належати
тій ж парі.
Приклад 4.
Фішка стоїть в кутку шахової дошки розміром n× n клітинок. Кожен з двох гравців по черзі
пересувають її на сусіднє поле (воно має спільну сторону з тим, на якому стоїть
фішка). Другий раз ходити на поле, де фішка побувала, неможна. Програє той, хто
не може зробити хід.
а) Доведіть,
що якщо n парне, то починаючи гру може досягти перемоги, а якщо непарне, то
виграє другий.
б) Хто виграє,
якщо на початку фішка стоїть не на кутовому полі, а на сусіднім з ним?
Розв’язання. а)
якщо n парне, то всю дошку можна розбити на прямокутники розміром 1× 2 (доміно).
Починаючий завжи буде мати можливість зробити хід (і тим самим виграє), якщо
буде слідувати такій стратегії:коли фішка стоїть на одній з клітинок якогось
доміно, то він ставить її на другу клітинку цього ж доміно («закриває» доміно).
Якщо n непарне, то можна розбити на доміно всі клітинки,
крім початкової – кутової. Тепер аналогічна стратегія буде виграшною для
другого гравця.
б) Виграє завжди починаючий. При парному n стратегія така ж, що в а) . При
непарному n потрібно знову розбити на
доміно всі клітинки, крім кутової. Розфарбувавши дошку в шаховому порядку,
легко пересвідчитись, що на кутову клітинку 2-й ніколи піти не зможе, тому 1-й
виграє, слідуючи тій ж стратегії «закривання « доміно.
Ігри на математичних
конкурсах та олімпіадах
Приклад 1. В одній купці n сірників, а в другій - m. Двое гравців по черзі беруть сірники.
Кожний може взяти будь-яку кількість, але тільки з однієї купки. Перемагає той,
хто забирає останні сірники. Хто виграє при правильній грі? (7 клас).
Стратегія. При
m≠ n
переможе той, хто починає. Кожним своїм ходом
він може зрівнювати кількість сірників у купках. При m= n,
дотримуючись такої стратегії, переможе другий.
Приклад 2. У купці 1991 сірник. Двоє гравців
беруть по черзі сірники – від 1 до 9. Виграє той, хто забере останній сірник
хто виграє при правильній грі? (7 клас).
Стратегія. Виграє гравець, який ходить першим.
Спочатку йому треба взяти 1 сірник, а потім після кожного ходу другим k
сірників йому треба брати 10- k сірників. Кількість сірників, кратні 10-ти (в
тому числі 0 ), будуть лишатися лише після ходів першого.
Приклад
3. Двоє
гравців по черзі кладуть п’ятикопійчані монети на прямокутний стіл. Монети
повинні повністю вміщуватись на столі і не торкатися одна одної. Той, кому
нікуди покласти монету, програє. Хто переможе при правильній грі – той, хто
ходить першим, чи той, хто другим? (8 клас).
Стратегія. Виграє той, хто ходить першим. Йому
треба першу монету покласти в центр стола, а потім класти монети симетрично
ходам другого відносно центра стола.
Приклад
4. На
дошці розміром 4×4 грають двоє. Ходять по черзі, і кожний гравець своїм ходом
зафарбовує одну клітинку. Кожну клітину можна зафарбувати лише один раз.
Програє той, після чийого ходу утвориться квадрат 2×2, що складається із
зафарбованих клітинок. Хто з гравців може забезпечити собі виграш – той, хто
ходить першим, чи його суперник? Відповідь обґрунтувати. (8 клас).
Стратегія. Виграш може забезпечити собі той, хто
ходить другим. Після ходу першого в клітинку з якимось номером (рис.1) він має
зафарбовувати іншу клітинку з таким самим номером.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
Приклад
5. Дано смужку 1×99. Двоє учнів грають у гру, по черзі роблячи свої ходи.
За один хід треба закреслити одну довільну клітинку в смужці або деякі дві
послідовності. Програє той, хто не може зробити хід. Хто може забезпечити собі
виграш – той, хто розпочинає гру, чи його суперник? (9клас).
Стратегія. Перемогу може забезпечити собі той, хто
розпочав гру. Першим ходом він закреслює 50-ту (центральну) клітинку, потім
повторює ходи суперника симетрично відносно неї.
Приклад 6. На столі лежать чотири яблука масою
600г, 400г, 300г та 250г. Двоє
суперників по черзі підходять до столу і беруть по яблуку, а потім за командою
починають їсти. Наступне яблуко
дозволяється брати гравцеві тільки після того, як він з’їв попереднє. Швидкість поїдання однакова в обох суперників.
Як повинен поводитись гравець, який починає гру, щоб з’їсти якомога більше? ( вказати, яку найбільшу
кількість грамів може забезпечити собі гравець, який починає гру, та протидії
суперника). (10 клас).
Стратегія. Перший має взяти яблуко масою 250г і
тоді або бере яблуко 600г і з’їдає в
сумі 850г, або (якщо другий взяв яблуко 600г) з’їсть яблуко масою 300г, а потім
400г і всього з’їсть 950г. всі інші ходи дадуть меншу суму оскільки другий тоді
може скористатися описаним алгоритмом і з’їсти щонайменше 850г, залишивши
першому не більше 700г.
Приклад 7. Кожній вершині куба поставлено у
відповідність невідємне число, причому сума всіх цих чисел дорівнює одиниці.
Перший гравець відповідає спільній вершині трьох обраних граней не
перебільшувало 1/6. (11 клас).
Стратегія. Серед восьми чисел знайдуться три, не
більше 1/6, причому два з них будуть лежати в кінцях діагоналі однієї із
граней. Цю грань і треба спочатку вибрати першому гравцю.
Задачі для самостійного
розв’язування
1. На столі стоїть 9 стаканів вверх дном. Грають двоє,
роблячи ходи по черзі. За один хід дозволяється перевернути будь-які 4 стакани
або доставити нові 2 стакани вверх дном. Виграє той, після ходу якого всі
стакани стоятимуть вниз дном. У котрого із гравців є виграшна стратегія?
2. У рівностях
* + * + * = *, * + * = *, * = *
двоє вписують по черзі на свій розсуд замість зірочок цілі числа.
Довести, що той, хто розпочинає гру, завжди може досягти правильності усіх
числових рівностей.
3. Дано шахівницю
8×8 і прямокутні доміно 1×2.
За один хід дозволяється накрити дві сусідні клітинки шахівниці так, щоб
плитки доміно не перекривались. Програє той, хто не зможе зробити наступного
ходу. У кого з гравців є виграшна стратегія?
4. На столі викладається коло з монет, які дотикаються
одна одної. Ходи робляться по черзі, за один хід можна взяти одну або дві
монети, що лежать поруч. Виграє той, хто візьме останню монету. Хто виграє при
правильній грі?
5. Микола та Віктор грають в наступну гру на
безкінечному папері у клітинку. Починаючи з Миколи, вони по черзі відмічають
вузли паперу в клітинку - точки перетину
вертикальних і горизонтальних прямих. При цьому кожен з них своїм ходом повинен
відмітити такий вузол, щоб після цього всі відмічені вузли лежали у вершинах
випуклого многокутника (починаючи з другого ходу Миколи). Той з гравців, хто не
може зробити наступного ходу, рахується програвши. Хто виграє при правильній
грі?
6. В таблиці 99×99 клітинок грають двоє. Перший гравець
ставить хрестик на центрі поля, слідом за цим другий гравець може поставити
нулик на будь-яку з восьми клітинок, які оточують хрестик першого гравця. Після
цього перший ставить хрестик на будь-яке з полів поряд з уже зайнятими і т. д.
Перший гравець виграє, якщо йому
вдасться поставити хрестик на будь-яку кутову клітинку. Довести, що при
будь-якій грі другого гравця перший завжди може перемогти.
7. На площині відмічено 1968 точок, які є вершинами
правильного 1968-кутника. Двоє гравців по черзі з’єднують дві вершини
многокутника відрізком, дотримуючись наступних правил: неможна з’єднувати дві
точки, хоча б одна з яких вже з’єднана з іншою і неможна перетинати вже
проведені відрізки. Програє той, хто не може зробити наступного ходу згідно з
цими правилами. Як потрібно грати, щоб перемогти? Хто виграє при правильній
грі?
8. В таблиці 4×4 клітинок грають двоє. Ходять по черзі,
кожен гравець своїм ходом зафарбовує одну клітинку. Клітинки зафарбовуються
один раз. Програє той гравець, після ходу якого якийсь квадрат 2×2 є повністю
зафарбованим. Хто виграє при правильній грі?
Немає коментарів:
Дописати коментар