Решение задачи 178

Условие:

На шахматной доске стоят 8 ладей так, что они не бьют друг друга. Докажите, что число ладей, стоящих на черных полях, четно.

Решение:

Первый способ:

Пусть на шахматной доске расположены как-то 8 ладей так, что они друг друга не бьют, т.е. в каждой строке и в каждом столбце стоит ровно по одной ладье (рисунок 1).

Сдвинем все ладьи на одну позицию влево (ладья, стоящая в первом столбец перейдет в 8-ой столбец, оставшись на той же строке). Очевидно, что ладьи так же не будут друг друга бить. Заметим, что ладья, стоявшая на черной клетке, перейдет на белую клетку, и наоборот. Пусть до сдвига k ладей стояли на черных клетка. Тогда после сдвига 8-k ладей будут стоять на черных клетках. Числа k и 8-k одной четности, это значит что после сдвига четность количества ладей, стоящих на черных клетках, не изменится. Сделаем столько сдвигов, пока верхняя ладья не окажется в первом столбце (в нашем примере два сдвига). Тогда расположение ладей будет следующим: (рисунок 2)

Теперь будем работать с квадратом 7×7, который содержит правую нижнюю угловую клетку, т.е. этот квадрат не содержит верхнюю левую ладью. Будем также проделывать сдвиги влево, но теперь внутри этого квадрата 7×7, т.е. ладьи со второго столбца будут переходит сразу на 8-ой. Заметим, что при одном сдвиге влево все ладьи перейдут на клетку другого цвета кроме ладьи, стоящей во втором столбце. Покажем, что и в этом случае четность количества ладей, стоящих на черных клетках, не изменится. Пусть во втором столбце ладья (она одна) стоит на белой клетке. Тогда после сдвига она также будет стоять на белой клетке. Пусть среди оставшихся шести ладей k стоят на черных клетках. Тогда после сдвига, эти 6 ладей (все кроме той, что стоит во втором столбце) поменяют цвет клетки, то есть теперь на черных клетках будут стоять 6-k ладей. Отметим сразу, что числа k и 6-k одной четности. Пусть теперь во втором столбце ладья стоит на черной клетке. Тогда после сдвига она также будет стоять на черной клетке. Пусть среди оставшихся шести ладей k стоят на черных клетка. Тогда после сдвига на черных клетках будут стоять 6-k ладей и еще та, которая перешла в 8-ой столбец. То есть после сдвига на черных клетках будет стоять 7-k ладей, а до сдвига на черных клетках стояло k+1 ладей. В этом случае k+1 и 7-k также одной четности. Получается, что после сдвига в квадрате 7×7 четность числа ладей, стоящих на черных клетках, не меняется. Сделаем столько сдвигов влево, пока ладья, стоящая во 2-ой строке (1-ая -- самая верхняя), не окажется во втором столбце. Тогда будет следующее расположение ладей: (рисунок 3)

Будем продолжать этот процесс, т.е. переходить к квадрату со стороной на 1 меньше (все квадраты содержат правую нижнюю угловую клетку) и делать в нем сдвиги, пока ладья, стоящая в i-ой строке не окажется в i-ом столбце. Тогда в любой момент четность количества ладей, стоящих на черных клетках, будет такой же, как и в самой начальной расстановке. В итоге мы добьемся того, что все ладьи будут стоять на диагонали: (рисунок 4)

Но в этом расположение ровно 0 ладей стоят на черных клетках, то есть четное число. Значит и в начальном положении число ладей, стоявших на черных полях, было четно.

Второй способ:

Пронумеруем столбцы и строки от 1 до 8: (рисунок 5)

Тогда каждая ладья будет иметь координаты (a,b), где a -- номер столбца, в котором она стоит, а b -- номер строки. Пусть на доске расположены 8 ладей так, что они друг друга не бьют. Пусть они имеют координаты (a₁,b₁), (a₂,b₂), ...,(a₈,b₈). Так как в каждой строке и в каждом столбце стоит по одной ладье, то наборы {a₁, a₂, ..., a₈} и {b₁, b₂, ..., b₈} это числа {1, 2, ..., 8}, переставленные в каком-то порядке. Заметим так же, что клетка является черной тогда и только тогда, когда сумма ее координат -- четное число. Рассмотрим сумму из восьми слагаемых: (a₁+b₂)+(a₂+b₂)+...+(a₈+b₈) = a₁+a₂+...+a₈+b₁+b₂+...+b₈ = 2*(1+2+...+8) = четное число. Это значит, что среди восьми чисел (a₁+b₂), (a₂+b₂), ...,(a₈+b₈) четное число нечетных. Напомним, что если aᵢ+bᵢ нечетно, то i-ая ладья стоит на белой клетке (обратное тоже верно). Отсюда следует, что число ладей, стоящих на белых клетках, четно, а значит и число ладей, стоящих на черных клетках, четно.