Гра - тип олімпіадних завдань по математиці, в яких вимагається проаналізувати стратегію гри і / або назвати переможця цієї гри. Зазвичай закінчується традиційним питанням: "хто виграє при правильній грі?"


1. Характеристики ігор

Як правило, в завданнях цього типу гри:

  • детерміновані
  • фінітних
  • з повною інформацією
  • включають рівно двох учасників
  • з неможливою (за правилами) нічиєї

Відхилення від зазначених характеристик поодинокі. Частина завдань полягає саме в доказі цих характеристик.

2. Ставлення до теорії ігор

Зазначені завдання, як правило, не припускають знання теорії ігор. Тим не менше, окремі положення теорії ігор - інтуїтивно очевидні - можуть використовуватися (див. нижче).

3. Використовувані ідеї

У завдання-іграх використовуються самі різні методи вирішення, проте є декілька часто повторюваних ідей:

  1. інваріант - один з гравців кожним своїм ходом приводить стан гри в деякий стан (наприклад, сума залишилися незайнятими полів) і такий стан є виграшним. А гра є фінітних
  2. виграшність доводиться "з кінця", з використанням ідей динамічного програмування : спочатку доводиться, що перебуваючи в одному з "передостанніх положень" можна потрапити в "останнє" (виграшне), потім - що з деякого безлічі "предпредпоследнего" можна потрапити тільки в "передостаннє" і так далі, поки не доведемо, що "предпред ... передостаннє" положення є початковим. (Див. функція Гранді).
  3. необов'язково розробляти стратегію, щоб довести її існування (при цьому достатньо довести т. н. "чисте існування" стратегії, не конструюючи її явно).
  4. якщо в фінітних детермінованою грі з двома учасниками довести неможливість виграшної стратегії одного з учасників, значиться другим виграє.
  5. т. н. передача ходу: якщо в деякій ситуації гравець А може передати хід противнику, то у А позиція не гірше, ніж у його супротивника.

4. "Правильна гра"

"Правильною грою" в завданнях цього класу називається виграшна стратегія з теорії ігор - стратегія, дотримуючись якої гравець виграє при будь-яких відповідних діях супротивника.