Difference between revisions of "2013 AMC 10B Problems/Problem 25"

(Solution 3)
(Solution 3)
Line 114: Line 114:
 
Since the left hand side is a multiple of <math>5</math>, then so does the right hand side. Thus <math>5\mid6(6b_1+b_2)+b_3</math>.
 
Since the left hand side is a multiple of <math>5</math>, then so does the right hand side. Thus <math>5\mid6(6b_1+b_2)+b_3</math>.
  
Since we already know that <math>b_3</math> is a multiple of <math>5</math>, <math>6(6b_1+b_2)</math> is also a multiple of <math>5</math>, from where we know that <math>(6b_1+b_2)</math> is a multiple of <math>5</math>.
+
Since we already know that <math>5\midb_3</math>, <math>5\mid6(6b_1+b_2)</math>, from where we also know that <math>5\mid6b_1+b_2</math> is a multiple of <math>5</math>.
  
 +
For <math>b_1,b_2<6</math>, there is a total of 7 ordered pairs that satisfy the condition. Namely,
 +
 +
<cmath>(b_1,b_2)=(0,0),(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)</cmath>
 +
 +
Since <math>N_6</math> has at least <math>3</math> digits, <math>(b_1,b_2)=(0,0)</math> doesn't work. Furthermore, when <math>b_1=5</math>, <math>625b_1</math> exceeds <math>1000</math> which is not possible as <math>N</math> is a three digits number, thus <math>(b_1,b_2)=(5,0)</math> won't work as well.
 +
 +
Since we know that <math>a_i<5</math>, for each of the other order pairs, there is respectively one and only one solution (a_1,a_2,a_3,a_5) that satisfies the equation
 +
 +
<cmath>625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3</cmath>
 +
 +
Thus there are five solutions for the equation. Also since we have 5 possibilities for <math>a_5=b_4</math>, we have a total of <math>5\cdot5=25</math> values for <math>N</math>. <math>\boxed{\mathrm{(E)}}</math>
 +
 +
~ Nafer
  
  

Revision as of 18:38, 7 August 2019

The following problem is from both the 2013 AMC 12B #23 and 2013 AMC 10B #25, so both problems redirect to this page.

Problem

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer $S$. For example, if $N = 749$, Bernardo writes the numbers $10,\!444$ and $3,\!245$, and LeRoy obtains the sum $S = 13,\!689$. For how many choices of $N$ are the two rightmost digits of $S$, in order, the same as those of $2N$?

$\textbf{(A)}\ 5 \qquad\textbf{(B)}\ 10 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 20 \qquad\textbf{(E)}\ 25$

Solution 1

First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities.

Say that $N \equiv a \pmod{6}$

also that $N \equiv b \pmod{5}$

Substituting these equations into the question and setting the units digits of $2N$ and $S$ equal to each other, it can be seen that $a=b$, and $b < 5$, (otherwise $a$ and $b$ always have different parities) so $N \equiv a \pmod{6}$, $N \equiv  a \pmod{5}$, $\implies N=a \pmod{30}$, $0 \le a \le 4$

Therefore, $N$ can be written as $30x+y$ and $2N$ can be written as $60x+2y$

Just keep in mind that $y$ can be one of five choices: $0, 1, 2, 3,$ or $4$, ; Also, we have already found which digits of $y$ will add up into the units digits of $2N$.

Now, examine the tens digit, $x$ by using $\mod{25}$ and $\mod{36}$ to find the tens digit (units digits can be disregarded because $y=0,1,2,3,4$ will always work) Then we take $N=30x+y$ $\mod{25}$ and $\mod{36}$ to find the last two digits in the base $5$ and $6$ representation. \[N \equiv 30x \pmod{36}\] \[N \equiv 30x \equiv 5x \pmod{25}\] Both of those must add up to \[2N\equiv60x \pmod{100}\]

($33 \ge x \ge 4$)

Now, since $y=0,1,2,3,4$ will always work if $x$ works, then we can treat $x$ as a units digit instead of a tens digit in the respective bases and decrease the mods so that $x$ is now the units digit. \[N \equiv 6x \equiv x \pmod{5}\] \[N \equiv 5x \pmod{6}\] \[2N\equiv 6x \pmod{10}\]

Say that $x=5m+n$ (m is between 0-6, n is 0-4 because of constraints on x) Then

\[N \equiv 5m+n \pmod{5}\] \[N \equiv 25m+5n \pmod{6}\] \[2N\equiv30m + 6n \pmod{10}\]

and this simplifies to

\[N \equiv n \pmod{5}\] \[N \equiv m+5n \pmod{6}\] \[2N\equiv 6n \pmod{10}\]

From careful inspection, this is true when

$n=0, m=6$

$n=1, m=6$

$n=2, m=2$

$n=3, m=2$

$n=4, m=4$

This gives you $5$ choices for $x$, and $5$ choices for $y$, so the answer is $5* 5 = \boxed{\textbf{(E) }25}$

Solution 2 (Shortcut)

Notice that there are exactly $1000-100=900=5^2\cdot 6^2$ possible values of $N$. This means, in $100\le N\le 999$, every possible combination of $2$ digits will happen exactly once. We know that $N=900,901,902,903,904$ works because $900\equiv\dots00_5\equiv\dots00_6$.

