Art of Problem Solving
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

2013 USAMO Problems/Problem 5: Difference between revisions

← Older editNewer edit →
Negia (talk | contribs)
editor
61 edits
Negia (talk | contribs)
editor
61 edits
Line 8: Line 8:


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>.
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=\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>.
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 23:50, 3 August 2020

Given postive 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. These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Solution

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


WLOG, 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$.

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