Найти все натуральные $%x$% такие, что записав несколько раз подряд число $%x$% в десятичной записи, получим двоичную запись этого же самого числа $%x$%. задан 7 Дек '14 23:03 EdwardTurJ |
У меня получилось только число $%10=1010_2$% ("вырожденный" случай числа 1 я не учитываю). Пусть число $%x$% в десятичной записи $%k$%-значно. Его цифрами являются 0 и 1. Тогда $%10^{k-1}\le x < 10^k/9$%. Предположим, что мы повторили эту запись $%4$% или более раз. Тогда двоичная запись будет как минимум $%4k$%-значна, и она задаёт число, не меньшее $%2^{4k-1}$%. Неравенство $%2^{4k-1}\le x < 10^k/9$%, очевидно, не имеет места. Поэтому число повторов записи не больше трёх. Рассмотрим случай двух повторов. Двоичное $%2k$%-значное число меньше $%2^{2k}$%, поэтому $%10^{k-1}\le x < 4^k$%, откуда $%k\le2$%. Число 10 подходит, а 11 не подходит. Основной случай -- когда повторов ровно три. Здесь, с одной стороны, $%10^{k-1}\le x < 2^{3k}$%, то есть $%(5/4)^k < 10$%. Это даёт ограничение $%k\le10$%. Далее, $%2^{3k-1}\le x < 10^k/9$%, откуда $%k\ge7$%. Случаев $%k$%-значных десятичных чисел из нулей и единиц, где $%7\le k\le10$%, имеется достаточно много, чтобы перебирать их вручную, но их сравнительно мало, чтобы осуществить компьютерный перебор. Он никаких вариантов не дал. Возможно, впрочем, тут есть какие-то принципы "отсева", позволяющее избежать машинного перебора. отвечен 8 Дек '14 14:21 falcao |
@EdwardTurJ: а у Вас в решении предполагался какой-либо компьютерный перебор?
@falcao: Моё решение по сути не отличается от Вашего, поэтому не привожу. Задача предлагалась в 2007 году на всеукраинском матбое, а поскольку задачи даются заранее, то не исключается компьютерный перебор.
@EdwardTurJ, а ведущие нули учитывать?