One Nice Solution: Let $N$ be the set of non-negative integers. Put $A = N - f(N)$ (the set of all $n$ such that we cannot find $m$ with $f(m) = n$). Put $B = f(A)$. Note that $f$ is injective because if $f(n) = f(m)$, then $f(f(n)) = f(f(m))$ so $m = n$. We claim that $B = f(N) - f(f(N))$. Obviously $B$ is a subset of $f(N)$ and if $k$ belongs to $B$, then it does not belong to $f(f(N))$ since $f$ is injective. Similarly, a member of $f(f(N))$ cannot belong to $B$. Clearly $A$ and $B$ are disjoint. They have union $N - f(f(N))$ which is ${0, 1, 2, ... , 1986}$. But since $f$ is injective they have the same number of elements, which is impossible since ${0, 1, ... , 1986}$ has an odd number of elements.

Solved for the more general case: http://www.mathlinks.ro/Forum/viewtopic.php?highlight=1987&t=2749

what if you: Take the derivative of $ f(f(n))$ which is one and therefore derivative of $ f(n)$ is also 1, which means $ f$ is a linear function, and since f must have integer coefficients in the form of $ an+b$, plug it in $ f(f(n))$ and see that b cannot be integer, a contradiction.

$ f: \set{N^*} \to \set{N^*}$ $ f'(x)=?$ :

You can't differentiate this function. That would be $ \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}$, and the concept of a limit doesn't make sense on the natural numbers or any other discrete set.

Define $a(n)=f(n)-n$. Then, from $f(f(n))=n+1987$ we get $(f(f(n))-f(n))+(f(n)-n)=1987$, or $a(f(n))+a(n)=1987$ for every $n$ natural. If we replace $n$ by $f(n)$ in $a(f(n))+a(n)=1987$, we get $a(f(f(n)))+a(f(n))=1987=a(f(n))+a(n)$, and then $a(n+1987)=a(n)$ for every natural $n$. Thus, $a$ is an 1987-periodic funcion. Now, let $a_1=a(1), a_2=a(2),...,a_{1987}=a(1987)$ be the 1987 possible values of $a(n)$ (Since $a$ is periodic, this is possible). We must pair the 1987 $a_i$ in the following mannner: $a_i$ is paired with $a_j$ if $a_i +a_j =1987$ (we can always do this, because $a(f(n))+a(n)=1987$ for every $n$ natural). If there's two or more $j$ satisfying the pairment, anyone serve. So, we can divide 1987 numbers in pairs, and this is a contradiction, because 1987 is odd. Finally, the problem is solved.

$f(x)$must be one-to-one.$f(f(n))=n+1987$so $f(f(n))$ will miss 1987 values. suppose that $f(n)$ miss exactly $k$ distinct values $c_1,c_2,...,c_k$so $f(f(n))$will miss $c_1,c_2,...,c_k,f(c_1),f(c_2),....,f(c_k)$so if $f(m)=w$so $w\ne f(c_1),f(c_2),....,f(c_k),m\ne c_1,c_2,...,c_k$so there is $n$ such that $f(n)=m$ hence $f(f(n))=w$so $f(f(n))$ misses $2k$ values. so it's contradiction.

Wrong solution thanx pco for ur help

varun.tinkle wrote: Assuming that a function exsists.... suppouse.... the function is $ ax+b $ ... Similarly we can check for higher degrees of equation........ But .... you cant check ALL the possible functions to achieve the result! And what's the meaning of "degrees of equation" ? What is the degree of the function $f(n)=1+\left\lfloor e^{175\sin(n)}\right\rfloor$ ? Dont forget that there exists infinitely many non polynomial functions

good solution

build a $Z_{1987}$ -> $Z_{1987}$ function

i can't find pco's solution who can help me? varun.tinkle wrote: Wrong solution thanx pco for ur help

I'm interested to know what is the number of function which verified $f(f(x))=x+k$ where k is even.

darkeagle wrote: I'm interested to know what is the number of function which verified $f(f(x))=x+k$ where k is even. I suppose you mean "functions from $\mathbb N\to\mathbb N$" If so, just look at the general solution and count. You'll find $\frac{k!}{\frac k2!}$

