Finding f(0) When f(f(x))=x^2-x+1

[ozheredov]

Есть некая функция $f(x)$, при этом известно, что $f(f(x))=x^2-x+1$. Требуется найти $f(0)$.

Официально предлагаемое решение:

Let $f(0) = a$ and $f(1) = b$.
Then $f(f(0)) = f(a)$.
But $f(f(0)) = 1$. So $f(a) = 1. (1)$
Also $f(f(1)) = f(b)$.
But $f(f(1)) = 1$. So $f(b) = 1. (2)$
From (1), $f(f(a)) = f(1)$.
But $f(f(a)) = a^2 - a + 1$. So $a^2 - a + 1 = b. (3)$
From (2),$ f(f(b)) = f(1)$, giving $b^2 - b + 1 = b$. So $b = 1$.
Putting $b = 1$ in (3) gives $a = 0$ or $1$.
But $a = 0 ⇒ f(0) = 0 ⇒ f(f(0)) = 0$, contradicting (1).
So $a = 1$, i.e. $f(0) = 1$.

Вопрос: как нужно было догадаться, что на первом шаге нужно брать две точки, и почему именно 0 и 1?

[Lia]

Просьба постановку задачи и все, что не удовлетворяет, изобразить здесь в письменном виде.
Так, чтобы пользователю пришлось смотреть видео только в крайнем случае, и канва событий восстанавливалась по Вашему запросу.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

См. выше.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[zykov]

Наверно потому что $(x^2-x+1)=x$ даёт только $x=1$ (стационарная точка), а $(x^2-x+1)=1$ даёт $x=0$ и $x=1$.

[B@R5uk]

Было бы интересно найти $f(x)$ при условии, например, что она непрерывна и дифференцируема. Будет ли такое решение единственным? В линейном случае решается:

$$f\left(f\left(x\right)\right)=ax+b$$

$$f\left(x\right)=cx+d$$

$$c=\sqrt{a},\quad d=\frac{b}_{1+\sqrt{a}}$$

Какая функция при подстановке сама в себя даст квадратичный полином — ума не приложу ($(1+x)^\sqrt{2}$ на множители так легко не раскладывается).

[ozheredov]

zykov
А почему нужно рассматривать именно стационарную точку?

-- 05.07.2022, 23:58 --

B@R5uk в сообщении #1559475 писал(а):

Было бы интересно найти $f(x)$ при условии, например, что она непрерывна и дифференцируема

Кстати, да. И еще прикольнее вопрос: если $f(f(x))$ по непрерывности/дифференцируемости лучше некуда (полином), может ли $f(x)$ быть негладкой? А разрывной?

[zykov]

Если точка является стационарной точкой $f(x)$, то она же будет стационарной точкой $f(f(x))$.
Вторая - только 1. Значит если $f(x)$ имеет стационарную точку, то это должна быть 1.

-- 06.07.2022, 00:25 --

B@R5uk в сообщении #1559475 писал(а):

Было бы интересно найти $f(x)$ при условии, например, что она непрерывна и дифференцируема.

Можно сделать замену $y=x-1$, $g(y)=f(1+y)-1$.
Тогда $g(g(y))=y^2+y$ и $g(0)=0$.
Далее методом неопределнных коэффициентов можно положить например $g(y)=c_1 y + c_2 y^2 + c_3 y^3$.
Получим $c_1^2=1$, $c_2 c_1 (1+c_1)=1$, $c_1 (c_1^2 c_3+c_3+2 c_2^2)=0$.
Если этот процесс продолжить (увеличивая порядок от 3 и выше), то можно получит разложение в ряд для $g(y)$.

Пока получается $c_1^2=1$, $c_2 (c_1 + 1)=1$, $c_3+ c_2^2=0$.
Из первого $c_1=\pm 1$, но из второго $c_1 \neq -1$.
Значит $c_1=1$, $c_2=\frac12$, $c_3=-\frac14$, $c_4=\frac14$, $c_5=-\frac{5}{16}$, и т.д.

-- 06.07.2022, 00:46 --

(Оффтоп)

$$y+\frac{{{y}^{2}}}{2}-\frac{{{y}^{3}}}{4}+\frac{{{y}^{4}}}{4}-\frac{5 {{y}^{5}}}{16}+\frac{27 {{y}^{6}}}{64}-\frac{9 {{y}^{7}}}{16}+\frac{171 {{y}^{8}}}{256}-\frac{69 {{y}^{9}}}{128}-\frac{579 {{y}^{10}}}{2048}+$$

