KNOWLEDGE HYPERMARKET


ДОСЯГНИ МЕТИ ПЕРШИМ

ДОСЯГНИ МЕТИ ПЕРШИМ


Математики різних часів і народів намагалися створити алгоритми для перемоги в різноманітних іграх. Одні робили це з чисто наукового інтересу, інші — з надією розбагатіти завдяки перемозі в азартних іграх, особливо іграх в карти. Математики сподівалися розбагатіти, використовуючи у своїй грі надійні алгоритми.


Виявляється, що не для будь-якої гри можна скласти алгоритм, який завжди забезпечить перемогу. Це стосується тих ігор, хід яких залежить від випадкових подій (наприклад, ігор у карти), а також ігор, в яких кількість можливих варіантів надзвичайно велика (наприклад, шахи).


Проте є багато ігор, повністю досліджених. Для них існують алгоритми-стратегії, користуючись якими можна завжди перемогти, незалежно від дій суперника. Можна також, не розпочинаючи гру, визначити, що при заданих початкових умовах і правильних діях суперника перемогти неможливо.


Розглянемо один з прикладів такої гри.


Є горизонтальний ряд з 15 клітинок. У крайній лівій клітинці стоїть фішка. У грі беруть участь двоє гравців, які роблять хід по черзі. За один хід можна пересунути фішку вправо па одну, дві або три клітинки. Виграє той, хто поставить фішку в крайню праву клітинку.


Для зручності, пронумеруємо клітинки зліва направо числами від 1 до 15.


Щоб перемогти, необхідно своїм ходом поставити фішку в 15-у клітинку. Оскільки пересувати фішку можна на одну, дві або три клітинки, хід у 15-у клітинку може бути зроблений або з 14-ї, або з 13-ї, або з 12-ї клітинки. Отже, необхідно примусити суперника поставити фішку в одну з цих трьох клітинок. А для цього ми повинні свій попередній хід зробити в 11-у клітинку.


Дійсно, якщо фішка знаходиться в 11-й клітинці, то, за правилами гри, суперник може зробити з неї хід тільки в 12-у, 13-у або 14-у клітинку. Отже, якщо передостаннім ходом ми поставимо фішку в 11-у клітинку, то при будь-якому ході-відповіді суперника ми зможемо поставити фішку в 15-у клітинку і перемогти.


Міркуємо аналогічним чином далі.


Для того, щоб за будь-яких обставин ми мали змогу поставити фішку в 11-у клітинку, вона повинна перед нашим ходом знаходитись або в 10-й, або в 9-й, або у 8-й клітинці. Тобто, ми повинні змусити суперника поставити фішку в одну з цих трьох клітинок. А для цього своїм иопсреднімходом нам необхідно поставити фішку в 7-у клітинку. Тоді, якщо суперник пересуне фішку па одну клітинку, ми пересунемо її на 3; якщо він пересуне фішку на 2 клітинки, ми пересунемо її теж на 2; якщо ж він пересуне фішку на 3 клітинки, ми пересунемо її на 1. При такому алгоритмі гри фішка обов'язково опиниться в 11-й клітинці.


Проводячи аналогічні міркування, бачимо, що для того, аби ми змогли зробити хід у 7-у клітинку, свій попередній хід ми повинні -, зробити в 3-ю клітинку. А цю клітинку ми можемо зайняти фішкою вже першим ходом, якщо він наш. Для цього треба пересунути першим ходом фішку на 2 клітинки.


З наведених вище міркувань випливає, що існують клітинки, пос-лідонно займаючи які, ми нпевгіепо наближатимемося до перемоги, незалежно від ходів нашого суперника. Такими є 3-я, 7-а, 11-а і 15-а клітинки. Назвемо умовно їх виграшними.


Відстані між послідовними виграшними клітинками однакові і дорівнюють 4. Тому наш хід-відповІдь на хід суперника повинен бутті таким, щоб сума відстаней двох ходів (ходу суперника та нашого ходу-відповіді) становила 4 клітинки.

Отже, гравець, який починає гру, завжди переможе, якщо використає такий алгоритм:
1. Пересунути першим ходом фішку на 2 клітинки.
2. Поки не досягнемо останньої клітинки, якщо суперник пересунув фішку па х клітинок, пересунути її на (4 — х) клітинок.

Проводячи аналогічні міркування, визначте виграшні клітинки і алгоритм гри, якщо довжина поля 16 клітинок.


Дещо інша ситуація виникне, якщо довжина поля 17 клітинок. Міркуючи аналогічно, з'ясовуємо, що виграшними є клітинки 17-а, 13-а, 9-а, 5-а і 1-а. Але гравець, який ходить першим, не може зробити хід ні в 1-у, ні в 5-у клітинку. Це означає, що в цій грі для нього виграшної стратегії не існує. Він може виграти тільки тоді, коли ного суперник деяким своїм ходом не займе одну з виграшних клітинок.


Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 18,19, 20, 30 клітинок.


Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 15, 16,17,18,19, 20, 30 клітинок і гравець за один хід може пересунути фішку на одну, дві, три або чотири клітинки.


Ломаковська Г.В., Колесніков С.Я., Ривкінд Й.Я. Інформатика 5 клас

Вислано читачаму з інтернет-сайту



1236084776 kr.jpg акселеративні методи на уроці                        1236084776 kr.jpg національні особливості
1236084776 kr.jpg виділити головне в уроці - опорний каркас            1236084776 kr.jpg нічого собі уроки
1236084776 kr.jpg відеокліпи                                           1236084776 kr.jpg нова система освіти
1236084776 kr.jpg вправи на пошук інформації                           1236084776 kr.jpg підручники основні допоміжні
1236084776 kr.jpg гумор, притчі, приколи, приказки, цитати             1236084776 kr.jpg презентація уроку
1236084776 kr.jpg додаткові доповнення                                 1236084776 kr.jpg реферати
1236084776 kr.jpg домашнє завдання                                     1236084776 kr.jpg речовки та вікторизми
1236084776 kr.jpg задачі та вправи (рішення та відповіді)              1236084776 kr.jpg риторичні питання від учнів
1236084776 kr.jpg закриті вправи (тільки для використання вчителями)   1236084776 kr.jpg рівень складності звичайний І
1236084776 kr.jpg знайди інформацію сам                                1236084776 kr.jpg рівень складності високий ІІ 

1236084776 kr.jpg ідеальні уроки                                     1236084776 kr.jpg рівень складності олімпійський III
1236084776 kr.jpg ілюстрації, графіки, таблиці                         1236084776 kr.jpg самоперевірка
1236084776 kr.jpg інтерактивні технології                              1236084776 kr.jpg система оцінювання
1236084776 kr.jpg календарний план на рік                              1236084776 kr.jpg скласти пазл з різних частин інформації
1236084776 kr.jpg кейси та практикуми                                  1236084776 kr.jpg словник термінів 
1236084776 kr.jpg комікси                                              1236084776 kr.jpg статті
1236084776 kr.jpg коментарі та обговорення                           1236084776 kr.jpg тематичні свята
1236084776 kr.jpg конспект уроку                                       1236084776 kr.jpg тести
1236084776 kr.jpg методичні рекомендації                               1236084776 kr.jpg шпаргалка 
1236084776 kr.jpg навчальні програми                                   1236084776 kr.jpg що ще не відомо, не відкрито вченими