(по мотивам задачи о числах Простобоначчи)

Последовательность чисел ЧерезРазБоначчи строится так. Первые два члена - 0 и 1. Третий равен сумме двух предыдущих, 4-й равен сумме трёх предыдущих, 5-й - снова сумме двух предыдущих и т. д. Неожиданно получаем последовательность, содержащую все степени тройки с ЦНП, все удвоенные степени тройки с ЦНП, а также нуль:

0 1 1 2 3 6 9 18 27 54 81 162 ...

Верно ли, что ни один факториал натурального числа, большего 4, не представим в виде суммы трёх или менее чисел ЧерезРазБоначчи?

задан 8 Авг 18:15

изменен 8 Авг 18:22

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

Это будет отвратительное решение.

Пусть $%f_n$% это $%n$%-е число ЧерезРазБоначчи.

Далее мы везде считаем, что $%k\geqslant 5$%, а случай для $%k=4$% доказан перебором.

Индукцией легко показать, что при $%n\geqslant 3$% мы имеем $%f_{2m+1}=3^{m-1}$% и $%f_{2m}=2\cdot3^{m-2}.$% Заметим, что

$%f_{2m+1}\in\{1,3\}\pmod{8}$% и $%f_{2m}\in\{-2,2\}\pmod{8}.$%

Покажем, что $%f_{n_1} + f_{n_2} + f_{n_3}\ne k!$% при любых $%n_1,n_2,n_3$%. Т.к. необходимо $%f_{n_1} + f_{n_2} + f_{n_3}=0\pmod{8}$%, то прямым перебором мы устанавливаем, что возможны лишь следующие комбинации остатков при делении на восемь: $%1+1-2$% и $%3+3+2$%, т.е. для некоторых натуральных $%m_1,m_2,m_3$% мы имеем $$ s_1=3^{2m_1}+3^{2m_2}+2\cdot 3^{2m_3+1} $$ или $$ s_2=3^{2m_1+1}+3^{2m_2+1}+2\cdot 3^{2m_3}. $$ Должно быть выполнено $%s_1,s_2=0\pmod{5}$%. Ясно, что $%3^{2m},2\cdot3^{2m+1}\in\{-1,1\}\pmod{5}$% и $%3^{2m+1},2\cdot 3^{2m}\in\{-2,2\}\pmod{5}.$% Но так как $%\pm1\pm1\pm1\ne0\pmod{5}$% и $%\pm2\pm2\pm2\ne0\pmod{5}$%, то мы доказали, что хотели.

Очевидно, что $%f_n\ne k!$% (действительно, $%f_n\ne0\pmod{8}$%).

Для доказательства $%f_{n_1} + f_{n_2}\ne k!$% достаточно заметить, что

$%f_{2m+1}\in\{-7,-5,1,3\}\pmod{16}$% и $%f_{2m}\in\{2,6\}\pmod{16}$% и $%k!=0\pmod{16}$%

и сделать небольшой перебор.

ссылка

отвечен 8 Авг 23:28

изменен 8 Авг 23:34

@Sunbro, а разве оно отвратительное? Очень даже симпатичное! Большое спасибо!

(8 Авг 23:53) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×675
×16
×8
×5
×1

задан
8 Авг 18:15

показан
54 раза

обновлен
8 Авг 23:53

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

по почте:

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

по RSS:

Ответы

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

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