$f(\cdot)$ is clearly injective. Let $I\subseteq [1986]\triangleq \{0,1,2,\dots,1986\}$ be a set, such that, $i\in I\iff f(i)<1987$; and $I^c$ be the complement of $I$, with respect to $[1986]$.Clearly, since, $f(f(i))=i+1987 \geq 1987$, we get, $i\in I \implies f(i)\in I^c$.Since, $f(\cdot)$ is an injection, we must have, $|I|\leq |I^c|$. Next, take an $i\in I^c$, and let, $f(i)=1987k+\ell$, where, $0\leq \ell <1987$. Using, $f(f(\ell))=\ell+1987$, with $f(\ell)$, in place of $\ell$, we have, $f(\ell+1987)=f(\ell)+1987$, and thus, via induction, $f(\ell+1987k)=f(\ell)+1987k$. Hence, $$ f(f(i))=f(1987k+\ell)=1987k+f(\ell)=i+1987 \implies f(\ell)+1987(k-1)=i. $$Since, $i<1987$, the only possibility, is to have, $k=1$, and, $f(\ell)=i$. Therefore, if, $i\in I^c$, then, $f(i)=1987+\ell$, where, $f(\ell)=i$. In particular, $\ell = f(i)-1987 \in I$; therefore, $i\in I^c \implies f(i)-1987 \in I$. Clearly, $t\mapsto f(t)-1987$ is also injective, and therefore, $|I^c|\leq |I|$. Combining this with what was previously obtained, we get, $|I|=|I^c|$; while, $I\cap I^c=\emptyset$, and, $I\cup I^c=[1986]$, and since, $[1986]$ has odd cardinality, this is impossible.

A generalization is here ($\mathbb N \to \mathbb N$) and here ($\mathbb Z \to \mathbb Z$).

grupyorum wrote: $f(\cdot)$ is clearly injective. Let $I\subseteq [1986]\triangleq \{0,1,2,\dots,1986\}$ be a set, such that, $i\in I\iff f(i)<1987$; and $I^c$ be the complement of $I$, with respect to $[1986]$.Clearly, since, $f(f(i))=i+1987 \geq 1987$, we get, $i\in I \implies f(i)\in I^c$.Since, $f(\cdot)$ is an injection, we must have, $|I|\leq |I^c|$. Next, take an $i\in I^c$, and let, $f(i)=1987k+\ell$, where, $0\leq \ell <1987$. Using, $f(f(\ell))=\ell+1987$, with $f(\ell)$, in place of $\ell$, we have, $f(\ell+1987)=f(\ell)+1987$, and thus, via induction, $f(\ell+1987k)=f(\ell)+1987k$. Hence, $$ f(f(i))=f(1987k+\ell)=1987k+f(\ell)=i+1987 \implies f(\ell)+1987(k-1)=i. $$Since, $i<1987$, the only possibility, is to have, $k=1$, and, $f(\ell)=i$. Therefore, if, $i\in I^c$, then, $f(i)=1987+\ell$, where, $f(\ell)=i$. In particular, $\ell = f(i)-1987 \in I$; therefore, $i\in I^c \implies f(i)-1987 \in I$. Clearly, $t\mapsto f(t)-1987$ is also injective, and therefore, $|I^c|\leq |I|$. Combining this with what was previously obtained, we get, $|I|=|I^c|$; while, $I\cap I^c=\emptyset$, and, $I\cup I^c=[1986]$, and since, $[1986]$ has odd cardinality, this is impossible. Same solution is given in the imo compendium

