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

Line 1: | Line 1: | ||

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

{{MAA Notice}} | {{MAA Notice}} | ||

+ | |||

+ | ==Solution== | ||

+ | |||

+ | This solution is adopted from the [http://web.archive.org/web/20130606075948/http://amc.maa.org/usamo/2013/2013USAMO_Day1_Day2_Final_S.pdf official solution]. Both the problem and the solution were suggested by Richard Stong. | ||

+ | |||

+ | WLOG, suppose <math>m \geq n \geq 1</math>. By prime factorization of <math>n</math>, we can find a positive integer <math>c_1</math> such that <math>c_1n=10^s n_1</math> where <math>n_1</math> is relatively prime to <math>10</math>. If a positive <math>k</math> is larger than <math>s</math>, then <math>(10^k c_1 m - c_1 n)= 10^s t</math>, where <math>t=10^{k-s} c_1m-n_1>0</math> is always relatively prime to <math>10</math>. Choose a <math>k</math> large enough so that <math>t</math> is larger than <math>c_1m</math>. We can find an integer <math>b\geq 1</math> such that <math>10^b-1</math> is divisible by <math>t</math>, and also larger than <math>10c_1m</math>. For example, let <math>b=\phi(t)</math> and use Euler's theorem. Now, let <math>c_2=(10^b-1)/t</math>, and <math>c=c_1c_2</math>. We claim that <math>c</math> is the desired number. | ||

+ | |||

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

## Revision as of 11:56, 18 April 2014

Given postive integers and , prove that there is a positive integer such that the numbers and have the same number of occurrences of each non-zero digit when written in base ten. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

## Solution

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

WLOG, suppose . By prime factorization of , we can find a positive integer such that where is relatively prime to . If a positive is larger than , then , where is always relatively prime to . Choose a large enough so that is larger than . We can find an integer such that is divisible by , and also larger than . For example, let and use Euler's theorem. Now, let , and . We claim that is the desired number.

Indeed, since both and are less than , we see that the decimal expansion of both the fraction and are repeated in -digit. And we also see that , therefore the two repeated -digit expansions are cyclic shift of one another. This proves that and have the same number of occurrences of non-zero digits. Furthermore, also have the same number of occurrences of non-zero digits with .