Элементы теории математических игр

Игрой

называется процесс, в котором участвуют две или более стороны, ведущие борьбу за реализацию своих интересов.

Согласно этому определению, довольно много жизненных ситуаций можно считать играми - для этого требуется лишь борьба двух или более лиц и какие-либо интересы, за которые эти лица ведут борьбу. Шахматы, домино, прыжки в высоту - всё это игры. Стремление занять свободное место в автобусе, соперничество мировых держав в ядерной сфере, беседа сотрудника ГИБДД с нарушителем, поход семейной пары в торговый центр - и это тоже игры. Так, в случае стремления занять свободное место в пустом автобусе в этом процессе участвуют не менее двух человек, которые ведут борьбу за свободные места (свои интересы), причём довольно часто количество свободных мест намного меньше количества участвующих в этой игре человек, поэтому в этой игре есть выигравшие и проигравшие. В этом случае интересы (занять свободное место) у игроков совпадают. Однако в случае игры «поход семейной пары в торговый центр» интересы часто строго противоположные: жене хочется совершить как можно больше покупок; мужу - потратить как можно меньше денег на эти покупки.

Изучение такого широкого класса игр математическими методам бессмысленно – в каждой игре есть свои мало-формализуемые особенности, а процесс принятия решений игроками может опираться не только на какие-то математические принципы, в него могут вписываться другие особенности человека, например, уровень интеллекта и характер.

Пример 1

Для решения спора Петя и Вася обращаются к компьютеру за случайным натуральным числом. Если выданное число - чётное, спор выигрывает Петя, если нечетное - спор выигрывает Вася. Является ли описанная процедура игрой?

Решение

Данная процедура тоже является игрой - два игрока ведут борьбу за свои интересы (выиграть спор), и то, как это они делают - неважно. Фактически, игроки с помощью компьютера реализовали подкидывание монетки.


Пример 2

Для решения спора Петя и Вася пишут цифры по очереди на доске слева направо, начинает Петя. Если после десяти ходов полученное `10`-значное число не делится на девять, в споре побеждает Петя, а если делится – Вася. Докажите, что Вася может выиграть спор.

Решение

Второй игрок (Вася) может дополнять число, написанное первым игроком, до девяти. Если ход Пети - «`9`», то ход Васи - «`0`» и т. п. После десяти ходов получим `10`-значное число, сумма цифр которого равна `9^(**)5=45`, и полученное число будет делиться на девять. Таким образом, второй игрок (Вася) сможет выиграть при любых ходах первого игрока (Пети).


Такие игры, в которых как играть - известно одному или обоим игрокам, уже представляют интерес для формализации и изучения. Одним из самых узких классов таких игр является класс математических игр. Этому классу и посвящено данное задание.