Let $a=1987$. If $f(m)=f(n)$, then \[m=f(f(m))-a=f(f(n))-a=n\]so $f$ is injective. Now make the observation that \[f(n+a)=f(f(f(n)))=f(n)+a\]so $f(n+ka)=f(n)+ka$ for all $k\in\mathbb{Z}$ by induction. This immediately implies that if $m\equiv n\pmod a$ then $f(m)\equiv f(n)\pmod a$. Now, define a function $g:\{0,\ldots,a-1\}\to\{0,\ldots,a-1\}$ which maps $n$ to the remainder when $f(n)$ is divided by $a$. Then for all $n\in\{0,\ldots,a-1\}$, $g(n)\equiv f(n)\pmod a$, so \[f(g(n))\equiv f(f(n))\equiv n+a\equiv n\pmod a\]and thus $g(g(n))=n$. So $g$ is an involution on $\{0,\ldots,a-1\}$. Since $a$ is odd, this involution has a fixed point $d$. Then $f(d)=d+ka$ for some $k\in\mathbb{Z}$, so \[d+a=f(f(d))=f(d+ka)=f(d)+ka=d+2ka\]and thus $k=\frac{1}{2}$, contradiction. So such a function does not exist.

$f(n + k) = f(f(f(n))) = f(n) + k$ and it follows by induction on m that $f(n + km) = f(n) + km$ for all $n, m$ $\in$ $N$. Now take an arbitrary integer p, 0$\leq$p$\leq$ k−1, and let $f(p) = kq+r$, where $q$ $\in$ N and 0$\leq$r$\leq$ k − 1. Then $p + k = f(f(p)) = f(kq + r) = f(r) + kq.$ Hence either $q = 0$ or $q = 1$ and therefore either $f(p) = r, f(r) = p + k or f(p) = r + k, f(r) = p.$ In both cases we have p not equal to r which shows that f defines a pairing of the set $A = {0, 1, . . . , k}$. Note that different functions define different pairings of $A.$ Conversely, any pairing of $A$ defines a function $f : N \rightarrow N$ with the given property in the following way. We define f on A by setting $f(p) = r, f(r) = p + k$ for any pair $(p, r)$ of the given pairing and $f(n) = f(q) + ks$ for $n \geq k + 1,$ where $q$ and $s$ are respectively the quotient and the remainder of $n$ in the division by $k$. So,it is clear that if $k$ is an odd integer then,there are no such functions and we are done.

It can be easily seen that the function $f$ is injective Our problem function produces natural values from $1988$ onwards Suppose the function $f$ alone does not generate $N$ values. So the function $f(f(n))$ does not produce $2N$ value. So, if a function wants to be true in the problem, the following equation must have a solution $2N=1978$ And this issue has no natural answer! So the function does not work in the problem $\blacksquare$

Pluto04 wrote: $f(n + k) = f(f(f(n))) = f(n) + k$ and it follows by induction on m that $f(n + km) = f(n) + km$ for all $n, m$ $\in$ $N$. Now take an arbitrary integer p, 0$\leq$p$\leq$ k−1, and let $f(p) = kq+r$, where $q$ $\in$ N and 0$\leq$r$\leq$ k − 1. Then $p + k = f(f(p)) = f(kq + r) = f(r) + kq.$ Hence either $q = 0$ or $q = 1$ and therefore either $f(p) = r, f(r) = p + k or f(p) = r + k, f(r) = p.$ In both cases we have p not equal to r which shows that f defines a pairing of the set $A = {0, 1, . . . , k}$. Note that different functions define different pairings of $A.$ Conversely, any pairing of $A$ defines a function $f : N \rightarrow N$ with the given property in the following way. We define f on A by setting $f(p) = r, f(r) = p + k$ for any pair $(p, r)$ of the given pairing and $f(n) = f(q) + ks$ for $n \geq k + 1,$ where $q$ and $s$ are respectively the quotient and the remainder of $n$ in the division by $k$. So,it is clear that if $k$ is an odd integer then,there are no such functions and we are done. The best solution so far

