My solution at the contest: Lemma $1$:For different $m,n$,$f(m)$ is not equal $f(n)$.Proof:Suppose not,then we will have that all integers bigger than $max(m,n)$ won't satisfay the $(1,2,...k)=(f(1),f(2),...f(k))$,so done. Lemma $2$:$f(m)<=m$.Suppose $f(m)>m$.The number of numbers in set ${1,2,...k}$ which are divisible by $f(m)$ is $[k/f(m)]$ and using Lemma $1$ and that $f(m)$ divides $f(mn)$ we get there at least $[k/m]$.Now,it is easy to prove that for all $n>=f(m)^2*m$ satisfay $[n/m]>[n/f(m)]$,so from this we have finitely many $n$,so we proved lemma $2$.Now,applying Lemma $1$ and Lemma $2$ we obtain the answer is $f(n)=n$.

Obviously $f(1)=1$ since $f(m)=f(m)f(1)$ Lemma 1. For all sufficiently large $x$, the inequality $a^{x+1}<(a+1)^x$ holds true. Obviously it is equivalent to $1>a(a^{-x}-1)$. Since $a^{-x}-1$ will be close to $0$ for a sufficiently large $x$ we have proven the lemma. Lemma 2. $f(x^k)=f(x)^k$. We shall prove by induction. Base $f(a^1)=f(a)^1$ Step: assume $f(k^{t-1})=f(k)^{t-1}$ $f(k^t)=f(k^{t-1})\cdot f(k)=f(k)^{t-1}\cdot f(k)=f(k)^t$ Lemma 3. $f(m)=f(n)$ only if $m=n$ Assume the contrary. Then for all sufficiently large $k$ we have that $\{1,2,3,\cdots,k\}$ will have less than $k$ elements. Contradiction. Lets prove $f(k)=k$ Proof will proceed by induction Base $f(1)=1$ Step: By the inductive hypothesis, assume $f(m)=m$ for all $m<k$. Let $n$ be a sufficiently large so that $\{1,2,\cdots,n\}=\{f(1),f(2),\cdots,f(n)\}$. Let $t$ be the largest $t$ so that $k^t<n$.Since $n$ is infinitely large, by Lemma 1 we can have that $(a+1)^t>a^{t+1}>n$. Since $k^t<n$ we have that $f(k)^t=f(k^t)\le n\implies f(k)<n^{\frac 1 t}<k+1$. Since$ f(k)<k+1$ and $f(t)=t$ for all $t<k$ by Lemma 3 we have $f(k)=k$, thus completing the proof.

Since $f(m)=f(m)f(1)$ we get $f(1)=1$. And second condition holds for infinitely many $n$, we can easily show that $f$ is bijective function. Now let's see what happens if $f(s)=p$ where $p\in \mathbb{P}$ and $s<p$. First of all let's say that second condition holds for $n=n_1<n_2<n_3<...$ $p\mid pf(l)=f(s)f(l)=f(sl)$. So if $s\mid r$ then $p\mid f(r)$. No let's take very large $n_i$. So $\lfloor \frac{n_i}{p}\rfloor$ number is divisible by $p$ in $\{1,2,...,n_i\}$. And there is $\lfloor \frac{n_i}{s}\rfloor$ number which is divisible by $s$ in $\{1,2,...,n_i\}$. So there is at least $\lfloor \frac{n_i}{s}\rfloor$ number divisible by $p$ in $\{f(1),f(2),...,f(n_i)\}$ So we have $\lfloor \frac{n_i}{p}\rfloor\geq \lfloor \frac{n_i}{s}\rfloor$. Since $s<p$ we have $\lfloor \frac{n_i}{p}\rfloor = \lfloor \frac{n_i}{s}\rfloor$. But obviously it's not true for very large $n_i$. So we get contradiction! So we get that if $f(z)=p\in \mathbb{P}$ then $z\geq p$. Note that if $z$ is composite number ($z=q_1^{\alpha_1}\cdots q_m^{\alpha_m}$,where $q_i$ is prime), then $p\mid f(z)=f(q_1)^{\alpha_1}\cdots f(q_m)^{\alpha_m}$ so we get $f(q_h)=p$ for some $h$. But from injectivity we get contradiction. So $z\in \mathbb{P}$ Lemma : Let $f(i)=p\in \mathbb{P}$ and $p\mid f(j)$ for some $j$. Then $i\mid j$. Proof : Let's write prime factorization of $j$, $j=r_1^{\theta_1}\cdots r_u^{\theta_u}$. So $p\mid f(j)=f(r_1)^{\theta_1}\cdots f(r_u)^{\theta_u}$ so we get $f(r_w)=p$ for some $w$. But from from injectivity, we get $r_w=i$. $\square$ Now assume that $f(z)=p$ where $z>p$. So $p\mid f(b) \iff z\mid b$. Now do same thing as proof of first case ($s<p$) and get that $\lfloor \frac{n_i}{p}\rfloor = \lfloor \frac{n_i}{z}\rfloor$ and like first case we get contradiction. Finally we get $f(p)=p$ for all $p\in \mathbb{P}$. And since $f$ is multiplicative function we get $f(n)=n$ for all $n\in \mathbb{N}$. So we are done!

Let $p=prime$ let $n$ a large enought number satisfying (2) such that $p^m<=n<p^{m+1}$ and $p^{m+1}<(p+1)^m$ and $(p-1)^{m+1}<p^m$ then if $f(k)=p$ by (1) we have that $f(k^l)=p^l$ which means $k=p$ for every prime number. now from (1) we have $f(n)=n$

2021 Mexico Center Zone Regional Olympiad P6 https://artofproblemsolving.com/community/c6h2759347p24127944