Задачі на виграшні стратегії
Під математичною грою розуміють гру двох суперників, що має таку властивість. У кожний момент гри стан характеризується позицією, яка може змінюватися тільки залежно від ходів гравців. Для кожного з гравців деякі позиції є виграшними. Досягти виграшної для себе позиції і є мета кожного. Іноді ігри допускають нічию. Це означає, що жоден з гравців не може досягти виграшної для нього позиції або деякі позиції оголошені нічийними.
Наприклад, шахи, шашки, хрестики-нулики є математичними іграми. А ігри в кості, доміно, більшість карточних ігор не є математичними іграми, оскільки стан гри залежить не тільки від ходів суперника, але і від розкладу або результату кидання кості.
У математичних іграх існує поняття виграшної стратегії, тобто набору правил (можна сказати, інструкцій або алгоритму), слідуючи яким, один з гравців обов’язково виграє (незалежно від того, як грає його суперник), і поняття нічийної стратегії, слідуючи якій один з гравців обов’язково доб’ється або виграшу, або нічиєї.
У будь-якій математичній грі існує або виграшна стратегія для одного з гравців, або нічийні стратегії для обох (якщо гра допускає нічию). В залежності від цього гру називають виграшною для першого або другого гравця, або нічийною. Наприклад, хрестики-нулики (на дошці 3 ´ 3) є нічийною грою. При розв’язуванні задач на виграшні стратегії можна використовувати певні підходи.
Відповідність. Наявність вдалого у відповідь ходу (може забезпечуватися симетрією, розбиттям на пари, доповненням числа).
Розв’язання з кінця. Послідовно визначають позиції, виграшні і програшні для першого гравця. Чергова позиція є виграшною, якщо з неї можна одержати раніше визначену програшну позицію, і є програшною, якщо будь-який хід з неї веде до попадання в раніше визначену виграшну позицію.
Передача ходу. Якщо ми можемо скористатися стратегією супротивника, то наші справи не гірші, ніж у нього. Наприклад, виграш (або нічия) забезпечується, коли можна за своїм бажанням потрапити в деяку позицію або примусити супротивника потрапити в неї.