Difference between revisions of "2013 USAMO Problems/Problem 5"
(complete reformatting) |
|||
Line 1: | Line 1: | ||
− | Given | + | == Problem == |
− | + | Given positive 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. | |
− | |||
− | |||
+ | == 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. | 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. | ||
− | |||
Without Loss of Generality, 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>. | Without Loss of Generality, 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=\varphi(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. | 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=\varphi(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. | 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>. | ||
− | + | {{MAA Notice}} |
Revision as of 18:27, 10 May 2023
Problem
Given positive 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.
Solution
This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.
Without Loss of Generality, 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
.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.