В каждой клеточке прямоугольной таблицы посиживает жук 1-го из 90 видов

Оценка:

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

Пример:

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

Ответ: 89 пар.