Найдите, пожалуйста, ошибки в моём решении.

[Busy_Beaver]

На Международной Математической Олимпиаде 1987-го года (порядковый номер олимпиады - 28) предлагалась следующая задача:
Докажите, что не существует функции f (из множества всех целых неотрицательных чисел во множество всех целых неотрицательных чисел) такой, что f(f(n)) = n + 1987 для любого n, принадлежащего множеству всех целых неотрицательных чисел.

Вот моё решение:
Назовём число x красным, если x и f(x) имеют разную чётность.
Назовём число x синим, если x и f(x) имеют одинаковую чётность.
Если x - красное, то f(x) обязано быть синим. В противном случае f(f(x))=x+1987 будет иметь ту же чётность, что и x.
Аналогично, если x - синее, то f(x) обязано быть красным.

Из предыдущего следует, что x+1987=f(f(x)) должно иметь тот же цвет, что и само х, а это значит, что остаток, который даёт число x при делении на 1987, однозначно задаёт цвет этого числа.

Если f(x) даёт остаток a при делении на 1987, то и f(x+1987) даёт остаток a, так как f(f(f(x)))=f(x)+1987. Таким образом, для всех x, дающих остаток a при делении на 1987, f(x) будет давать один и тот же остаток b.

Установим взаимно однозначное соответствие между "красными" и "синими" остатками.
Каждому "красному" остатку a, получаемому при делении некоторого x на 1987, поставим в соответствие "синий" остаток b, получаемый при делении f(x) на 1987, так как x и f(x) имеют разный цвет.
Каждому "синему" остатку b, получаемому при делении некоторого f(x) на 1987, поставим в соответствие "красный" остаток a, получаемый при делении x на 1987, так как x и f(x) имеют разный цвет.
Таким образом, "красных" и "синих" остатков - поровну, но это невозможно, так как всего имеется 1987 (нечетное число) остатков.
Мы пришли к противоречию, значит, функции, указанной в условии задачи, не существует.
============================================================

Простите, что получилось размыто и отягощённо.

[Dandan]

Busy_Beaver в сообщении #345173 писал(а):

Каждому "синему" остатку b, получаемому при делении некоторого f(x) на 1987, поставим в соответствие "красный" остаток a, получаемый при делении x на 1987, так как x и f(x) имеют разный цвет.

а с чего вы взяли, что каждый синий остаток представим в виде f(x)%1987 ? Вы неявно предполагаете, что функция f - обратима, т.е. существует $x = f^{-1}(y)$ для любого y. Среди f(0), ..., f(1986), вообще говоря, может быть меньше чем 1987 различных остатков.

[Busy_Beaver]

Спасибо за замеченную ошибку. Я так и чувствовал, что что-то не так (простите за каламбур).
Видимо, не каждому дано быть математиком. Ладно, буду писать стихи

[Dandan]

ну вы зря расстраиваетесь, вы близки к решению (хоть и наплодили лишних понятий). А на счет "не дано быть математиком" - я вас уверяю, чтобы побеждать на олимпиадах нужно долго и упорно тренироваться, независимо от того, сколько у вас "талантов" к этому (собсно это касается любого вида деятельности).

[Busy_Beaver]

Тренироваться необходимо простым смертным (таким, как я, и, может быть, Вы), а вот такие гении, как Рамануджан, Фон-Нойман, Нэш, Мандельброт и т.п., без всякой тренировки создавали математические шедевры. К слову сказать, и тут есть исключения. Колмогоров, Гильберт, Лобачевский, Перельман, Тао и т.п. трудились в поте лица во имя получения результата (что вовсе не умаляет их гениальности).

[mihiv]

Dandan в сообщении #345222 писал(а):

Вы неявно предполагаете, что функция f - обратима, т.е. существует $x = f^{-1}(y)$ для любого y.

Функция $f$ действительно обратима,т.к. из $f(x)=f(y)$ следует $f(f(x))=f(f(y))\to x+1987=y+1987,x=y$

[Dandan]

верно, но автор топика этого не заметил и не указал. Я это и имел ввиду, когда говорил, что он близок к решению. На олимпиаде без этого записанного факта поставили бы максимум 3из7 баллов.

[TOTAL]

Dandan в сообщении #345222 писал(а):

Вы неявно предполагаете, что функция f - обратима, т.е. существует $x = f^{-1}(y)$ для любого y.

Во-первых, он перешел к остаткам. Во-вторых, он предполагает, что для любого $y$ существует $x = f(y)$ (т.к. он показал, что $x=f(f(x))$). Так что этот случай больше похож не на ошибку решающего, а на придирку проверяющего.