$%P(x)$%-хороший многочлен, если все его коэффициенты равны 0,1,2 или 3. Для данного $%n\in\mathbb{N}$% найти число хороших многочленов, таких, что $%P(2)=n$%.

задан 7 Окт '12 14:44

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

Пусть $%\{с_n\}$% - последовательность коэффициентов одного из искомых многочленов. Тогда строки $%...,c_{2i},...,c_4,c_2,c_0$% и $%...,c_{2i+1},...,c_5,c_3,c_1$% будут являться записью неких чисел $%a$% и $%b$% (соответственно) в четверичной системе счисления. Нетрудно заметить, что $%n=a+2b$%. Значит, число удовлетворяющих условию многочленов равно количеству целочисленных неотрицательных пар $%\{a,b\}:n=a+2b,a\leq n,b\leq n$%. Из-за однозначной зависимости $%a$% от $%b$% и $%n$% это число будет равняться количеству $%b:2b\leq n$%. Ответ: $%\left[\frac n 2\right]+1$%.

ссылка

отвечен 7 Окт '12 15:41

изменен 7 Окт '12 17:12

$%b$% может быть равно 0, так что $%[\frac{n}{2}]+1$%, а в остальном верно

(7 Окт '12 17:07) dmg3

исправил в ответе

(7 Окт '12 17:12) chameleon
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,005
×315

задан
7 Окт '12 14:44

показан
813 раз

обновлен
7 Окт '12 17:12

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

по почте:

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

по RSS:

Ответы

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

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