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

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

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

Решение

Рассмотрим граф: вершины — точек, рёбра — проведённые отрезки.

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

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

Пример на отрезков. Возьмём число и различных простых чисел . Запишем у одной точки, а — у остальных. Все чисел различны.

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

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

💡 Почему так

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

Ответ

✓ dzmen.ru

Помогло?

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