AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
is given. It turns out that for every positive integer number 
, for which the numbers 
and 
are positive, they have the same number of divisors. Is it necessarily true that 
?
such that
+1 w
is self-bounded if for each 
, 
there exist at least 
terms of the sequence that are less than or equal to . Find the maximum possible value of 
for a self-bounded sequence .
+1 w
such that 
is an integer.
cards on which the numbers 
, 
, 
, are written respectively. Alice and Bob play the following game: in each turn, Alice gives two cards to Bob, who must keep one card and discard the other. The game proceeds for four turns in total; in the first two turns, Bob cannot keep both of the cards with the larger numbers, and in the last two turns, Bob also cannot keep both of the cards with the larger numbers. Let 
be the sum of the numbers written on the cards that Bob keeps. Find the greatest positive integer 
for which Bob can guarantee that is at least .
such that
for any positive integers 
, 
.
, with a,b,c,d are arbitrary integers and p is an arbitrary prime such that the fraction is an integer too.
and 
positive real numbers. Prove that![\[\frac{1+x_{1}^2}{1+x_{1}x_{2}}+\frac{1+x_{2}^2}{1+x_{2}x_{3}}+\cdots+\frac{1+x_{n}^2}{1+x_{n}x_{1}}\geq n.\]](http://latex.artofproblemsolving.com/e/9/e/e9e73a14f4dfa6315e7562998a9394d371847139.png)
is such that 
.
divides 
can be partitioned into tuples 
such that![\[
f(r_1)=r_2, f(r_2)=r_3, \ldots, f(r_{k-1})=r_k, f(r_k)=r_1+a.
\]](http://latex.artofproblemsolving.com/2/3/5/23505a800a744048db41e1e7d127ae0ea2b48dce.png)
and also for 
Using the lemma it is not hard to get 
and to find the only two solutions:
be 
iterated on 
, 
times. Let the problem assertion be 
. Then for 
, from 
and 
we get that
, and so 
for all and a constant 
. From this, is inyective. We get 
, so 
. as an injective function in 
which, if iterated four times, gives the identity. Notice that, for any , the numbers 
are all distinct in . as a union of disjoint sets of the form 
. This is a partition. (Note that this implies 
). Let 
be a function where 
. Then 
. Therefore, if we choose randomly and uniformly in , ![$\mathrm{E}[g(m)]=\frac{c}{4}$](http://latex.artofproblemsolving.com/6/a/b/6ab6e500cc4a43278351638f347a1176bebe531a.png)
. randomly and uniformly in , then we are choosing 
also randomly and uniformly, so 
is also random and uniform (since it is not hard to verify is a bijection in ), and so 
is also like this. Also note 
. Therefore, because of linearity of expectation,![$\frac{c}{4} = \mathrm{E}[f(f(m+1)+1)-(f(m+1)+1)] = \mathrm{E}[m+c-(f(m+1)+1)] = \mathrm{E}[(m+1)-f(m+1)] + \mathrm{E}[c-2] = -\frac{c}{4}+(c-2)$](http://latex.artofproblemsolving.com/f/e/1/fe10b28817837726f08c0ea1bff43b3fafbc873c.png)
.
so we only need to find 
to finish.
into sets of size 
: 
. Call these sets 
. If 
where is in a previous 
than , we conclude that 
, contradiction. If where is two advanced from , then because of the previous rule, we conclude 
, contradiction. Therefore, 
for 
.
and the following convoluted one:
for all 
.
to mean composed times. So 
. The FE can now be stated as 
. of both sides yields
So therefore we see that 
. It therefore follows that 
where 
. is injective. Suppose 
. That means 
and so 
. We can now be certain that 
exists (the inverse). We can also establish an important relationship by considering . Take of both sides to get 
. We now break into two cases.
:, because 
. Let us first prove that 
are distinct modulo . Suppose 
. That would get us into trouble because that means 
and would yield 
, contradiction. Similarly, if 
, we would get 
for some . So therefore, each of those must be distinct. I will define the term class to mean a set . It is also obvious that these classes have to be mutually exclusive. Note that this easily implies 
. Now let's add!
, we can do some bashing. We want to analyze 
but this is easy. Bash through and we get 
or 
which is weird but whatever.
.
. This means 
. This means 
. Then, plug in 
which is then 
which is impossible. Sadly, this part took me the longest 
will always denote 
composed with itself times (as opposed to raised to the th power).
is a solution. It is easy to verify that 
is also a solution. We will show that these are the only solutions for .
.
for some constant 
.
; accordingly, we have 
for all 
. Thus 
is linear in and we have 
. Letting 
, the result follows. 
, where 
denotes 
. is surjective over 
.
. 
for all 
into Lemma 1. We get 
. Since the LHS equals 
, the result follows. 
where 
are integers and 
, we have 
. is injective.
for some 
. Note that implies 
and so 
. Thus 
for all 
; i.e. is eventually periodic, contradicting Lemma 3. 
is injective.![\[ S = \sum_{n=0}^{c} (f(n) - n) \]](http://latex.artofproblemsolving.com/2/4/5/245571bd868c92cd7cd3a3237b1ddc4223d04d01.png)
and to express this in two different ways. On the one hand, since , we have 
are distinct modulo 
. Thus we have ![\[S = \frac{1}{4} \sum_{n=0}^{c} ((f(n)-n) + (f^2(n) - f(n)) + (f^3(n) - f^2(n)) + (f^4(n) - f^3(n))) = \frac{1}{4}(c+1)^2. \]](http://latex.artofproblemsolving.com/0/a/f/0afab43fadb6eb315ce12c7fb8b4354c20924fc2.png)
On the other hand, since , we have 
are distinct modulo . Thus we have ![\[ S = - (c+1) + \sum_{n=0}^{c} (g(n)-n) = -(c+1) + \frac{1}{2}\sum_{n=0}^{c}((g(n) - n) + (g^2(n) - g(n))) = -(c+1) + \frac{1}{2}(c+1)^2 . \]](http://latex.artofproblemsolving.com/9/d/5/9d5189e0d4e251663c867a586a2d08858a6adddb.png)
We have ![\[ \frac{1}{4}(c+1)^2 = -(c+1) + \frac{1}{2}(c+1)^2\]](http://latex.artofproblemsolving.com/3/2/a/32a22b6a3d192d3b75cbed5c05645517755c2bb9.png)
and thus ![\[ c = 3. \]](http://latex.artofproblemsolving.com/2/3/1/231b8ab1c464ac7111be64922e5de383e4556b90.png)
completely determine . Note that 
, so we must have 
(otherwise 
, contradiction). Thus 
. If 
, we have 
, so 
, contradicting Lemma 2. Similarly, if 
, we have 
, contradicting Lemma 2. Thus 
and 
; these imply 
and 
. Now is surjective over 
so 
. The possibilities for 
are ![\[ (0,2), (0,6),(4,2),(4,6), (2,0), (2,4), (6,0), (6,4). \]](http://latex.artofproblemsolving.com/1/b/6/1b6a38d4f4056b95e3670db3d8fd1e7dcd360690.png)
Checking all of these, we see that the first five cases violate Lemma 2, the sixth case produces the solution , the seventh case produces the solution , and the eighth case violates injectivity. 
, and 
for 
, 
for 
, and 
for 
.
, so define 
gives 
. So 
. Let 
, and 
, then 
. Note that 
. If 
, then for any 
, 
which is is impossible, so for all 
, we have 
for some 
and 
. If 
for some , then 
, which is also impossible, so 
. Now for all 
, 
, if 
then 
, otherwise if 
then 
. In particular, all residues of can be paired up into pairs 
so that 
and 
. So must be even. Define a residue 
to be good if and bad if otherwise, for some other residue 
. Consider the quantity 
Note that if is a pair then exactly one of and 
is good, so 
. Furthermore for any 
, 
. Note that 
, so 
is a complete set of residues modulo for every 
. Thus 
While we also have 
Compare both sides we deduce 
, since .
. First, if 
has 
, then 
or 
. But 
otherwise 
which is false. So . If 
then 
, false. If 
then 
, false. So 
and so 
. So 
, and so we have and 
are the other pair of residues. If is bad then 
, then 
, so we get 
. This gives for all 
, and hence for all 
. Check, we get 
, which does works. Otherwise is good, then 
, then 
, so we get 
. Check the with the original equation modulo : 
, 
, 
, 
, which is indeed a solution. So we get the desired solution set. 
are distinct modulo . Thus we have 
, let 
be the image of . Let 
for convenience. For 
, let ![$[a,b] = \{a,a+1, \dots, b\}$](http://latex.artofproblemsolving.com/2/7/9/2795a40750abecb1061c55f66d87b0d5bf751589.png)
and 
(so if 
, this set is empty).
. It then follows from iteration that 
, so 
, so is injective., so 
. It follows that whenever 
, we have that 
. It follows that we can split 
into the union of two disjoint intervals ![$[a, f(0)]\cup [b, \infty)$](http://latex.artofproblemsolving.com/3/1/4/31467f36b5ef185e791f8b319ca48048adf441eb.png)
for 
. Now note that 
is precisely the set of values 
, so ![$f^3(Z) = [a+1, f(0)] \cup [b+1, \infty)$](http://latex.artofproblemsolving.com/e/b/0/eb035635fe596d5df092482e8f0bea3950c133ef.png)
. Let 
, so from the injectivity of it follows that 
. Again by injectivity, 
and 
, so comparing magnitudes yields 
, meaning we can just let 
for some 
.
, so 
, so ![$f(Z) = [a,f(0)] \cup [b,\infty)$](http://latex.artofproblemsolving.com/1/c/d/1cd27ce9d6a04e830940e3155fe600620b174940.png)
, where 
. Then clearly 
in some order. In one case we have 
, contradiction, so we must have the other case, meaning 
. Now we induct on to show , with base cases 
obvious. For the inductive step, we note 
, as desired.
, in which case since ![$f(Z) = [a,f(0)]\cup [b,\infty)$](http://latex.artofproblemsolving.com/7/5/0/750a4e915949ee2ecf97cad5bf6a78452b5ca1f5.png)
it follows that 
. Then once again we have 
. In one case, we have 
, contradiction, so therefore we must have the other case, meaning 
. Then 
. But once again by injectivity, we have 
, and from our previous expression, we have 
, so 
. Since 
, it follows that 
, so it's pretty clear from our expression for that 
.
. This last equality is all we really need to finish. We'll induct on to show that 
. For the base case, 
, we've already shown the first three equalities. From 
, we get 
, as desired.
. Then 
. Meanwhile, 
, and 
yields 
. Finally, 
, as claimed. Hence the solutions are and 
equalling 
for even , 
for , 
for .
and note that we must have 
unless 
, so in particular is unbounded. Now, if for 
we get , i.e. periodic, which is not allowed. Thus is injective, and is either of the form 
or 
, where we let 
.
where 
if 
. Note that each element has indegree at most one and outdegree exactly one. We define the height of an element to be the largest such that there exists a path 
(possibly infinity if is in a cycle). Note that 
elements have height 
, and these each are the sources of chains which are subsets of . Consider the elements with height or , two from each chain. They are in but not in 
, so not in 
, i.e. not in 
. There at most possible such elements, so we conclude 
i.e. 
.
. In that case, we have that 
is partitioned into a bunch of cycles. But then everything has infinite height, which is a contradiction since zero cannot have height 
.
. Apply the extension of the 
trick to get 
, i.e. is linear and equal to 
for some . Then, 
, which means that there can actually be no cycles in the graph since if 
. The exception to this is , which implies that 
, or 
. But then is in a cycle again, which is not allowed.
, in which case 
and the thing looks like 
. Let , then since 
is not in we see that is not in 
, i.e. 
, or 
. Now, similarly 
, so 
. We claim that by induction in this case. Indeed, we proceed by strong induction, with 
clear. For the inductive step, take 
, and we invoke ![\[
n+1 = f(n-1)+1 = f(f(f(n-2)) = f(f(n-1)) = f(n)
\]](http://latex.artofproblemsolving.com/b/6/b/b6b2279942ab139b149b6056721f0828511bd8e1.png)
and done.
, in which case 
. So, our chain starts with 
and 
. Now, 
. So, 
and 
are 
in some order. Since 
, our chain must start with ![\[
\beta+1\to \beta+2\to 0 \to \beta
\]](http://latex.artofproblemsolving.com/4/0/5/4058571b08f30ae0fed86960ec0d3ef433f7d9c5.png)
Now 
, so and we get ![\[
2\to 3\to 0 \to 1\to\cdots.
\]](http://latex.artofproblemsolving.com/7/6/8/768bb144c4ba219830c073f210fb768ecbb1f4ac.png)
Now we claim by induction that our solution is ![\[
A_0 \to A_1 \to \cdots,
\]](http://latex.artofproblemsolving.com/b/d/8/bd8d7b519e41886d132e927e75d3013dafe51663.png)
where 
. In particular, we will show that 
forms the 
elements of the chain, with 
done. For the inductive step assume it is true for , and we will show that ![\[
4i+2\to 4i+3\to 4i+0\to 4i+1\to 4i+6\to 4i+7\to 4i+4\to 4i+5.
\]](http://latex.artofproblemsolving.com/c/4/7/c4784a57b44b4f574fc9a33a0a35dda426cd4353.png)
Note that 
so this part is done. Let 
. Then, 
. Then, we have ![\[
4i+2\to 4i+3\to 4i+0\to 4i+1\to k\to k+1\to 4i+4\to ?
\]](http://latex.artofproblemsolving.com/c/d/2/cd263f44a82ca3d9678a5aeee09305531bc53f7b.png)
![\[
f(f(f(k))) = f(k+1)+1 = 4i+5.
\]](http://latex.artofproblemsolving.com/9/7/e/97ebb34bca3f7b195f4f5a69b827202de102ac20.png)
Finally, 
and we are done. Our solutions are and ![\[
2\to 3\to 0 \to 1 \to 6 \to 7 \to 4 \to 5 \to \cdots \to 4k+2\to 4k+3\to 4k\to 4k+1\to \cdots.
\]](http://latex.artofproblemsolving.com/c/1/c/c1cdab9c20989a46fd266f0798e4f884d9c27ccc.png)
and ![\[ f(n) = \begin{cases} n+1 & n \text{ even} \\ n+5 & n \equiv 1 \pmod 4 \\ n-3 & n \equiv 3 \pmod 4. \end{cases} \]](http://latex.artofproblemsolving.com/9/7/1/971c38e72e6ffb5f561d33b7bd7abda7bc11441e.png)
One can check that both of these functions work. So we now have to prove they're the only ones.![\[ f^4(n) = f(f(n+1)+1) = f(f(n)+1)+1. \]](http://latex.artofproblemsolving.com/9/a/2/9a28d13d99624a3f54d64a3ce63b2f47b50702c7.png)
For 
the last expression also equals ![\[ f^4(n) = f\left( f^3(n-1) \right)+1 = f^4(n-1)+1. \]](http://latex.artofproblemsolving.com/a/e/a/aeae5df6af64c09fe1d20acd5274573d0907e184.png)
So 
is linear with slope one, meaning![\[ f^4(n) = n+c \qquad (1) \]](http://latex.artofproblemsolving.com/6/d/8/6d851784d9dee0b7b59e7be25bff6c5af1d12829.png)
for some constant . since 
according to the first line. (This is really the only time we use the far-right side of the first line until the end of the solution later.) In particular is injective and has no fixed points.
) gives![\[f(n+c) = f^5(n) = f(n)+c \qquad (2). \]](http://latex.artofproblemsolving.com/2/9/1/2915bc5381102abca040cf2aad7acb32d5e6a661.png)
as function modulo 
, say 
. In fact: is a bijection on 
.
is the identity, so is a bijection (with inverse 
). . We claim that for each the elements ![\[ (n, f(n), f^2(n), f^3(n)) \]](http://latex.artofproblemsolving.com/2/2/4/2246a9065f69259e5f586fc4f52deb7d79464008.png)
are distinct in . Indeed, if and differed by a multiple of , say , then (2) would apply in tandem with with (1) to get 
, contradiction.. The basic idea is that because of (2), the quantity ![\[ S = \sum_{n=1}^c \left( f(x_n) - x_n \right) \]](http://latex.artofproblemsolving.com/6/7/2/672f4f70f4045ff15c6bb5fc16495e3f0008506f.png)
is constant for any complete residue system 
. So in particular 
where ![\[ A_k = \sum_{n=0}^{c-1} f^k(n) \qquad k = 1, 2, 3. \]](http://latex.artofproblemsolving.com/8/a/d/8ad0c6dc18180ca2e7d61c9d051469609bcb0659.png)
But we have the additional relation 
Solving the system of equations gives 
, 
, 
, 
, 
. on 
. This is a finite case check; one of many solutions is presented here. Of course 
.
, we have ![\[ f(f(n)+1)= n+3. \]](http://latex.artofproblemsolving.com/8/1/0/81085b081df40dd0b857e975e37a613c4df366f9.png)
We call this property and use it pin down the small values of . and .
by 
.
fails by taking 
in the original.
implies , which then gives 
which is wrong.
then gives 
, which is absurd.; thus . 
. We now consider cases on 
.
, then 
gives 
, wrong., we recover 
., then gives 
, wrong since 
.
, we recover the other solution described at the beginning of the proof.
and 
where![\[\phi(n):=\begin{cases}
n+1 & n\equiv 0\pmod{4} \\
n+5 & n\equiv 1\pmod{4} \\
n+1 & n\equiv 2\pmod{4} \\
n-3 & n\equiv 3\pmod{4} \\
\end{cases},\]](http://latex.artofproblemsolving.com/8/9/8/8981d55a66aa7f3604b7a5b68ec39f3fa1ee74c6.png)
which we can check both work.![\[f(f(n)+1)+1=f^3(f(n))=f(f^3(n))=f(f(n+1)+1),\]](http://latex.artofproblemsolving.com/4/0/2/402d42e223b016b93294ed041cffa0e410ca85cc.png)
so![\[f^4(n)=f(f(n+1)+1)=f(f(n)+1)+1=f(f(n-1)+1)+2=\cdots=f(f(0)+1)+1+n.\]](http://latex.artofproblemsolving.com/8/7/8/878a784cee5e00b76b3e99d41aaa07853e9775ec.png)
Let 
, so we have 
. This already implies that is injective and that the image of contains 
. Now, we simply note that![\[f(n+d)=f(f^4(n))=f^4(f(n))=f(n)+d.\]](http://latex.artofproblemsolving.com/0/2/8/0281c47fbe73169dd5968f222774221d13c9ea02.png)
So we have the two equations 
and 
for some fixed integer 
. This completes the standard FE tricks portion.
be the directed graph such that 
if and only if 
. If there was a cycle, say 
for , then we would get![\[x=f^{4m}(x)=x+4d,\]](http://latex.artofproblemsolving.com/7/e/0/7e0d4176153811549b908723c2ac740c3f821ead.png)
which is a contradiction. Thus, there are no directed cycles. Furthermore, since is injective, each vertex has indegree and outdegree . This implies that looks like a disjoint collection of chains of the form![\[x\mapsto f(x)\mapsto f^2(x)\mapsto\cdots.\]](http://latex.artofproblemsolving.com/1/2/f/12f38b05811b7eca0956e1d285ddcbbfcf79097a.png)
We see that the complement of the image of is finite, so the number of such chains is finite. Let 
be the starting points of the chains. Given any 
, let 
denote its distance to the starting point of the chain that it's in.
, then 
, so 
. This implies that![\[x_i,f(x_i),f^2(x_i),f^3(x_i)<d\]](http://latex.artofproblemsolving.com/8/6/9/8690dadfc382c3ad4a5090265a260d10f4ed8bda.png)
and 
for all 
. Since the complement of the image of is finite, we see that every residue class mod 
is hit, so in particular, 
contains all the residue classes. From the above, we see then that the sets![\[\{x_i,f(x_i),f^2(x_i),f^3(x_i)\}_{i=1}^m\]](http://latex.artofproblemsolving.com/f/f/2/ff239cdd41f585851af6ff9a0f495525b7b31cef.png)
partition 
exactly (this implies 
in particular).
on 
such that![\[f(\sigma(i))=i+\epsilon_i d\]](http://latex.artofproblemsolving.com/2/8/1/281911b04b6f60e5b79653e19bc7a0d87e93bbb7.png)
where exactly 
of the 
s are equal to (these correspond to the ![$i\in[0,d-1]$](http://latex.artofproblemsolving.com/c/a/d/cad4ae0c58f0114ac00a3a67048ca70d10ed0dd0.png)
that come from 
) and the rest are . We also see that![\[f^3(i)=f^{-1}(i+d)=\sigma(i)+(1-\epsilon_i)d\]](http://latex.artofproblemsolving.com/e/5/6/e56d0555a9400d700114007643a92d90716fec7a.png)
since if 
, then 
and if 
, then 
.
for all 
, so summing, we see that![\[\sum_{i=0}^{d-1}f^3(i)=d+\sum_{i=1}^d f(i)=2d+\sum_{i=0}^{d-1}f(i).\]](http://latex.artofproblemsolving.com/3/7/b/37bf18e540c61c4e8c83e44249cbecf69e44aff5.png)
Thus,![\[(0+\cdots+(d-1))+d\left(d-\sum_{i=0}^{d-1} \epsilon_i\right)=2d+(0+\cdots+(d-1))+d\sum_{i=0}^{d-1}\epsilon_i,\]](http://latex.artofproblemsolving.com/6/c/e/6ce70152feb2a3c36ffa8e2e9f98bed6fa587551.png)
so![\[\sum_{i=0}^{d-1}\epsilon_i = \frac{d-2}{2}.\]](http://latex.artofproblemsolving.com/7/9/b/79bca12c25b9299aa64dbde15596a20788e12b9b.png)
However, we already know that exactly 
of the are and the rest are , so![\[\frac{d}{4}=\frac{d-2}{2},\]](http://latex.artofproblemsolving.com/8/e/4/8e42d75b27bd83b397e73d0b54618ce915010ab7.png)
or 
. This completes the arrow decomposition portion.
to be some permutation of 
uniquely determines the function, since its graph is just a chain starting from these . This is a finite case check of size 
, but its actually not that bad if one is careful.
. Then, the FE gives 
, and we have 
(it can't be since starts the chain). Also, 
(since ), so 
. Thus, we must have 
, so 
. This corresponds to the solution , which is one of the claimed solutions at the beginning.
. Then, the FE gives 
, and we have 
(it can't be since starts the chain). Also, 
(since ), so 
. This is a contradiction as 
, so there are no solutions in this case.
. Then, the FE gives 
, and we have 
(it can't be since starts the chain). Also, 
, so 
. However, 
, so 
, 
, so 
. This corresponds to the solution 
, which is one of the claimed solution at the beginning.
. The FE then gives 
, and we have 
. Thus, 
, so 
. This is a contradiction since 
, so there are no solutions in this case.
denote the assertion of to the given functional equation![\[ P(n) : f(f(f(n))) = f(n + 1) + 1 \]](http://latex.artofproblemsolving.com/3/0/3/303f518538ab841c85f17ec85fedf67799868411.png)
as the composition of by the function as many as times.
for a constant . ad 
gives us![\[ f^4(n) = f^3 ( f(n)) = f(f(n) + 1) + 1 = f( f^3 (n - 1)) + 1 = f^4(n - 1) + 1 \]](http://latex.artofproblemsolving.com/8/1/3/81399898f1823e872baf8b81f65b3c0e032c7ab7.png)
Therefore, we can have 
.
, then we have .
is injective., then we have![\[ a + c = f^4 (a) = f^4 (b) = b + c \]](http://latex.artofproblemsolving.com/c/a/5/ca51778a968f5e36a70f8a7731e1762cc5588071.png)
Therefore, we must have 
, proving that must be injective.
.![\[ f(n + c) = f( f^4 (n) ) = f^5 (n) = f^4 (f(n)) = f(n) + c \]](http://latex.artofproblemsolving.com/e/3/3/e33d03181bb04bfb706ca7cb76dff2bf9fe979da.png)
is divisible by .![\[ n, f(n), f(f(n)), f(f(f(n))) \]](http://latex.artofproblemsolving.com/e/f/f/effdcd91d2a8a694ae643678a71ddc5f443f7915.png)
are distinct in .
, take 
. Therefore,![\[ f(f(f(f(n)))) = f(f(f(n + kc))) = f(f(f(n))) + kc = f(f(n)) + 2kc = f(n) + 3kc = n + 4kc \]](http://latex.artofproblemsolving.com/0/d/5/0d55cdf75ce19622b8e9b1af1cf1fedbd6a756da.png)
This gives us 
, a contradiction.
, take 
. Therefore,![\[ f(f(f(f(n)))) = f(f(n + kc)) = n + 2kc \]](http://latex.artofproblemsolving.com/6/6/a/66a27a9f53b86e7790a6cd1bc95d85568149400c.png)
This gives us 
, a contradiction.
, take 
. Therefore,![\[ f(f(f(f(n)))) = f(n + kc) = f(n) + kc \]](http://latex.artofproblemsolving.com/f/e/2/fe2d75f770dfa8f04ea5dadec6199c8c5a529049.png)
This gives us , which has been done before.
are distinct in . where every vertex denote a residue in and connect 
when . We get that we can partition graph into distinct cycles of length . (Notice that by injectivity, no two cycles will coincide.).
:![\[ n = f^4(n) = f(f(n+1) + 1) = f(f(n) + 1) + 1 \]](http://latex.artofproblemsolving.com/3/5/7/3579805d730207c9ae21e3dfde4e3c05563beabd.png)
Plug 
to the above equation, and we have 
, a contradiction as 
.
, then must be .
and 
are the same in .![\[ Q(k) : \sum_{i = 0}^{c - 1} f(i) - i \]](http://latex.artofproblemsolving.com/9/e/e/9eed91eb2983eb142fbbd5c8d6776c8fbf7331c6.png)
which must be constant due to obvious reasons.
. By assertion 
, we have![\[ S_{m + 1} - S_m \ \text{being constant} \]](http://latex.artofproblemsolving.com/3/e/1/3e1683bacaebb03bdbe50f719bdab292944e5370.png)
Now, notice that![\[ S_4 - S_3 = S_3 - S_2 = S_2 - S_1 = S_1 - S_0 \]](http://latex.artofproblemsolving.com/f/f/c/ffc5d9ae569c52760bd41f9b87a2f450337b4d97.png)
Therefore, we have 
by easy manipulation and![\[ S_4 = \sum_{i = 0}^{c - 1} f^4(i) = \sum_{i = 0}^{c - 1} ( i + c ) = S_0 + c^2 \]](http://latex.artofproblemsolving.com/d/e/3/de367719b9e39903cc62971049701984a71d774a.png)
We then have 
.
gives us![\[ \sum_{i = 0}^{c - 1} f(f(f(i))) = \sum_{i = 0}^{c - 1} ( f(i + 1) + 1 ) = c + \sum_{i = 1}^c f(i) = 2c + \sum_{i = 0}^{c - 1} f(i) \]](http://latex.artofproblemsolving.com/d/9/0/d906aafca4da2e745a0a5768366951e47cc6ebc2.png)
by considering 
.
.![\[ 2c = S_3 - S_1 = 2(S_1 - S_0) = \frac{1}{2} ( 4 (S_1 - S_0) ) = \frac{1}{2} c^2 \]](http://latex.artofproblemsolving.com/7/3/e/73ee99479b8d1e157f6abf7206ab2ea87dccdb7b.png)
Therefore, .
, we just need to consider the graph of vertex 
.:
, then 
, a contradiction.
, then 
, a contradiction.
, then 
, a contradiction.
, then , a contradiction.
and 
.
., then![\[ 0 = f(0 + 1) = f(f(1) + 1) = f(f(0) + 1) + 1 \]](http://latex.artofproblemsolving.com/9/4/4/94415cd2765df7f7191c434264442953acd378c6.png)
a contradiction. is surjective for all values 
, then we must have . gives us![\[ f^3(0) = f(1) + 1 = 5\]](http://latex.artofproblemsolving.com/a/f/6/af680e33828621d47c72755f6e60c49b2a3d3359.png)
If 
, then we must have 
, then 
. This gives us 
, which gives us 
, a contradiction.
.
, then![\[ f(6) + 1 = f^3(5) = f^4(2) = 2 + 4 = 6 \]](http://latex.artofproblemsolving.com/b/f/b/bfbe0d87a7b9f42f63c011f892c379ebd58927d3.png)
Hence, 
, giving us 
, a contradiction..![\[ f(f(3) + 1) = f(f(2) + 1) + 1 = 2 \]](http://latex.artofproblemsolving.com/9/b/0/9b05492d6a21f87e00c84c6c43c0882c4a3cc15d.png)
and 
is the minimal value of mod in all values of 
. Hence, we must have 
.![\[8 = f(0) + 5 = f(4) + 1 = f^3(3) = f^2(2) = f(1) = 4\]](http://latex.artofproblemsolving.com/8/5/d/85d487dcfb5b8e5d86b8b68ac76785a3e0d41c18.png)
a contradiction.
.
or 
., then we must have![\[ f(1) + 1 = f^3(0) = f^4(3) = 7 \]](http://latex.artofproblemsolving.com/b/3/d/b3d935a95ef4251de25bdf551e7bc011f451c986.png)
and hence .
. This gives us 
. Since 
and is the minimum among all values of 
. Hence, . This gives us 
, which by injectivity gives us .
, we have that
is a solution. (Just check if you don't believe it!), we have that![\[ f(9) + 1 = f^3(8) = f^4(7) = 11 \]](http://latex.artofproblemsolving.com/7/3/b/73b123dac3f9c612a2f9c08cf0b1e208ccfbef2e.png)
Hence, 
. This gives us . Hence,![\[ f(3) = f(f(1) + 1) = f(f(0) + 1) + 1 \]](http://latex.artofproblemsolving.com/4/2/0/420335d624372e9dc2623e91f0663c3331208aca.png)
This gives us . Since 
is the minimal value of and has the value of 3 modulo 4, we have that . By injectivity, we have , and therefore by the property 
, we have that
is a solution.
Hence 
for some ; as a corollary, is injective.
. In what follows, we draw an arrow from to 
whenever .![\[w\to x\to y\to z\to w+c\to x+c\to y+c\to z+c\to\cdots,\]](http://latex.artofproblemsolving.com/d/b/2/db288c1edfb4ce03261abc70d764d7cac2751ba4.png)
where 
, , , 
are distinct nonnegative integers less than .. All elements of the chain are distinct, since the chain grows arbitrarily large, and otherwise it would be periodic.
. Assume, for example, that 
; then 
by injectivity, so we may instead start our chain at 
. The same argument applies for , , , so we may suitably choose so that . 
, since we can partition the elements of 
into subsets 
of size such that 
..
of the nonnegative integers 
is 
; analogously for 
of the nonnegative integers is 
. Summing over the given functional equation,
This solves to . 
(with 
) that covers all nonnegative integers. We take cases:
, then 
, so 
and ; the corresponding chain is 
.
, then 
. Clearly 
; 
since 
; and 
since 
.
, then 
. Clearly ; since 
; and 
implies , and the corresponding chain is 
.
, then 
. and , so the answer is ![\[ \boxed{f(n)=n+1}\quad\text{or}\quad\boxed{f(n)= \begin{cases} n+1&\text{if $n$ even}\\ n+5&\text{if $n\equiv1\pmod4$}\\ n-3&\text{if $n\equiv3\pmod4$} \end{cases} }. \]](http://latex.artofproblemsolving.com/5/4/8/5486f367402dd4e53fb78a1f51a80ea1446f4ec3.png)
Both work, so we are done.
be the set of all nonnegative integers. Find all the functions 
satisfying the relation![\[ f(f(f(n))) = f(n+1 ) +1 \]](http://latex.artofproblemsolving.com/8/b/9/8b953428105df2c2344963cbaf3eb81d8201e0df.png)
for all 
.
denote the statement of the problem or the assertion of the problem.
. such that 
.
and since the domain consists of only integers, we're free to say that 
for some integer constant or in other words, 
. Now, using the lemma mentioned by tash : is such that . divides can be partitioned into tuples such that and also for Using the lemma it is not hard to get and to find the only two solutions:
or if is even and 
and 
if 
and 
respectively.
![\[f^4(n) = f^3(f(n)) = f(f(n) + 1) + 1 = f(f^3(n-1)) + 1 = f^4(n-1) + 1\]](http://latex.artofproblemsolving.com/f/b/6/fb6cedeba3d492464fad3355df104d94a36199a0.png)
so it follows that the function 
is linear; so we may write for a constant . Here we note that is injective, since if , then![\[b + c = f^3(f(b)) = f^3(f(a)) = a + c \implies a = b.\]](http://latex.artofproblemsolving.com/a/3/5/a3598f43701505dce3751fa53d76610bf8261ca7.png)
Furthermore, we may also obtain 
.
is impossible since that would mean and thus would be a bijection. Hence, an inverse would exist and be defined for all thus 
. Plugging in the value would yield![\[0 = f^{-1}(f(0)) = f(f(0) + 1) + 1 \geq 1\]](http://latex.artofproblemsolving.com/3/c/2/3c2115629c89f1ace59324d67eb39c7bac5b51d5.png)
which would indeed be a contradiction., and we claim that 
are all different modulo for all . If not:
for some , then setting 
gives![\[f^4(k) = f^3(k + mc) = f^2(f(k) + mc) = f(f^2(k) + mc) = f^3(k) + mc\]](http://latex.artofproblemsolving.com/9/3/2/932432556b67d3382fe4aaca40bb935b75e1b01a.png)
since for all , through induction, gives![\[f(n + mc) = f(n + (m-1)c) + c = \ldots = f(n) + mc\]](http://latex.artofproblemsolving.com/1/b/2/1b2b92223bd0dfc5ddb5c28a28c4f5985a4397d2.png)
for all 
. An unwrap yields![\[f^3(k) + mc = f^2(k + mc) + mc = f^2(k) + 2mc = f(k) + 3mc = k + 4mc = f^4(k) = k + c\]](http://latex.artofproblemsolving.com/f/d/e/fde9d847b6e6dc4c8ce848b9d39a3a26f886610d.png)
which implies 
, impossible. 
for some , then setting 
gives![\[k + c = f^4(k) = f^2(k + mc) = f(f(k) + mc) = f^2(k) + mc = k + 2mc\]](http://latex.artofproblemsolving.com/b/b/6/bb69ed9f2be827a813af151f9e9fdb8c03492252.png)
hence 
, impossible. 
for some , then setting 
gives![\[k + c = f^4(k) = f(k + mc) = f(k) + mc\]](http://latex.artofproblemsolving.com/3/0/a/30a6bf35ff7f68f4ec47fc6ff403edb63dc3e7c3.png)
so . Thus 
which has been covered in the first case. 
for any fixed has period modulo , since in general. Clearly, no two chains can have overlapping residues due to injectivity, so 
can be partitioned into some collection of disjoint chains (each covering residues), and thus 
. \newpage We will go on further to prove that in fact, . Notice that,![\[\sum_{i = 0}^{c-1} f^3(i) = \sum_{i = 1}^{c} (f(i) + 1) = 2c + \sum_{i = 0}^{c-1} f(i) \implies \sum_{i = 0}^{c-1} f^3(i) - \sum_{i=0}^{c-1} f(i) = 2c.\]](http://latex.artofproblemsolving.com/e/5/2/e529e889793b1f9f1a47f9b3e80bc03d2ce1c9a5.png)
Note that each of the elements of takes on the role of one of 
for some chain defined by 
. Since the chains are disjoint, exactly 
of them take on the role of each one. Denote set 
as the set of elements of that takes the role of some 
, and also similarly the sets 
. Write
hence 
and indeed, . Now, we finish the problem.
it must be defined by 
. The rest of the chain is automatically generated by 
.
, then 
. Clearly 
is implausible, and 
implies that 
, which is false. Thus, 
. Furthermore, we know 
so 
must be , and 
must be . The chain must be 
and so on.
, then 
. If 
, then 
, which is not possible since 
. Clearly 
is implausible, and also, 
implies that 
, which is false. This case is impossible.
, then 
. Clearly 
is implausible, and 
implies that 
, which is false. Thus, 
. Furthermore, we know so must be , and must be . The chain must be 
and so on.
, then 
. Note that 
must always differ by at most , so this is impossible.![\[0, f^1(0), f^2(0), \ldots = \{0, 1, 2, 3, 4 \ldots\} \text{ and } 2, f^1(2), f^2(2), \ldots = \{2, 3, 0, 1, 6 \ldots\}.\]](http://latex.artofproblemsolving.com/2/2/f/22fa7abaaaeb86f4e714119eb11962b696ddc295.png)
We can extrapolate the answers from these two chains.
. The rest of the function is automatically generated by 
, so in this case, the solution of![\[\boxed{f(n) = n + 1}\]](http://latex.artofproblemsolving.com/d/3/9/d39ab10ea230099d0cd2aa9e25f2a54481b04073.png)
is reached.
, and . Similarly, the rest of the function is automatically generated by , so this case yields the solution of![\[\boxed{f(n) =
\begin{cases}
n+1 & \text{ if }n \equiv 0 \pmod 4\\
n+5 & \text{ if }n \equiv 1 \pmod 4\\
n+1 & \text{ if }n \equiv 2 \pmod 4\\
n-3 & \text{ if }n \equiv 3 \pmod 4.
\end{cases}}\]](http://latex.artofproblemsolving.com/4/c/3/4c38dfc423f8ee5766fa5bacdffe78b35076de32.png)
These two solutions both clearly work, so we are done. 
so 
for some constant 
., then forms only -cycles and -cycles. Notice if is the local max of a cycle then so is 
, but not every number is a local max so contradiction., then is injective whose chains only begin between and 
inclusive. Thus forms a draconic chain, a function dictated by a finite set of chains. A quasi-linear function. We know each chain takes four of the starting values. Anyways, simply sum the given over to 
to get 
so .
be the assertion. Note that 
gives 
. On the other hand, gives 
so ![\[f^4(n)=n+c\]](http://latex.artofproblemsolving.com/d/d/8/dd80db64672785e5847e6718a2722db2f57f44c7.png)
where 
. Now, 
. If 
then 
so 
. Thus, for any list 
that forms a complete residue system 
then 
also does. Let 
. Note that 
. We have if then 
. forms a complete residue system then there exists a permutation, 
such that 
. Then, 
In particular, using on 
, we have![\[g(0)+g(1)+\dots + g(c-1)=g(f(0))+g(f(1))+\dots +g(f(c-1))=g(f^2(0))+g(f^2(1))+\dots +g(f^2(c-1))\]](http://latex.artofproblemsolving.com/e/8/e/e8eb313ce3b24ef4bb5d619837cba9252de80050.png)
Let 
then ![\[f^3(0)+f^3(1)+\dots + f^3(c-1)=f(1)+1+f(2)+1+\dots + f(c)+1=c+S+f(c)-f(0)=S+2c\]](http://latex.artofproblemsolving.com/c/d/f/cdfc8b3fa03de86dffd76cb3b387bcff71924efb.png)
and Thus, ![\[2c=g(f^2(0))+g(f(0))+\dots + g(f^2(c-1))+g(f(c-1))=2\left(S-\frac{c(c-1)}{2}\right)\]](http://latex.artofproblemsolving.com/9/a/9/9a9ff561169c90fcf6d212b6785990e31f1c800b.png)
implying 
.![\[g(0)+g(1)+\dots + g(c-1)=g(f^3(0))+g(f^3(1))+\dots +g(f^3(c))\]](http://latex.artofproblemsolving.com/b/c/0/bc0cd36ce9eb85b500becfb77332e6f0fee2bf34.png)
Which gives ![\[S-\frac{c(c-1)}{2}=c^2+\frac{c(c+1)}{2}-S-2c\]](http://latex.artofproblemsolving.com/7/b/1/7b104814c13338e0be0adce348124d5e656ec206.png)
so 
. Either or . If then 
so gives 
, absurd.. It remains to determine . We have 
. We have 
so 
. If 
then 
, absurd. If 
then 
, so 
, absurd. We already know 
, so 
, implying 
. Thus, for all even .
. Note that and are both even. If 
then 
, absurd. If 
then 
so , absurd. and both give valid solutions, which are![\[f(n)=n+1\]](http://latex.artofproblemsolving.com/7/1/0/7108424e6348d5433beb78a83698b61f40f03b10.png)
and![\[ f(n) = \begin{cases} n+1 & n \equiv 0\pmod 4 \\ n+5 & n \equiv 1 \pmod 4 \\ n+1 & n \equiv 2\pmod 4 \\ n-3 & n \equiv 3 \pmod 4. \end{cases} \]](http://latex.artofproblemsolving.com/1/a/9/1a914b89288bce1da0f0627ae77a114be15fabfc.png)
![\[ f^4(x) = f^3(f(x)) = f(f(x) + 1) + 1 > 0 \]](http://latex.artofproblemsolving.com/4/4/5/4453265e52d7e061cfa764f5f456530e161292ad.png)
but also that ![\[ f^4(x) = f(f^3(x)) = f(f(x+1)+1) \]](http://latex.artofproblemsolving.com/5/9/d/59d8ff5dbd9aa4a11569534be4e8fc0595d346b4.png)
Thus, 
As such, is injective.
.
.
to get that ![\[ f^5(x) = f^4(f(x)) = f^4(0) + f(x) \]](http://latex.artofproblemsolving.com/7/d/9/7d9250a72ed6ad9d3a91c7399ac281ecfb38c3e7.png)
and that ![\[ f^5(x) = f(f^4(x)) = f(x + f^4(0)) \]](http://latex.artofproblemsolving.com/b/8/a/b8a76c5f9fb632fc1ba0c4f5d22b7ede8767d2ca.png)
Thus, if we let then . is injective, it follows that the residues 
form a bijection.
only depends on its residue.![\[ S = \sum_{i=0}^{c-1} (f(x_i) - x_i) \]](http://latex.artofproblemsolving.com/9/c/3/9c3468592763eec1731d6a3dcb20b2a1b84c25ff.png)
is constant if 
is a complete residue system.![\[ 4 \cdot S = \sum_{i=0}^{c-1} (f^4(i) - i) = c^2, \]](http://latex.artofproblemsolving.com/f/7/2/f72f742cfaafdc2f94a653bcbc864b5ffbf5f48c.png)
meaning that 
.![\[ c = \sum_{i=0}^{c-1} (f^3(n) - f(n + 1)) = \sum_{i=0}^{c-1} (f^3(n) - f(n)) - c = 2 \cdot S - c \]](http://latex.artofproblemsolving.com/0/6/2/062a2e1142ad22d134cce426084c03cdf9029e4f.png)
it follows that 
.
and . 
is the same as with one of the elements having added to it.
, it follows that no residue maps to itself. Similarily 's graph can not consist of two cycles, and can only be one element cycle.
cycles means that when considered as an element of 
, is either 
or 
. or ![\[ f(x) = \begin{cases} x - 3 & x \equiv 3 \pmod{4} \\ x + 1 & x \ne 0, 2 \pmod{4} \\ x + 5 & x \equiv 1 \pmod{4} \end{cases}. \]](http://latex.artofproblemsolving.com/d/e/8/de8f81e068a564a0a0fe8831d0cb4efb4880ccfa.png)
and![\[\boxed{f(n)=\begin{cases}n+1&n\text{ is even}\\n-3&n\equiv 3\pmod 4\\n+5&n\equiv 1\pmod 4\end{cases}}.\]](http://latex.artofproblemsolving.com/7/3/3/7330d322b29d306a7a880262d4dffc878eee854d.png)
It is not hard to check that these work, so we will show that these are the only solutions.![\[f(f(f(f(n))))+1=f(f(n+1)+1)+1=f(f(f(f(n+1)))),\]](http://latex.artofproblemsolving.com/0/5/3/053020a30e384c336b1a50f45d6e803e6ca6b5e8.png)
so there exists some 
such that 
satisfies 
.
.
. Considering the arrows graph of , we get that 
, so let 
.Also by considering the arrows graph, we get that reaches all but exactly nonnegative integers.
. Then we also have![\[f^4 = (f\circ h)^2.\]](http://latex.artofproblemsolving.com/c/1/c/c1c07662b50e570218f5876903a9a4c00e44b6f3.png)
Therefore, 
reaches all but exactly 
nonnegative integers, meaning that misses at least 
nonnegative integers. Thus 
, so 
. 
. Then 
. We claim that this is not possible for 
. In fact, since is a bijection(since is the identity), we would need to have![\[h(f(h(f(f(0)+1))))=f(0)+1\Longrightarrow h(f(f(0)+1))=0,\]](http://latex.artofproblemsolving.com/0/6/3/0635969b56f54758203a00463c07b8eb6995cadd.png)
absurd.
. Then cycles through all four residues mod then adds to the cycle, etc. Thus is injective. We have![\[f(h(f(h(3))))=f(h(f(4)))\in f(h(\{5,6,7,9,10,11\}))\in f(\{6,7,8,10,11,12\}),\]](http://latex.artofproblemsolving.com/c/8/b/c8b89f2f9a59e19cf6f06c1bfe9925e6a4c4f71a.png)
so![\[f(f^3(3))\in f(\{6,7,8,10,11,12\})\Longrightarrow f(f(f(3)))\in\{6,7,8,10,11,12\}.\]](http://latex.artofproblemsolving.com/d/f/8/df88625a91ae0804abcd922e71a3ac4722d1ada6.png)
But 
, and 
, so 
, so 
, so 
, so .
to be , so . This indeed shows that the claimed solutions are the only ones, so we are done. 
is injective. is the minimum value among 
All values 
are in range of such that 
by abusing the involution trick
are distinct modulo and uniquely determine 
are in the range of 
where 
such that 
and keep in mind u have 
as well thats at max one more solution
be the set of all solutions to the first ineuqliaty and 
for second then 
must have atleast one solution and finish the problem
and we have 
Through induction we get that ![\[f^4(n)=n+c \implies f(n+c)=f(n)+c \text{ } \left(\clubsuit \right)\]](http://latex.artofproblemsolving.com/9/b/4/9b48d8f759781a12f92cb861989a6add4fca4e36.png)
Assume 
.
If , then 
, which is a contradiction. If 
, then 
will easily give us the only working function is .
.
only depends on 
. Hence we get that ![\[\{f(0),f(1),\dots,f(c-1)\} \equiv \{0,1,\dots,c-1\} \pmod c\]](http://latex.artofproblemsolving.com/2/9/4/294688e3b0225cb5e3fe455f6f6ad0f71b8bf0e0.png)
Again see that 
. And hence we get ![\[K=\sum_{i=0}^{c-1} f(i)-i=\sum_{i=1}^{c-1} f^2(i)-f(i)=\sum_{i=1}^{c-1} f^3(i)-f^2(i)=\sum_{i=1}^{c-1} f^4(i)-f^3(i)\]](http://latex.artofproblemsolving.com/a/2/0/a20f7df722422cc2513ea2a511e9e5633893e80e.png)
And so if we sum it up and use 
, we get that 
. And see that again since we have ![\[f(f(n)+1)=n+c-1 \text{ and } \sum_{i=0}^{c-1} f(f(i)+1) \equiv \sum_{i=1}^{c-1} i \pmod c\]](http://latex.artofproblemsolving.com/e/e/3/ee371688e681c95994b9d66623e375df25274a11.png)
We get that ![\[(c-1)c=\sum_{i=1}^{c-1} f(f(i)+1)-i=K+\sum_{i=1}^{c-1} f(i)-i+1 = 2K+c = \frac{c^2}2+c \iff c=4\]](http://latex.artofproblemsolving.com/5/e/2/5e2e469671655cd2f2a6e07145b4e3cba9de4042.png)
Let 
be the digraph of on 
modulo . That is 
.
is 
. Again recall that 
, check some values and see that the only two working functions are ![\[\boxed{f(n) \equiv n+1 \text{ } \forall \text{ } n \in \mathbb{Z}_{\geq 0}} \text{ AND } \boxed{f(n)= \begin{cases} n+1 \text{ if } n \equiv 0 \pmod 2 \\ n+5 \text{ if } n \equiv 1 \pmod 4 \\ n-3 \text{ if } n \equiv 3 \pmod 4 \end{cases} \text{ } \forall \text{ } n \in \mathbb{Z}_{\geq 0}}\]](http://latex.artofproblemsolving.com/7/a/5/7a5da695d3e15e8b331c7a900a9e8d09184a7f31.png)
of both sides to get 
subtract 1 and take 3 times to get 
or all nonnegative integers. Thus, if 
then 
. Take of both sides and we get 
If 
we get is linear, and thus, 
is bijective over 
We get 
so 
Thus, is identity over This is obviously impossible. Hence, is injective. Since the size of the sets are the same, is also bijective.
is constant. Thus,
However, also note that 
so ![\[S = \sum_{n = 0}^{c - 1}f^3(n) - f^2(n) = \sum_{n = 0}^{c - 1} f^3(n) - f^2(n) = 2c + \sum_{n = 0}^{c - 1} f(n) - f^2(n) = 2c - S\]](http://latex.artofproblemsolving.com/f/a/6/fa6e478db087648f1671fd3f6eb51a7907032026.png)
or 
However, adding all the equations together, we get 
Hence, 
Hence, 
We plug values into this equation.
Observe that 
this is impossible
we must have 
Impossible, as 
so 
contradicting the range
Hence, 
We do casework on 
taking 
we get 
contradiction
we get 
which works taking 
we get 
we get 
which is valid.
and![\[f\equiv\begin{cases}
x + 1 & x \equiv 0 \pmod 2 \\
x + 5 & x \equiv 1 \pmod 4 \\
x - 3 & x \equiv 3 \pmod 4 \\
\end{cases}\]](http://latex.artofproblemsolving.com/9/2/b/92b138e09f1ed0d411363cfe8360e94894d4775e.png)
of both sides to get subtract 1 and take 3 times to get or all nonnegative integers. Thus, if then . Take of both sides and we get If we get is linear, and thus, is bijective over We get so Thus, is identity over This is obviously impossible. Hence, is injective. Since the size of the sets are the same, is also bijective. is constant. Thus,However, also note that so or However, adding all the equations together, we get Hence, Hence, We plug values into this equation. Observe that this is impossible we must have Impossible, as so contradicting the range Hence, We do casework on taking we get contradiction we get which works taking we get we get which is valid. and
and![\[f(n) = \begin{cases} n+1 & n \equiv 0, 2 \pmod 4 \\ n+5 & n \equiv 1 \pmod 4 \\ n - 3& n \equiv 3 \pmod 4. \end{cases}\]](http://latex.artofproblemsolving.com/c/2/2/c22c0b91afd76fa60e04ec58e0ddf2866087837e.png)
Verifying these solutions work is not difficult. Now, first for the easy part.. Then, for all positive integers , and . in two ways using the given yields ![\[f^4(n+1) = f(f(n+1) + 1) = f(f(n) + 1) + 1 = f^4(n) + 1\]](http://latex.artofproblemsolving.com/4/7/a/47a0a0788b12ae9f87bb64cb254d239d89ef77bd.png)
which implies that , as needed. The second assertion comes from writing 
in two ways using . is periodic modulo . Next for the black magic part.. be a complete residue system of integers modulo . Notice that the sum ![\[A_S = \sum_{i \in S} \left(f(i) - i \right) = \sum_{i=0}^{c-1} \left(f(i) - i\right)\]](http://latex.artofproblemsolving.com/f/6/8/f6842814d52bb80b462322dbe408ced2a47f4208.png)
is a constant for all choices of . In particular, let 
for 
. Then ![\[2A = A_{S_1} + A_{S_2} = \sum_{i=0}^{c-1} \left(f^3(i) - f(i)\right) = c+f(c+1)-f(1) = 2c\]](http://latex.artofproblemsolving.com/6/c/6/6c67995d6e73e4573259f246e61d992c8374f4fd.png)
thus we get 
. On the other hand, ![\[4A = A_{S_0} + A_{S_1} + A_{S_2}+A_{S_3}= \sum_{i=0}^{c-1} \left(f^4(i) - f(i)\right) = c^2\]](http://latex.artofproblemsolving.com/4/1/2/41246952a042acd352c7da8fe865ed7834332c1c.png)
implying . Wow. is injective, it follows that 
, and are distinct residues modulo . (Otherwise, we may scale up and down by 's to find .) On the other hand, since every sufficiently large integer congruent to 
mod appears in the set 
for each , it follows that for every positive integer , there exists a (possibly negative) such that 
.
were defined. Then 
, which is a contradiction; hence one of the three sets 
for 
is congruent to the set . A quick case check yields the above solutions. would be motivated at all.
Prove that
such that
so we have : 
now
exist 
such that for any 
we know exist 
such that 
is also solution.
,
then 
for some 
,
for some 
and 
then 
and 
then 
so this is analogous to the previous case.
,
is the fractional part).
Now with some simple shifting of indices on the RHS,
Where we replaced 
with 
.
We have already established that 
and 
run through 
modulo 
we know 
and so we have 
.
If we let 
.
modulo 
so 
.
and if we add up letting 
Okay we are now ready to solve for 
and this yields 
.
.![\[f(f(n)+1)+1 = f^4(n) = f(f(n+1)+1)\]](http://latex.artofproblemsolving.com/2/5/b/25b5e001f12d956ee4238701240ed85ac89cd0ca.png)
we can get![\[f(f(n)+1) = n + f(f(0)+1).\]](http://latex.artofproblemsolving.com/b/5/f/b5faeddd314c606ab792ed500b521c3c18bad86d.png)
In particular, 
,
,
.
.
.
,
as required. 
,
and one of the following holds
.
.
(here we use the second condition). In particular, we can get 
,
looks like ![$\mathbb{Z} \cap ([u,f(0)]\cup [v,\infty))$](http://latex.artofproblemsolving.com/c/1/5/c15220ec456b457a812f55738101ade021bd554b.png)
for some integers 
.
.
,
.
,
with 
,
,
.
,
.
,
,
so 
,
,
,
.
doesn't always hold. Suppose 
,
,
with 
and 
,
.
then 
,
,
.
contains a single element, and 
by lemma 2. In fact, this means either 
(in which case 
eventually, implying 
,
(in which case 
by lemma 2). Therefore, we have the following chain:![\[s \stackrel{f}{\longrightarrow} s+1 \stackrel{f}{\longrightarrow} 0 \stackrel{f}{\longrightarrow} s-1 \stackrel{f}{\longrightarrow} \dots\]](http://latex.artofproblemsolving.com/7/8/0/7802c58da1463657f7e7d6f23c31033c7575af87.png)
Plug in 
in the original equation, we get 
,
.
,
.![\[f(n) = \begin{cases} n+1, & \text{if } n\equiv 0\pmod 2;\\ n-3, & \text{if } n\equiv 3\pmod 4;\\ n+5, & \text{if } n\equiv 1\pmod 4.\end{cases}\]](http://latex.artofproblemsolving.com/4/7/f/47f92170bcc2860d7b7e5e22a70a91dc69209407.png)
Subcase 2.2. 
.
,
and 
.
,
for some constant 
,
.
,
,
,
.
,
,
for 
,
where 
,
.
,
,
.
,
,
for some 
,
Therefore, 
,
.
Therefore, 
,
,
,
.
,
.
,
and 
.
and 
.
,
,
,
,
,
,
.
,
,
.
,
,
.
,
,
.
,
.
.
,
.
,
,
,
,
,
,
,
and 
,
and 
,
and 
and 
,
.
and 
we get 
It follows that 
Note that 
note that it is constant. Observe that 
But from the original equation, 
Now solving these sums yields the claim. 
then we'll be done. We do case-work on 
then 
absurd. Surely 
If 
then 
absurd. If 
then 
Now note that 
We do case-work on 
If 
then 
absurd. If 
then 
If 
then 
or 
all of these work.