19:27 

Функция целого аргумента

wpoms.
Step by step ...

Пусть `f` - функция из множества неотрицательных целых чисел в себя, такая что для всех `n >= 0` выполняются следующие условия:
(а) `(f(2n + 1))^2 - (f(2n))^2 = 6f(n) + 1`
(б) `f(2n) >= f(n)`.
Какое количество чисел, меньших `2003`, принадлежит множеству функции значений `f`?



@темы: Исследование функций

Комментарии
2013-08-27 в 16:22 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Из (a) следует, что числа `f(2n + 1)` и `f(2n)` имеют разную четность, так как `6f(n) + 1` — нечетное число. Обозначим `k(n) = f(2n + 1) - f(2n)`; очевидно, `k(n) > 0`, в противном случае выполнялось бы `f(2n + 1)^2 - f(2n)^2 = 6f(n) + 1 < 0`, что невозможно, так как `f(n) >= 0`. Так как `f(2n + 1)` и `f(2n)` имеют разную четность, то `k(n)` — нечетное число для всех `n`.
Уравнение (a) преобразуется к виду `(f(2n + 1) - f(2n))*(f(2n + 1) + f(2n)) = 6f(n) + 1`, или `k(n) * (2 f(2n) + k(n)) = 6f(n) + 1 <= 6 f(2n) + 1`. Прибавляя `f(2n)^2` к обеим частям неравенства, получим `(f(2n) + k(n))^2 <= f(2n)^2 + 6f(n) + 1 = (f(2n) + 3)^2 - 8 < (f(2n) + 3)^2`, откуда `k(n) < 3` для всех `n`, и, в силу нечетности, `k(n) \equiv 1`.
Следовательно, `f(2n + 1) = f(2n) + 1`, и `2 f(2n) + 1 = 6 f(n) + 1 <=> f(2n) = 3*f(n)`. Для `n = 0` получаем `f(0) = 3 f(0)` и `f(0) = 0`. Тогда `f(1) = 1`.

Пусть число `n` имеет в двоичной записи вид `\bar(a_1 a_2 a_3 ... a_k)_2`, `a_i \in {0,\ 1}`. Тогда число `f(n) = \bar(a_1 a_2 a_3 ... a_k)_3`.
Доказательство.
Очевидно, `0 = 0_2,\ f(0) = 0_3` и `1 = 1_2,\ f(1) = 1_3`. Предположим, что для всех `m < n` выполняется `f(m) = f (\bar(a_1 a_2 a_3 ... a_k)_2) = \bar(a_1 a_2 a_3 ... a_k)_3`, где `\bar(a_1 a_2 a_3 ... a_k)_2` — двоичное представление `m`; пусть `n = \bar(a_1 a_2 a_3 ... a_s)_2`. Тогда, если `n` четно, то `a_s = 0` и `f(n) = f(\bar(a_1 a_2 a_3 ... a_{s - 1} 0)_2) = 3 * f(\bar(a_1 a_2 a_3 ... a_{s - 1})_2) = 3 * \bar(a_1 a_2 a_3 ... a_{s - 1})_3 = \bar(a_1 a_2 a_3 ... a_{s - 1} 0)_3`; если `n` нечетно, то `a_s = 1` и `f(n) = f(\bar(a_1 a_2 a_3 ... a_{s - 1} 0)_2 + 1) = 3 * f(\bar(a_1 a_2 a_3 ... a_{s - 1})_2) + 1 = 3 * \bar(a_1 a_2 a_3 ... a_{s - 1})_3 + 1 = \bar(a_1 a_2 a_3 ... a_{s - 1} 1)_3`. По теореме о полной индукции, для всех `n = \bar(a_1 a_2 a_3 ... a_k)_2`, `f(n) = \bar(a_1 a_2 a_3 ... a_k)_3`.

С другой стороны, очевидно, что если `k = \bar(a_1 a_2 a_3 ... a_k)_3`, где `a_i \in {0,\ 1}`, то существует единственное `m` такое, что `f(m) = k`; следовательно, область значений функции `f` есть все числа, в троичной записи которых не встречаются цифры `2`.

Считать, сколько их, лениво, так что полный перебор (VS C++ 2012, /Ox):

Вывод:

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная