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

[wpoms.]

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

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

Comments

[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):

#include <stdio.h>

int check (int n) {
	int k = n;
	while (k > 0) {
		if (k % 3 == 2) return 0;
		k /= 3;
	}
	return 1;
}

void main () {
	FILE *f;
	fopen_s (&f, "out.txt", "w");
	int count = 0;
	for (int i = 0; i < 2004; i++) {
		count += check (i);
	}
	fprintf_s (f, "%d", count);
}

Вывод:

128