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


Содержание

ММ151

Конкурсная задача ММ151 (ТГ-1) (4 балла)

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

Решение

Очевидно, что клетки, имеющие разное число соседей, не могут быть смежны. Поэтому в графе не менее трех связных компонент, образованных соответственно: угловыми клетками (их 4); боковыми, но не угловыми (их 8); центральными (их 4). Поэтому в графе не более чем 2C(4,2)+C(8,2) = 40 ребер. Это число очевидно достигается при такой раскраске:

:marathon:mm151_1.jpg

Несколько более сложно достигается случай графа без ребер. Дело в том, что каждая из угловых клеток имеет от 0 до 3 белых соседок и сама покрашена из один из двух цветов. Всего получается 8 вариантов. И боковых клеток тоже 8. Поэтому необходима раскраска реализующая все 8 случаев. Подойдет, например, такая:

:marathon:mm-151_2.jpg

Поскольку на каждой из диаграмм поровну черных и белых клеток, ответы к пунктам a) и b) совпадают: минимальное количество ребер - 0; максимальное - 40.

Обсуждение

Многие участники Марафона не ограничились рассмотрением случаев указанных в условии. Обобщение задачи велось преимущественно по трем направлениям:
нахождение наибольшего и наименьшего числа ребер в случае фиксированного числа белых клеток (обобщение пункта б);
нахождение всех возможных значений числа ребер;
рассмотрение досок nxn при других n.
Конечно, можно было бы обобщать задачу и в других направлениях, например, изменив число разрешенных цветов. То таких попыток участники не делали. Воздержусь от них и я :-)
Наибольших успехов в обобщении задачи добился Олег Полубасов. Приведу найденные им графы с минимальным числом ребер для досок 5×5 и 6×6.

:marathon:mm151_3.jpg

:marathon:mm151_4.jpg

В первом случае граф содержит 4 ребра. Меньше 4-х ребер быть не может. Как уже отмечалось, для боковых клеток имеется всего 8 возможностей, а на доске 5×5 таких клеток 12. Поэтому при разбиении их на классы 4 класса будут двухэлементными (если использовать классы с бОльшим числом элементов число ребер только увеличится). Во втором случае, граф содержит 14 ребер. Это тоже гарантированный минимум. Боковых клеток для доски 6×6 уже 16, что дает, как минимум 8 ребер. Еще, как минимум, 6 ребер образую центральные клетки. Их тоже 16, а вариантов для них 10 (от нуля до четырех белых соседей и цвет самой клетки).

Максимальное количестве ребер, очевидно, достигается при одноцветной раскраске графа и равно C(4,2)+C(4n-8,2)+C((n-2)2,2). При больших n невозможна ситуация, когда такое же число ребер возникнет при раскраске, в которой представлены оба цвета.

Замечу, что граф, возникающий при каждой раскраске доски nxn, всегда является графом некого отношения эквилентности, заданного на множестве из n2 элементов. По условию задачи каждое такое отношение содержит не менее 3-х и не более 22-х (до 4-х для угловых клеток, до 8-и - для боковых и до 10-и - для центральных) классов. Если использовать большее число цветов, все равно каждая раскраска будет задавать отношение эквивалентности, только возможных классов станет больше.

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

Награды

За правильное решение и ряд интересных обобщений задачи ММ151 Олег Полубасов получает 5 призовых баллов. Сергей Половинкин, Алексей Волошин, Евгений Гужавин, Виктор Филимоненков и Николай Дерюгин получают по 4 призовых балла. (Последний, несмотря на «тождество» 6+6+28=42. Все же задача на графы, а не на арифметику :-) ). Александр Князев получает 1 призовой балл.

Эстетическая оценка - 4.2 балла

Разбор задачи ММ151 подготовил Владимир Лецко


 

 


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

marathon/problem_151.txt · Последние изменения: 2012/01/30 20:57 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006