Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 USAMO Problems/Problem 5"

(→‎Solution: Added Solution 2)
(→‎Solution 1)
Line 12: Line 12:
  
 
This proves that <math>cm</math> and <math>c_2n_1</math> have the same number of occurrences of non-zero digits. Furthermore, <math>cn = c_2c_1n=10^s c_2n_1</math> also have the same number of occurrences of non-zero digits with <math>c_2n_1</math>.
 
This proves that <math>cm</math> and <math>c_2n_1</math> have the same number of occurrences of non-zero digits. Furthermore, <math>cn = c_2c_1n=10^s c_2n_1</math> also have the same number of occurrences of non-zero digits with <math>c_2n_1</math>.
 +
 +
~hashbrown2009 (added aspects and enhanced solution with a few revisions)
  
 
== Solution 2 ==
 
== Solution 2 ==

Revision as of 20:36, 29 March 2025

Problem

Given positive integers $m$ and $n$, prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

Solution 1

This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.

Without Loss of Generality, suppose $m \geq n \geq 1$. By prime factorization of $n$, we can find a positive integer $c_1$ such that $c_1n=10^s n_1$ where $n_1$ is relatively prime to $10$. If a positive $k$ is larger than $s$, then $(10^k c_1 m - c_1 n)= 10^s t$, where $t=10^{k-s} c_1m-n_1>0$ is always relatively prime to $10$.

Choose a $k$ large enough so that $t$ is larger than $c_1m$. We can find an integer $b\geq 1$ such that $10^b-1$ is divisible by $t$, and also larger than $10c_1m$. For example, let $b=\varphi(t)$ and use Euler's theorem. Now, let $c_2=(10^b-1)/t$, and $c=c_1c_2$. We claim that $c$ is the desired number.

Indeed, since both $c_1m$ and $n_1$ are less than $t$, we see that the decimal expansion of both the fraction $(c_1m)/t = (cm)/(c_2t) = (cm)/(10^b-1)$ and $n_1/t=(c_2n_1)/(10^b-1)$ are repeated in $b$-digit. And we also see that $10^k (c_1m)/t = (t+c_1n)/t= 1+10^s (n_1/t)$, therefore the two repeated $b$-digit expansions are cyclic shift of one another.

This proves that $cm$ and $c_2n_1$ have the same number of occurrences of non-zero digits. Furthermore, $cn = c_2c_1n=10^s c_2n_1$ also have the same number of occurrences of non-zero digits with $c_2n_1$.

~hashbrown2009 (added aspects and enhanced solution with a few revisions)

Solution 2

This is a rephrasing of the above solution.

It is enough to solve the problem when $m,n$ are replaced by $km,kn$ for any positive integer $k$. In particular, by taking $k=2^a5^b$ for appropriate values of $a,b$, we may assume $n=10^sn_1$ where $n_1$ is relatively prime to 10.

Furthermore, adding or removing trailing zeros from $m$ and $n$ doesn't affect the claim, so we may further assume $\gcd(n,10)=1$ and that $m$ has a xillion trailing zeros (enough to make $m$ way bigger than $n$, and also so that $m$ has at least one trailing zero).

For clarity of exposition, we will also multiply $m,n$ by a small number to make the units digit of $n$ be $1$ (though this is not necessary for the solution to work).

The point is that, for any positive integer $X$, most nonzero digits appear the same number of times in $X$ and $X+999\dots999$ if there are enough $9$s; In particular, if the units digits of $X$ is $1$, then all nonzero digits appear the same number of times as long as there are at least as many $9$s as digits in $X$.

So we will pick $c$ to satisfy:

  • $mc=nc+999\dots999$ where the number of $9$s is more than the number of digits of $nc$
  • The units digit of $nc$ is $1$.

Because we made the units of $n$ to be $1$, the second condition is equivalent to making the units digit of $c$ to be $1$.

The first condition is equivalent to $(m-n)c=999\dots999$. Because $m$ has at least one trailing 0, the units digit of $m-n$ is 9, so $\gcd(m-n,10)=1$ and there is some $c$ so that $(m-n)c=999\dots999$, and the units digit of $c$ must be $1$ which agrees with the other condition.

Finally, as $m\gg n, (m-n)c\approx mc\gg nc$ so it is possible to make the number of $9$s more than the number of digits in $nc$.


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAMO_Problems/Problem_5&oldid=246245"