Мета публікації донести до відвідувачів сайту результати Шпраґе і Ґранді, опубліковані у таких роботах:

1. Sprague R. P. (1935–36). "Uber mathematische Kampfspiele". Tohoku Mathematical Journal, 41, p. 438–444.

2. Grundy P. M. (1939). "Mathematics and games". Eureka 2: 6–8. Reprinted, 1964, 27, p. 9–11.

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

Теорема 1. Роглянемо скінчену антагоністичну гру з повною інформацією і без випад­кового втручання такого вигляду:

• є орієнтований граф без циклів і вершина у ньому;

• два гравці по черзі здійснюють перехід до наступної вершини-позиції гри дугою (орієнтованим ребром) графа, починаючи з вказаної вершини;

• програє той, хто не може зробити наступний перехід.

У такій грі:

• усі вершини-позиції можна поділити на виграшні й програшні;

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

Доведення (методом математичної індукції за максимальною кількістю ходів партії).

1. База індукції. Якщо з даної вершини не виходить жодна дуга, то дану позицію вважаємо програшною для гравця, чия черга ходити. У цьому випадку виграшна стратегія його суперника може мати довільний вигляд, наприклад задаватися порожньою множиною.

2. Припущення індукції. Нехай висловлювання теореми справджується для всіх вершин, починаючи з яких максимальна кількість ходів партії не перевищує певне ціле n.

3. Крок індукції. Розглянемо множину усіх початкових позицій-вершин графа, для яких максимальна тривалість партії дорівнює n + 1. Тоді кінці дуг, спрямованих з цих вершин, є вершинами-позиціями, починаючи з яких партія триває не більше, ніж n ходів. Для цих кінців дуг справджується висловлювання теореми. Довільну позицію-вершину графа, для якої максимальна тривалість партії дорівнює n + 1 вважаємо:

   • програшною, якщо усі ходи з неї ведуть у виграшні позиції;

   • виграшною, якщо існує хід з неї у програшну позицію.

Виграшна стратегія полягає у здійсненні ходу з виграшної (для себе) позиції у програшну (для суперника).

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

Означення 1. Сумою ігор І та І' з графами гри відповідно G і G' називають гру, у графі якої:

• множина вершин є декартовим добутком множини вершин G і множини вершин G';

• ребро сполучає вершини (a; a') і (b; b') тоді й лише тоді, коли справджується одне з таких двох висловлювань:

  • справджується рівність a = b і граф G' містить дугу (a'; b');

  • справджується рівність a' = b' і граф G містить дугу (a; b).

Інакше кажучи, суму ігор грають на відповідних графах ігор-доданків. При цьому ходом суми ігор є хід однієї з ігор-доданків. Таку гру позначають І + І'.

Зауваження 1. Для довільної гри І гра І + І з початковою позицією на діагоналі декартового добутку вершин відповідних графів (тобто такою, що має вигляд (a; a)) є програшною для гравця, що починає гру. Виграшна симетрична стратегія суперника полягає у повертанні на діагональ добутку вершин графа.

Зауваження 2. Для довільних ігор І та J ігри J та І + І + J з початковими позиціями вигляду j та (i; i; j) є виграшною для одного й того ж самого гравця. Виграшна стратегія цього гравця полягає у дотриманні виграшної стратегії у грі J та симетричних ходах-відповідях, якщо суперник переходить до однієї з ігор І.

Зауваження 3. Для довільних ігор І та J у грі І + J :

• програшною є позиція, яка є парою програшних позицій ігор І та J ;

• виграшною є позиція, яка є парою програшної та виграшної (у довільному порядку) позицій ігор І та J .

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

Означення 2. Ігри з графами гри G i G' та відповідно початковими позиціями s i s' взаємно моделюють одна одну, якщо існує відношення R — підмножина декартового добутку множини вершин G i множини вершин G' — з такими властивостями:

