Найти все натуральные $%x$% такие, что записав несколько раз подряд число $%x$% в десятичной записи, получим двоичную запись этого же самого числа $%x$%.

задан 7 Дек '14 23:03

@EdwardTurJ: а у Вас в решении предполагался какой-либо компьютерный перебор?

(8 Дек '14 22:03) falcao

@falcao: Моё решение по сути не отличается от Вашего, поэтому не привожу. Задача предлагалась в 2007 году на всеукраинском матбое, а поскольку задачи даются заранее, то не исключается компьютерный перебор.

(8 Дек '14 22:16) EdwardTurJ

@EdwardTurJ, а ведущие нули учитывать?

(31 Май '15 2:32) Isaev
10|600 символов нужно символов осталось
3

У меня получилось только число $%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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×41

задан
7 Дек '14 23:03

показан
727 раз

обновлен
31 Май '15 2:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru