|
|
 |
Условие
На каждой клетке доски 10×10 стоит фишка. Разрешается выбрать диагональ, на которой стоит чётное число фишек, и снять с неё любую фишку.
Какое наибольшее число фишек можно убрать с доски такими операциями?
Решение
Назовём (не)чётной диагональ, на которой (в данный момент) стоит (не)чётное число фишек. После снятия фишки чётная диагональ становится нечётной, а нечётная – чётной. Поэтому число нечётных диагоналей не уменьшается. В начале на доске есть 20 нечётных диагоналей, значит, и в конце их не меньше 20. Из них не менее 10 параллельных, и уже на них останется не менее 10 фишек.
Снять 90 фишек можно, например, в следующем порядке. Снимем все фишки левого столбца. Теперь можно снять все фишки 2-го столбца, кроме верхней и нижней, затем все фишки 3-го столбца... и т.д.
Ответ
90 фишек.
Замечания
1. Возможны и другие алгоритмы. В некоторых полезно заметить, что фишки с белых и чёрных полей (в шахматной раскраске) снимаются независимо друг от друга. Поэтому достаточно суметь снять 45 "белых" фишек. Также отметим, что надо всегда снимать фишку с пересечения чётной и нечётной диагоналей (иначе число нечётных диагоналей увеличится).
2. 6 баллов.