We know for sure that the units digit will add perfectly every $30$ added or subtracted, because $\text{lcm }5,6=30$. So we only have to care about cases of $N$ every $30$ subtracted. In each case, $2N$ subtracts $6$/adds $4$, $N_5$ subtracts $1$ and $N_6$ adds $1$ for the $10$'s digit.

\[\textbf{5 }\textcolor{red}{\text{ 0}}\text{ 4 3 2 1 0 }\textcolor{red}{\text{4}}\text{ 3 2 1 0 4 3 2 1 0 4 }\textcolor{red}{\text{3 2}}\text{ 1 0 4 3 2 1 0 4 3 2 }\textcolor{red}{\text{1}}\]

\[\textbf{6 }\textcolor{red}{\text{ 0}}\text{ 1 2 3 4 5 }\textcolor{red}{\text{0}}\text{ 1 2 3 4 5 0 1 2 3 4 }\textcolor{red}{\text{5 0}}\text{ 1 2 3 4 5 0 1 2 3 4 }\textcolor{red}{\text{5}}\]

\[\textbf{10}\textcolor{red}{\text{ 0}}\text{ 4 8 2 6 0 }\textcolor{red}{\text{4}}\text{ 8 2 6 0 4 8 2 6 0 4 }\textcolor{red}{\text{8 2}}\text{ 6 0 4 8 2 6 0 4 8 2 }\textcolor{red}{\text{6}}\]

As we can see, there are $5$ cases, including the original, that work. These are highlighted in $\textcolor{red}{\text{red}}$. So, thus, there are $5$ possibilities for each case, and $5\cdot 5=\boxed{\textbf{(E) }25}$.


Solution 3

Notice that $N_5$ ranges from $3$ to $5$ digits and $N_6$ ranges from $3$ to $4$ digits.

Then let $a_i$, $b_i$ denotes the digits of $N_5$, $N_6$, respectively such that \[0\le a_i<5,0\le b_i<6\] Thus we have \[N=5^4a_1+5^3a_2+5^2a_3+5a_4+a_5=6^3b_1+6^2b_2+6b_3+b_4\] \[625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4\] Now we are given \[2N \equiv S \equiv N_5+N_6\pmod{100}\] \[2(625a_1+125a_2+25a_3+5a_4+a_5) \equiv (10000a_1+1000a_2+100a_3+10a_4+a_5)+(1000b_1+100b_2+10b_3+b_4)\pmod{100}\] \[1250a_1+250a_2+50a_3+10a_4+2a_5 \equiv 10000a_1+1000a_2+1000b_1+100a_3+100b_2+10a_4+10b_3+a_5+b_4\pmod{100}\] \[50a_1+50a_2+50a_3+10a_4+2a_5 \equiv 10a_4+10b_3+a_5+b_4\pmod{100}\] Moving the $a_5$ to left, we have \[50a_1+50a_2+50a_3+10a_4+a_5 \equiv 10a_4+10b_3+b_4\pmod{100}\]

Since $a_5$, $b_4$ determine the unit digits of the two sides of the congruence equation, we have $a_5=b_4=0,1,2,3,4$. Thus,

\[50a_1+50a_2+50a_3+10a_4 \equiv 10a_4+10b_3\pmod{100}\] canceling out $10a_4$, we have \[50a_1+50a_2+50a_3 \equiv 10b_3\pmod{100}\] \[5a_1+5a_2+5a_3 \equiv b_3\pmod{10}\] Thus $b_3$ is a multiple of $5$ and the possibilities are $b_3=0,5$.

In addition, since $N$ is a three digits integer, the only values for $a_1$ are $a_1=0,1$, or otherwise $625a_1$ will exceed 1000.

Now going back to our original equation \[625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4\] Since $a_5=b_4$, \[625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3\] \[5(125a_1+25a_2+5a_3+a_4)=6(36b_1+6b_2+b_3)\] \[5(125a_1+25a_2+5a_3+a_4)=6[6(6b_1+b_2)+b_3]\]

Since the left hand side is a multiple of $5$, then so does the right hand side. Thus $5\mid6(6b_1+b_2)+b_3$.

Since we already know that $5\midb_3$ (Error compiling LaTeX. Unknown error_msg), $5\mid6(6b_1+b_2)$, from where we also know that $5\mid6b_1+b_2$ is a multiple of $5$.

For $b_1,b_2<6$, there is a total of 7 ordered pairs that satisfy the condition. Namely,

\[(b_1,b_2)=(0,0),(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)\]

Since $N_6$ has at least $3$ digits, $(b_1,b_2)=(0,0)$ doesn't work. Furthermore, when $b_1=5$, $625b_1$ exceeds $1000$ which is not possible as $N$ is a three digits number, thus $(b_1,b_2)=(5,0)$ won't work as well.

Since we know that $a_i<5$, for each of the other order pairs, there is respectively one and only one solution (a_1,a_2,a_3,a_5) that satisfies the equation

\[625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3\]

Thus there are five solutions for the equation. Also since we have 5 possibilities for $a_5=b_4$, we have a total of $5\cdot5=25$ values for $N$. $\boxed{\mathrm{(E)}}$

~ Nafer


2013 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 22
Followed by
Problem 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions
2013 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 24
Followed by
Last Question
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 10 Problems and Solutions

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