equation

[man111]

If $f:\mathbb{N}\rightarrow \mathbb{N}$ and $f(f(x)) = 3x$. Then $f(2014) = $

[gris]

Рискну предположить, что $f(2014)=2015$
$f(2013)=6030$
$f(2012)=2515$

Впрочем, подойдёт и $f(2014)=6045$ и $f(2014)=1$

Тю, да тут очень много чисел может быть. Но не все.
Правда, у меня получается не биекция.

[Руст]

Если не говорится, что f должна быть биекцией (взаимно обратным отображением), то решений бесконечно много.
Биекцией является только такая функция.
Представим $n$ в троичной системе исчисления
$n=\sum_j a_{i_j}3^{k_j}, a_{i,j}\not =0$ и определим значение

$$f(n)=\sum_j (a_{i_j}-(-1)^{a_{i_j}})3^{k_j+\theta_j}, \theta_j=2-a_{i_j}.$$

[Deggial]

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

[gris]

Я чего-то не уразумею
Если существует биекция, то у каждого числа есть один прообраз. Какой прообраз может быть у прообраза числа $1$?

[Руст]

gris в сообщении #849680 писал(а):

Я чего-то не уразумею
Если существует биекция, то у каждого числа есть один прообраз. Какой прообраз может быть у прообраза числа $1$?

Согласно формуле 2.

[gris]

Я имею в виду, что если $\exists n: f(n)=1;\, \exists m: f(m)=n \Rightarrow f(f(m))=3m=1$, что не имеет решения в натуральных числах. Или я что-то не то говорю?

[Руст]

Вы правы, если число не делится на 3, то у него не может быть двойного прообраза.
Я строил так, чтобы у 1 был прообраз 2. Соответственно у числа 2 нет прообраза. Т.е., то, что я строил не является биекцией.
Но без дополнительного условия решение не единственно. Возможно надо требовать условие монотонности.

[gris]

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

$(1\to 3 \to 9 \to 27 \to ...) + (2\to 6 \to 18 \to 54 \to ...) =(1\to 2 \to 3 \to 6 \to 9 \to 18 \to...)$

$(5\to 15 \to 45 \to 135 \to ...) + (4\to 12 \to 36 \to 108 \to ...) =(5\to 4 \to 15 \to 12 \to 45 \to 36 \to...)$

При попарном объединении всех прогрессий получается функция, удовлетворяющая условиям. Мне кажется, что у Вас нечто подобное?
Конечно, в каждом конкретном случае все числа не кратные трём не имеют "второго прообраза", а "половина" из них и первого.

[Руст]

gris в сообщении #849758 писал(а):

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

Делящееся на 3 число $3m$ всегда имеет два прообраза.
Монотонность делает решение единственной. Достаточно слегка модернизировать

$$f:n=\sum_j a_{i_j}3^{k_j}\to \sum_j b_{i_j} 3^{k_{i_j}+a_{i_j}-1}, b_{i_j}=a_{i_j}*2^{(-1)^{a_{i_j}+1}}.$$

[gris]

Смотрю на Вашу формулу и цепенею от восторга, но приложить её к размышлениям не в силах.
Да, требование монотонности и прогрессии цепко держат функцию.
$1285\to2014\to3855$

[Руст]

Я хотел записать краткой формулой.
Очевидно, что отображение инъективно и $f(x)\not =x$.
Допустим, что f монотонно. Тогда при всех х $f(x)>x$ (иначе нарушается монотонность) и $f(1)=a,f(a)=3\to a=2.$
Таким образом однозначно определили $f(1)=2,f(2)=3\to f(3)=f(f(2))=6$.
Следовательно $f(6)=f(f(3))=9$ и $6=f(3)<f(4)<f(5)<f(6)=9\to f(4)=7,f(5)=8$.
Далее $f(7)=f(f(4))=12,f(8)=f(f(5))=15,f(9)=f(f(6))=18$.
Пусть монотонная функция определена при всех $n\le 3^k$.
Тогда по индукции $f(3^k)=f(f(2*3^{k-1}))=2*3^k,f(2*3^k)=3^{k+1}$.
По индукции $f(3^k+x), 0<x<3^k$ определится однозначно из соображений монотонности
как $f(3^k+x)=2*3^k+f(x)<3^{k+1}.$
Так как количество таких х равно количеству возможных значений у между $2*3^k$ и $3^{k+1}$, отображение в этом интервале биективно
и для нахождения $f(y), 2*3^k<y<3^{k+1}$ достаточно найти прообраз и выразить $f(y)=f(f(f^{(-1)}(y)))=3f^{(-1)}(y)=3x,f(x)=y$.
Таким образом монотонность однозначно определяет значение функции. Вычисление значения определяется представлением числа в троичной системе исчисления.

[gris]

А я просто начал строить функцию в надежде, что подальше от начала наступит достаточное разряжение в области значений, и можно будет в определённых границах произвольно задавать некоторые значения. Но дойдя до $f(81)$ увидел, что не тут-то было. Функция выстраивается так, что никакого произвола не позволяет.
<Интересно, а условие $f(f(n))=4n$ допускает неоднозначность монотонной функции?>
Далее, рассуждая по-школьному, можно выделить два типа линейных участков и определить, на каком из них лежит искомое значение.

Спасибо за пояснения!

[Руст]

Для этого случая нет однозначности. Однозначно определяются только значения $f(2^k)=2^{k+1}$.