• (s ; s') належить до R;

• при довільній парі вершин (v; v') з R:

  • якщо у графі G існує дуга з початком v і кінцем w, то у графі G' існує вершина w', при якій пара вершин (w; w') належить до R і у графі G' існує дуга з початком v' і кінцем w';

  • якщо у графі G' існує дуга з початком v' і кінцем w', то у графі G існує вершина w, при якій пара вершин (w; w') належить до R і у графі G існує дуга з початком v і кінцем w.

Рис. 1. Приклад графів двох ігор, що моделюють одна одну.

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

Означення 3. Кожній грі S поставимо у відповідність модель гри — множину m(S), яку побудуємо індуктивно за максимальною кількістю ходів партії:

• якщо неможливо зробити жодного ходу, то m(S) = {} (порожня множина);

• якщо хід з початкової позиції гри S призводить до однієї з позицій S₁, S₂, …, S_n, то

Побудована таким чином множина m(S) є спадково скінченою, тобто вона скінчена, її елементи скінчені, елементи її елементів скінчені і т.і. Таким чином, не порушено аксіоми теорії множин і висловлювань, які забороняють нескінчені послідовності такого вигляду: множина, елемент множини, елемент елемента … Таку спадково скінчену множину можна розглядати як початкову позицію певної гри I_m(S), у якій ходом є перехід від множини до її елемента.

Лема 1. Довільна гра S взаємно моделюється грою I_m(S).
Доведення. Для довільної позиції s гри S позначимо через S_s гру, що відрізняється від S лише початковою позицією s. Цій позиції s поставимо у відповідність m(S_s), якщо s досяжна з початкової позиції гри S, або ніщо, якщо вона недосяжна. Для досяжної позиції s множина m(S_s) є елементом елемента ... елемента m(S), бо переходу дугою графа гри S відповідає перехід від множини до її елемента. Таким чином, множина m(S_s) для досяжної позиції s насправді є позицією гри m(S). З означення 3 випливає таке: якщо з позиції s можна зробити хід у позицію t, то m(S_t) належить як елемент до множини m(S_s). І навпаки: довільний елемент множини m(S_s) є m(T) для деякої гри T, яку отримують з після одного ходу S_s, тобто дорівнює m(S_t) при позиції t, у яку можна потрапити за один хід з позиції s.

Лема 2. Дві гри S і S' взаємно моделюють одна одну тоді й лише тоді, коли m(S) = m(S').

Доведення. Відношення взаємного моделювання ігор є відношенням еквівалентності (зауваження 3), тому з леми 1 випливає достатність. Доведемо необхідність методом математичної індукції за максимальною кількістю ходів, що залишилися, починаючи з позицій s і s', що відповідають одна одній при взаємному моделюванні ігор S і S'.

1. База індукції. Якщо з позиції s неможливо зробити хід, то s' також є кінцевою позицією, і навпаки. У цьому випадку m(S_s) = m(S'_s') як порожні множини.

2. Припущення індукції. Нехай висловлювання теореми справджується для всіх вершин, починаючи з яких максимальна кількість ходів партій не перевищує певне ціле n.

3. Крок індукції. Розглянемо ігри S_s і S'_s', що взаємно моделюють одна одну і в яких максимальна кількість ходів партій не перевищує n + 1. Елементами множин m(S_s) і m(S'_s') є значення m(…) для всіх ігор, що виникають відповідно в іграх S_s і S'_s' після одного ходу. З умови взаємного моделювання й припущення індукції випливає рівність відповідних елементів множин m(S_s) і m(S'_s'), а значить — і самих множин.

Означення 4. Дві гри S і S' називають еквівалентними за Шпраге — Ґранді, якщо для довільної гри T в іграх T + S та T + S' виграє один і той самий гравець.

Зауваження 5. З ізоморфності графів ігор чи навіть зі взаємного моделювання ігор випливає їхня еквівалентність за Шпраге — Ґранді.

Означення 5. Розглянемо довільну скінчену антагоністичну гру з повною інформацією і без випадкового втручання на орієнтованому графі з програшними кінцевими позиціями (тобто таку, яку описано в умові теореми 1). Для кожної позиції s (вершини графа) означимо невід'ємне ціле число i(s), яке назвемо оцінкою (числом Шпраге — Ґранді) цієї позиції:

• якщо з позиції s неможливо зробити хід, то i(s) = 0;

• якщо з позиції s можна зробити хід в одну з таких позицій s₁, s₂, …, s_k (перера­ховано всі такі позиції), то i(s) — найменше невід'ємне ціле число, відмінне від i(s₁), i(s₂), …, i(s_k).

Рис. 2. Граф гри, у якому цифрами вказано оцінки (числа Шпраге — Ґранді) позицій.

Лема 5 [про нульове значення оцінки позиції]. Позиція s програшна тоді й лише тоді, коли її оцінка дорівнює нулю.

Доведення (методом математичної індукції за максимальною кількістю ходів, що залишилися, починаючи з позицій s).

1. База індукції. Якщо з позиції s неможливо зробити хід, то згідно з означенням 5 i(s) = 0.

2. Припущення індукції. Нехай висловлювання теореми справджується для всіх вершин, починаючи з яких максимальна кількість ходів партій не перевищує певне ціле n.

3. Крок індукції. Нехай максимальна кількість ходів партій з початковою позицією s не перевищує ціле n + 1. Тоді:

   • справдження рівності i(s) = 0 означає, що з позиції s усі можливі ходи ведуть у позиції з додатними оцінками, які згідно з припущенням індукції є виграшними;

   • справдження нерівності i(s) > 0 означає, що з позиції s щонайменше один хід веде у позицію з оцінкою нуль, яка згідно з припущенням індукції є програшною.

Позначимо через +₂ операцію порозрядного додавання за модулем 2 у двійковій системі числення (див. операцію xor у мові Pascal).

Зауваження 6. Операція +₂ задовольняє сполучний та переставний закони. Для довільного невід'ємного цілого j справджується рівність j +₂ j = 0, тому операція +₂ j є оберненою сама до себе.

Лема 6 [про порозрядне додавання]. Число ( j +₂ k ) — це найменше невід'ємне ціле число, відмінне від чисел вигляду ( j' +₂ k ) та ( j +₂ k' ) при j' < j , k' < k.

Доведення. Операція +₂ k обернена само до себе: подвійне її застосування залишає довільне число без змін. Якщо j' менше від j, то різними є суми ( j' +₂ k ) та ( j +₂ k ). Тому число ( j  +₂ k ) не зустрічається серед чисел вигляду ( j' +₂ k ) при j' < j. Аналогічно, ( j +₂ k ) не зустрічається серед чисел вигляду ( j +₂ k' ) при k' < k.

Покажемо, що всі невід'ємні числа l, менші за ( j +₂ k ), зустрічаються серед пар вказаного вигляду. Згідно з вибором l < ( j +₂ k ) існує розряд двійкового запису цілих чисел (надалі — виділений розряд), у якому:

• цифра числа l дорівнює 0;
• цифра числа ( j +₂ k ) дорівнює 1,

а в усіх старших розрядах цифри чисел l і ( j +₂ k ) збігаються. У цьому самому розряді цифри чисел j і k різні, бо їхня побітна сума дорівнює 1 . Не обмежуючи загальності міркувань, обмежимося випадком, коли у цьому розряді саме число j має цифру 1. Розглянемо число j', двійковий запис якого такий:

• у виділеному розряді має цифру 0;

• у довільному старшому розряді цифра збігається з відповідною цифрою числа j;

• у довільному молодшому розряді, якщо такий існує, цифру підбирають таким чином, щоб її сума з відповідною цифрою сума k збігалася (mod 2) з цифрою l у цьому самому розряді.

Маємо: l = ( j' +₂ k ) при j' < j.

Якщо у виділеному розряді двійкового запису число k має цифру 1, то l = ( j +₂ k' ) при k' < k, а пошук двійкового запису k' здійснюють з точністю до перепозначення так само, як і для числа j'.

Лема 7 [про оцінку суми ігор]. Оцінка позиції суми ігор дорівнює сумі оцінок відповідних позицій цих ігор при порозрядному додаванні за модулем 2 у двійковій системі числення.

Доведення. Операції +₂ і додавання ігор задовольняють сполучний закон, тому у доведенні обмежимося розглядом суми двох ігор. Нехай x — найменше серед невід'ємних цілих чисел, відмінних від x₁, x₂, …, x_j, y — найменше серед невід'ємних цілих чисел, відмінних від y₁, y₂, …, y_k. Доведемо, що (x +₂ y) — найменше серед невід'ємних цілих чисел, відмінних від (x₁ +₂ y), (x₂ +₂ y), …, (x_j +₂ y) та (x +₂ y₁), (x +₂ y₂), …, (x +₂ y_j). По-перше, число (x +₂ y) відмінне від перелічених вище (j + k) чисел, бо подвійне порозрядне додавання є тотожнім перетворенням. По-друге, серед чисел x₁, x₂, …, x_j зустрічаються усі ті, які менші за x (також, можливо, деякі більші за x), а серед чисел y₁, y₂, …, y_k зустрічаються усі ті, які менші за y (також, можливо, деякі більші за y). Тому згідно з попередньою лемою 6, серед перелічених вище (j + k) чисел є всі числа, які менші за (x +₂ y). Для завершення доведення достатньо всі числа, які розглядалися, тлумачити як оцінки відповідних позицій ігор.

Теорема 2 [Шпраґе — Ґранді]. Дві гри еквівалентні за Шпраґе — Ґранді тоді й лише тоді, коли оцінки початкових позицій у них збігаються.

Доведення. Якщо оцінки ігор початкових позицій ігор S і S' збігаються, то для довільної гри T збігаються оцінки початкових позицій ігор S + T і S' + T. Отже, ці оцінки позицій одночасно додатні або дорівнюють нулю, а відповідні позиції відповідно виграшні або програшні (див. лему 5 про нульове значення оцінки позиції). Якщо оцінки ігор початкових позицій ігор S і S' різні, то розглянемо ігри S + S та S' + S. Початкова позиція гри S + S — програшна, а початкова позиція гри S + S' — виграшна, бо її оцінка додатна. У цьому випадку ігри S і S' не еквівалентні за Шпраґе — Ґранді.

Після ознайомлення з викладеною теорією доволі прозорим видається аналіз відомої гри «фан-тан» чи нім, яка має такі правила. На початку гри є k куп предметів. Перша купа містить m₁ предметів, друга — m₂ предметів, …, k-та купа — m_k предметів. Двоє гравців по черзі забирають з будь-якої купи довільну додатну кількість предметів (можливо, й усі предмети купи). Переможцем вважають того, хто зробить останній хід. У грі з однією купою предметів оцінка позиції дорівнює кількості предметів у купі. Тому переможець повинен створювати ті позиції, у яких для кожного розряду двійкової системи числення сума цифр кількостей предметів у всіх купах парна.