$$+\frac{10689 {{y}^{11}}}{4096}-\frac{60261 {{y}^{12}}}{8192}+\frac{116535 {{y}^{13}}}{8192}-\frac{304555 {{y}^{14}}}{16384}+\frac{268707 {{y}^{15}}}{32768}+$$

$$+\frac{7942071 {{y}^{16}}}{262144}-\frac{19570935 {{y}^{17}}}{262144}+\frac{9537731 {{y}^{18}}}{1048576}+\frac{1117836325 {{y}^{19}}}{4194304}-\frac{630737297 {{y}^{20}}}{8388608}-$$

$$-\frac{52310180977 {{y}^{21}}}{16777216}+\frac{618435378229 {{y}^{22}}}{67108864}+\frac{523526983623 {{y}^{23}}}{67108864}-\frac{3672122551119 {{y}^{24}}}{33554432}+\frac{8661572895987 {{y}^{25}}}{67108864}+$$

$$+\frac{1205887924659627 {{y}^{26}}}{1073741824}-\frac{8604836834766111 {{y}^{27}}}{2147483648}-\frac{77855893119175779 {{y}^{28}}}{8589934592}+$$ $$+\frac{361603115910936909 {{y}^{29}}}{4294967296}-\frac{152305703959002777 {{y}^{30}}}{17179869184}-\frac{13663291494961963791 {{y}^{31}}}{8589934592}+$$ $$+\frac{930319681643781465159 {{y}^{32}}}{274877906944}+\frac{7744345260199075453761 {{y}^{33}}}{274877906944}-\frac{74957616592443792206343 {{y}^{34}}}{549755813888}-$$ $$-\frac{237621055201522057591119 {{y}^{35}}}{549755813888}+\frac{19848927534546151309514391 {{y}^{36}}}{4398046511104}+\frac{55865315152940191973506305 {{y}^{37}}}{17592186044416}-$$ $$-\frac{10012538507216110592697218313 {{y}^{38}}}{70368744177664}+\frac{13051600707461268121142637357 {{y}^{39}}}{70368744177664}+$$ $$+\frac{311204897997769328562593792487 {{y}^{40}}}{70368744177664}+...$$

[ozheredov]

zykov
Ок, допустим, $f(x) = x + 1$. Она вообще не имеет стационарных точек. И вот условие задачи: $f(f(x)) = x + 2$, найдите $f(0)$. Или для функций без стационарных точек такая задача имеет множество решений? Но тогда почему об этом ничего не сказано в условии?

[xagiwo]

ozheredov в сообщении #1559477 писал(а):

Кстати, да. И еще прикольнее вопрос: если $f(f(x))$ по непрерывности/дифференцируемости лучше некуда (полином), может ли $f(x)$ быть негладкой? А разрывной?

Может. Пусть мы хотим $f(f(x)) = x$, тогда $f$ можно взять $\mathbb{Q}$-линейной функцией, которая в $1$ равна $1$, а остальные вектора из базиса Гамеля бьёт на пары и меняет местами.
Несложно построить примеры и без аксиомы выбора, есть, например, разрывная в рациональных точках функция $INT$, которую можно найти в книге "Гёдель, Эшер, Бах: эта бесконечная гирлянда" в главе 5, но есть ли она где-то ещё — фиг знает. Вот картинка и ещё картинка, построение функции в книге описано лишь примерно (по картинке и так понятно, хотя для наших целей было бы проще, если бы копии графика, из которых он состоит, были прямыми, а не изогнутыми).

$INT$ продолжается на все вещественные числа по закону $INT(x+n) = INT(x) + n$, то есть $INT$ коммутирует с $g(x) = x+1$. Если положить $f = INT \circ g$ (то есть просто $f(x) = INT(x+1)$), то $f \circ f = INT \circ g \circ INT \circ g = g \circ g \circ INT \circ INT = g \circ g$, то есть $f(f(x)) = g(g(x)) = x+2$, как Вы и просили.

