48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

For arbitrary prime $p$ and positive integer $n$, denote by ${\mathrm{ord}}_p(n)$ the exponent of $p$ in $n$. Thus, $${\nu }_p(n)={\mathrm{ord}}_p(n!)=\sum _{i=1}^n{\mathrm{ord}}_p(i)$$ Lemma. Let $p$ be a prime number, $q$ be a positive integer, $k$ and $r$ be positive integers such that $p^k>r$. Then ${\nu }_p\left(q{p}^k+r\right)={\nu }_p\left(q{p}^k\right)+{\nu }_p(r)$. Proof. We claim that ${\mathrm{ord}}_p\left(q{p}^k+i\right)={\mathrm{ord}}_p(i)$ for all $0<i<p^k$. Actually, if $d={\mathrm{ord}}_p(i)$ then $d<k$, so $q{p}^k+i$ is divisible by $p^d$, but only the first term is divisible by $p^{d+1}$; hence the sum is not. Using this claim, we obtain $${\nu }_p\left(q{p}^k+r\right)=\sum _{i=1}^{q{p}^k}{\mathrm{ord}}_p(i)+\sum _{i=q{p}^k+1}^{q{p}^k+r}{\mathrm{ord}}_p(i)=\sum _{i=1}^{q{p}^k}{\mathrm{ord}}_p(i)+\sum _{i=1}^r{\mathrm{ord}}_p(i)={\nu }_p\left(q{p}^k\right)+{\nu }_p(r)$$ For any integer $a$, denote by $\bar{a}$ its residue modulo $d$. The addition of residues will also be performed modulo $d$, i.e. $\bar{a}+\bar{b}=\overline{a+b}$. For any positive integer $n$, let $f(n)=(f_1(n),\dots ,f_k(n))$, where $f_i(n)=\overline{{\nu }_{p_i}(n)}$. Define the sequence $n_1=1,n_{\ell +1}=(p_1{p}_2\dots p_k{)}^{n_{\ell }}$. We claim that $$f\left(n_{{\ell }_1}+n_{{\ell }_2}+\dots +n_{{\ell }_m}\right)=f\left(n_{{\ell }_1}\right)+f\left(n_{{\ell }_2}\right)+\dots +f\left(n_{{\ell }_m}\right)$$ for any ${\ell }_1<{\ell }_2<\dots <{\ell }_m$. (The addition of $k$-tuples is componentwise.) The base case $m=1$ is trivial. Suppose that $m>1$. By the construction of the sequence, $p_i^{n_{{\ell }_1}}$ divides $n_{{\ell }_2}+\dots +n_{{\ell }_m}$; clearly, $p_i^{n_{{\ell }_1}}>n_{{\ell }_1}$ for all $1\le i\le k$. Therefore the Lemma can be applied for $p=p_i,k=r=n_{{\ell }_1}$ and $q{p}^k=n_{{\ell }_2}+\dots +n_{{\ell }_m}$ to obtain $$f_i\left(n_{{\ell }_1}+n_{{\ell }_2}+\dots +n_{{\ell }_m}\right)=f_i\left(n_{{\ell }_1}\right)+f_i\left(n_{{\ell }_2}+\dots +n_{{\ell }_m}\right)\text{ for all }1\le i\le k$$ and hence $$f\left(n_{{\ell }_1}+n_{{\ell }_2}+\dots +n_{{\ell }_m}\right)=f\left(n_{{\ell }_1}\right)+f\left(n_{{\ell }_2}+\dots +n_{{\ell }_m}\right)=f\left(n_{{\ell }_1}\right)+f\left(n_{{\ell }_2}\right)+\dots +f\left(n_{{\ell }_m}\right)$$ by the induction hypothesis. Now consider the values $f\left(n_1\right),f\left(n_2\right),\dots$ There exist finitely many possible values of $f$. Hence, there exists an infinite sequence of indices ${\ell }_1<{\ell }_2<\dots$ such that $f\left(n_{{\ell }_1}\right)=f\left(n_{{\ell }_2}\right)=\dots$. and thus $$f\left(n_{{\ell }_{m+1}}+n_{{\ell }_{m+2}}+\dots +n_{{\ell }_{m+d}}\right)=f\left(n_{{\ell }_{m+1}}\right)+\dots +f\left(n_{{\ell }_{m+d}}\right)=d\cdot f\left(n_{{\ell }_1}\right)=(\overline{0},\dots ,\overline{0})$$ for all $m$. We have found infinitely many suitable numbers.

---

Alternative solution.

We use the same Lemma and definition of the function $f$. Let $S=\{f(n):n\in \mathbb{N}\}$. Obviously, set $S$ is finite. For every $s\in S$ choose the minimal $n_s$ such that $f\left(n_s\right)=s$. Denote $N={\max }_{s\in S}{n}_s$. Moreover, let $g$ be an integer such that $p_i^g>N$ for each $i=1,2,\dots ,k$. Let $P=(p_1{p}_2\dots p_k{)}^g$. We claim that $$\{f(n)\mid n\in [mP,mP+N]\}=S\text{\hspace{1em}(1)}$$ for every positive integer $m$. In particular, since $(\overline{0},\dots ,\overline{0})=f(1)\in S$, it follows that for an arbitrary $m$ there exists $n\in [mP,mP+N]$ such that $f(n)=(\overline{0},\dots ,\overline{0})$. So there are infinitely many suitable numbers. To prove (1), let $a_i=f_i(mP)$. Consider all numbers of the form $n_{m,s}=mP+n_s$ with $s=(s_1,\dots ,s_k)\in S$ (clearly, all $n_{m,s}$ belong to $[mP,mP+N]$ ). Since $n_s\le N<p_i^g$ and $p_i^g\mid mP$, we can apply the Lemma for the values $p=p_i,r=n_s,k=g,q{p}^k=mP$ to obtain $$f_i\left(n_{m,s}\right)=f_i(mP)+f_i\left(n_s\right)=a_i+s_i;$$ hence for distinct $s,t\in S$ we have $f\left(n_{m,s}\right)\ne f\left(n_{m,t}\right)$. Thus, the function $f$ attains at least $|S|$ distinct values in $[mP,mP+N]$. Since all these values belong to $S,f$ should attain all possible values in $[mP,mP+N]$.