Как решить олимпиадное задание? На доске записываются 16 различных положительных целых чисел, ни одно из которых не
превышает 60. Для каждой пары чисел найдём их положительную разность. Докажи, что в
множестве полученных таким образом разностей найдётся по меньшей мере три равных
числа.

Предыдущий
вопрос Следующий
вопрос

Доказательство:

Рассмотрим все возможные разности между числами на доске. У нас 16 чисел, следовательно, всего различных разностей будет ( \binom{16}{2} = 120 ).

Теперь заметим, что каждая разность между двумя числами не превышает 60 (так как мы работаем только с положительными числами). Таким образом, наибольшее количество различных разностей, которые могут быть на доске, равно 60.

Если у нас есть 120 различных разностей между числами и только 60 различных чисел от 1 до 60, то как минимум 2 разности должны быть равны между собой (по принципу Дирихле).

Таким образом, у нас найдутся хотя бы 3 равные разности между числами на доске.