Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Олимпиады




 Страница 1 из 2 [ Сообщений: 19 ] На страницу 1, 2  След.



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

Зарегистрирован: 20 дек 2013, 17:51
Сообщений: 118
Откуда: Занзибар
Подскажите пожалуйста идею решения этой задачи:
Пусть `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)`.
Спасибо заранее!


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 16:29 
Не в сети

Зарегистрирован: 17 дек 2010, 20:02
Сообщений: 1678
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` (таких вариантов достаточно много).


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 17:02 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
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 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы.
А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея.


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 18:33 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 6791
Откуда: Москва
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`.

_________________
Никуда не тороплюсь!


Последний раз редактировалось OlG 22 мар 2015, 18:38, всего редактировалось 1 раз.

Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 18:36 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
OlG писал(а):
`b(1997)=871`.


Нет, 38.


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 20:19 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 6791
Откуда: Москва
alex123 писал(а):
Нет, 38.


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

_________________
Никуда не тороплюсь!


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 21:35 
Не в сети

Зарегистрирован: 20 дек 2013, 17:51
Сообщений: 118
Откуда: Занзибар
Спасибо всем откликнувшимся! Ниже привожу решение этой задачи. Хотел найти более простую решение задачи с помощью посетителей форума.
Принимая во внимание какое значение может получить `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`.


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 22:22 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
OlG писал(а):
alex123 писал(а):
Нет, 38.


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


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


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 22:46 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 6791
Откуда: Москва
alex123 писал(а):
OlG писал(а):
alex123 писал(а):
Нет, 38.


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


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


`11111001101`

`11111001021`

`11111000221`

`11110201101`

`11110201021`

`11110200221`

`11110121101`

`11110121021`

`11110120221`

`11110112221...`

`02222112221`.

_________________
Никуда не тороплюсь!


Вернуться наверх 
 Заголовок сообщения: Re: Натуральное число
 Сообщение Добавлено: 22 мар 2015, 23:04 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
OlG писал(а):

`11111001101`

`11111001021`

`11111000221`

`11110201101`

`11110201021`

`11110200221`

`11110121101`

`11110121021`

`11110120221`

`11110112221...`

`02222112221`.


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


Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 1 из 2 [ Сообщений: 19 ] На страницу 1, 2  След.





Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: