Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№115

Задача ММ15 составлена специально для Математического марафона Сергеем Половинкиным.

Призовые баллы за решение ММ115 учитываются дважды: в тематическом конкурсе и в основном Марафоне.

Конкурсная задача ММ115 (Ш-3) (10 баллов)

На шахматной доске расставлены кони.

:pic_115

Разрешается менять цвет фигур одновременно в клетках на одной вертикали, горизонтали или диагонали (в частности, в одной угловой клетке - считается, что она сама - диагональ). Можно ли получить одноцветный квадрат 5×5 в каком-либо месте доски?

Решение

Приведу решение Анатолия Казмерчука (по сути совпадающее с авторским).

Каждый из 16-и квадратов 5х5 содержит одно из четырех множеств полей:
1) b3, b4, c2, c5, d2, d5, e3, e4 (сиреневый восьмиугольник);
2) b5, b6 ,c4, c7, d4, d7, e5, e6 (зеленый восьмиугольник);
3) d3, d4, e2, e5, f2, f5, g3, g4 (желтый восьмиугольник);
4) d5, d6, e4, e7, f4, f7, g5, g6 (синий восьмиугольник).

Каждое допустимое преобразование либо вовсе не затрагивает такое множество, либо инвертирует цвета ровно двух коней, стоящих на полях, принадлежащих такому множеству. Но на полях каждого из множеств стоит нечетное (а именно 3) число черных коней. Поэтому получить квадрат 5х5, заполненный конями одного цвета невозможно.

:marathon:115-2.jpg

Обсуждение

Некоторые участники нашли (в каждом квадрате 5х5) другие конфигурации клеток, обладающие теми же свойствами, что конфигурация, используемая в приведенном решении. А именно:
каждая конфигурациия содержащие нечетное число черных коней;
четность числа черных коней, принадлежащих конфигурации, инвариантна относительно допустимых преобразований.
(Для некоторых других квадратов 5х5 конфигурацию на левом рисунке надо повернуть на 90 градусов.)

:marathon:115_1.jpg :marathon:115_3.jpg

Алексей Волошин показал, что исходная позиция не позволяет получить не только квадрат 5х5, и прямоугольник 4х5 (4 горизонтальных ряда), заполненный одноцветными конями. В то же время, прямоугольник 5х4 (и даже 8х4) получить можно.

Николай Дерюгин показал, что для решения задачи достаточно показать невозможность заполнения одного произвольно выбранного квадрата 5х5 и исследовал граф состояний и переходов, связанный с таким квадратом. (Однако Николай так и не нашел инварианта, подходящего для доказательства отсутствия решения, а граф состояний, разумеется, слишком огромен для переборного решения.)

Награды

За составление (и исследование) задачи ММ115 Сергей Половинкин получает 12 призовых баллов. За правильное решение и обобщение задачи Алексей Волошин получает 11 призовых баллов. За правильное решнеие Анатолий Казмерчук, Эдвард Туркевич и Дмитрий Пашуткин получают по 10 призовых баллов. Николай Дерюгин получает 4 призовых балла, а новичок Марафона SiO2 - 1 призовой балл.

Эстетическая оценка задачи - 5 баллов

Отмечу, что эта задача получила наивысшую оценку участников (Браво, Сергей!) за всю историю Марафона. Задачи, оцененные на 5 баллов, в Марафоне уже были, но те пятерки были «средними арифметическими» одной оценки (максимум двух). Этой же задаче пятерки выставили сразу 5 марафонцев!


 

 


Страница: [[marathon:problem_115]]

marathon/problem_115.txt · Последние изменения: 2010/07/07 11:00 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006