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

Отрезки между точками с простым отношением чисел

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

Решение

Оценка. Предположим, что среди отрезков есть замкнутая ломаная (цикл) . Пусть числа у точек равны . Обходя цикл, перемножим отношения соседних чисел:

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

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

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

Итого: отрезка.

💡 Почему так

Цикл из отрезков невозможен: произведение отношений вдоль цикла равно , а при различных простых числах оно не может быть равно . Значит, отрезки образуют лес, и их не больше .

Ответ

✓ dzmen.ru

Помогло?

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