Задача 115367

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

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

Условие

Автор: Агаханов Н.Х.

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

Решение

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

Ответ

Нет

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2009-2010
Этап
Вариант	4
Класс
Класс	10
задача
Номер	06.4.10.2
олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2009-2010
Этап
Вариант	4
Класс
Класс	9
задача
Номер	06.4.9.3