Математика. Подготовка к ЕГЭ. Решение задач.
http://alexlarin.com/

Натуральное число
http://alexlarin.com/viewtopic.php?f=671&t=11829
Страница 1 из 2

Автор:  atakga [ 22 мар 2015, 13:01 ]
Заголовок сообщения:  Натуральное число

Подскажите пожалуйста идею решения этой задачи:
Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`.
Спасибо заранее!

Автор:  michel [ 22 мар 2015, 16:29 ]
Заголовок сообщения:  Re: Натуральное число

atakga писал(а):
Подскажите пожалуйста идею решения этой задачи:
Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`.
Спасибо заранее!

Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много).

Автор:  alex123 [ 22 мар 2015, 17:02 ]
Заголовок сообщения:  Re: Натуральное число

michel писал(а):
atakga писал(а):
Подскажите пожалуйста идею решения этой задачи:
Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`.
Спасибо заранее!

Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много).


b(0) = b(1) = 1.

n >=0 -->
b(2n+1) = ?????
b(2n+2) = ?????

Потом воспользоваться этой рекурсией и получить результат за 11 шагов.

Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы.
А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея.

Автор:  OlG [ 22 мар 2015, 18:33 ]
Заголовок сообщения:  Re: Натуральное число

alex123 писал(а):
michel писал(а):
atakga писал(а):
Подскажите пожалуйста идею решения этой задачи:
Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`.
Спасибо заранее!

Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много).


b(0) = b(1) = 1.

n >=0 -->
b(2n+1) = ?????
b(2n+2) = ?????

Потом воспользоваться этой рекурсией и получить результат за 11 шагов.

Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы.
А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея.


`b(1997)=872`.

Автор:  alex123 [ 22 мар 2015, 18:36 ]
Заголовок сообщения:  Re: Натуральное число

OlG писал(а):
`b(1997)=871`.


Нет, 38.

Автор:  OlG [ 22 мар 2015, 20:19 ]
Заголовок сообщения:  Re: Натуральное число

alex123 писал(а):
Нет, 38.


Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается
(недолгим перебором) еще 37 вариантов представления.

Автор:  atakga [ 22 мар 2015, 21:35 ]
Заголовок сообщения:  Re: Натуральное число

Спасибо всем откликнувшимся! Ниже привожу решение этой задачи. Хотел найти более простую решение задачи с помощью посетителей форума.
Принимая во внимание какое значение может получить `a_(0)` получим:
`b(2n+1) = b(n)` и `b(2n) = b(n) + b(n-1)`.
Для `n=1997` получим `b(1997) = b(998) = b(499) + b(498) = 2b(249) + b(248) = 2b(124) + b(248)` `(1)`
`b(62) = b(31) + b(30), ( b(31) = b(15) = b(7) = b(3) = b(1) = 1 ) ==> b(62) = b(30) + 1`
`b(124) = b(62) + b(61) = b(62) + b(30) = 2b(30) + 1` `(2)`
`b(248) = (2b(30) + 1) + b(123) = 3b(30) + 1` `(3)`
Подставляя `(2)`и `(3)` в `(1)` получим:
`b(1997) = (4b(30) + 2) + (3b(30) + 1) = 7b(30) + 3`
`b(30) = b(15) + b(14) = 1 + b(14) = 1 + b(7) + b(6) = 2 + b(6) = 2 + b(3) + b(2) = 3 + b(2) = 5`
Отсюда получим `b(1997) = 7 x 5 + 3 = 38`.

Автор:  alex123 [ 22 мар 2015, 22:22 ]
Заголовок сообщения:  Re: Натуральное число

OlG писал(а):
alex123 писал(а):
Нет, 38.


Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается
(недолгим перебором) еще 37 вариантов представления.


Так предъявите? И докажите, что 39-го варианта нет. :)

Автор:  OlG [ 22 мар 2015, 22:46 ]
Заголовок сообщения:  Re: Натуральное число

alex123 писал(а):
OlG писал(а):
alex123 писал(а):
Нет, 38.


Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается
(недолгим перебором) еще 37 вариантов представления.


Так предъявите? И докажите, что 39-го варианта нет. :)


`11111001101`

`11111001021`

`11111000221`

`11110201101`

`11110201021`

`11110200221`

`11110121101`

`11110121021`

`11110120221`

`11110112221...`

`02222112221`.

Автор:  alex123 [ 22 мар 2015, 23:04 ]
Заголовок сообщения:  Re: Натуральное число

OlG писал(а):

`11111001101`

`11111001021`

`11111000221`

`11110201101`

`11110201021`

`11110200221`

`11110121101`

`11110121021`

`11110120221`

`11110112221...`

`02222112221`.


Тут пока явно меньше, чем 38 :)

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/