Question

в 18-ти точках, отмеченных на рисунке расставлены числа от 1 до 18. Доказать, что найдётся ребро на концах которого стоят числа с разностью больше трёх.

Answer 1

Предположим, что это не так. Возьмем число 18, оно дает разность не больше 3 только с 15, 16 и 17, тогда ставим число 18 в точку из которой выходит 3 ребра и на другие их концы ставим 15, 16 и 17, Далее обращаем внимание на число 17, оно дает разность не больше 3 только с 18, 16, 15 и 14. С 18 число лежит на 1 ребре, а с 16 и 15, наоборот, не может лежать в любом случае, т.е. у нас 2 пары чисел 17 и 18, 17 и 14. А число 17 стоит в точках из которых выходит либо 3, либо 4 ребра, т.е. нам придется поставить число, разность которого с 17 больше 3

Answer 2

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

В данной задаче у нас есть 18 точек и каждая из них соединена с другими точками рёбрами, образуя граф. Всего рёбер будет $C_{18}^2 = \frac{18!}{2!(18-2)!} = 153$ (каждая пара из 18 точек соединена ровно одним ребром).

Теперь предположим, что у нас нет ребра с разностью чисел на его концах больше трёх. То есть, максимальная разница между числами на концах каждого ребра составляет 3 или меньше.

Давайте посмотрим на такие пары чисел: (1, 4), (2, 5), (3, 6), ..., (15, 18). У нас есть 6 таких пар с разностью 3. Теперь давайте рассмотрим пары (1, 5), (2, 6), ..., (14, 18). У нас также есть 6 таких пар с разностью 4. Продолжая этот процесс, мы можем получить пары (1, 7), (2, 8), ..., (12, 18) с разностью 6. Наконец, у нас есть пара (1, 8) с разностью 7.

Теперь посчитаем общее количество пар чисел с разницей, не превышающей 3: 6 + 6 + 6 + 1 = 19. Это число больше количества рёбер в графе (153), что означает, что мы не можем назначить каждой паре чисел своё ребро без нарушения условия разницы меньше или равной 3.

Таким образом, мы пришли к противоречию, исходное предположение о том, что нет ребра с разностью чисел больше трёх, неверно. Следовательно, найдётся хотя бы одно ребро с разностью чисел на его концах больше трёх.