|
||||||||||||||||||
|
Содержание№115Задача ММ15 составлена специально для Математического марафона Сергеем Половинкиным. Призовые баллы за решение ММ115 учитываются дважды: в тематическом конкурсе и в основном Марафоне. Конкурсная задача ММ115 (Ш-3) (10 баллов) На шахматной доске расставлены кони. Разрешается менять цвет фигур одновременно в клетках на одной вертикали, горизонтали или диагонали (в частности, в одной угловой клетке - считается, что она сама - диагональ). Можно ли получить одноцветный квадрат 5×5 в каком-либо месте доски? Решение Приведу решение Анатолия Казмерчука (по сути совпадающее с авторским).
Каждый из 16-и квадратов 5х5 содержит одно из четырех множеств полей: Каждое допустимое преобразование либо вовсе не затрагивает такое множество, либо инвертирует цвета ровно двух коней, стоящих на полях, принадлежащих такому множеству. Но на полях каждого из множеств стоит нечетное (а именно 3) число черных коней. Поэтому получить квадрат 5х5, заполненный конями одного цвета невозможно. Обсуждение
Некоторые участники нашли (в каждом квадрате 5х5) другие конфигурации клеток, обладающие теми же свойствами, что конфигурация, используемая в приведенном решении. А именно: Алексей Волошин показал, что исходная позиция не позволяет получить не только квадрат 5х5, и прямоугольник 4х5 (4 горизонтальных ряда), заполненный одноцветными конями. В то же время, прямоугольник 5х4 (и даже 8х4) получить можно. Николай Дерюгин показал, что для решения задачи достаточно показать невозможность заполнения одного произвольно выбранного квадрата 5х5 и исследовал граф состояний и переходов, связанный с таким квадратом. (Однако Николай так и не нашел инварианта, подходящего для доказательства отсутствия решения, а граф состояний, разумеется, слишком огромен для переборного решения.) Награды За составление (и исследование) задачи ММ115 Сергей Половинкин получает 12 призовых баллов. За правильное решение и обобщение задачи Алексей Волошин получает 11 призовых баллов. За правильное решнеие Анатолий Казмерчук, Эдвард Туркевич и Дмитрий Пашуткин получают по 10 призовых баллов. Николай Дерюгин получает 4 призовых балла, а новичок Марафона SiO2 - 1 призовой балл. Эстетическая оценка задачи - 5 баллов Отмечу, что эта задача получила наивысшую оценку участников (Браво, Сергей!) за всю историю Марафона. Задачи, оцененные на 5 баллов, в Марафоне уже были, но те пятерки были «средними арифметическими» одной оценки (максимум двух). Этой же задаче пятерки выставили сразу 5 марафонцев!
|
|||||||||||||||||
|
||||||||||||||||||
|