Назовём натуральное число $%n$% детонирующим, если набор чисел $%1, 2, \dots , 2n$% можно разбить на пары, сумма чисел в каждой из которых есть степень тройки. Можно ли найти все детонирующие числа?

задан 4 Июл 0:12

10|600 символов нужно символов осталось
3

Есть рабочая гипотеза. Рассмотрим последовательность, которая задается следующим образом: $%a_0=1$% и для произвольного натурального $%k: \;\; a_{2k-1}=3a_{k-1}, \; a_{2k}=3a_{k-1}+1$%. Т.е. наша последовательность 1,3,4,9,10,12,13,27,28,... Гипотеза: все члены этой последовательности являются детонирующими числами и только они. Если найдете контрпример (детонирующее число, которого нет в этой последовательности, или же член этой последовательности не являющийся детонирующим числом), то будет круто. Но мне кажется, что гипотеза верна. Только не спрашивайте как я к ней пришел))

ссылка

отвечен 4 Июл 2:52

@Witold2357, это все числа, не содержащие двойку в троичной записи?

(4 Июл 11:35) Казвертеночка
10|600 символов нужно символов осталось
4

Гипотеза @Witold2357 верна, и её можно доказать индукцией по $%n$%. Сформулировать удобно так: число $%n$% в троичной записи не содержит цифры 2.

Рассмотрим случай, когда старший разряд числа $%n$% равен 1. Положим $%n=3^m+k$%, где $%k < 3^m$%. Доказать нужно то, что $%n$% "детонирующее" тогда и только тогда, когда $%k$% обладает этим же свойством. (Число 0 удобно считать детонирующим, так как оно представимо в виде пустой суммы.)

Рассмотрим число $%2n=2\cdot3^m+2k$%. Оно должно давать степень тройки в сумме с каким-то меньшим числом. Легко понять, что $%3^{m+2}$% и более в сумме получиться не может, то есть может быть лишь $%3^{m+1}$%. Из этого следует, что $%2k\le3^m-1$%, то есть $%k\le\frac{3^m-1}2$%, что имеет запись из одних единиц в троичной системе. Итак, $%2n$% находится в паре с $%3^{m+1}-2n=3^m-2k$%. Также ясно, что $%2n-1$% при этом будет в паре с $%3^m-2k+1$%; число $%2n-2$% в паре с $%3^m-2k+2$% и так далее. Это следует из того, что все числа $%2n-1$%, $%2n-2$%, ... строго больше $%n\ge3^m$%, поэтому они могут находиться в паре только с числом, которое в сумме даёт $%3^{m+1}$%.

Отобранные выше пары "покрывают" все числа от $%3^m-2k$% до $%2n$%. Это значит, что предыдущие числа от 1 до $%3^m-1-2k$% также разбиваются на пары, то есть $%\frac{3^m-1}2-k$% детонирующее. Понятно, что если из $%11...1$% (в троичной) вычитается меньшее число без двоек в записи, то получается число из нулей и единиц, и наоборот: наличие двойки в записи $%k$% в каком-то разряде даёт двойку в результате вычитания (в том же разряде, если брать крайний справа).

Осталось рассмотреть второй случай, когда старший разряд $%n$% равен 2, и доказать, что такое число детонирующим не является. Пусть $%n=2\cdot3^m+k$%, где $%k < 3^m$%. Допустим, что $%2n=4\cdot3^m+2k$% даёт степень тройки в сумме с меньшим числом. Ясно, что такой степенью может быть лишь $%3^{m+2}$%, то есть меньшим числом должно быть $%5\cdot3^m-2k < 2n$%, откуда $%3^m < 4k$%. Таким образом, для чисел отрезка $%[5\cdot3^m-2k,2n]$% имеется разбиение на пары чисел, в сумме дающих $%3^{m+2}$%, и только оно может быть иметь место, так как большие из чисел пар превышают $%3^{m+2}/2 > 3^{m+1}$%.

В итоге оказывается, что на пары должны разбиваться числа отрезка $%[1,5\cdot3^m-2k-1]$%, и число $%\frac{5\cdot3^m-1}2-k=3^m+\frac{3^{m+1}-1}2-k$% детонирующее. Но это противоречит индукционному предположению, так как здесь к числу из единиц $%\frac{3^{m+1}-1}2$% прибавляется положительное число $%3^m-k$%, и это гарантирует появление хотя бы одной двойки в двоичной записи.

ссылка

отвечен 4 Июл 19:51

1

@falcao, большущее Вам спасибо! Красивое решение у Вас получилось, да и задача тоже красивая.

(5 Июл 0:03) Казвертеночка
1

@Казвертеночка: да, задача очень естественная получилась, и она украсила бы любую хорошую олимпиаду.

Кстати, я несколько первых чисел нашёл, когда начинал решать, но рассматривал их в удвоенном виде (как 2n), и там труднее было увидеть свойство двоичной записи. К тому же я не знал, что оно там совсем хорошее. Потом уже увидел гипотезу @Witold2357 и стал доказывать формально.

(5 Июл 0:06) falcao

@falcao, Вы хотели сказать "троичной"?

(5 Июл 0:11) Казвертеночка
1

@Казвертеночка: да, конечно -- я оговорился, и даже не заметил. Думаю, помешало слово "удвоенной", которое и спровоцировало :)

(5 Июл 0:32) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

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

по почте:

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

по RSS:

Ответы

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

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