07_premer_2003

Теорія ігор

Гра “хрестики-нулики” проводиться на квадратному полі, що містить 9 квадратних клітини. Двоє гравців по черзі заповнюють вільні клітини: перший – хрестиком, другий – нуликом. Переможцем вважається той, хто першим заповнить своїми символами горизонталь, вертикаль або діагональ з трьох квадратів. Якщо це не вдалося нікому, то гра закінчується внічию.
Гра “9 цифр”. На столі лежать 9 карток, на кожній з яких написано одну з цифр від 1 до 9 включно. Цифри на різних картках різні. Картки лежать написами догори. Двоє гравців по черзі беруть по одній картці зі столу. Переможцем вважається той, хто першим візьме 3 картки, сума цифр на яких дорівнює 15 (на руках у переможця можуть бути й інші картки).
Гра “9 слів”. На столі лежать 9 карток, кожна з яких містить одне зі слів: Лорен, какао, місто, хек, ліс, рама, Ала, меч, рік. Слова на різних картках різні. Картки лежать написами догори. Два гравці по черзі беруть по одній картці зі столу. Переможцем вважається той, хто першим візьме 3 картки зі словами, що мають одну спільну літеру (на руках у переможця можуть бути й інші картки).
Гра “9 шляхів”. 8 міст, позначених першими літерами латиниці, сполучає 9 доріг, що проходять відповідно через міста AEH, AF, ADG, BE, BDFH, BG, CDE, CF, CGH. Два гравці по черзі зафарбовують своїм кольором (червоним або синім) позначення шляхів на карті. Переможцем вважається той, хто перший зафарбує своїм кольором позначення всіх доріг, що проходять через одне місто.
Гра Баше^¹. У початковий момент є n предметів. Два гравці по черзі забирають з цієї купки предмети (від 1 до p включно). Переможцем вважається той, хто примусить суперника зробити останній хід.
Гра “на стежині”. На кінцях стежини, розбитої на m клітин, стоять шашки різного кольору. Двоє гравців по черзі рухають шашку певного кольору на вільну клітину на довільну кількість клітин в межах від 1 до p включно в довільному напрямку, але без перескакування шашки суперника й виходу за межі стежини. Переможцем вважається той, хто зробить останній хід.
Певну кількість фішок розташовано в ряд. Два гравці по черзі забирають будь-які 1 або 2 сусідні фішки. Переможцем вважається той, хто зробить останній хід.
Певну кількість фішок розташовано по колу. Два гравці по черзі забирають будь-які 1 або 2 сусідні фішки. Переможцем вважається той, хто зробить останній хід.
На початку гри є k груп предметів. Двоє гравців по черзі розбивають кожну групу, що містить більше одного предмета, на дві менші групи. Переможцем вважається той, хто виконає останнє розбиття.
Два гравці по черзі виймають зі скриньки предмети, кількість яких не перевищує половини наявних у скриньці. Програє той, хто візьме останній предмет.
Є дві купи предметів. Два гравці по черзі забирають одну купу, а іншу ділять на дві частини (обидві дії виконує один і той же гравець). Переможцем вважається той, хто останнім ходом залишить дві купки по одному камінцю.
Є n шашок, розташованих у ряд, n<15. Двоє гравців ходять по черзі. Першим ходом перевертається будь-яка шашка, а кожним наступним – будь-яка одна або дві сусідні ще не перевернуті шашки. Переможцем вважається той, примусить суперника зробити останній хід.
Гра “фан-тан” (нім). На початку гри є k груп предметів. Двоє гравців по черзі забирають з будь-якої групи довільну кількість предметів (можливо, й усі предмети групи). Переможцем вважається той, хто зробить останній хід.
Нім Фібоначчі. Два гравці по черзі виймають зі скриньки предмети. Першим ходом можна взяти довільну кількість, але не всі предмети. Починаючи з другого ходу, кожен гравець бере довільну кількість предметів у межах від 1 до подвоєної кількості предметів, взятих попереднім ходом. Переможцем вважається той, хто зробить останній хід.
Нім-ізоморфна гра. Прямокутна таблиця має розміри n на m клітин. На початку гри в кожному рядку таблиці розташовано по одній шашці. Два гравці по черзі рухають будь-яку шашку на довільну кількість клітин праворуч без виходу за межі таблиці. Переможцем вважається той, хто робить останній хід.
Нім-ізоморфна гра. На m-клітинній лінійці розташовано n різнокольорових шашок. Два гравці по черзі рухають довільну шашку на довільну кількість клітин праворуч без виходу за межі таблиці. Переможцем вважається той, хто робить останній хід.
Нім-ізоморфна гра. Дано певне натуральне число n. Два гравці по черзі замінюють це число на його частку від ділення на степінь простого числа за умови, що остача дорівнює 0. Переможцем вважається той, хто робить останній хід.
Нім-ізоморфна гра Норткотта. Поле для гри – прямокутна таблиця розміру n на m клітин. На початку гри кожна клітина першого і останнього стовпчиків містять відповідно по одній білій чи чорній шашці. Два гравці по черзі пересувають будь-яку шашку свого кольору на будь-яку кількість клітин, не виходячи за межі відповідного рядка і не перестрибуючи через шашку суперника. Переможцем вважається той, хто зробить останній хід.
Гра Дьюдені^². Двоє гравців по черзі називають натуральні числа в межах від 1 до m включно, причому кожне назване число відмінне від попереднього. Знаходиться сума S всіх названих чисел. Переможцем вважається той, хто отримає рівність S = p або примусить суперника отримати нерівність S>p.
Гра Болтянського^³. Двоє гравців по черзі називають натуральні числа в межах від даних натуральних чисел a до b включно. Знаходиться добуток усіх названих чисел. Переможцем вважається той, хто перший отримає добуток, більший за дане натуральне число c.
Гра дат. Перший гравець називає будь-який день січня. Далі гравці по черзі збільшують на одиницю або порядковий номер місяця в році, або номер дня у місяці. Переможцем вважається той, хто перший отримає дату 31 грудня.
Давньокитайська гра “цзяньшицзи”‘ (вибирання каменів). На початок гри є дві групи предметів. Двоє гравців по черзі забирають предмети з цих груп: або лише з однієї групи довільну кількість (можна всі предмети, але не менше одного), або з обох груп однакову кількість. Переможцем вважається той, хто зробить останній хід.
“Одинокий король”. На початку гри шаховий король стоїть на полі шахівниці a1 (нижній лівий кут). Двоє гравців по черзі рухають короля на одне поле праворуч, вгору або по діагоналі праворуч і вгору одночасно. Переможцем вважається той, хто перший пересуне короля на поле h8 (правий верхній кут).
Г ра “перемагає парність”. На початку гри є група предметів, що містить їх непарну кількість n = 2k + 1. Двоє гравців по черзі забирають з цієї групи предмети – від одного до p включно, накопичуючи їх у себе. Переможцем вважається той, хто наприкінці гри матиме парну кількість предметів.
Н а початку гри на полі 5 розташовано білу шашку, а на полі 15 – чорну. Два гравці по черзі пересувають шашки: перший – тільки білу (він починає гру), другий – тільки чорну на сусіднє поле вздовж лінії. Перший гравець виграє тоді, коли не більше, ніж за 6 ходів поставить білу шашку на чорну. Інакше перемагає другий гравець, який ходить чорною шашкою.
Гра “Тригекс”. Поле для гри містить 9 кругів з центрами на 9-ти прямих. Двоє гравців по черзі ставлять на круги по одній фішці свого кольору (білого або чорного). Переможцем вважається той, хто перший займе три круга на одній з проведених прямих.
Г ра Піта Хейна “такс-тікс”. Квадратну дошку розділено на однакові клітини квадратної форми. На початку гри кожна клітина містить по одній шашці. Грають двоє, ходять по черзі. За один хід забирається довільна кількість шашок з будь-якого вертикального стовпчика або горизонтального рядка. Брати шашки дозволяється лише підряд, не перескакуючи через порожні клітини. Переможцем вважається той, хто бере останню шашку.
Гра Піта Хейна “гекс”. Дошку у вигляді ромбу розбито на правильні шестикутники. Дві протилежні сторони ромба називають чорними, дві інші – білими. Двоє гравців по черзі виставляють на вільні шестикутники по одній фішці: один гравець – білі, інший – чорні фішки. Переможцем вважається той, хто перший побудує ланцюг зі “своїх” фішок між “своїми” сторонами.
Гра Ґранді^⁴. На початку гри є одна група предметів. Два гравці по черзі розділяють одну з наявних груп на дві нерівні частини. Гра триває доти, доки всі групи не міститимуть 1–2 предмети. Переможцем вважається той, хто виконає останнє розбиття.
Гра “двоколірні шашки”. Ігрове поле – прямокутна дошка розміру n на m квадратних клітин. На початку гри на кожній клітині встановлено по одній двоколірній шашці (одна сторона біла, інша чорна) довільним чином. Два гравці сидять з одного боку дошки і по черзі перевертають шашки у довільному прямокутному блоці клітин, правий нижній кут якого містить шашку з чорним верхом. Переможцем вважається той, хто отримає розташування всіх шашок білою стороною догори.
Гра Джона Конуея і Майкла Стюарта Патерсона “розсада”. На аркуші паперу виділено n точок (“ямок для розсади”). Двоє гравців по черзі проводять лінії, що починаються в одній з точок (“розсада пускає росток”). Ці лінії або з’єднують дві різні виділені точки, або описують петлю й повертаються у початкову виділену точку. Кожна така лінія не має точок самоперетину, не перетинає інші проведені лінії і не проходить через виділену точку, що не є її початком або кінцем. При цьому з кожної точки має виходити не більше, ніж 3 лінії. Після проведення лінії гравець ставить на ній нову точку. Переможцем вважається той, хто проведе останню лінію.
Г ра “L”. Ігрове поле – квадратна дошка, поділена на 16 квадратних клітин. Двоє гравців мають по одній L-подібній фігурі різного (білого або чорного) кольору, що займає 4 квадрати, і дві спільні фішки. Початкову позицію гри подано рисунком. Виконати хід – це обов’язково змінити розташування своєї фігури, не покриваючи клітинки поля, зайняті фігурою суперника або фішками, при необхідності перевертаючи фігуру. Після цього можна, але не обов’язково, перемістити одну фішку на вільну клітину. Гравці ходять по черзі. Гру починають білі. Переможцем вважається той, хто зробить останній хід.
На площині дано n точок. Два гравці по черзі сполучають їх відрізками прямих таким чином, щоб внутрішні точки одного не належали іншому відрізку. Переможцем вважається той, хто проводить останній відрізок.
На площині дано вершини правильного шестикутника. Два гравці по черзі зафарбовують сторони і діагоналі шестикутника синім і червоним кольором. Переможцем вважається той, хто примусить суперника побудувати трикутник з відрізків свого кольору.
Головоломка “Ханойські башти”. На одному стержні A нанизано диски таким чином, що діаметри основ дисків зменшуються знизу догори. Потрібно перекласти ці диски на інший стержень B, використовуючи допоміжний стержень C. При цьому заборонено розташовувати диск більшого діаметра над диском меншого діаметра.
На прямій рухаються точки A і B з максимальними швидкостями v_A і v_B відповідно, v_A > v_B. Указати одну з можливих стратегій (поведінок) точки А, за яких точка A зіткнеться з точкою В незалежно від того, у яку сторону і на якій відстані точка B буде розташована відносно A у початковий момент, якщо відомо: а) v_A і v_B ; б) v_A .Обчислити час до зіткнення для обраної стратегії за певних значень v_A і v_B та початкового розташування точок A і B. Яка найслабкіша умова існування такої стратегії для несталих максимальних швидкостей?

Содержание