Задача про функцию

[codeineDreaming]

Добрый вечер. Наткнулся на следующую задачу :
Существует ли такая функция, определенная на множестве натуральных чисел и принимающая значения в множестве натуральных чисел (что очень важно), что для любого натурального $x$ выполнено $f(f(x)) = x^2$
У меня нет никакого опыта в решении подобных задач и мне бы хотелось разобраться.
Первая и единственная функция, что пришла в мою голову - $ f(x) = x^\sqrt{2}$ , но она не подходит под условие насчёт того, что должна принимать значения только в множестве натуральных чисел. И как-бы становится интуитивно понятно, что функции-то такой в принципе и не существует, но надо же обосновать, а вот это я уже не понимаю, как тут сделать. Подскажите пожалуйста!

[Pphantom]

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

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

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

[Pphantom]

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

[EUgeneUS]

codeineDreaming
эта функция строится несложно.
Натуральные числа удобно вычеркивать, а потом доказать, что вычеркнули все, но ровно один раз.

Пусть $f(1)=1$, вычеркнули $1$
Требуется $f(f(2)) = 4$, вычеркнули $2$ и $4$
По той же причине, вычеркнули все числа вида $2^{2^n}$

Пусть $f(2)=a$ (а значит $f(a)=4$)
Вопрос: какое число удобно считать за $a$? То есть какое число удобно вычернуть следующим?

[codeineDreaming]

EUgeneUS в сообщении #1542948 писал(а):

codeineDreaming
эта функция строится несложно.
Натуральные числа удобно вычеркивать, а потом доказать, что вычеркнули все, но ровно один раз.

Пусть $f(1)=1$, вычеркнули $1$
Требуется $f(f(2)) = 4$, вычеркнули $2$ и $4$
По той же причине, вычеркнули все числа вида $2^{2^n}$

Пусть $f(2)=a$ (а значит $f(a)=4$)
Вопрос: какое число удобно считать за $a$? То есть какое число удобно вычернуть следующим?

Я, наверное, немного не уловил ход ваших мыслей, но мне почему-то хотелось бы вычеркнуть $3$, а вместе с ней заодно все числа вида $3^{2^n}$.
Я сейчас объясню то, как я понял, а вы меня поправьте если что пожалуйста.
То есть мы удалим $3, 9, 81, 81^2$ и так далее.
Если дальше удалять, нам всяко придется отдельно смотреть числа, которые не являются квадратом какого-то другого числа, например $26$ мы никак не вычеркнем, не принимая $a$ за $26$. Аналогично придется обращаться к нечетным степеням двойки, тройки, потому что мы их не вычеркнули в прошлых ходах, так что, исходя из этого, я не очень понимаю, как тут поступить разумнее и что удобнее вычеркивать
Хотя я, по всей видимости, просто вас неправильно понял, исправьте меня пожалуйста

[EUgeneUS]

codeineDreaming в сообщении #1542956 писал(а):

Я, наверное, немного не уловил ход ваших мыслей, но мне почему-то хотелось бы вычеркнуть $3$, а вместе с ней заодно все числа вида $3^{2^n}$.

Все вы верно уловили. Обратите внимание, мы вычеркиваем те числа, для которых определили значение функции.

codeineDreaming в сообщении #1542956 писал(а):

я не очень понимаю, как тут поступить разумнее и что удобнее вычеркивать

Разумнее продолжить действовать точно также - на i-ом шаге выбрать два минимальных числа $a_i$ и $b_i$ , которые еще не вычернули на предыдущи шагах. Положить $f(a_i) = b_i$ и вычеркнуть эти два числа и два порожденных ряда полных квадратов.

Какие у нас минимальные не вычеркнутые числа сейчас?

[lel0lel]

$f(x^2)=f(x)^2$ квадраты должны преобразовываться в квадраты

[mihaild]

lel0lel в сообщении #1542959 писал(а):

квадраты должны преобразовываться в квадраты

Да, но это надо доказать.

lel0lel в сообщении #1542959 писал(а):

$f(x^2)=f(x)^2$

Нет, почему бы так было?UPD: бред написал.

