Шахматы с Говоруном

У этой задачи есть множество решений. Здесь будет представлено одно из них.

Первая попытка: Расставим ладьи по перестановке $$$1, 2, 3, \ldots, n$$$ (ладья в строке $$$i$$$ стоит в столбце $$$i$$$). Если мы не выиграли, значит угадали нечётное количество ладей.

Возможны два случая:

1. Угадали меньше $$$n$$$ ладей: Тогда существует хотя бы одна угаданная и одна неугаданная ладья. Во второй попытке поменяем их местами. Угаданная ладья перестанет совпадать ($$$-1$$$ совпадение), а неугаданная всё равно не будет совпадать ($$$0$$$ изменений). Итого количество совпадений уменьшится на $$$1$$$ и станет чётным!

2. Угадали все $$$n$$$ ладей: Значит, Говорун расставил перестановку $$$1, 2, 3, \ldots, n$$$. Во второй попытке используем циклический сдвиг: перестановку $$$2, 3, 4, \ldots, n, 1$$$ (ладья в строке $$$i$$$ стоит в столбце $$$i+1$$$, кроме последней строки). Эта перестановка не имеет ни одного общего элемента с исходной, поэтому получим ровно $$$0$$$ совпадений — чётно!