\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] Suppose there existed such a function. We have $f(n + 1987) = f^3(n) = f^2(f(n)) = f(n ) + 1987$, so $f(n + 1987) = f(n) + 1987$ for all nonnegative integers $n$. If $f(a) = f(b)$, then $f(f(a)) = f(f(b))$, so $a + 1987 = b + 1987$, which means $a = b$, so $f$ is injective. Additionally, every integer greater than or equal to $1987$ is in the image of $f$. We have $a\equiv b\pmod{1987}$ implies $f(a)\equiv f(b)\pmod{1987}$. Now we prove a helpful claim. Claim: $f(n)\not\equiv n\pmod{1987}$ for all $n\ge 0$. Proof: Suppose some $n$ satisfied $f(n) = n + 1987k$, where $k$ is an integer. Note that \[n + 1987 = f(f(n)) = f(n + 1987k) = f(n) + 1987k = n + 1987 \cdot 2k,\]so $k = \frac{1}{2}$, absurd. $\square$ Now we define $g\colon \{0,1,2\ldots, 1986\} \to \{0,1,2\ldots, 1986\}$ such that $g(n)\equiv f(n)\pmod{1987}$ for any $0\le n\le 1986$. We already know $g$ has no fixed points by our previous claim. Additionally, we have $g(g(n))\equiv f(g(n)) \equiv f(f(n)) \equiv n\pmod{1987}$, so $g(g(n)) = n$, which means $g$ is bijective. Due to $g$ being an involution, it only has cycles of length $1$ or $2$, but since $g$ has no fixed points, it has only cycles of length $2$. This is impossible since $1987$ is odd. Therefore we have no such functions $f$.

Note that $f$ is injective, and thus the arrows graph on $\mathbb{Z}_{\ge 0}$ induced by $f$ is compromised of multiple disjoint chains. Realize that $f(n+1987) = f(f^2(n)) = f^2(f(n)) = f(n)+1987$. Consider the chain \[ n \to f(n) \to f^2(n) \to \ldots.\]Note that it must contain at most two distinct residues modulo $1987$ since $f^k(n) \equiv n \pmod{1987}$ for even $k$. If $f(n) \equiv n \pmod{1987}$, then the chain is a cycle, a contradiction. Otherwise, each disjoint chain corresponds to a unique codeset $\{a, b\}$ of residues, and all codesets are disjoint. However, by parity reasons, at least one residue is not covered by the codesets, which is impossible.

Consider any integer $n$ and look at the values of $f^k(n)$ modulo $1987$; they cover exactly two distinct residues. On the other hand, every set of residues must be disjoint, but as $1987$ is odd, one set can never be covered, contradiction.

this is literally mathpath qt p6

Did blackpink exist in 1987? Let $k = 1987$. FTSOC suppose that such an $f$ exists. Note that $f$ is injective. Consider the chains of the form $a, b, a + k, b + k, \dots$ formed by $f$ when interpreted as a graph. Each chain contains two residues $\pmod{k}$, however there are $1987$ residues, contradiction.

We'll show the following claim, which clearly implies the problem. Claim: There exists a function $f \colon \mathbb{N}_0 \to \mathbb{N}_0$ such that $f(f(x)) = x + k$ iff $k$ is even. Proof. Note that for $k$ even, we have $f(x) = x + \frac{k}{2}$ clearly satisfies the equation, so it suffices to show that there's no such $f$ for $k$ odd. Assume for sake of contradiction that there exists such $f$ and $k$ is odd. Note that $f$ must be injective, since $f(a) = f(b) \implies f(f(a)) = f(f(b)) \implies a + k = b + k \implies a = b$. Also, we have $f(f(f(x))) = f(x + k)$, but on the other hand, $f(f(f(x))) = f(x) + k$, so $f(x + k) = f(x) + k$. Now, assume there exist two $a, b$ with $a \not \equiv b \pmod{k},$ and $f(a) \equiv f(b) \pmod{k}$. We have $f(a) + kx = f(b) + ky$ for some $x, y$ which gives $f(a + kx) = f(b + ky)$, which gives $a + kx = b + ky,$ so $a \equiv b \pmod{k}$, a contradiction, so $f(a) \equiv f(b) \iff a \equiv b \pmod{k}$. So, the values $\{f(0), f(1), \cdots, f(k - 1) \}$ modulo $k$ must be a permutation, and we also have $f(x \pmod{k}) \equiv f(x) \pmod{k}$ But, since $f(f(x)) = x + k \equiv x \pmod{k},$ the length of each cycle in the permutation must divide $2$; that is, each cycle is either of length $1$ or length $2$. Note that we must have at least one cycle of length $1$, since $k$ is odd, since the sum of each cycle length is $k$. So, $f(e) \equiv e \pmod{k}$, for some element $0 \le e < k$. We can't have $f(e) = e$, as then $f(f(e)) = e$, a contradiction, so $f(e) \ge e + 1987$, so we have $f(f(e)) \ge f(e) + 1987 \ge e + 1987 \cdot 2$, a contradiction. So, there's no such function, and we're done.

