Question

Вкаждой клетке прямоугольной таблицы сидит жук одного из 90 видов (все виды присутствуют). пара видов жуков называется дружественной, если существует две клетки, соседние по ребру, в которых сидят жуки этих двух видов. каково минимальное число пар дружественных жуков?

Answer 1

Оценка:

Рассмотрим граф, вершинами которого являются виды жуков, а рёбрами - "дружба" между двумя видами жуков. Пусть нашлась вершина нулевой степени (или с "петлёй"), тогда, так как жуки данного вида присутствуют в таблице, все соседние клетки с клеткой с таким жуком тоже будут содержать таких жуков. Несложно вывести из этого, что в таком случае все клетки таблицы содержат жуков данного вида, что противоречит условию. Значит, все вершины графа имеют исходящие рёбра. Пусть граф несвязен, тогда, объединив все виды жуков из одной компоненты связности графа в один общий вид, получаем противоречие по уже доказанному. Значит, граф связен. Минимальный связный граф - "дерево", в котором 89 рёбер. Значит, пар дружественных жуков не меньше 89.

Пример:

Рассмотрим прямоугольник 1 на 178 клеток. Пусть во всех клетках с нечётным порядковым номером сидят жуки первого вида, а в оставшихся 89 клетках сидят жуки оставшихся 89 видов, по одному каждого вида на таблицу. Так как таблица покрасилась "шахматной раскраской", никакие два жука первого вида не сидят рядом и никакие два жука не первого вида не сидят рядом, следовательно, рядом могут сидеть только жук первого вида и жук не первого вида. Следовательно, пар дружественных жуков всего 89.

ответ: 89 пар.