Question

Вася выписал 20 последовательных натуральных чисел в некотором порядке. Докажите, что найдутся два числа, стоящих рядом, у которых совпадает хотя бы одна цифра.

Answer 1

Допустим 12 или 13 14 15 16 у них у всех первое число совпадает

Answer 2

Давайте докажем данное утверждение по принципу Дирихле (Принцип крайне удобный при доказательстве существования объектов). В данном случае, у нас есть 20 последовательных натуральных чисел, каждое из которых имеет не более 2 цифр (так как числа натуральные и последовательные).

Если рассмотреть 19 пар чисел, стоящих рядом, то первое число в каждой паре уникально (может повторяться только в конце и только если последовательность начинается с числа, оканчивающегося на 9), так как это натуральные числа и они идут последовательно. Каждое из этих чисел имеет одну или две цифры. Существует всего 180 возможных комбинаций однозначных и двузначных чисел.

Таким образом, у нас есть 19 пар чисел, стоящих рядом, и 180 возможных комбинаций. По принципу Дирихле, если количество "контейнеров" (в данном случае пар чисел) больше, чем количество "элементов" (в данном случае комбинаций), то какой-то из контейнеров должен содержать более одного элемента.

Таким образом, в нашем случае обязательно найдутся два числа, стоящих рядом, у которых совпадает хотя бы одна цифра. Доказательство завершено.