|
$%P(x)$%-хороший многочлен, если все его коэффициенты равны 0,1,2 или 3. Для данного $%n\in\mathbb{N}$% найти число хороших многочленов, таких, что $%P(2)=n$%. задан 7 Окт '12 14:44 
dmg3 |
|
Пусть $%\{с_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 
chameleon $%b$% может быть равно 0, так что $%[\frac{n}{2}]+1$%, а в остальном верно
(7 Окт '12 17:07)
dmg3
исправил в ответе
(7 Окт '12 17:12)
chameleon
|