Доказать, что не существует функции...

[Xenia1996]

Доказать, что не существует функции $f$ из множества всех натуральных чисел в него же, такой, что $f(f(n)) = 2n$ для любого n.

Мне как раз показалось, что я нашла именно такую функцию. Не могу понять, где я ошиблась.

Предположим, что $n$ - натуральное число, а $A$ - наибольший нечётный делитель числа $n$.
Тогда искомая функция выглядит следующим образом:

$f(n) = n(A+2)/A$, если $A$ даёт остаток 1 при делении на 4, и $f(n) = 2*n*(A-2)/(A)$ в противном случае.

[TOTAL]

Xenia1996 в сообщении #358238 писал(а):

Не могу понять, где я ошиблась.

Надо проверять формулу, скажем, для $n$ из первой сотни.

[Day]

Не поленился, взял $n=10$
$A=5$, применяем 1-ю формулу
$f(10) = 10*7/5 = 14$
$f(14) - A = 7$, 2-я формула
$f(f(10)) = f(14) = 2*14*7 / 9$ - вообще не целое, целая часть = 21

[Xenia1996]

TOTAL в сообщении #358243 писал(а):

Xenia1996 в сообщении #358238 писал(а):

Не могу понять, где я ошиблась.

Надо проверять формулу, скажем, для $n$ из первой сотни.

В уме проверила, вроде работает. На компе не умею, так как имею сильный перекос: умею решать некоторые олимпиадные задачи по математике, но вот информатикой не владею абсолютно (вершиной моих умений в информатике является прога на С, вычисляющая ацерет). И, положа (или положив?) руку на сердце, могу сказать, что презираю технику.

-- Сб окт 02, 2010 11:52:41 --

Day в сообщении #358245 писал(а):

Не поленился, взял n=10
A=5, применяем 1-ю формулу
f(10) = 10*7/5 = 14
f(14) - A = 7, 2-я формула
f(f(10)) = f(14) = 2*14*7 / 9 - вообще не целое, цеая часть = 21

Пардон, там минус, а не плюс.

-- Сб окт 02, 2010 11:56:18 --

Исправила

[Day]

Кажется, пока я хлопал ушами, 2-я формула изменилась ?

[Руст]

Решение правильное. Лучше найти общее решение. Для каждого четного числа $2n$ существует $m=f(n)$, что выполняется $f(m)=2n$. Следовательно $f(2n)=f(f(m))=2m=2f(n)\to f(2^kn)=2^kf(n)$.
Тем самым $f$ определяется своими значениями на подмножестве нечетных чисел.
Обозначим через $O$ множество нечетных натуральных чисел, образ которых так же нечетный. Обозначим через $E$ образы $f(O)$. Тогда их пересечение пусто (иначе образ f(f(a)) опять нечетное для некоторого а) и объединение составляет все множество нечетных чисел (иначе некоторое четное число не имеет образа). Обозначим через $g:E\to O$ отображение $g(a)=\frac{f(a)}{2},a\in O$.
Из вышеприведенного следует, что $f,g$ взаимно обратные отображения. При этом любое взаимно однозначное отображение части нечетных чисел $f$ в дополнение $E$ до всех нечетных чисел доопределяется до функции $f$ удовлетворяющей указанному свойству.
$f(2^ka)=2^kf(a),f(2^kb)=2^{k+1}g(b),a\in O,b\in E$.
Таким образом таких функций имеется континиум.