By induction $f$ is nondecreasing. As $f(1)=f(1)^2$, $f(1)$ is either 0 or 1. If $f(1)=0$ then $f(n)=0$ for all $n$. So suppose $f(1)\neq 0$; then $f(1)=1$ and $f(n)\geq 1$ for all $n$. Suppose there exist integers $a<b$ such that $f(a)=f(b)=k$. Then $k=\frac{f(p)}{f(q)}$ for all $a\leq\frac{p}{q}\leq b$ such that $(a,q)=(b,q)=1$ (since $f(q)f(a)=f(qa)\leq f(p) \leq f(qb)=f(q)f(b)$.) If we then construct an increasing sequence of rational numbers ${1, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \ldots \frac{p_l}{q_l}, a}$ all coprime to $b$, $a$ and each other, and each no more than $\frac{b}{a}$ times the last, then \[ \frac{p_i}{q_i}<\frac{p_{i+1}}{q_{i+1}}<\frac{bp_i}{aq_i} \] so \[ ap_iq_{i+1}\leq ap_{i+1}q_i\leq bp_iq_{i+1} \] so \[ kf(p_iq_{i+1})=f(ap_iq_{i+1})\leq f(ap_{i+1}q_i)\leq f(bp_iq_{i+1})=kf(p_iq_{i+1}) \] so $f(ap_iq_{i+1})=f(ap_{i+1}q_i)$ and $\frac{f(p_i)}{f(q_i)}=\frac{f(p_{i+1})}{f(q_{i+1})}$. Continuing down the list, we find by induction that $1=f(1)=f(a)$, by extension that $f(n)=1$ for all $n\leq b$, and by a similar construction that $f(n)=1$ for all $n$. Otherwise we can assume the function is strictly increasing, and in this case I don't think there's much we can say: just define on all prime powers in increasing order (choose $f(2)$ then $f(3)$ then $f(4)$ then $f(5)$ then $f(7)$, etc.) so that each time the value chosen is within the acceptable interval for the function to be increasing. I haven't checked it rigorously but I think that this can be done pretty arbitrarily, and the function need not be particularly nice.

you are wrong we choose$f(2)=2 ,f(3)=5$ ...then$f(4)=5<f(3)$

How do you get $f(4)=5$¿

I thing the root is $f(n)=1 \forall n \in N*$ OR $f(n)= n^a \forall n \in N*$ and with $a>0$

ZetaX wrote: How do you get $f(4)=5$¿ I am very sorry $f(4)=f(2)f(2)=4< f(3)=5$ but we have f(n+1)>=f(n)

Note that $\gcd(2,2)=2$, so you cannot claim $f(4)=f(2)f(2)$!

ZetaX wrote: Note that $\gcd(2,2)=2$, so you cannot claim $f(4)=f(2)f(2)$! sorry .I don't read it careful but I still thing the solution of Agrippina is wrong choose $f(2)=2 ,f(3)=5 ,f(5)=6, f(7)=8$ then we claim$f(6)= 10>f(7)$ and my root can be wrong

tranngoctrung wrote: choose $f(2)=2 ,f(3)=5 ,f(5)=6, f(7)=8$ then we claim$f(6)= 10>f(7)$ What I meant in the condition in my earlier solution ("so that each time the value chosen is within the acceptable interval for the function to be increasing") is that when you pick the value of the function for a prime power $p^k$ you must ensure that the value you pick is strictly between $\frac{f(m_1)}{f(n_1)}$ and $\frac{f(m_2)}{f(n_2)}$, where $\frac{m_1}{n_1}$ and $\frac{m_2}{n_2}$ are the closest rational approximations from above and below to $p^k$ for coprime $m$ and $n$ whose only prime power factors are less than $p^k$. This avoids the sort of contradiction you've been producing, but I don't think it necessarily yields a "nice" solution like $f(n)= n^a$.

thank you ! now I kown that I wrong

Erdos proved that if $f$ is multiplicative (i.e $f(mn)=f(m)f(n)$ when $(m,n)=1$), positive, and monotonic then there is a constant $c$ such that $f(n)=n^c$. Thus since $f(1)$ can be only $0$ or $1$, the only possible solutions are $f(n)=n^c$ for some constant $c$ or $f(n)=0$. I don't think it's all right to put such problems on an Olympiad .

f(1)=1, so f(n)>=0 so, f(2)>=1 suppose f(2)=a, then, we could know that f(mn)>=af(m). like this, a is the smallest value of f(n) except f(1), we also could know that a^n+1>f(2^n)>=a^n. like this, at any p(p is prime number), we can find the value like f(p)=a_p a_2=<a_3=<a_3.......=<a_p. like above, f(p^n)>=(a_p)^n and, gernerally, we can find that f(m)>=f([m/p]x p) thus we can reason that f(p^n)=(a_p)^n f shoul satisfy this condition--->f(mn)=f(m)f(n) thus, f(p)=p^n(n is one of real number)

Kimjiman and {x}, I wonder whether you are taking the range of $f(n)$ to be the integers rather than the reals? In particular, Kimjiman, if I understand you correctly you deduce from $a^n+1>f(2^n)\geq a^n$ that $f(2^n)=a^n$, which you can only do if you know that $f(n)$'s range is restricted to $\mathbb{Z}$. When you do restrict $f(n)$ to taking only integer values, I think you are right: the only solutions are indeed the "nice" ones. I'm afraid I can't follow your proof, though!

I don't have the reference I used yesterday right now, but I am almost 100 % sure that Erdos's prove does concern multiplicative function from $\mathbb{Z^+}$ to $\mathbb{R}$

