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