Find all functions $f:\mathbb{N} \to \mathbb{N}$ such that\[f\left(\Big \lceil \frac{f(m)}{n} \Big \rceil\right)=\Big \lceil \frac{m}{f(n)} \Big \rceil\]for all $m,n \in \mathbb{N}$. Proposed by Md. Ashraful Islam Fahim
Problem
Source: BdMO 2024 Higher Secondary National P7
Tags: functional equation, ceiling function, number theory, algebra
Quidditch
18.03.2024 16:07
After some routine substitutions, you get $f(f(m))=m, f(1)=1$. The key step of this problem is to induct that $f(n)=n$ using bijectivity. To be exact, let $f(i)=i$ for $i=1,2,\dots,k-1$. Let $f(k_0)=k$. Note that $k_0$ and $f(k)$ must be at least $k$ due to the injectivity. Plug in $m\mapsto f(m)$, we have $f\bigg(\bigg\lceil \frac{m}{n}\bigg\rceil\bigg)=\bigg\lceil \frac{f(m)}{f(n)}\bigg\rceil$. Plug in $(m,n)\mapsto (k_0,k)$, we have $$f\bigg(\bigg\lceil \frac{k_0}{k}\bigg\rceil\bigg)=\bigg\lceil \frac{k}{f(k)}\bigg\rceil=1,$$since $k\leq f(k)$. So $\bigg\lceil \frac{k_0}{k}\bigg\rceil=1$ implying $k_0\leq k$. Thus $k_0=k$.
internationalnick123456
18.03.2024 18:08
Another proof: Put $m=n=1$ we have $f(f(1)) = 1$. Put $m=f(1), n = 1$ we have $f(1) = 1$. Hence, $f(f(m)) = m,\forall m\in\mathbb N$. Moreover, $f\left(\left\lceil \frac{f(m)}{f(n)}\right\rceil\right) = \left\lceil \frac{m}{n}\right\rceil$ for all $m,n$, so $f$ is increasing. If $f(m) > m$ then $f(f(m)) > f(m) > m$, absurd, hence, $f(m)\leq m$. Likewise, $f(m)\geq m$. Thus, $f(m) = m$.
ATGY
18.03.2024 18:53
nice problem! Let $P(x, y)$ be the given assertion, $P(1, n)$ with $n > f(1)$, gives $f(1) = 1$, $P(m, 1)$ gives $f(f(m)) = m$, implying bijectivity. $P(f(m), m)$ gives $f\left(\left\lceil \frac{m}{n}\right\rceil\right) = \left\lceil \frac{f(m)}{f(n)}\right\rceil$, so for $m > n$, $f(m) > f(n)$. If $f(x) > x$, $f(f(x)) = x > f(x) > x$, impossible. If $f(x) < x$, $f(f(x)) = x < f(x) < x$, impossible. so $f(x) = x$!
FAA2533
19.03.2024 16:23
$f(x)=x$ is the only function that satisfy the given equation. We can easily check that this function works. Now we'll show this is the only solution.
By $P(a, b)$, we will denote the given functional equation for positive integer $a, b$. We'll prove that $f(f(a))=a$.
Observe\[P(1,f(1))\Rightarrow f(1)=\Big\lceil\frac{1}{f(f(1))}\Big\rceil=1\]From $P(a,1)$ we get $f(f(a))=a$. Which concludes that $f$ is bijective. So we've $f(1)=1$ and $f$ is bijective. Observe \[P(n+1,f(n))\Rightarrow f\left(\Big \lceil \frac{f(n+1)}{f(n)} \Big \rceil \right)=2\Rightarrow \Big \lceil \frac{f(n+1)}{f(n)} \Big \rceil \geq 2 \Rightarrow f(n+1)>f(n)\Rightarrow f(n+1)\geq f(n)+1\]From $f(n+1) \geq f(n)+1$, by induction we get $f(n) \geq n$, which is true for all positive integer $n$. But we've $f$ is bijective. Combining these two characteristics we will have $f(x)=x$.
Proof: Assume for the sake of contradiction, let $a>1$ be the smallest positive integer such that, $f(a) \neq a$. So $f(a)>a$ which implies there exist positive integer $b$ such that $f(b)=a$. Obviously $b<a$. So $b$ is the smallest integer such that $f(b)\neq b$, a contradiction. We must have $f(x)=x$ for all positive integer $x$.
pie854
16.05.2024 23:55
Let $P(m,n)$ be the assertion. $P(f(1),1)\implies f(f(f(1)))=1$ Let $k$ be such that $f(k)=1$ then, $P(k,k) \implies k=f(\lceil 1/k\rceil)=f(1)$ Thus $f(f(1))=1$ and so $f(1)=f(f(f(1)))=1$ $P(m,1) \implies f(f(m))=m$ so $f$ is bijective. $$P(f(m+1),m) \implies \lceil \frac{f(m+1)}{f(m)}\rceil =f\left (\lceil \frac{m+1}m\rceil \right )=f(2)$$so $\frac{f(m+1)}{f(m)}>f(2)-1\geq 1$, since $f(2)\neq 1$. This means that $f$ is strictly increasing, combined with the fact that $f$ is surjective we must have $f(n)=n$ for all $n$. This function clearly works.
mathe369
17.08.2024 22:27
@FAA2533 where did you get the official solution ?