Можно ли при каком-то натуральном k разбить все натуральные числа от 1 до k на две группы и выписать числа в каждой группе подряд в некотором порядке так, чтобы получились два одинаковых числа?

   Решение

Темы:    [ Десятичная система счисления ] [ Разбиения на пары и группы; биекции ]

Сложность: 3+ Классы: 7,8,9

Прислать комментарий

Условие

Можно ли при каком-то натуральном k разбить все натуральные числа от 1 до k на две группы и выписать числа в каждой группе подряд в некотором порядке так, чтобы получились два одинаковых числа?

Решение

Предположим противное. Ясно, что k > 10 , так как в наборе цифр от 1 до 9 нет повторяющихся. Рассмотрим наибольшую степень десятки 10ⁿ , не превосходящую k. Последовательность цифр числа 10ⁿ целиком войдет в одно из составленных чисел. Но тогда такая же последовательность из единицы и n последующих нулей должна повториться во втором числе. Эта последовательность цифр не могла появиться из объединения двух или более чисел (так как натуральные числа не начинаются с нулей), значит, она содержалась в одном числе, отличном от 10ⁿ . Но наименьшее число, отличное от 10ⁿ и содержащее такой набор цифр, — это 10ⁿ⁺1 . Мы получили противоречие с тем, что 10ⁿ  — максимальная степень десятки, не превосходящая k .

Ответ

Нет

Источники и прецеденты использования