[lel0lel]

mihaild в сообщении #1542960 писал(а):

почему бы так было?

$f(f(f(x)))=f(x^2)$

[codeineDreaming]

EUgeneUS в сообщении #1542958 писал(а):

codeineDreaming в сообщении #1542956 писал(а):

Я, наверное, немного не уловил ход ваших мыслей, но мне почему-то хотелось бы вычеркнуть $3$, а вместе с ней заодно все числа вида $3^{2^n}$.

Все вы верно уловили. Обратите внимание, мы вычеркиваем те числа, для которых определили значение функции.

codeineDreaming в сообщении #1542956 писал(а):

я не очень понимаю, как тут поступить разумнее и что удобнее вычеркивать

Разумнее продолжить действовать точно также - на i-ом шаге выбрать два минимальных числа $a_i$ и $b_i$ , которые еще не вычернули на предыдущи шагах. Положить $f(a_i) = b_i$ и вычеркнуть эти два числа и два порожденных ряда полных квадратов.

Какие у нас минимальные не вычеркнутые числа сейчас?

А, замечательно.
Получается, после удаления тройки за $a_i$ принимаем $5$, за $b_i$ соответственно принимаем $25$

[EUgeneUS]

lel0lel в сообщении #1542959 писал(а):

квадраты должны преобразовываться в квадраты

да, но в квадраты какого-то другого числа.
Выше уже построили цепочку:
$2 \to 3 \to 4 \to 9 \to 16 \to 81 \to 256 ...$
ТС осталось понять, как строить такие цепочки, чтобы покрыть все натуральные числа, и кое-что доказать потом.

-- 14.12.2021, 22:41 --

codeineDreaming в сообщении #1542962 писал(а):

А, замечательно.
Получается, после удаления тройки за $a_i$ принимаем $5$, за $b_i$ соответственно принимаем $25$

нет же
$25$ это $f(f(5))$
а вот что выберем за $f(5)$?

[codeineDreaming]

EUgeneUS в сообщении #1542963 писал(а):

и кое-что доказать потом.

Вы имеете в виду, что надо будет доказать, что, вычеркивая условно $2$ со всеми ей сопутствующими числами, мы никак не попадём на серию для $8$?

EUgeneUS в сообщении #1542963 писал(а):

а вот что выберем за $f(5)$?

Разве не $5$?

[lel0lel]

EUgeneUS в сообщении #1542963 писал(а):

да, но в квадраты какого-то другого числа

Функция биективна

[EUgeneUS]

codeineDreaming в сообщении #1542964 писал(а):

Вы имеете в виду, что надо будет доказать, что, вычеркивая условно $2$ со всеми ей сопутствующими числами, мы никак не попадём на серию для $8$?

да.

Но Вы пока с построением путаетесь.

codeineDreaming в сообщении #1542964 писал(а):

EUgeneUS в сообщении #1542963

писал(а):
а вот что выберем за $f(5)$?

Разве не $5$?

Если $f(5)=5$, тогда мы зациклились, и $f(f(5)) =5$, а не $25$, как требуется.
Какое минимальное число не вычеркнуто, после вычеркивания пятерки?

[codeineDreaming]

EUgeneUS в сообщении #1542966 писал(а):

Если $f(5)=5$, тогда мы зациклились, и $f(f(5)) =5$, а не $25$, как требуется.

я понял свою ошибку, да
еще я понял, что рассуждал в терминах "вычеркивания" и не уловил вот эту мысль

EUgeneUS в сообщении #1542948 писал(а):

Пусть $f(2)=a$ (а значит $f(a)=4$)
Вопрос: какое число удобно считать за $a$? То есть какое число удобно вычернуть следующим?

а именно : как понять, что надо принять за $a$? или за $a$ надо принимать буквально (для пяти) $f(5)$?

EUgeneUS в сообщении #1542966 писал(а):

Какое минимальное число не вычеркнуто, после вычеркивания пятерки?

$6,7,8,10,11,12,13,14,15,17$ и так далее, каждое придется вычеркивать отдельно со всеми сопутствующими им сериями.