МІСЬКИЙ КЛАСИЧНИЙ ЛІЦЕЙ
РЕФЕРАТ
Математичні ігри та головоломки
Підготував:
Петров А. А.,
10Б клас (фіз-мат)
р. Кемерово - 1999
Математичні ігри та головоломки дуже популярні, як, втім, і всі ігри. І далеко не завжди більш складна гра - більше цікава. Часто мільйони людей з незгасного інтересу грають у найпростіші ігри, і саме ці ігри найбільше цінують, саме вони входять в історію математики й прославляють своїх творців.
Найбільш наближеними до математики є головоломки, але багато головоломок утворилося з колись існуючих (а деякі з ще існуючих) ігор. Більшість таких основоположних ігор було придумано давньогрецькими математиками.
Останнім часом математичним іграм увага приділяється, в основному, для знаходження виграшних стратегій, на що сильно вплинуло поширення програмування: скласти алгоритм, за яким в гру зміг би грати комп'ютер, часто буває складніше й цікавіше, ніж самому навчитися грати в неї , при цьому глибше вникаєш в суть гри, після чого виграти в неї можеш уже практично кожного.
Ігри
Найпростіші математичні ігри часто використовують як задачі, в яких потрібно знайти виграшну стратегію, або одне положення перевести в інше. Іноді задачі бувають досить простими, коли вони вирішуються відомими методами, такими як інваріант і розфарбування, але є й досить прості, але досі недозволені задачі, пов'язані з математичними іграми.
Прикладом може бути популярна гра хрестики-нулики на нескінченному полі (рендзю). Вона, як відомо, при правильній стратегії обох гравців нескінченна, але виграшну стратегію при цьому ніхто не знає. В даний час придумано безліч алгоритмів цієї гри, заснованих, насамперед, на переборі різних варіантів і аналізі гри на наступні кілька ходів, які дуже близькі до виграшної стратегії, але лише при їх реалізації на комп'ютері - людина ж їм слідувати практично не може. Існують найпростіші прийоми цієї гри, якими користуються гравці, але вирішальної найчастіше буває уважність.
Гра ним і інші аналогічні ігри
Існує кілька ігор, в яких двоє граючих A і B, керуючись певними правилами, по черзі виймають те або інше число фішок з однієї або декількох купок - перемагає той, хто бере останню фішку. Найпростіша така гра - це гра з однієї купкою фішок, і зробити хід у ній - значить взяти з купки будь-яке число фішок від 1 до m включно. Багато подібні ігри піддаються дослідженню за допомогою числа Шпраг-Гранді G (C). Порожній позиції O, яка не містить фішок, відповідає G (O) = 0. Комбінацію купок, що складаються відповідно з x, y, ... фішок, позначимо C = (x, y, ...) і припустимо, що припустимі ходи переводять C в інші комбінації: D, E, ... Тоді G (C) є найменше невід'ємне число, відмінне від G (D), G (E), ... Це дозволяє по індукції визначити G (C) для будь-якої комбінації C, дозволеної правилами гри. Так, у згаданій задачі G (x) = x mod (m +1).
Якщо G (C)> 0, то гравець, що робить наступний хід, допустимо, це гравець A, може забезпечити собі виграш, якщо йому вдасться перейти до "безпечної" комбінації S з G (S) = 0. Дійсно, за визначенням G (S) у цьому випадку або S - порожня позиція, і тоді A уже виграв, або B наступним ходом повинен перейти до "небезпечної" позиції U з G (U)> 0 - і тоді все повторюється знову. Така гра після кінцевого числа ходів закінчується перемогою A.
До подібних ігор відноситься ним. Є довільне число купок фішок, і гравці по черзі вибирають одну якусь купку й виймають з неї будь-яке число фішок (але хоча б одну обов'язково).
Більш загальний випадок представляє гра Мура, яку також можна назвати k-ним. Правила її ті ж, що і в звичайному ниме (1-ним), але тут дозволяється бать фішки з будь-якої кількості купок, не переважаючого k.
Ще одна подібна гра - Кеглі. У ній фішки розкладені в ряд, і при кожному ході забирається одна будь фішка або дві сусідні. При цьому ряд може розбитися на два менших ряду. Виграє той, хто візьме останню фішку. Узагальнена варіація цієї гри відома під ім'ям гри Вітхоффа.
Є цікава варіація гри ним під назвою "зоряний їм". Вона досить проста, але стратегія в ній видна не відразу. Грають у цю гру на зіркоподібній фігурі, зображеної на рис. 1, зліва. Поставте по одній фішці на кожну з дев'яти вершин зірки. Гравці A і B роблять ходи по черзі, знімаючи при кожному ході або одну, або дві фішки, з'єднані відрізком прямої. Той, хто знімає останню фішку виграє.
У гравця B при грі в зоряний їм є виграшна стратегія, що використовує симетрію ігрової дошки (взагалі, виграшні стратегії багатьох математичних ігор будуються на цьому). Уявімо, що відрізки прямих, що з'єднують вершини зірки, - це нитки. Тоді всю конфігурацію можна розгорнути в окружність, топологічно еквівалентну нитяною зірці. Якщо A знімає з окружності одну фішку, то B знімає дві фішки із протилежної ділянки окружності. Якщо A бере дві фішки, то B знімає із протилежної ділянки окружності одну фішку. В обох випадках на окружності залишаються дві групи із трьох фішок. Яку б фішку (або які б фішки) не взяв A з однієї групи, B бере відповідну фішку (або фішки) з іншої групи. Ясно, що остання фішка дістанеться гравцеві B.
Інші математичні ігри
В кінці 60-х років Дж. Леутуейт із шотландського міста Терса винайшов чудову гру з мистецьки схованою стратегією "парних ходів", що забезпечує другому гравцеві явний виграш. На дошці розміром 5 * 5 квадратних кліток у шаховому порядку розставлені 13 чорних і 12 білих фішок, після чого будь-яка з чорних фішок, наприклад, стоїть на центральному полі, знімається (рис. 2, зліва).
Гравець A ходить білими фішками, гравець B - чорними. Ходи робляться по вертикалі і горизонталі. Програли вважається той із гравців, хто першим не зможе зробити черговий хід. Якщо дошку розфарбувати подібно шахівниці, то стане ясно, що кожна фішка зі свого поля переходить на поле іншого кольору і що ні одну фішку не можна змусити ходити двічі. Отже, гра для кожного гравця не може тривати більше 12 ходів. Але вона може закінчитися і раніше виграшем для будь-якого гравця, якщо тільки B не буде дотримуватися раціональної стратегії.
Раціональна стратегія для гравця В полягає в тому, щоб подумки уявити собі всю матрицю (за винятком порожньої клітки), покриту дванадцятьма неперекривающіеся кістками доміно. Як саме вони розкладені на дошці, не має значення. На рис. 2, праворуч показаний один із способів покриття дошки костями доміно. Який би хід ні зробив гравець А, В просто робить хід на ту кістку доміно, яку тільки що покинув А. При такій стратегії у В завжди є хід після чергового ходу А, тому В свідомо виграє за 12 або за менше число ходів.
У гру Леутуейта можна грати не тільки фішками на дошці, але й квадратними плитками або кубиками, що пересуваються всередині плоскої коробочки, на дні якої накреслена матриця. Припустимо тепер, що в правила гри внесена поправка, яка дозволяє будь-якому гравцеві в будь-який час ходити будь-яким числом (від 1 до 4) фішок, що стоять на одній горизонталі або вертикалі, якщо перша й остання фішки в обраній їм горизонталі або вертикалі "його" кольору. Перед нами чудовий приклад того, як тривіальне (на перший погляд)...
