Find all functions $f:\mathbb{Z}^+\rightarrow \mathbb{Z}^+$ satisfying $$m!!+n!!\mid f(m)!!+f(n)!!$$for each $m,n\in \mathbb{Z}^+$, where $n!!=(n!)!$ for all $n\in \mathbb{Z}^+$. Proposed by DVDthe1st
Problem
Source: SMO Open 2022
Tags: functional equation, number theory, factorial, function
gghx
02.07.2022 11:13
Amazing problem.
We claim that the only function that works is $f(m)\equiv m$. It obviously satisfies the condition. We show it is the only one.
Fix any number $m$. We show that $f(m)=m$. Define the sequence $m_0=m$, $m_{n+1}=f(m_n)$.
Taking $m=m_i,n=m_{i+1}$ in the condition gives $m_i!!+m_{i+1}!!|m_{i+1}!!+m_{i+2}!!$.
Taking $m=m_i,n=m_i$ in the condition gives $m_i!!|m_{i+1}!!$, which means $m_i\le m_{i+1}$.
Case 1: The sequence $m_i$ is unbounded.
Note that we have $m_0!!+m_1!!|m_1!!+m_2!!|\cdots|m_i!!+m_{i+1}!!$.
Consider $m_0!!+m_1!!=m!!+f(m)!!$. If $f(m)=m$ then we are done. If not, consider $t=\frac{m_1!!}{m_0!!}=(m_1!)(m_1!-1)\cdots(m_0!+1)$.
Note that any prime $p$ dividing $t+1$ satisfies $p>m_1!$.
This is because if $m_0!+1\le p\le m_1!$ then $p|t$, impossible. If $p\le m_0!$, then since $m_1!\ge 2m_0!$ there is a multiple of $p$ in the range $[m_0!+1,m_1!]$, so $p|t$ anyways, a contradiction.
Take some prime $p|t+1$, then $p|(m_0!!)(t+1)=m_1!!+m_0!!$. Since $p<m_1!!$ and $m_i$ is unbounded, there exists $k$ such that $p>m_k!$ but $p\le m_{k+1}!$. Then, $p|m_k!!+m_{k+1}!!$ implies $p|m_k!!$, contradicting $p>m_k!$.
Case 2: $m_i$ is bounded.
Then, since it is non-decreasing, it is eventually constant.
Note that if $m_i=m_{i+1}$, then $m_{i-1}!!+m_i!!|2m_i!!$. Since the LHS is a factor of $2m_i!!$ but is $>m_i!!$, it must be exactly $2m_i!!$, which means $m_{i-1}!!=m_i!!$. We can thus induct downwards to show that $f(m)=m$.
Thus, $f(m)\equiv m$ is the only solution.
DVDthe1st
20.07.2022 20:37
The official solution that I submitted:
Let $P(m,n)$ denote the assertion that $m!!+n!!\mid f(m)!!+f(n)!!$.
For any fixed positive integer $n$, we have the following:
\begin{align*}
P(m,f(m))&:\quad m!! +f(m)!! \mid f(m)!! + f(f(m))!!\\
P(f(m),f(f(m))&:\quad f(m)!! + f(f(m))!! \mid f(f(m))!! +f^3(m)!!\\
\dots\\
P(f^{k-1}(m),f^k(m))&:\quad f^{k-1}(m)!! + f^k(m)!!\mid f^k(m)!! +f^{k+1}(m)!!
\end{align*}where $f^k(m) = \underbrace{f(f(\dots f(m)\dots)}_{k\text{ times}}$. Hence it follows immediately that for any integer $k\ge 0$,
$$m!!+f(m)!!\mid f^k(m)!! +f^{k+1}(m)!!$$If the sequence $\{m,f(m),f^2(m),...\}$ is unbounded, then we pick the minimal integer $k\ge 0$ such that $m!!+f(m)!!\mid f^{k+1}(m)!!$ (which must exist). Clearly $k>0$, and by definition, $$m!!+f(m)!! \nmid f^k (m)!!+ f^{k+1}(m)!!$$which contradicts our previous observation. Hence the above sequence is bounded. Furthermore, it is non-decreasing since $P(n,n)$ gives $f(n)\ge n$.
Let $k\ge 0$ be the minimal integer where $f^k(m)=\max\{m,f(m),f^2(m),...\}$. If $k>0$, then consider:
$$P(f^{k-1}(m),f^k(m)):\quad f^{k-1}(m)!! + f^k(m)!!\mid f^k(m)!! +f^{k+1}(m)!!$$But we also have:
\begin{align*}
f^k(m)!! +f^{k+1}(m)!! &\le 2f^k(m)!!\\
&< 2\left(f^{k-1}(m)!! + f^k(m)!!\right)
\end{align*}Hence $$f^{k-1}(m)=f^{k+1}(m)\ge f^k(m) \ge f^{k-1}(m)$$which contradicts the minimality of $k$. Hence $k=0$, thus $f(m)=m$ for any initial choice of $m$. It is trivial to check that $f(m)\equiv m$ is indeed a solution.
Some notes about how I proposed it:
A while back (around 2016-2017?) I saw a very similar problem on AoPS which was $m! + n! | f(m)! + f(n)!$. However, that problem is much less interesting since you can plug in $(m,n) = (1, p-1)$ and use some properties of primes to finish. I was slightly disappointed at first because I found a solution similar to my official solution for this problem, but I realized that I can just simply change the problem to make the primes approach unfeasible.
The only thing I needed was to find a different function $g$ such that for any positive integer $k$, $k|g(n)$ for sufficiently large $n$. The simplest one I could think of was $g(n) = (n!)!$, so I ran with that.