Пусть теперь $g$ — произвольная функция. Если функция $h$ обратима и обладает свойством $h(x+1) = g(h(x))$, то $h \circ INT \circ h^{-1}$ коммутирует с $g$ и работают выкладки выше (получаем странное решение уравнения $f(f(x)) = g(g(x))$). Я не знаю, как часто такая $h$ существует, но, например, если $g(x) = x^2$, можно взять $h(x) = 2^{2^x}$ (она не совсем обратима, правда, но на каком-то куске $\mathbb{R}$ решение будет)

-- 06.07.2022, 08:30 --

А мне всё же интереснее, существует ли функция $f$ из стартового сообщения. То, что она, если вообще существует, может быть плохой, и так понятно.

[zykov]

Похоже, ряд расходится. Посчитал до порядка 60, некоторые коэффициенты сильно подскакивают.
Если это так, то аналитической функции $f(x)$ нет.

А разрывную можно построить. Взять функцию $r(x)=x^2-x+1=(x-\frac12)^2+\frac34$ и из любой точки построить послдеовательность $x_{n+1}=r(x_n)$.
(Похоже кстати на конструкцию для Mandelbrot set для $c=\frac34-\frac12=\frac14$.)
Эту последовательность можно было бы и назад продолжить. Но там неоднозначность из-за квадратного корня. К тому же, там могут пойдти комплексные значения.

Если надо только действительные значени, то $x_0$ можно любой взять, а дальше $x_n \geq \frac34$ (и быстро уходит на бесконечность для точек больше 1, для точек меньше 1 стремится к 1). Если взять две таких последовательности не имеющие общих точек и объеденить их через одну точку, то получим послдеовательность для функции $f(x)$.
Если ограничится областью $x \geq 1$, то $f(x)$ можно наверно получить гладкую. При больших $x$ примерно будет $f(x)\approx x^{\sqrt2}$.
Тут можно и назад продолжать последователньость. Будет сверху к 1 стремится.

[xagiwo]

(Оффтоп)

xagiwo в сообщении #1559496 писал(а):

Если функция $h$ обратима и обладает свойством $h(x+1) = g(h(x))$

Наверное, этот абзац я совершенно зря написал. Подозреваю, что такая $h$ почти никогда не существует.

zykov в сообщении #1559514 писал(а):

Если взять две таких последовательности не имеющие общих точек и объединить их через одну точку, то получим последовательность для функции $f(x)$.

А что это значит? Как всё-таки получается $f(x)$?

P.S. понял: если у вас есть две таких последовательности $x_i$ и $y_i$ то вы берёте $f(x_i) = y_i$ и $f(y_i) = x_{i+1}$, так? Но это определяет $f$ в счётном числе точек, а нужно — во всех. Нужно как-то искать континуум последовательностей без общих точек, покрывающие всё $\mathbb{R}$?

[zykov]

Есть последовательность $a_0, a_1, a_2, ...$ и последовательность $b_0, b_1, b_2, ...$.
Тогда $f(a_n)=b_n$ и $f(b_n)=a_{n+1}$.
И отдельно будет $f(1)=1$.

-- 06.07.2022, 11:51 --

Например $r(2)=3$. Значит любая точка $x_0 \in [2, 3)$ задаёт двухстороннюю последовательность. И любые две такие последовательности из разных точек $x_0$ не имеют общих точек.
Значит все их можно разбить на пары любым способом и определить $f(x)$. Обычно разрывную, но если их правильно упорядочить, то можно и гладкую получить.

[xagiwo]

zykov в сообщении #1559516 писал(а):

Значит все их можно разбить на пары любым способом и определить $f(x)$

О, понял.

zykov в сообщении #1559516 писал(а):

Обычно разрывную, но если их правильно упорядочить, то можно и гладкую получить.

А в этом сомневаюсь. Хотя верю, что можно получить непрерывную.

[zykov]

Получается для гладкого варианта на области $x \geq 1$ такая асимптотика.
На бесконечности $f(x)$ будет как $x^{\sqrt 2}$.
Около 1 можно тот ряд, что я приводил обрезать до любого порядка. Если ограничится $y+\frac{y^2}{2}$, то будет $\frac{x^2+1}{2}$.

-- 06.07.2022, 12:05 --

xagiwo в сообщении #1559520 писал(а):

А в этом сомневаюсь

Почему? На пары то можно любым образом разбить. Это чтобы правильно (для непрерывности) разбить - нужно постараться.