Дана таблица размером 8 х 8, изображающая шахматную доску. За каж- дый шаг разрешается поменять местами любые два столбца или любые две строки. Можно ли за несколько шагов сделать так, чтобы верхняя по- ловина таблицы стала белой, а нижняя половина чёрной? Подсказка: что в этом процессе является инвариантом?

Ответ: Нельзя.

Разбираемся:

• Рассмотрим шахматную доску 8x8.
• В исходной шахматной доске каждая строка и каждый столбец содержит 4 белых и 4 черных клетки.
• После любого количества перестановок строк и столбцов количество белых и черных клеток в каждой строке и каждом столбце остается неизменным.
• В целевой конфигурации (верхняя половина белая, нижняя черная) верхние 4 строки должны содержать 8 белых и 0 черных клеток, а нижние 4 строки должны содержать 8 черных и 0 белых клеток.
• Но это противоречит инварианту, так как каждая строка должна содержать 4 белых и 4 черных клетки.

Ответ: Нельзя.