Question

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

Answer 1

Оценка:

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

Пример:

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

Ответ: 89 пар.

Answer 2

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

У нас есть 90 видов жуков и таблица с неизвестным нам числом строк и столбцов. Предположим, что минимальное количество пар дружественных жуков достигается в ситуации, когда каждая пара видов жуков образует по одной дружественной паре. Таким образом, у нас будет 90 пар дружественных жуков.

Однако, для того чтобы образовать дружественную пару, эти два вида жуков должны стоять рядом друг с другом. Предположим, что у нас есть прямоугольная таблица размером 9x10, и каждая ячейка содержит жука одного из 90 видов. Тогда самая первая пара жуков, находящихся в верхнем левом углу, не имеет возможности образовать дружественную пару, так как у них нет соседей справа и снизу.

Таким образом, хотя мы можем образовать 90 пар дружественных жуков, на самом деле не все пары будут дружественными из-за ограничений окружающих клеток. Чтобы найти истинное минимальное число пар дружественных жуков, нам нужно анализировать конкретное расположение жуков в таблице, чтобы определить, какие пары могут быть дружественными.

Таким образом, без конкретной таблицы или дополнительных условий нельзя точно определить минимальное число пар дружественных жуков.