You're right; Google turned up this reference: http://alumnus.caltech.edu/~however/papers/paper01.html to "Erdos' theorem" that "every increasing multiplicative function from the positive integers to the reals is of the form $f(n)=n^a$ for some real $a>1$". When I've convinced myself of it I'll let you know. Kimjiman, I don't understand the step in your proof when you go from $f(mn)\geq af(n)$ for $m$ coprime to $n$ and $\geq 2$, to $a^n+1>f(2^n)\geq a^n$. Does anyone else have a proof? Anyway, I agree; a classic theorem seems an odd choice of problem for an Olympiad.

Apologies for my earlier skepticism: [x] and Erdos were right, and my "counterexample" was based on fallacious reasoning. Here is a proof from the American Mathematical Monthly, October 1986. $f(p^{n+1})=f(p)f(p^n)$ for all naturals $n$ and primes $p$. For \[ \frac{f(xp-1)}{f(x)}\leq \frac{f(p^{n+1})}{f(p^n)}\leq \frac{f(xp+1)}{f(x)} \] for all $(x,p)=1$, and so \[ f(p)\frac{f(x-p)}{f(x)}\leq \frac{f(p^{n+1})}{f(p^n)}\leq f(p)\frac{f(x+p)}{f(x)} \] for all $(x,p)=1$. If $\frac{f(p^{n+1})}{f(p)f(p^n)}=r$ then $f(x+kp)\geq r^kf(x)$ for all naturals $k$; for some sufficiently large $x$, $f(2)f(x)=f(2x)>f(x+kp)$ as the function is increasing, so $f(2)>r^k$ for all integers $k$, and so $r\leq 1$. Likewise $r \geq 1$, so $\frac{f(p^{n+1})}{f(p)f(p^n)}=r=1$ for all $p$, $n$. Therefore $f(p^n)=f(p)^n$ for all $p$, $n$ and so $f$ is strictly multiplicative as well as increasing. Then if $f(n)$ is not of the form $n^a$ for some constant $a$, then there would exist integers $l$, $m$ so that $\frac{\ln l}{\ln m}\neq \frac{\ln f(l)}{\ln f(m)}$. If the LHS were greater, there is a rational number $\frac{\ln l}{\ln m}>\frac{s}{t}>\frac{\ln f(l)}{\ln f(m)}$, so that $l^t>m^s$ but $f(m^s)=f(m)^s>f(l)^t=f(l^t)$, a contradiction; similarly, there is a contradiction if the RHS is greater.

${f(m n)=f(m) f(n)}$ ${g(x)=\log_{b}(f(x))}$ ${g(m n)=g(m)+g(n)}$ ${\frac{\partial \frac{\partial g(m n)}{\partial m}}{\partial n}=\frac{\partial \frac{\partial (g(m)+g(n))}{\partial m}}{\partial n}}$ ${g'(m n)+m n g''(m n)=0}$ ${m n=u}$ ${g'(u)+u g''(u)=0}$ ${g(u)=c_{1}\log_{b}(u)}$ ${g(x)=\log_{b}(f(x))}$ ${f(x)=b^{g(x)}}$ ${f(x)=b^{c_{1}\log_{b}(u)}}$ ${f(x)=u^{c_{1}}}$ ?

Differentiating functions defined on $\mathbb Z^{+}$ only ¿

hi i can recommend you something about the problem though i cannot solve this problem. For example, you can look at IMO 1994/5 and 1997/4 in this step

Let $m=n=1$, we get $f(1)=f(1)^2$, so $f(1)$ is $0$ or $1$. If $f(1)=0$, then let $m=1$ we get $f(n) = f(1)f(n) = 0$ for all positive integer $n$. Below we assume $f(1)=1$, then $f(n)\geq f(1)=1$ for all positive integer $n$. Lemma. For any integers $a > 1$ and $k\ge 0$, we have \[ f(a)^{k-1} \leq f(a^k) \leq f(a)^{k-1} f(a+1). \]

Let $a>1, n>1$ be integers. Let $k=\lfloor\log_a n\rfloor$, $k>\frac{\ln n}{\ln a}-1$. Then \[ f(n) \geq f(a^k) \geq f(a)^{k-1}. \]Taking logarithm: \[ \ln f(n) \geq (k-1) \ln f(a) \ge \left(\frac{\ln n}{\ln a}-2\right) \ln f(a). \]Dividing both sides by $\ln n$: \[ \frac{\ln f(n)}{\ln n} \ge \frac{\ln f(a)}{\ln a} - \frac{2\ln f(a)}{\ln n}. \] On the other hand, let $k=\lceil\log_a n\rceil, k<\frac{\ln n}{\ln a}+1 $, then \[ f(n) \le f(a^k) \le f(a)^{k-1} f(a+1). \]Taking logarithm then divide both sides by $\ln n$: \[ \frac{\ln f(n)}{\ln n} \le \frac{\ln f(a)}{\ln a} + \frac{\ln f(a+1)}{\ln n}. \] Combining the last two inequalities: \[ \frac{\ln f(a)}{\ln a} - \frac{2\ln f(a)}{\ln n} \leq \frac{\ln f(n)}{\ln n} \le \frac{\ln f(a)}{\ln a} + \frac{\ln f(a+1)}{\ln n}. \]It follow that \[ \lim_n \frac{\ln f(n)}{\ln n} = \frac{\ln f(a)}{\ln a}. \] We have shown that for any integer $a>1$, $\frac{\ln f(a)}{\ln a}$ is the limit \[ \lim_n \frac{\ln f(n)}{\ln n} = \frac{\ln f(a)}{\ln a}. \]Let the limit be $\alpha$, then $\alpha \geq 0$ and $f(a) = a^\alpha$ for any positive integer $a$. To sum up, $f(n)=0$ or $f(n)=n^\alpha (\alpha\geq0)$. One checks that these are all valid solutions to the functional equation.