Okay, hard problem. The generalization is quite normal though, but well I think someone did count number of functions when $N$ is even, right? Here's a solution... Would really love to learn arrows, alas! I don't get them a lot of time, how do people do this witch-craft? Solution: Label the original functional equation as $(\clubsuit)$ and let $N = 1987$. It is obvious that function $f$ is injective. By the triple involution trick, we have that \[f(f(f(x))) = f(x + N) = f(x) + N.\]This means it is sufficient to show that $f$ is not well-defined on $S \coloneqq \{0,1,2, \dotsc, N-1\}$. Claim: For $r \in S$, $f(r) < 2\cdot N$. Proof: For an arbitrary $r \in S$, it easy to show by induction that $f(Nk + r) = Nk + f(r)$ for any $k \in \mathbb{Z}_{\ge 0}$. Put $x = Nk + r$ in $(\clubsuit)$. We get \[f\left(Nk + f(r)\right) = r + N(k+1).\]If $f(r) > 2\cdot N$, then upon writing $f(r) = 2\cdot N + \epsilon$ for $\epsilon \in \mathbb{Z}_{\ge 0}$, we get the desired contradiction. $\square$ Let $r_i \in S$. From the above claim, if $f(r_1) = r_2$, then $f(r_2) = r_1 + N$. This creates a chain and pins down all $f(r_1 \pmod{N}), f(r_2 \pmod{N})$. Similarly, another possibility is $f(r_3) = r_4 + N$. Here, $r_3,r_4$ will create a similar chain as $r_1,r_2$ did. Therefore, we can naturally pair $r_i$ which create these chains. But, since $N$ is odd. One of the elements will get paired to themselves. So, we get that there is at least one $m$ such that either $f(m) = m$ or $f(m) = m + N$ for $m \in S$. If $f(m) = m$, then we put it in $(\clubsuit)$ to get a contradiction. This means $f$ can't have a fixed point. If $f(m) = m + N$, then again putting in $(\clubsuit)$ we would get $f(m + N) = m + N$ which gives a fixed point, impossible. Therefore there exists no such $f$ as desired. $\blacksquare$ Remark. An obvious generalization follows. Clearly odd $N$ won't work and is well-illustrated in the above solution. If $N = 2k$, then $f(x) = x + k$ works.

This problem should seem very familiar to MathPath applicants this year......

torch wrote: This problem should seem very familiar to MathPath applicants this year...... Well, it isn't too uncommon for math camps to have unoriginal problems on their qualifying tests, and you can't really blame MathPath for that (although I agree, it is wrong to have a problem on your qualifying test intentionally directly based on an older problem).

Assume $f^k(n) = n$ for some $k \ge 1$ and $n \in \mathbb{Z}_{\ge 0}$. Then $n + 1987k = f^{2k}(n) = n$, a contradiction. Thus $f$ doesn't contain a cycle. Since $f$ is injective and $\text{Im}(f)$ contains all numbers greater or equal to 1987, hence the graph of $f$ is a finite number of chains. Call a positive integer startpos if it isn't in $\text{Im}(f)$. Then all chain has exactly one startpos. Assume there were $k$ startpos and $a_1, a_2, \dots, a_k$ be the startposes. Then in order to cover $\mathbb{Z}_{\ge 0}$, $\{a_1, a_2, \dots, a_k, f(a_1), f(a_2), \dots, f(a_k)\}$ must form complete residue class module $1987$. But $2k \neq 1987$, a contradiction. Hence there are no such function. $\blacksquare$

Suppose a value smaller than $1988$ is in the image, than it cannot be in the image of the image, thus we can pair up distinct values smaller than $1988$ to forms chains however $1987$ is odd so not possible.

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.