Find all functions f:Z→Z such that n2+4f(n)=f(f(n))2 for all n∈Z. Proposed by Sahl Khan, UK
Problem
Source:
Tags: IMO Shortlist, algebra, functional equation
12.07.2015 14:41
hajimbrak wrote: Find all functions f:Z→Z such that n2+4f(n)=f(f(n))2 for all n∈Z. Here is an ugly heavy solution (hope somebody will find something prettier) : Let P(n) be the assertion n2+4f(n)=f(f(n))2 Let a=f(0) Note that f(u)=f(v) implies u=±v Equation immediately implies that ∀n, either f(n)=0, either |f(n)|≥|n|−1 and |f(n)|≥|f(f(n))|−1 Replacing n by f(n), we also get that ∀n, either f(f(n))=0, either |f(f(n))|≥|f(n)|−1 So ∀n, if f(n)≠0 and f(f(n))≠0, we get |f(n)|+1≥|f(f(n))|≥|f(n)|−1 So ∀n : either f(n)=0, either |f(f(n))|∈{0,|f(n)|−1,|f(n)|,|f(n)+1} If f(n)=0, equation implies n=±a If f(n)≠0 and |f(f(n))|=|f(n)|, equation implies n2+4=(f(n)−2)2 and so n=0 and f(0)=4 and f(4)=−4 (since f(4)=f(0)=4 is impossible) and then P(4) implies f(−4)=0 If f(n)≠0 and |f(f(n))|=|f(n)|−1, equation implies n2+4f(n)=f(n)2−2|f(n)|+1 and so : - either f(n)<0 and f(n)=1−|n| - either f(n)>0 and n2+8=(f(n)−3)2 and so n=±1 and f(n)=6 If f(n)≠0 and |f(f(n))|=|f(n)|+1, equation implies n2+4f(n)=f(n)2+2|f(n)|+1 and so : - either f(n)>0 and f(n)=1+|n| - either f(n)<0 and n2+8=(f(n)−3)2 and so n=±1 and f(n)=∈{0,6}, impossible As a intermediate conclusion, we get that ∀n∉{−1,0,1}, f(n)∈{0,1+n,1−n} This forbids the case f(4)=−4 Let us have a look at the case f(n)=0 : If f(u)=0, then P(u) implies f(0)=±u and since P(0) implies f(0)≥0, we get f(0)=|u| P(0) ⟹ f(|u|)2=4|u| and so : If u≥0, this becomes f(u)2=4u and so u=0 If u<0, this implies u=−t2 for some t≥1 and so : f(−t2)=0 and f(t2)=±2t and f(0)=t2 and then P(t2) implies t4±8t perfect square and so t∈{1,2} but we previously got that the case t=2 did not match And so f(n)=0 implies n∈{0,−1} So ∀n∉{−1,0,1}, f(n)∈{1+n,1−n} So f(2)∈{−1,3} If f(2)=−1 : P(2) ⟹ f(−1)=0 P(−1) ⟹ f(0)=1 (remember that P(0) implies f(0)≥0) P(0) ⟹ f(1)=±2 but then P(1) is wrong. So f(2)=3 and simple induction implies f(n)=n+1 ∀n≥2 If f(k)=1+k for some k<−1, it is easy to show with induction that f(n)=n+1 ∀ n∈[k,−2] Then P(−2) implies f(−1)=0 P(−1) implies f(0)=1 (since ≥0) P(0) implies f(1)=±2 and P(1) implies f(1)=2 If f(n)=1−n ∀n<−1 P(−1) implies f(−1)∈{0,2} If f(−1)=0 we easily get f(0)=1 and f(1)=2 If f(−1)=2 : P(1) implies f(1)∈{0,2} and so f(1)=2 and then f(0)∈{0,1} Hence all the solutions : S1 : f(x)=1+x ∀x∈Z which indeed is a solution S2 : f(x)=1−x ∀x≤a and f(x)=1+x ∀x>a which indeed is a solution, whatever is integer a≤0 S3 : f(0)=0 and f(x)=1−x ∀x<0 and f(x)=1+x ∀x>0 which indeed is a solution
17.07.2015 17:35
The official solution is just bash -_-
21.07.2015 19:17
pco wrote: hajimbrak wrote: Find all functions f:Z→Z such that n2+4f(n)=f(f(n))2 for all n∈Z. Here is an ugly heavy solution (hope somebody will find something prettier) : If you had seen the official solution, you would have been really happy with your beautiful solution.
09.10.2015 18:15
can anyone explain me why |f(n)|≥|n|−1 and |f(n)|≥|f(f(n))|−1 thank
09.10.2015 18:32
jindoak10 wrote: can anyone explain me why |f(n)|≥|n|−1 and |f(n)|≥|f(f(n))|−1 thank If you have a2+4b=c2 where a,b,c∈Z, then : Either b=0 Either b>0 and so |c|≥|a|+2 (they are both odd or both even) and so 4b≥4|a|+4 and so b≥|a|+1≥|a|−1 Either b<0 and so |a|≥2 and |c|≤|a|−2 (they are both odd or both even) and so 4b≤−4|a|+4 and so −b≥|a|−1 And so either b=0, either |b|≥|a|−1 But we may also write a2+4b=c2 as c2+4(−b)=a2 and same path gives : either b=0, either |b|≥|c|−1 So a2+4b=c2 implies either b=0, either |b|≥|a|−1 and |b|≥|c|−1
10.10.2015 03:25
Pco thank you a lot
03.12.2018 07:31
Can someone explain how f(u)=f(v) implies u=±v
03.12.2018 10:20
Plops wrote: Can someone explain how f(u)=f(v) implies u=±v Because f(u)=f(v) implies u2=f(f(u))2−4f(u)=f(f(v))2−4f(v)=v2
05.07.2019 02:43
What a Pathological problem. Here is a (long) solution with ewan. The solution set consists of three families: 1. f(x)≡x+1. 2. f(x)={x+1x≥C1−xx<Cfor some C≤0. 3. f(x)={x+1x>00x=01−xx<0. We break the solution into multiple parts. First is a useful lemma: Lemma 1: Consider the functional digraph of f. The only cycles that appears in it, if any, are 0→0 or 4→−4→0→4 (obviously not both)
Lemma 2: If f(a)=0, then a∈{−4,−1,0}.
Lemma 3: For all n, |f(n)|≥|n|−1 unless n=−4 and f(−4)=0.
Lemma 4: For |n| > 4, f(n) \in \{1-n, 1+n\}. Furthermore, if f(n) \neq 0, f(f(n))\neq 0, and |n| > 1, then f(n) \in \{1-n, 1+n\}.
Lemma 5: For n \geq 1, f(n) = n+1.
Lemma 6: The only cycle possible is 0\to 0 and if f(a) = 0, then a\in \{-1, 0\}.
Lemma 7: For n < 0, if f(n) = n+1, then f(n+1) = n+2.
Lemma 8: For all n \neq 0, f(n) \in \{1-n, 1+n\}. Also, f(0) \in \{0, 1\}.
Lemma 9: If f(0) = 0, we obtain family 3.
Lemma 10: If f(0) = 1, we obtain families 1 and 2.
Thus we have obtained the desired families of solutions.
06.06.2020 04:27
Solution with awang11 and stroller. For fun, we shall provide a series of 9 claims that will give the solution easily. And of course, we shall appreciate the pure bashiness of the problem by letting all claims to be exposed fully. No hide tags! Claim 1. For any chain a_0=n,a_1=f(n),\ldots, we have a_{n-2}^2+4a_{n-1}=a_n^2Proof. Just use the functional equation and substitute into the recurrence. This is quite literally from the definition. Claim 2. f(m)=f(n)\implies m=\pm n. Proof. Substituting m and n, we get m^2=f(f(m))^2-f(m)=f(f(n))^2-f(n)=n^2 Claim 3. f(f(n))\equiv n\pmod 2. Proof. We note that f(f(n))^2=4f(n)+n^2\equiv n^2\pmod 2 Claim 4. f(0)\in\{0,1,4\}. Proof. Let a_0=0 (and use Claim 1 for the rest of the a_i). Then, we get that a_2=\sqrt{4a_1}, so a_1=a^2 for some a\in\mathbb Z^+. Now, this means a_2=\pm 2a, so thus a_3^2=a^4\pm8a. Now, we note that we can easily bound if a\geq 4, then if a_3^2=a^4+8a, a^4<a_3^2<(a^2+1)^2(as 2a^2+1<8a in that range). Similarly, we get if a_3^2=a^4-8a, then (a^2-1)^2<a_3^2<a^4(as 2a^2+8a>1). Thus, we see that a=0,1,2,3, but a=3 gives 3^4\pm3\cdot 8=57,105, which isn't a perfect square. Thus this gives the current solutions. Claim 5. f(1)=2. Proof. Define a_0=1 and then we get that as a_0\equiv a_2\pmod 2, we have a_2=\pm(2a+1) for some a\geq 0. Furthermore, this implies that a_1=\frac 14(a_2^2-a_0^2)=a^2+aNote a\neq 0 as then we get that 1^2+4f(1)=f(f(1))^2, so f(0)=1, and then we get that 0^2+4f(0)=f(f(0))^2, so 1=4, absurd. For the sake of contradiction, let a>1. Thus, we get a_3^2=a^4+2a^3+a^2\pm (8a+4). Now, we note the very useful result (a^2+a)^2=a^4+2a^3+a^2, (a^2+a+2)^2=a^4 + 2 a^3 + 5 a^2 + 4 a + 4, and (a^2+a-2)^2=a^4 + 2 a^3 - 3 a^2 - 4 a + 4. Thus, if we use the + from the \pm in a_3, then we get that (a^2+a)^2<a_3^2<(a^2+a+2)^2Thus, we get a_3^2=(a^2+a+1)^2 but as a_3\equiv a_1 is even and a^2+a+1 is odd, we get a contradiction. Similarly, if we take the - from the \pm, we get (a^2+a-2)^2<a_3^2<(a^2+a)^2Thus, we get a_3^2=(a^2+a-1)^2 but as a_3\equiv a_1 is even and a^2+a-1 is odd, we get a contradiction. Thus, we have a=1, so thus f(1)=2. Claim 6. f(2)=3. Proof. We note that 9=1+4f(1)=f(f(1))^2=f(2)^2In particular, we have that f(2)=\pm 3. If f(2)=-3, then we achieve a contradiction as -8=4+4f(2)=f(f(2))^2=f(-3)^2 Claim 7. f(n)=n+1 on the positive numbers. Proof. We shall induct on n. Note that f(n)^2 = 4n + f(n-2)^2 = (n+1)^2 \implies f(n) = \pm (n+1)Now suppose f(n) = -n-1, then 4f(n) + f(n-1)^2 = 4(-n-1) + n^2 = n^2 - 4n -4is a perfect square f(n+1)^2. However, n^2-4n+4 is a perfect square. Thus, we see that (n-2)^2-f(n+1)^2=8, which implies n=5 (or -1, but then n+1=-(n+1)=0 so it doesn't matter). However, if f(5)=-6, then we have f(-6)=\pm 1. f(-6)\neq 1 (as otherwise we get 40=(-6)^2+4\cdot 1=f(1)^2=4 absurd) so f(-6)=-1. And then we can derive contradiction as f(-1)^2=36\pm 4=40. Claim 8. f(n)=1\pm n for negative n. Proof. We note that first f(-1) has to be nonnegative (as 1+4f(-1)=f(f(-1))^2\geq 0), so thus f(-1)=0,1,2 by the semi-injectivity of f. However, we also have that if f(-1)=1, then f(f(-1))\neq 2, a contradiction. Thus, we get f(-1)=0,2. Now, assume n\leq -2. We note that |f(n)|=\frac 14|f(f(n))^2-n^2|\geq\frac 14|(n\pm 2)^2-n^2|\geq |n|-1as we have f(n)=0 if and only if n=-1,0 and f(f(n))\equiv n\pmod 2. If f(n)\geq 0, then we note that the semi-injectivity of f implies f(n)=0,1,1-n, but we can check 1 doesn't work as 4=f(1)^2=f(f(n))^2=4+n^2\implies n=0and the only roots of f are -1,0. Now, we shall assume f(n) is negative, so f(n)\leq 1+n. If f(n)<1+n, then we get |n|-2\leq |f(n)|-1\leq |f(f(n))|=\sqrt{4f(n)+n^2}<\sqrt{n^2+4n+4}=\sqrt{|n|^2-4|n|+4}=|n|-2a contradiction. Thus, f(n)=1+n if it is negative. Claim 9. f(n)=n+1 implies f(n+1)=n+2 for any n\in\mathbb Z. Proof. It suffices to show for n<0. We note that f(n+1)^2=f(f(n))^2=4f(n)+n^2=(n+2)^2\implies f(n+1)=\pm(n+2)If f(n+1)=-(n+2), then we note that f(-n-3)=-n-2. Thus, if n\leq -4, we get that f(-n-3)=f(n+1), a contradiction. Now, we take cases for n\in\{-3,-2,-1\}. If n=-3, then we get that f(-2)=\pm 1. If f(-2)=1, then we get 4=f(1)^2=f(f(-2))^2=4f(-2)+4=8absurd. Similarly, if n=-2, then f(-1)=0. If n=-1, then we get f(0)=\pm 1. If f(0)=-1, then 0=f(-1)^2=f(f(0))^2=4f(0)+0=-4absurd. This finishes the claim. Now, it's time for the ending. Note that f(0)=4 combined with f(3)=4 and Claim 2 all come to show 0=\pm 3. Thus, f(0)=0,1, from which we get f(x)=x+1f(x)=\begin{cases}x+1&x\geq c\\1-x&x<c\end{cases}\qquad c\leq -1f(x)=\begin{cases}x+1&x>0\\1-x&x<0\\0&x=0\end{cases}as if f(0)=0, then we can never have f(x)=1+x for x<0 (otherwise we induct with our last claim to get f(0)=1).
16.08.2020 17:33
We claim that the only f which work are: f(x)=x+1, f(x)=\begin{cases}1-x&\text{ when } x<a\\x+1&\text{ when } x\ge a\end{cases}, and f(x)=\begin{cases}1-x&\text{ when } x<0\\0&\text{ when } x=0\\x+1&\text{ when } x>0\end{cases}. First, consider f(0), which must be k^2 for some k\ge 0. We need 0\to k^2\to \pm 2k, so k^4 \pm 8k must be a perfect square. If we take the positive sign, note that the next square of the same parity of k^4 is k^4+4k^2+4\implies 2k\ge k^2+1\implies k\le 1. Note that k=0,1 both yield a perfect square. On the other hand, if we take the negative sign, we need 2k\ge k^2-1\implies k\le 2. k^4-8k is only a square in this range when k=0,2. Hence, function f must satisfy one of the three cases: 0\to 0, 0\to 1 or 0\to 4\to -4\to 0. Similarly, we now investigate f(1). We have that f(1)=k^2-k for some k\ge 1. So, this time we need (k^2-k)^2\pm 8(2k-1) to be a square. First considering the + case, we use the exact same bounding as before to get 2k-1\ge k^2-k+1\implies k^2-3k+2\le 0\implies k\le 2. So, in this case, we only have k=1,2 work. On the other hand, the - case gives 2k-1\le k^2-k-1\implies k\le 3. Here, we get that k=3 works. Hence, we have f must satisfy one of the three cases: 1\to 2, 1\to 0\to 1, or 1\to 6\to -5. To eliminate the second case, note that we should have 4f(0)=f(f(0))^2, but this yields 4=0, which is a contradiction. On the other hand, if we consider the third case, note f(f(6))=\pm 4, but 25+4f(f(6)) must be a square, so f(f(6))=-4. Hence, 1\to 6\to -5\to -4. We can continue this inductively to get 1\to 6\to -5\to -4\to -3\to -2\to -1\to 0. Now, from our casework on 0, we know that either 0\to -1, 0\to 1, or 0\to -4. All three of these cases yield loops in this chain which easily fail. Hence, the third case is impossible as well and we must have 1\to 2. Now, we claim that when 1\to 2 occurs, we must have f(n)=n+1 for all n>0. We can prove this by induction with base cases n=1,2. In particular, for the inductive step, we have f(n)^2=4n+(n-1)^2=(n+1)^2\implies f(n)=\pm(n+1). But, if f(n)=-(n+1), then plugging in n into the assertion gives f(f(n))^2=n^2-4(n+1)=(n-2)^2-8, which is never a square unless n=5. So, the only case where our induction might fail is at n=5. In this case, we get 1\to 2\to 3\to 4\to 5\to -6. The next term is \pm 1, but 36\pm 4 is not a perfect square. Hence, this case is not possible and we have f(n)=n+1 for all n>0. Note that this eliminates the 0\to 4\to -4\to 0 case. Now, consider some k<0. If f(k)\ge 1, then f(f(k))=f(k)+1, so k^2=(f(k)-1)^2, and k=1-f(k). If f(k)>0, suppose there exists some a such that f(a)=k. Then, we have that a^2+4k=(1-k)^2\implies a^2=k^2-6k+1. However, this is not a square for k=-1, and for k<-1, note that k^2-4k+4<k^2-6k+1<k^2-6k+9. Hence, a never exists. So, if a negative goes to a positive number, it is a leaf on our arrow graph. On the other hand, if k\to a for some a<0, we claim that |a|<|k|. If we suppose the contrary, then k^2+4a<(k+2)^2. We can't have f(a) is positive, since we established earlier that then k would not exist. So, k+2<f(a)<0. Hence, (a+2)^2<a^2+4f(a)<a^2, which is a contradiction. Hence, we have that |f(k)|<|k| for negative k. In fact, by similar bounding, we have that f(k)<0\implies f(k)=k+1. If f(k-1)=k, then k is now part of a chain and not a leaf, so by earlier logic, f(k)=k+1. Now, we consider the smallest value of k<0 for which f(k)=k+1. If such a value doesn't exist, we either have that such values are unbounded, or don't exist. In the former, note that if f(x)=x+1 for any small x, we get x\to x+1\to x+2\to\ldots, so x is unbounded implies f(x)=x+1 for all x<0. For the latter, this just means that f(x)=1-x for all x<0. On the other hand, if m is the smallest value for which f(m)=m+1, note that we get the chain m\to m+1\to m+2\to\ldots, so f(x)=x+1 for m\le x<0. And, if x<m, we must have f(x)=1-x. To finish, note that in the 0\to 1 case, we can choose m arbitrarily and get the first and second cases. On the other hand, when f(0)=0, if m exists, then -1\to 0\to 0, which is a contradiction. Hence, f(x)=1-x\forall x<0, leading to the third class of solutions. This exhausts all cases, and hence the three aforementioned classes of solutions are the only ones.
22.08.2020 13:35
hajimbrak wrote: Find all functions f : \mathbb{Z} \to\mathbb{ Z} such that n^2+4f(n)=f(f(n))^2 for all n\in \mathbb{Z}. Proposed by Sahl Khan, UK What a monstrosity! We claim that all dolutions are of the form \boxed{f(x) = 1 + x \cdot \frac{x - a}{\mid x - a \mid}} for all x \neq a and \boxed{f(a) = 1 + a} for all integers x and for some non-negative integer a and \boxed{f(x) = 1 + x\cdot \frac{x}{\mid x \mid}} for all reals x \neq 0 and \boxed{f(0)= 0}. Step 1 : Some 'prerequisites' as such. Let P(n) be the assertion of the problem. P(0) \implies f(f(0))^2 = f^2(0)^2 = 4f(0). Now see that P(f^k(0)) \implies f^{k+2}(0)^2 = f^{k}(0)^2 + 4f^{k+1}(0) and we see thatf^2(0) = 2\sqrt{f(0)} which means that f(0) is a perfect square. Now, f^3(0)^2 = f(0)^4 \pm 8f(0). If f^3(0) = f(0)^4 + 8f(0), we get that f(0)^4 \leq f^3(0)^2 = f(0)^4 + 8f(0) \leq (f(0)^2+1)^2 and if f^3(0)2 = f(0)^4 - 8f(0), then (f(0)^2-1)^2 \leq f^3(0)^2 = f(0)^4 - 8f(0) \leq f(0)^4 and simply solving these equations over integers yield that \boxed{f(0) = 0, 1, 4} are the only such values for f(0). Step 2 : The 'most difficult' process. We see that f(f(1)) \equiv 1 \pmod{2} using P(1). We see that similar to the way we solved for f(0), we solve for f(1) and get that f^2(1) = \pm (2t + 1) where t is integer and also observe that f(1) = t^2 + t and we see that t \neq 0 or it yields a contradiction, so without loss of generality let t be positive as it doesn't matter much such that t \neq 1 for now. therefore f^3(1)^2 = t^4 + t^3 + t^2 \pm (8t+4) and so if we have f^3(1) value with +(8t+4), we'll yield that f^3(1)^2 lies between (t^2+t)^2 and (t^2+t+2)^2 easily which means that f^3(1)^2 = (t^2+t+1)^2 \equiv f(1)^2 \pmod{2}, a contradiction since f(1) is even. So, t = 1 and hence using few verification, we find that f(1) = 2. I'll skip the proof for f(2) = 3 as my PC is overheating and will add later, but it is really similar to the way we solved f(0), f(1). Step 3 : Induction FTW Using induction on n+1 , we see that f(n+1) = \pm (n +2) using P(n) and so, if f(n+1) = - n - 2 we would have that using P(n) that f(n+1)^2 - (n+2)^2 = -8 which is a easily handle-able case which yields contradiction nevertheless. Now, f(n) = n+1 for all positive reals. (which shows that f(0) \neq 4. Using P(-1) we conclude that f(-1) \in \{ 0, 2 \} by using basic simplifications. If f \leq -2, then P(2) \implies \mid f(n) \mid \geq \mid n \mid + 1. But using the fact that f(u) = f(v) if and only if u = \pm v yields that \mid f(n) \mid \geq 1. But we see that if f(n) = n + 1 for some n implies f(k) = k + 1 for all k \geq n, because if f(k) = -(k+1) for some k > n, we get f(-k -3) = f(k - 1) = -k- 2 which then boils down to three cases - n = 0, 1, 2, 3 all of which can be handled swiftly. So, we have our desired results using all above results, which, I in the first line wrote it in the lazy form or in other words the form which I haven't derived in the same way but writing it like that saves my time. Also sorry for a rushed proof and I'll redesign it later (I might forget my arguments so posted the dolution immediately)
26.08.2020 03:48
29.12.2020 01:01
Here are some steps for a more NT flavored solution. Step 1: Note that any solution (x,y,z) to x^2+4y=z^2 is of the form (a-b,ab,a+b). so f(n) = b_n(n+b_n) \ \ \ \ \ \text{and} \ \ \ \ \ f(f(n))=n+2b_nFor some sequence b_n of integers. Step 2: The pair (x,y)=(b_n,b_{f(n)}) solves the equation: y^2 + yx(n+x) - [x+(n+x)] = 0This follows immediately from step 1 applied to the integers n and f(n). Step 3: The previous quadratic equation can be solved (think about the discriminant) to deduce that for all n\in \mathbb{Z}, b_n has to be one of the following possibilities: 1, 1-n, -\frac{n}{2}, -n , 0Step 4: Deduce that f(n) is 1+n or 1-n, unless n=0, it's possible to have f(0)=0. Step 5: Now it's easy to describe all solutions.
20.08.2022 07:14
In a way, it's a kind of meditation. Apply the condition to 0, f(0) to yield a classical square difference bound on f(f(0)), giving three cases after continuous application of the condition on f^k(0): Case A: f(0) = 0 Case B: f(0) = 1, f(n) = n+1 for all n \geq 0 Case C: f(0) = 4, f(4) = -4, f(-4) = 0 Call a number such that f(n) = n+1 a flower and a number such that f(n) = -n+1 a tomato. Notice that if f(n) is a flower then f(n) is either a flower or a tomato by equation solving. Notice that if f(n) is a tomato, then f(n) = 0 or f(n) = 6 by square bounding and euclidean algorithm. Now consider Case B. Notice that for a negative number n, if f(n) is negative then f(f(n)) is positive or f(f(n)) > n, and f is strictly increasing on nonnegative numbers, hence f(f(n)) > n for all n. Thus we induct down starting from -1. f(f(-1)) is a flower and f(-1) is not a tomato so f(-1) is a flower so f(-1) is either a flower or tomato. The condition is that all numbers above a number are either a flower or a tomato. Clearly the identical argument holds as we induct down, and f(i) must be a tomato if f(i+1) is a tomato, so we get the following valid solution sets: f(x) = \begin{cases} x+1 & x \geq c \\ -x + 1 & x < c \end{cases} for some c \leq 0 if there exists a tomato, and f(x) = x+1 if all integers are flowers. Call these solutions tranquil. We now look for nontranquil solutions. Again, we apply classical square difference bounding to the value of f(f(-1)) by applying the condition to -1, f(-1), then get the following cases after continuous application of the condition on f^k(-1): Case X: f(-1) = 0, f(0) = 1, all nonnegative integers are flowers. Case Y: f(-1) = 2, f(2) = 3, all integers at least two are flowers. Case Z: f(-1) = 6, f(6) = -5, f(-5) = -4, f(-4) = -3, f(-3) = -2, f(-2) = -1, f(-1) = 0. Notice that Case X implies tranquility as it implies Case B. Furthermore notice Case Z is not compatible with neither Case A, B, or C, since in Case A the condition fails for -1, in Case B -1 is neither a flower or a tomato, and in Case C f(-4) = 0. Finally, consider case Y. Notice f(1) = 0 violates the condition for 1, so f(f(1)) > 1 for the same reason as in Case B and 1 cannot be a tomato, so 1 is a flower. Furthermore, no element maps to 0 since it would violate the condition on that element, so the same argument as in Case B applies, giving us that f(1) = 2, f(-1) = 2, and by inducting down, all negative numbers are tomatoes. This nets the final valid and nontranquil solution: f(x) = \begin{cases} x+1 & x > 0 \\ 0 & x = 0 \\ -x + 1 & x < 0 \end{cases} And we are done. \blacksquare
22.10.2022 14:32
Let f(f(n))^2=n^2+4f(n) be eq.(*). First, f(f(1)) is odd. For k\geqslant 0, let f(f(1))=\pm 2k \pm 1. Whence f(1)=k^2+k. If k=0, then f(0)=1 (since by (*) f(0)\geqslant 0), and contradiction by (*). If k>1, then (*) for f(1) implies f(f(f(1)))^2 \in \{ (k^2+k+1)^2, (k^2+k-1)^2\}. This is absurd, since k^2+k has same parity as f(f(f(1))). So k=1 and f(1)=2, so f(2)=\pm 3 and (*) gives f(2)=3. By induction, f(n)=\pm (n+1) for all n>0. If f(a)=-a-1 for some a>1, then (*) gives a=5, so f(5)=-6 and f(-6)=\pm 1. Again contradiction from (*) for -6. Thus, f(n)=n+1 for all n>0. Since f(0)\geqslant 0, we have f(0)=0 or f(f(0))=f(0)+1. The latter in (*) implies f(0)=1. If f(0)=0, then f is injective at 0. Also f(-1)\geqslant 0, and similarly f(-1)\in \{0,2\}. Let x<-1. If f(x)>0, then f(f(x))=f(x)+1 and so f(x)=1-x. Clearly f(x)=0 yields a contradiction. If f(x)<0, then (*) implies f(x)\leqslant x+1, which easily gives f(x)=x+1. So for any x<0, f(x)=\pm x+1. If for some m<-1, f(m)=m+1, then inducting we get f(n)=n+1 for all n\geqslant m and f(n)=1-n else. So the solution is: f(n)\equiv n+1 or for some m<0, f(n)=\begin{cases} 1+n & \text{for } n\geqslant m \\ 1-n &\text{for } n<m\end{cases}or maybe, f(n)=\begin{cases} 1+n &\text{for } n>0 \\ 1-n &\text{for } n<0 \\ 0 &\text{else} \end{cases}All of these work.
22.07.2023 04:13
Define a chain as a sequence of distinct integers a_1, a_2, \dots such that a_i^2 + 4a_{i+1} = a_{i+2}^2 and a_{i+1} is completely determined by a_i. The functional digraph of f is then composed of such chains. Claim: f(f(n)) \equiv n \pmod{2}. Likewise, a_i \equiv a_{i+2} \pmod{2} in a chain. Proof. Immediate. \blacksquare Claim: f(n) = n + 1 for n \ge 1. Proof. We claim that only the chain beginning at 1 is 1, f(1) = 2, f(f(1)) = 3, \dots. Suppose that 1, f(1), f(f(1)), \dots is a chain. Then f(f(1)) must be a odd integer, and f(1) = \frac{1}{4}(f(f(1))^2 - 1). Furthermore, one of f(1)^2 \pm 4f(f(1)) must be a perfect square. This can only hold if f(f(1)) \ge f(1) - 1 due to the difference of consecutive squares. f(f(1)) \ge \frac{1}{4}(f(f(1))^2 - 1) - 1 only holds for |f(f(1))| \le 5. The only possible chains start out as then 1, 0, \pm 1, \dots, 1, 2, \pm 3, \dots, 1, 6, \pm 5, \dots. It turns out that choosing the sign of each number while building the chain is forced, so we end up with the following result. The first case becomes 1, 0, 1, 2, and thus can't be a chain. The second case becomes 1, 2, 3, \dots as desired. The final case becomes 1, 6, -5, -4, -3, -2, -1, 0, 1, 2, and thus can't be a chain. \blacksquare Claim: f(0) \in \{0, 1\}. Proof. Consider the possible chains starting with a_1 = 0 in the digraph. f(0) must then be equal to \frac{1}{4} \cdot f(f(0))^2 and is thus a perfect square. First assume f(f(0)) = 0. This implies a_2 = 0, giving the chain 0, 0, 0, \dots. Next, assume f(f(0)) \ne 0. This implies in turn that f(0) > 0, so it must hold that f(0) + 1 = f(f(0)), or that \frac{1}{4} \cdot f(f(0))^2 + 1 = f(f(0)) which only holds if f(f(0)) = 2, giving the only other chain of 0, 1, 2 \dots. \blacksquare Claim: f(-1) \in \{0, 2\} Proof. First consider the chain -1, f(-1), f(f(-1)) \dots. f(-1) \ge 0 must follow since -1 + 4f(-1) = f(f(-1))^2. Since f(-1) + 1 = f(f(-1)), it must follow that f(-1) \in \{0, 2\}. \blacksquare Claim: For x < 0, f(x) = 1 \pm x. Proof. Consider potential chains x, f(x), f(f(x)), \dots such x \le -2. If f(x) > 0, then f(f(x)) = f(x) + 1, so x^2 + 4f(x) = (f(x) + 1)^2 implies that 1 - x = f(x). Note that this claim is independent of the induction. If f(x) = 0, this implies that x = -1. Else, assume f(x) < 0. If f(f(x)) \ge 0 holds as well, this implies that f(f(x)) = 1 - f(x) which means that x^2 = f(x)^2 - 6f(x) + 1 which is a contradiction by difference of squares. Thus, f(f(x)) < 0 holds as well. By repeating this, it follows that the chain x, f(x), f(f(x)), \dots is negative until -1 and then 0 occurs. It must also terminate similarily. We can then induct backwards to get that the chain is an AP with common difference 1. \blacksquare Claim: If f(n) = n + 1, then f(n + 1) = n + 2. Proof. Follows since f(n + 1) = f(f(n)) and then the assertion. \blacksquare Thus, we can now fully classify f. First assume that f(0) = 1. Let c \le 0 be minimal such f(c) = c + 1. If no such c exists, then f(x) = x + 1 works. Else, f(x) = \begin{cases} 1 + x & x \ge c \\ 1 - x & x < c \end{cases} which can be seen to work. Else, suppose f(0) = 0. This implies that f(-1) = 2, which forces f(x) = \begin{cases} 1 + x & x > 0 \\ 0 & x = 0 \\ 1 - x & x \le 0 \end{cases} and also works.