гра гранди

Гра Гранді - це математична гра на стратегію для двох гравців. Спочатку існує одна купа предметів. Два гравці по черзі поділяють одну купу на дві купи різних розмірів. Гра закінчується, коли залишаються тільки купи з двох і менше предметів і жодна з них не може бути розділена на купки різних розмірів. У гру зазвичай грають як і в піддавки. Це означає, що останній гравець, який зможе зробити дозволений хід, виграє.

Гра в піддавки, яка починається з однієї купки з 8 предметів, виграшна для першого гравця, якщо він розділить вихідну купу на дві з 7 і 1 предметів:

Гравець 2 зараз може зробити один з трьох ходів: розбити 7 на 6 + 1, 5 + 2 або 4 + 3. В кожному з цих випадків гравець 1 може забезпечити повернення противнику куп з 4 предметів і купи розміром 2 і менше:

Зараз гравець 2 повинен розділити купу з чотирьох предметів на 3 + 1, гравець 1, в подальшому, розділить 3 на 2 + 1:

Гра може бути проаналізована за допомогою теорії Шпраг-Гранді. Для цього потрібно розмірами куп в грі Гранді поставити у відповідність еквівалентні розміри куп в грі Ним. Це відповідність описується послідовністю:

Використовуючи це відповідність, стратегія для гри Ним може бути також використана і для гри Гранді. Питання, чи стає послідовність Ним-значень для гри Гранді періодичної, це невирішена проблема. Елвін Берлекемпа, Джон Конвей і Річард Гай припустили [1]. що вона періодична, незважаючи на те, що перші 2 35 значень, знайдені Achim Flammenkamp, ​​цього не підтверджують.

Схожі статті