На окружности отмечены 26 точек. Рядом с каждой… (алгебра)

№ Числа на вершинах графа, простые отношения

На окружности отмечены 26 точек. Рядом с каждой точкой записали натуральное число так, что все 26 записанных чисел различны. Две точки соединили отрезком, если отношение чисел, записанных рядом с этими точками, равно простому числу. На отрезках написали эти простые числа. Оказалось, что все написанные простые числа различны. Какое максимальное количество отрезков может быть проведено?

Решение

Оценка. Допустим, отрезки образуют цикл. Идём по циклу и перемножаем отношения соседних чисел: каждое равно или , где — простое число на соответствующем отрезке. После полного обхода получаем число, с которого начали, то есть произведение всех отношений равно .

Простые числа на отрезках цикла различны, поэтому каждое из них входит в произведение ровно один раз в степени или . Сократиться ничему не с чем, и произведение не может равняться . Значит, цикла нет.

Граф без циклов на вершинах — лес, в нём не более рёбер.

Пример на отрезков. Берём различных простых чисел (например, все простые меньше ). Записываем:

у одной точки число ;
у остальных точек числа .

Все чисел различны. Отношение — простое, поэтому единица соединена с каждой из точек, и на отрезках стоят различные простые числа. Отношение двух простых чисел при не является целым, поэтому других отрезков нет. Получилось ровно отрезков.

💡 Почему так

Цикл невозможен, потому что в произведении отношений вдоль цикла каждое простое число встретилось бы один раз и не сократилось бы. Граф без циклов на n вершинах имеет не более n− рёбер.

Ответ

✓ dzmen.ru

Помогло?

На окружности отмечены 26 точек. Рядом с каждой точкой записали натуральное…