58th Ukrainian National Mathematical Olympiad

At first suppose, that number $n=p_1^{m_1}\dots p_k^{m_k}$, where $p_i$, $i=1,\overline{k}$ – are distinct prime numbers and $m_i$ – are natural numbers, $i=1,\overline{k}$. Then let's choose all ordered pairs of numbers $(a,b)$, for which $[a,b]=n$. Here we do not have condition $a<b$, so pairs $(a,b)$ and $(b,a)$ for $a\ne b$ are considered different. If $a=p_1^{a_1}\dots p_k^{a_k}$ and $b=p_1^{b_1}\dots p_k^{b_k}$, so for satisfying condition $[a,b]=n$ it is necessary and sufficient that $\forall i=1,\overline{k}\max \{a_i,b_i\}=m_i$. Then possible variants of pairs $(a_i,b_i)$: $(0,m_i),(1,m_i),\dots ,(m_i-1,m_i),(m_i,m_i),(m_i,m_i-1),(m_i,m_i-2),\dots ,(m_i,0).$ In total there are $2m_i+1$ variants. So, in total there will be exactly $N=(2m_1+1)\dots (2m_k+1)$ ordered pairs of numbers. And there are exactly $\frac{1}{2}(N-1)$ pairs, for which $a<b$. Really, for all computed pairs we need to delete pair $(n,n)$, and for every two pairs $(a,b)$ and $(b,a)$ we need to leave one. So, we need to find the biggest three-digit natural number, for which $\frac{1}{2}(N-1)=16$.

Then $N=33$, so there are two possible variants: $N=2\cdot 16+1$ or $N=(2\cdot 5+1)(2\cdot 1+1)$. In first case, for some prime $p$ condition is true $n=p^{16}\ge 2^{16}>999$. In second case, we have, that $n=p^{5}q$, where $p,q$ – are distinct prime numbers. As $5^5>999$, then $p=2$ or $p=3$. For $p=3$ we have, that $3^5=243$, so the number can only be $3^5\cdot 2=486$, as $3^5\cdot 5>999$. For $p=2$ we have, that $2^5=32$, so the number can be maximum three-digit number of form: $2^5\cdot p$, where $p>2$ – is prime. As $1000:2^5=31.25$, it is not hard to see, that the number is $2^5\cdot 31=992$.