Можно подумать об этом следующим образом: каждому ребру необходимо связать два числа таким образом, чтобы на обеих конечных точках имелся делитель 2 и делитель 3.
Из чисел от 1 до 60включительно, есть 20 чисел без делителей 2 или 3 (а именно, 1, 7, 13, 19, ... и 5, 11, 17, ...).Есть 10 чисел с делителем 2 и 3 (6, 12, 18, ...).Есть 10 чисел с 3 делителями (3, 9, 21, ...) и 20 чисел с 2 делителями (2, 8, 14, ... и 4, 10, 16, ...).
Существует как минимум одно оптимальное решение, которое всегда объединяет числа с 2 и 3 делителями с числами, не имеющими ни 2, ни 3 делителей.(Вы можете доказать это противоречием).Итак, начнем с этого.Таким образом,
- 10 чисел без 2 или 3 делителей
- 10 чисел только с 3 делителями.
- 20 чисел только с 2 делителями.
Эти 10 чисел без делителей 2 или 3 не имеют ребер ни к одному из других чисел, поэтому мы можем их игнорировать.Из оставшихся чисел есть ребра от всех чисел с 3 делителями до всех чисел с 2 делителями, поэтому вы должны соединить все 10 чисел с 3 делителями с 10 числами только с делителем 2.
Всего получается 20 ребер: все кратные 6 с 10 числами, которые являются либо 1, либо 5 моду 6, и все числа, которые являются 3 мод 6, с 10 числами, которые являются либо 2, либо 4 мода 6.
Надеюсь, это поможет!