Задача
Петя и Вася играют на доске размером 7×7. Они по очереди ставят в клетки доски цифры от 1 до 7 так, чтобы ни в одной строке и ни в одном столбце не оказалось одинаковых цифр. Первым ходит Петя. Проигрывает тот, кто не сможет сделать ход. Кто из них сможет выиграть, как бы ни играл соперник?
Решение
Назовём расстановку чисел в клетках данной доски "антисимметричной", если клетки, симметричные относительно центральной клетки доски, либо обе пустые, либо в них стоят числа, сумма которых равна 8.
Петя должен играть так: первым ходом поставить число 4 в центральную клетку, а затем, после каждого хода Васи осуществлять "антисимметричную" расстановку чисел. То есть, если Вася поставил в какую-то клетку число n, то Петя должен поставить в симметричную клетку число 8 – n.
Играя так, Петя выиграет. Действительно, клетка, симметричная только что занятой, перед каждым ходом Пети будет пустой. Докажем, что он сможет поставить в эту клетку указанное число.
Предположим, что это не так, то есть Вася поставил в какую-то клетку A число n, а в одной из клеток B линии (строки или столбца), содержащей симметричную клетку A', уже стоит число 8 – n. Заметим, что B не совпадает с A. Действительно, если эти клетки совпадут, то 8 – n = n, то есть n = 4. С другой стороны, симметричные клетки A = B и A' лежат на одной линии A'B = A'A. На этой же линии лежит и центральная клетка доски O, следовательно, Вася не имел права поставить 4 в A.
Из "антисимметричности" следует, что в симметричной B клетке B' уже стоит n. Поскольку клетки A и B' лежат на линии, симметричной A'B, Вася не имел права поставить n в A. Противоречие. (Поясним эти рассуждения на конкретом примере – см. рис. Кружком обведён очередной ход Васи; он поставил число 1. Петя хочет поставить 7 в клетку, отмеченную точкой. Предположим, он не может этого сделать из-за того, что в закрашенной клетке уже стоит 7. Тогда в клетке, отмеченной крестиком, уже стоит 1, то есть Вася не мог сделать предыдущий ход.)
Ответ
Петя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь