Find all functions $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ (where $\mathbb{Z}^+$ is the set of positive integers) such that $f(n!) = f(n)!$ for all positive integers $n$ and such that $m-n$ divides $f(m) - f(n)$ for all distinct positive integers $m, n$.
Problem
Source: 2012 USAMO #4
Tags: function, induction, factorial, modular arithmetic, algebra, 2012 USAMO, number theory
26.04.2012 01:03
26.04.2012 01:07
i forgot f(n) = 2 case. how many points would i lose?
26.04.2012 01:17
26.04.2012 01:18
u'll probably get like 2-3 at least u got some points from this question don't worry (dangit i fail)
26.04.2012 01:20
wait, so i forget one trivial case and i lose 4-5 points?
26.04.2012 01:21
Remark that $f(1) = f(1)! \implies f(1) = 1,2$ Similarly $f(2) = 1,2$. Define $!^nk$ recursively as $!^nk = (!^{n-1}k)!$ and $!^0k = k$. Remark the $!^nk$ is just taking the factorial of $k$ $n$ times. Case 1: $f(n) < n$ for some $n \ge 3$ Then $(!^mn - 1)|(f(1) - !^mf(n))$ However, as $m$ tends to infinity we have $|!^mn - 1| > |f(1) - !^mf(n)|$, a contradiction unless $f(1) - !^mf(n) = 0 \implies f(n) = f(1) = 1,2$. But then remark that $(!^mn - z)|(f(z) - !^mf(n))$ for any $z$, giving similarly $f(z) = f(n)$ and therefore we have $f$ is a constant function which either evaluates to $1$ for all $n$ for to $2$ for all $n$. From now on we take $f(n) \ge n$ for $n \ge 3$. Therefore $f(n) \ge n$ for each $n \ge 3$. Case 2 : $f(1) = 2$ Then we have $(n-1)|(f(n) - 2)$ for each $n$. Let $n = (p-2)!$, then we have $((p-2)! - 1)|(f(p-2)! - 2)$. But remark that $(p-2)! \equiv 1 \pmod{p}$, so we must have $f(p-2)! - 2 \equiv 0 \pmod{p}$. This requires $p \nmid f(p-2) \implies f(p-2) = p-2,p-1$. But neither of these work for sufficiently large primes $p$, therefore we have reached a contradiction so $f(1) = 1$. Remark that $((p-2)! - 1)|(f(p-2)! - 1)$ where $p$ is prime. As $p$ divides the left thing we know $p-2 \le f(p-2) < p$. If $f(p-2) = p-1$ then the right thing is $-2 \pmod{p}$, contradiction. Hence $f(p-2) = p-2$. In particular, $f(5-2) = 3$. Claim : $f(n) = n$ for all $n$. Remark that $(!^m3 - x)|(!^m3 - f(x))$ for each positive integer $x$. But as $m$ grows large the only way this is possible is if $f(x) = x$, and hence all functions are $\boxed{f(x) = 1, f(x) = 2, f(x) = x}$.
26.04.2012 01:23
26.04.2012 01:31
I did it differently with $<1$ minute to spare! Brief outline: $f(n)\leq n$ for all $n\geq 2$! Then do casework on the value of $f(3)$!
26.04.2012 01:36
I did it differently with $>1$ minute to spare! Brief outline: Do casework on the value of $f(3)$!
26.04.2012 01:47
Don't you mean $f(x)\ge x$?
26.04.2012 02:01
Your solution has $f(x)\leq x$ for all $x\geq 3$ for each function you have.
26.04.2012 02:07
$f(x)=1$, $2$ are special cases. For the rest, $f(x)\ge x$ is true, which should be obvious by my first example. We are probably both right, since I said $f(x)\ge x$ but then proved that $f(x) \not > x$, which implies $f(x)=x$.
26.04.2012 06:21
Here's my solution, basically in the jumbled order i wrote it. Is it a 7?
Sorry it's drawn out, but if someone could verify it it'd be great
26.04.2012 06:26
Problem: By your reasoning, you haven't ruled out the case that subcase 1 (your last part) holds for some $x$ and subcase 2 holds for some other values of $x$.
26.04.2012 14:55
awww My bad. How many points off? I knew that was shaky but i had trouble putting it in words. Would this have been better?
26.04.2012 17:41
If you assume $f(n)=kn$ for some $n$, why is $f(n!)=kn!$ necessarily true?
26.04.2012 20:45
superpi83 wrote: Then $f(3!)=3!$, $f((3!)!)=(3!)!$, $f(((3!)!)!)=((3!)!)!$, and so on, meaning there are arbitrarily large $m$ such that $f(m)=m$. Another way to show this fact (which is admittedly less simple than superpi83's method) is to use Wilson's Theorem, which means that \[p | (p - 2)! - 1 | f(p - 2)! - 1,\] so $f(p - 2) < p$, and then use bounding from the divisibility relation above to prove that $f(p - 2)$ must necessarily be $p - 2$.
28.04.2012 02:23
On a random note, the key idea in the most general solution to this problem seems to have a lot of harder variants. It would be amusing if someone won a tiebreaker by posing and solving one of these extensions, e.g. "Find all $f:\mathbb{N}\to\mathbb{N}$ such that $\gcd(m,n)=1\implies \gcd(f(m),f(n))=1$ and $m-n$ divides $f(m)-f(n)$ for all distinct positive integers $m,n$." (Originally posted here.)
02.09.2012 09:46
Case 1: $f$ is a constant function. Easy to prove that $f(n)=1$ for all positive integers $n$ or $f(n)=2$ for all positive integers $n$. Case 2(a): $f(n)=a$ for infinitely many positive integers $n$, but $f$ is not a constant function. then $m-n|f(m)-a$ for infinitely many positive integers $n$, and if we let $m$ be such that $f(m)$ is not $a$, we have a contradiction. Case 2(b): There is no positive integer $a$ such that $f(n)=a$ for infinitely many positive integers $n$. Then for every positive integer $k$ there exists $n \ge k$ such that $f(n) \ge k$ and since $f(n!)=f(n)!$, there exists a positive integer $b$ such that $k|b$ and $k|f(b)$. Thus $k|f(n)$ for all $k|n$ by the second condition. Hence $n|f(n)$ for all positive integers $n$. Letting $n=2$ in the first condition gives $f(2)=1$ or $2$ but $2|f(2)$ so $f(2)=2$. Then $m!-2|f(m)!-2$ for all positive integers $m$ so $4|f(3)!-2$ and it follows that $f(3)=3 \implies f(6)=6 \implies f(720)=720$ etc. so $f(n)=n$ for infinitely many positive integers $n$. Let $m$ be any positive integer. Thus for infinitely many $n$, $m-n|f(m)-n$, so for infinitely many $n$, $m-n|f(m)-m$ which implies that $f(m)=m$ for all positive integers $m$.
04.04.2022 17:33
The answer is $f \equiv 1$, $f \equiv 2$, and $f(x)=x$. Clearly we have $f(1)=f(1)!$ and $f(2)=f(2)!$, hence $f(1),f(2) \in \{1,2\}$. Clearly, we have $$n! \mid m!-n! \mid f(m!)-f(n!)=f(m)!-f(n)!.$$If $f(n)<n$, it follows that $f(m)=f(n)$ for all $m>n$, so $f$ is thereafter constant. If $f$ is eventually constant at some value $c$, we must have $c!=c \implies c=1,2$. But then, for all $y$, we have $x-y \mid c-f(y)$ for large enough $x$, implying $f(y)=c$ for all $y$, yielding $f \equiv 1$ or $f \equiv 2$. Henceforth suppose $f(n) \geq n$ for all $n$. Note that we have $$n\cdot n!=(n+1)!-n! \mid f(n+1)!-f(n)!.$$If $f(1)=f(2)=2$, I claim that $f(3)=2$, which implies that $f \equiv 2$ by the above results. Indeed, we have $$4=2 \cdot 2! \mid f(3)!-2 \implies f(3)! \equiv 2 \pmod{4},$$so $f(3)=2,3$. If $f(3)=3$, then $3-1 \mid f(3)-f(1) \implies 2 \mid 1$, which is incorrect, hence $f(3)=3$. If $f(1)=1$, $f(2)=2$, I claim that we have $f(n)=n$ by induction, with the base case of $n=1,2$ already shown. Suppose we have $f(n)=n$. Then we have $$f(n+1)! \equiv n! \pmod{n\cdot n!},$$so $f(n+1)<2n$, else $n \mid 2n \mid \tfrac{f(n+1)!}{n!}$. Further, we have $$n=(n+1)-1 \mid f(n+1)-f(1)=f(n+1)-1,$$hence $f(n+1) \equiv 1 \pmod{n}$. Combining these, it follows that $f(n+1)=n+1$, completing the induction. Combining all of these possibilities, it follows that the only possibilities are $f \equiv 1$, $f \equiv 2$, and $f(x)=x$, as desired. $\blacksquare$
22.06.2022 15:39
$f(1)=f(1)!$ and $f(2)=f(2)!$ so $f(1),f(2)\in \{1,2\}.$ Denote the second condition by $P(m,n).$ We do casework. A. $f(2)=1:$ Then $P(m!,2)$ gives $m!-2| f(m)!-2$ we can easily get $f(m)=1$ for all $m\geq 3.$ Then $P(m,1)$ gives $f(1)=1.$ So $f\equiv 1$, clearly works. B. $f(1)=f(2)=2:$ Then $P(3!,1!)$ implies $f(3)=2.$ Then we easily get from $P(m!,3!)$ that $f(m)=2$ for all $m\geq 4.$ So $f\equiv 2,$ clearly works. C. $f(1)=1$ and $f(2)=2:$ Then combining $P(3!,1!)$ and $P(3!,2!)$ we get $f(3)=3.$ Assume $f(m)=m$ for some $m\geq 3.$ Then $P(m,n)$ gives $m-n\mid f(n)-n.$ But note that we have $f(m!)=m!, f((m!)!)=(m!)!,\dots.$ So we make $m$ large so that $f(n)=n,$ clearly works.
24.06.2022 13:08
Hi, im taking a contest in a couple of days, so if someone could check my solution writing, that would be great. Consider $f(1)$ and $f(2)$. We know that $f(1)=f(1)!, f(2)=f(2)!$ which means that $f(1)=1,2; f(2)=1,2$ We now have 4 cases: Case 1: $f(1)=1,f(2)=1$ Claim: $f(3)=1$. Suppose otherwise. Let $f(3)=k$ for some $k\neq1$ We have $3-1=2|f(3)-f(1)$, in other words $f(3)$ is odd. However, at the same time $f(6)=k!$ and $6-2=4|f(6)-f(2)$. In particular, the latter gives us that $f(6)$ is odd, which is only true if $k=1$, which is a contradiction. Thus $f(3)=1$. Now we will show by induction that $f(x)=1$ for all $f(x)$. Clearly, if $f(k)=1$, then $f(k!)=1$. The base case of $f(1), f(2)$ is clearly true. Claim: If $f(k)=1$, then $f(k-1)=1$. Suppose otherwise. Now $f(k-1)\equiv1 mod t$ for all $t=1,2,... k-2$. Let $f(k-1)=p(k-2)!+1$ for some positive integer $p$. Now we have that $f(k!)=1$. In fact, we also have that $f((k!)!)=1$. In particular, for any integer $c$, we can find some value of $f(K)=1$ with $K>c$. Now, we have that $K-(k-1) | 1-(p(k-2)!+1) | p(k-2)!$ for some arbitrarily large integer $K$ with $f(K)=1$. However, it is easy to see that we can find some value of $K$ such that $(K-(k-1))>p(k-2)!$, such that the first cannot be a factor of the latter. This is a contradiction. Thus, $p$ cannot be a positive integer which means $p=0$, i.e. $f(k-1)=1$. Since $f(3)=1, f(6)=1, f(6!)=1,$ etc. then we can choose increasingly large values of $k$. Moreover, we can easily induct from $f((3!)..!)$ to $f((3!)..!)!)$. This completes the induction that $f(x)=1$, which is a solution when substituted. A similar argument can be applied for Case 2: $f(1)=2, f(2)=2$ to obtain that $f(x)=2$ which is clearly a solution. Case 3: $f(1)=2, f(2)=1$. Now we get that $3-1=2|f(3)-f(1)$ which means that $f(3)$ is even. However, $6-2=4|f(6)-f(2)$, in particular, $f(6)$ is odd. However, $f(6)=f(3)!$ and $f(3)$ is even which means $f(3)\ge2$, that is, $f(3)!$ is even which is a contradiction. Thus, there is no solution to this case. Case 4: $f(1)=1, f(2)=2$. Claim: $f(3)=3$. We have that $6-2=4|f(6)-f(2)$. In particular, this means that ${4}\nmid{f(6)}$ but ${2}\mid{f(6)}$ However, we realise that for each $k\ge4$, $4|4!|k!$. Thus, $f(3)\le3$. However, if $f(3)=1$, then $f(6)=1$ which contradicts ${2}\mid{f(6)}$. Thus $f(3)=3$. Now we will show by induction that $f(x)=x$. We will now use a similar argument to Case 1. Suppose for some $f(k)=k, f(k-1)=k-1$ Clearly, if $f(k)=k$, $f(k!)=k!$. Since $f(3)=3$, we can find arbitrarily large values of $k$ that satisfy $f(k)=k$ and thus we can induct from $f((3!)..!)$ to $f((3!)..!)!)$ Now it is clear that for some arbitrarily large value $((..(k!)!)..)!$, we have that $((..(k!)!)..)!-(k-1)|((..(k!)!)..)!-f(k-1)$ and since the $LHS > RHS$, we have a contradiction and this means that $f(k-1)=k-1$. Thus, the solution is $f(x)=x$ which works. The solutions are ${f(x)}\equiv{1}$, ${f(x)}\equiv{2}$ and ${f(x)}\equiv{x}$.
29.08.2022 05:23
The answers are $f(n)=1, f(n)=2, f(n)=n$ for all positive integers $n$ which clearly work. As usual, let $P(m,n)$ denote the assertion $m-n\mid f(m)-f(n)$. Since $f(1)=f(1)!,f(2)=f(2)!$, we have $f(1),f(2)\in\{1,2\}$. Case 1: $f(2)=1$ Consider a positive integer $n\geq 3$. $$P(n!,2):2\mid n!-2\mid f(n)!-1\implies f(n)!\text{ is odd}\implies f(n)=1$$If $f(1)=1$ then $f(n)=1$ for all positive integers $n$, as desired. But if $f(1)=2$ then we get a contradiction by plugging $P(3,1):2\mid f(3)-f(1)=1-2=-1$. Case 2: $f(2)=2$ We use the same idea. Let $p>69420$ be a large prime, so we don’t have to worry about annoying cases. $$P((p-2)!,1):p\mid (p-2)!-1\mid f(p-2)!-f(1)$$If $f(p-2)\geq p$ then $p\mid f(p-2)!$ so $p\mid f(1)$ as well but $f(1)$ is either $1$ or $2$ while $p>69420$, a contradiction. Hence, $f(p-2)\leq p-1$ for all sufficiently large prime $p$. Case 2.1: $f(1)=1$ $P(p-2,1):p-3\mid f(p-2)-1\implies f(p-2)\neq 2$ $P(p-2,2):p-4\mid f(p-2)-2\stackrel{f(p-2)\neq 2}{\implies} f(p-2)\geq p-2$ The possible values of $f(p-2)$ boil down to either $p-1$ or $p-2$. But it has to be in the form $(p-4)k+2$ too, so $f(p-2)=p-2$ for all sufficiently large prime $p$. $$P(p-2,n): p-2-n\mid p-2-f(n)\implies p-2\mid n-f(n)$$Choosing $p$ really large yields $n-f(n)=0$ so $f(n)=n$ for all positive integers $n$. Case 2.2 $f(1)=2$ Assume for the sake of contradiction that there exist prime $p>69420$ such that $f(p-2)\neq 2$. Then we can do the same as last case by plugging $P(p-2,2)$ to get $f(p-2)\geq p-2$, so $f(p-2)\in\{p-1,p-2)$. But both of them doesn’t satisfy both $P(p-2,1):p-3\mid f(p-2)-2$ and $P(p-2,2):p-4\mid f(p-2)-2$, a contradiction. Thus, $f(p-2)=2$ for all prime $p>69420$. $$P(p-2,n):p-2-n\mid 2-f(n)$$Choosing $p$ really large yields $2-f(n)=0$ so $f(n)=2$ for all positive integers $n$. I finally finish writing this… This write up took me almost 40 minutes because I can’t remember my sol
11.01.2023 03:03
Interesting solution I found which has not been mentioned before i think (mainly case 4) The solutions are $f(x)=x, f(x)=1, f(x)=2$, which obviously work. If we take $n=1,n=2$, we get $f(1), f(2) \in \{1,2\}$. We break it up into cases. Case 1: $f(1)=f(2)=1.$ Then for all $n,$ we have $f(n) \equiv 1 \pmod{n-1}$ and $f(n) \equiv 1 \pmod{n-2}$, so $f(n) \equiv 1 \pmod{(n-1)(n-2)}.$ But then $f(n)! \equiv 1 \pmod{(n!-1)(n!-2)}$ so $f(n)=1$ for all $n$ since $f(n)!$ has to be odd. Case 2: $f(1)=f(2)=2.$ We claim $f(3)=2$. With a similar argument as above, we have $f(3) \equiv 0 \pmod 2$ and $f(6) \equiv 2 \pmod {20},$ so $4\nmid f(3)!$ which means $f(3)<4$ or $f(3)=2.$ Then for $n>3$, we have $f(n)! \equiv 2 \pmod{\text{lcm}(n!-1, n!-2, n!-3)}$, so $3\nmid f(n)!$ which means $f(n) <3$. But since $f(n)$ is even, $f(n)=2$ as desired. Case 3: $f(1)=2,f(1)=2$. We find that $f(3) \equiv 0 \pmod 2$ and $f(6) \equiv 17 \pmod{20}$, but this is obviously impossible. Case 4: $f(1)=1, f(2)=2$. We prove by induction $f(n)=n$ for all $n$. The base case is $n=3$. We have $f(3) \equiv 1 \pmod 2$ and $f(3)!= f(6) \equiv 6 \pmod{20},$ so $f(3) <4$ and $f(3)=3$. Assume that $f(n)=n$ for $n\leq k$. Then we see that $f(k+1) \equiv i \pmod{k+1-i}$ for all $1\leq i \leq k$, so $f(k+1) \equiv k+1 \pmod{i}$ for all $1\leq i \leq k$. We can simplify this to $f(k+1) \equiv k+1 \pmod{\text{lcm}(1,2,\dots, k)}$. We also have $f(k+1)! \equiv (k+1)! \pmod{\text{lcm}(1,2,\dots, (k+1)!-1)}$. It is trivial to see that $\text{lcm}(1,2,\dots, k) \geq k+1$, so by Bertrand's postulate, there exists a prime $p$ such that $k+1 < p < k+1 + \text{lcm}(1,2,\dots, k) < (k+1)!$. This means $f(k+1)=k+1$, or else, we would have an unwanted prime factor in $f(k+1)!$ which would contradict the modulo statement ($p$ would divide $f(k+1)!$ and it divides the stuff inside the modulo, $\text{lcm}(1,2,\dots,(k+1)!-1)$, so it must divide $(k+1)!$ and it doesn't.)
11.01.2023 03:35
math154 wrote: On a random note, the key idea in the most general solution to this problem seems to have a lot of harder variants. It would be amusing if someone won a tiebreaker by posing and solving one of these extensions, e.g. "Find all $f:\mathbb{N}\to\mathbb{N}$ such that $\gcd(m,n)=1\implies \gcd(f(m),f(n))=1$ and $m-n$ divides $f(m)-f(n)$ for all distinct positive integers $m,n$." (Originally posted here.) What's a tiebreaker?
11.01.2023 04:07
because sometimes they take only a fraction of people who are exactly on the mop cut i think
14.04.2023 01:50
The solutions are $f \equiv 1, f \equiv 2$, and $f\equiv n$. The idea is to use Wilson's. Note that $f(1), f(2) \in \{1, 2\}$. Assume now that $f$ is nonconstant. Now $$p \mid (p-2)! - 1 \mid f(p-2)! - f(1)$$by the condition. Thus $p \nmid f(p-2)$, or $f(p-2) \leq p-1$. If $f(p-2) = p-1$, then $p \mid (p-1)! - f(1)$ or $p \mid 6$ by Wilson. Thus $f(p-2) \leq p-2$. On the other hand, $f(p-2) = p-2$ precisely for size reasons. This is enough to extend to all $f(n)$, because $$n-(p-2) \mid f(n) - n$$for all primes $p$, so $f(n) = n$.
09.07.2023 05:35
Note that $f(n) = f(n)!$ for $n = 1, 2$ so there are four cases. First suppose that $f(1) = 1, f(2) = 1$ Then $f(n) \equiv 1 \pmod{(n-1)(n-2)}$ and must be odd. Then, for $k \ge 3$, since \[ f(k)! = f(k!) \equiv 1 \pmod{2} \]it follows that $f(k) = 1$. Then, $f(x) = 1$ is a solution. Next, suppose $f(1) = 2, f(2) = 2$ Then $f(n) \equiv 2 \pmod{(n-1)(n-2)}$. Then, $f(3)! = f(3!) \equiv 2 \pmod{20}$ forcing $f(3) = 2$. Thus, for $k \ge 3$, $f(n) \equiv 2 \pmod{(n-1)(n-2)(n-3)}$ implies that $f(n) = 2$ Then, $f(1) = 1, f(2) = 2$. Then $f(n) \equiv n \pmod{(n-1)(n-2)}$. Similar to case two it follows that $f(3) = 3$ and $f(n) \equiv n \pmod{(n-1)(n-2)(n-3)}$. For each $n \ge 4$, we inductively claim that given $f(k) = k, \forall k = 1, 2, \dots n$, then $f(n + 1) = n + 1$. We have that \[ f(n + 1) \equiv n + 1 \pmod{\text{lcm}(1, 2 \dots n - 1, n)} \]However, \[ n \cdot n! = (n + 1)! - n! \mid f(n + 1)! - n! \]bounds that $f(n + 1) < 2n$, so the result holds and $f(n) = n$. Lastly, $f(1) = 2, f(2) = 1$ Then \[ f(n) \equiv 1 \pmod{n - 2} \]and \[ f(n) \equiv 2 \pmod{(n - 1} \]which means $f(6) \equiv 17 \pmod{20}$, contradiction and there are no solutions.
21.08.2023 04:55
Man this was quite hard for a p4, here is a summarized solution. Its easy to see $f(1), f(2) \in {1, 2}$. We proceed with casework Case 1: $f(1) = 1, f(2) = 2$. Note that since $6-1 | f(3)! - 1$ and $6-2 | f(3)! - 2$, we must have $f(3) = 3$. Thus $f((((3!)!)\dots)!) = (((3!)!)\dots)!$. Consider any $x = (((3!)!)\dots)!$. Then $x-m | x - f(m)$, so $$f(m) \equiv x\equiv x - (x-m) \equiv m \pmod{x-m}$$. Since there are infinite possible $x$, $f(m)-m$ has infinite distinct divisors, so $f(x) \equiv x$. Case 2: $f(1) = 1, f(2) = 1$. Then $m! - 2 | f(m)! - 1$, so if $m\geq 2$, $f(m)!$ is odd and thus $1$, so $f(x)\equiv 1$. Case 3: $f(1) = 2, f(2) = 2$. then we can write $f(m)! -2 = (m!-2)(m!-1)k$ by CRT. If $k$ is even, by taking $v_2$ of both sides $f(m) \leq 3$, and $f(m) = 1$ or $f(m) = 3$ are impossible. If $k$ is odd, then $f(m)! \neq 0 \pmod 3$, and thus $f(x)\equiv 2$. Case 4: $f(2) = 1, f(1)= 2$. Then since $m! - 2 | f(m)! - 1$, so if $m\geq 2$, $f(m)!$ is odd and thus $1$, so $f(m) = 1$ for $m\geq 2$. Now $m-1 | f(m)-2 = -1$, impossible. Our only solutions are $f(x) \equiv 1, f(x)\equiv 2, f(x)\equiv x$.
07.10.2023 14:11
Note that $f(1)=f(1)!$ and $f(2)=f(2)!$. So, $f(1),f(2)\in\{1,2\}$. Note that $f(3)$ and $f(1)$ must have same parity, while $f(6)=f(3)!\equiv f(2)\pmod{4}$. We solve the problem in four cases. Case 1) $f(2)=2$. Here, $f(3)!\equiv2\pmod{4}\Longrightarrow f(3)=2,3$. If $f(3)=2$ then for any $n>3$, $3\mid n!\Longrightarrow 3|n!-3$ and $n!-3\mid f(n)!-f(3)\Longrightarrow3\mid f(n)!-2\Longrightarrow f(n)=2$. Moreover, for any $n\geq2$, we have $n-1\mid2-f(1)$. So, $2-f(1)$ has infinitely many divisors, forcing $f(1)=2$. So, $f\equiv2$. Suppose $f(3)=3\Longrightarrow f(6)=6$. Define sequence $\langle a_n\rangle_{n\geq0}$ by the formula $a_{n+1}=a_n!$, taking $a_0=3$. Then, by induction we have that $f(a_n)=a_n$. Note that $a_n$ is not bounded above. Also, for any $m\notin\langle a_n\rangle$, we have $m-a_n\mid f(m)-a_n\Longrightarrow a_n-m\mid f(m)-m$. If $f(m)\ne m$, then we take $n$ such that $a_n>f(m)+2m$, and hence $f(m)+m\leq|a_n-m|\leq|f(m)-m|$, a contradiction. It means $f(m)=m$. Case 2) $f(2)=1$. We know that for any $n\geq2$, $2\mid n!\Longrightarrow 2\mid n!-2$ and $n!-2\mid f(n)!-1$, which means $f(n)!$ is odd, forcing $f(n)=1$. For any $n\geq2$, we have $n-1\mid1-f(1)$, which means that $1-f(1)$ has infinitely many factors, forcing $f(1)=1$. Therefore the only solutions are $f\equiv1$, $f\equiv2$ and $f\equiv \text{id}$ (identity function, i.e. $f(n)=n$). Verifying the solutions: if the function is constant $c$, then $c!=c$, which is satisfied when $c=1,2$. The property $m-n|f(m)-f(n)$ is satisfied as well, as $m-n\mid c-c=0$. if the function is identity, then $f(n!)=n!=f(n)!$, and $f(m)-f(n)=m-n$ which is divisible by $m-n$.
26.11.2023 06:15
Claim: If $f(2) = 1$, then $f(x) = 1$ for $x \geq 3$. Proof: Note that then for any positive integer $n\geq 3$, \[ n! - 2 \mid f(n!) - 1 = f(n)! - 1 \]If $f(n) \neq 1$ then we must have that an even number divides an odd number (as $f(n) \neq 2$ obviously), which is a contradiction. Thus, $f(n) = 1$ in this case. $\square$ Claim: If $f(1) = 2$, then $f(x) = 2$ for $x \geq 3$. Proof: for any positive integer $n\geq 3$, \[ n! - 1 \mid f(n!) - 2 = f(n)! - 2 \]Assume $f(n) \neq 2$. Note that then $f(n) > n$, so $f(n) \geq 4$. Then $n! - 1$ is odd and $f(n)! - 2 \equiv 2 \pmod 4$. For $n$ odd, $(n+1)(n! - 1) = f(n)! - 2$. However, this implies that $f(n) = n$ because $f(n) \geq n+1$ makes the RHS to large, but this is a contradiction. For $n$ even, then $(n+2)(n+1)(n! - 1) = f(n)! - 2$. But this implies that $f(n) = n+1$, and then $n+1 \mid 2$, contradiction. $\square$ To resolve $f(1)$ if $f(2) = 1$, just note that $f(1) \neq 2$ or else it contradicts that $f(x) = 1$ for $x \geq 3$. Then $f(1) = 1$. Similarly, if $f(1) = 2$, then $f(2) = 2$. Claim: If $f(1) = 1$ and $f(2) = 2$, then $f(x) = x$. Proof: For a positive integer $n \geq 3$, \[ n! - 1 \mid f(n!) - 1 = f(n)! - 1 \]This implies that $f(n) \neq 2$. Also, \[ n! - 2 \mid f(n!) - 2 = f(n)! - 2 \]So there exists $k$ such that $k(n! - 2) = f(n)! - 2$. Then since $f(n) \neq 2$, this implies that $f(n) \geq n$. Note that when $n = 3$ then we must have $f(n) = 3$, as otherwise then $4 \mid f(n)! - 2$. Now, assume FTSOC that $f(n) > n$ for $n\geq 4$, and let $m = f(n)$. Then \[ k(n! - 2) = m! - 2 \]This implies that $k$ is odd, and in particular $k = n+1$. Then $m = n$, because $m \geq n+1$ makes the RHS too large. This is a contradiction. $\square$ Thus, the solutions are $f(x) = 1$, $f(x) = 2$, and $f(x) = x$, all of which work. $\blacksquare$
21.01.2024 20:49
The first condition tells us $f(1), f(2) \in \{1,2\}$. Thus we can use casework on these two values: $f(2)=1 \implies$ Substituting $(m!,2)$ into the second condition, we get \[m!-2 \mid f(m)!-1 \implies f(m)=1~\forall~m \ge 3,\] otherwise the LHS is odd and the RHS is a positive even integer. This also implies $f(1)=1$, so our solution in this case is $f(x)=1$. $f(1)=f(2)=2 \implies$ Substituting $(3!,1)$ into the second condition, we get $f(3)=2$. Now substituting $(m!,3)$, we get \[m!-6 \mid f(m)!-2 \implies f(m)=2~\forall~m \ge 4,\] otherwise the LHS is a multiple of 3 and the RHS isn't. This gives us the solution $f(x)=2$. $f(1)=1, f(2)=2 \implies$ We use induction to show that $f(k)=k$ implies $f(k+1)=k+1$. Then substituting $((k+1)!, k!)$ and $(k+1,1)$ we get \[k \cdot k! \mid f(k+1)!-k! \implies k \leq f(k+1) < 2k\]\[(k+1)-1 \mid f(k+1)-1 \implies f(k+1) \equiv 1 \pmod k,\] and hence we get the desired, so our solution in this case is $f(x)=x$. Thus our only solutions are $\boxed{f(x)=1, \quad f(x)=2, \quad f(x)=x}$, which clearly work. $\blacksquare$
06.02.2024 20:55
Since $f(1)=f(1)!$ and $f(2)=f(2)!$ then $f(1),f(2)\in\{1,2\}$. Case 1: If $f(1)=1=f(2)$. Then $f(n)=1 \forall n\in \mathbb{Z}$ ($P(n!,2) \rightarrow n!-2 \mid f(n)!-1$) Case 2: if $f(1)=2$ and $f(2)=1$. $P(3!,2) \rightarrow$ $3!-1!\mid f(3)!-2$ then $f(3)!\equiv 2\pmod{5}$, so $f(3)=2$. But notice that $3!-2!\mid f(3)!-1$, so $4\mid 1$ contradiction. Case 3: if $f(1)=2=f(2)$. $P(3!,1) \Rightarrow$ $f(3)! = f(6) \equiv 2 \pmod{5}\Rightarrow f(3)=2$. Then for any $n \geq 4$, we have $f(n)! = f(n!) \equiv 2 \pmod{3}$ which implies $f(n)=2 \forall n\in \mathbb{N}$ Case 4: if $f(1)=1, f(2)=2$. $P(3!,2)\rightarrow 4\mid f(3)!-2$ so $ f(3)=3$ Now, notice that $f((3 \underbrace{!)!)...)!)}_{k-times}=(3 \underbrace{!)!)...)!)}_{k-times}$. Hence there is infinitely many positive integers $x$ for which $f(x)=x$ . So for any natural number $m$, we have : $P(x,m)\rightarrow x-m \mid f(x)-f(m)=x-m \iff x -m \mid x-f(m)-(x-m)= m-f(m)$ By taking $x$ large enough we get $f(m)=m \forall m\in \mathbb{N}$ $$\mathbb{Q.E.D.}$$
30.12.2024 20:11
If the number theorist can say "log log log" then I can say "factorial factorial factorial". Wait, that doesn't exactly roll off the tongue... We claim the only working functions are $f(x) = 1 \forall x$, $f(x) = 2 \forall x$ and $f(x) = x \forall x$, all of which work. Now we prove they are the only working functions. Note that $f(1), f(2) \in \{1, 2\}$. We now take four cases, in order of how interesting they are. Case 1: $f(1) = 2, f(2) = 1$. Note that $4 = 3!-2 \mid f(3)! - f(2) = f(3)! - 1 \implies f(3) = 1$. But then we have $2 = 3-1 \mid f(3) - f(1) = -1$, which isn't true. Therefore this case yields no solution. Case 2a: $f(1) = f(2) = 1$. Note that we have $4 \mid f(3)!-1 \implies f(3) = 1 \implies f(720) = f((3!)!) = (f(3)!)! = 1$. Now for $n \ge 4$, $4 \mid 720 -- n! \mid f(720) - f(n)! = 1-f(n)! \implies f(n) = 1$. Thus $f\equiv 1$. Case 2b: $f(1) = f(2) = 2$. Similarly, $4 \mid f(3)! - 2 \implies f(3) \in \{ 2, 3\}$. Now assume $f(3) = 3$. Then we have $2 = 3-1 \mid f(3) - f(1) = 1$, contradiction. So $f(3) = 2$ $\implies f(720) = f((3!)!) = 2$. Now for $n \ge 4$, we have $4 \mid 720 - n! \mid f(720) - f(n)! = 2-f(n)! \implies f(n) = 2$. Thus $f \equiv 2$. Case 3: $f(1) = 1, f(2) = 2$. Note that once again $4 \mid f(3)! - 2 \implies f(3) \in \{ 2, 3\}$. Now if $f(3) = 2$, then $2 = 3-1 \mid f(3)-f(1) = 1$, contradiction, so $f(3) = 3$. This is where the boring part ends, and the fun part begins. We let $g(n) = n!, g^k(n) = g(g^{k-1}(n))$. (So for example $g^2(3) = 720$.) Note that the sequence $\{g(3), g^2(3), g^3(3), \dots\}$ has infinitely many terms in it. Further, $f(g^k(3)) = g^k(3)$ as $f(3) = 3$. Then we have $g^k(3) - n \mid g^k(3) - f(n) \implies g^k(3) - n \mid n-f(n)$. But then $n- f(n)$ has infinitely many divisors, so $f(n) = n \forall n$. These three cases overall must give us all the solutions, so we are done.