Mathematical Reflections 2017, Issue 1 - Problem J399

Problem:
Two nine-digit numbers $m$ and $n$ are called cool if

   (a) they have the same digits but in different order,
   (b) no digit appears more than once,
   (c) $m$ divides $n$ or $n$ divides $m$.

Prove that if $m$ and $n$ are cool, then they contain digit $8$.

Proposed by Titu Andreescu, Dallas, Texas

Solution:
Assume by contradiction that there exist two \emph{cool} numbers $m$ and $n$ not containing digit $8$. Then in $m$ and $n$ appear the digits $0,1,2,3,4,5,6,7,9$ exactly once. Since the sum of their digits is $37$, then $m,n \equiv 1 \pmod{9}$. Assume without loss of generality that $m$ divides $n$. Then, $n=mk$, where $k$ is a natural number. Hence, $n-m=m(k-1)$. Reducing modulo $9$ this equation, we get $k-1 \equiv 0 \pmod{9}$, i.e. $k-1$ is divisible by $9$. Since $m$ and $n$ have the same digits in different order, then $m \neq n$, which gives $k \neq 1$. So, $k \geq 10$. But then $n \geq 10m$, i.e. $n$ has more digits than $m$, contradiction.