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

Latest revision as of 17:45, 8 November 2024

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 $b < 5$ (because otherwise $a$ and $b$ will have different parities), and thus $a=b$ . $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 5x \pmod{6}$ $N \equiv 6x \equiv x \pmod{5}$ $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

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$ work 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}$ Canceling out $a_5$ left with $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}$ $5(a_1+a_2+a_3) \equiv b_3\pmod{10}$

Thus $b_3$ is a multiple of $5$ .

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 side is a multiple of $5$ , then so does the right side. Thus $5\mid6(6b_1+b_2)+b_3$ .

Since we already know that $5\mid b_3$ , then $5\mid6(6b_1+b_2)$ , from where we also know that $5\mid6b_1+b_2$ .

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$ , $216b_1$ exceeds $1000$ which is not possible as $N$ is a three digit number, thus $(b_1,b_2)=(5,0)$ won't work as well.

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

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

Thus there are five solutions to 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{\textbf{(E) }25}$

~ Nafer

Solution 4

Observe that the maximum possible value of the sum of the last two digits of the base $5$ number and the base $6$ number is $44+55=99$ . Let $N \equiv a \pmod {25}$ and $N \equiv b \pmod {36}$ .

If $a < \frac{25}{2}$ , $2N \equiv 2a \pmod {25}$ and if $a > \frac{25}{2}$ , $2N \equiv 2a - 25 \pmod {25}$ .

Using the same logic for $b$ , if $b < 18$ , $2N \equiv 2b \pmod {36}$ , and in the other case $2N \equiv 2b - 36 \pmod {36}$ .

We can do four cases:

Case 1: $a + b = 2a - 25 + 2b - 36 \implies a + b = 61$ .

For this case, there is trivially only one possible solution, $(a, b) = (25, 36)$ , which is equivalent to $(a, b) = (0, 0)$ .

Case 2: $a + b = 2a - 25 + 2b \implies a + b = 25$ .

Note that in this case, $a \geq 13$ must hold, and $b < 18$ must hold. We find the possible ordered pairs to be: $(13, 12), (14, 11), (15, 10), ..., (24, 1)$ for a total of $12$ ordered pairs.

Case 3: $a + b = 2a + 2b - 36 \implies a + b = 36$ .

Note that in this case, $b \geq 18$ must hold, and $a < 13$ must hold. We find the possible ordered pairs to be: $(24, 12), (25, 11), (26, 10), ..., (35, 1)$ for a total of $12$ ordered pairs.

Case 4: $a + b = 2a + 2b$ .

Trivially no solutions except $(a, b) = (0, 0)$ , which matches the solution in Case 1, which makes this an overcount.

By CRT, each solution $(a, b)$ corresponds exactly one positive integer in a set of exactly $\text{lcm} (25, 36) = 900$ consecutive positive integers, and since there are $900$ positive integers between $100$ and $999$ , our induction is complete, and our answer is $1 + 12 + 12 = \boxed{\textbf{(E) }25}$ .

~ fidgetboss_4000

Video Solution

https://www.youtube.com/watch?v=tgCK-H5jsOE&t=497s

@@ Line 14: / Line 14: @@
 also that <math>N \equiv b \pmod{5}</math>
-Substituting these equations into the question and setting the units digits of <math>2N</math> and <math>S</math> equal to each other, it can be seen that <math>a=b</math>, and <math>b < 5</math>, (otherwise <math>a</math> and <math>b</math> always have different parities) so
+Substituting these equations into the question and setting the units digits of <math>2N</math> and <math>S</math> equal to each other, it can be seen that <math>b < 5</math> (because otherwise <math>a</math> and <math>b</math> will have different parities), and thus <math>a=b</math>.
 <math>N \equiv a \pmod{6}</math>,
 <math>N \equiv  a \pmod{5}</math>,
@@ Line 36: / Line 36: @@
 Now, since <math>y=0,1,2,3,4</math> will always work if <math>x</math> works, then we can treat <math>x</math> as a units digit instead of a tens digit in the respective bases and decrease the mods so that <math>x</math> is now the units digit.
+<cmath>N \equiv 5x \pmod{6}</cmath>
 <cmath>N \equiv 6x \equiv x \pmod{5}</cmath>
-<cmath>N \equiv 5x \pmod{6}</cmath>
 <cmath>2N\equiv 6x \pmod{10}</cmath>
@@ Line 68: / Line 68: @@
 <math>5* 5 = \boxed{\textbf{(E) }25}</math>
-==Solution 2 (Shortcut)==
+==Solution 2==
-Notice that there are exactly <math>1000-100=900=5^2\cdot 6^2</math> possible values of <math>N</math>. This means, in <math>100\le N\le 999</math>, every possible combination of <math>2</math> digits will happen exactly once. We know that <math>N=900,901,902,903,904</math> works because <math>900\equiv\dots00_5\equiv\dots00_6</math>.
+Notice that there are exactly <math>1000-100=900=5^2\cdot 6^2</math> possible values of <math>N</math>. This means, in <math>100\le N\le 999</math>, every possible combination of <math>2</math> digits will happen exactly once. We know that <math>N=900,901,902,903,904</math> work because <math>900\equiv\dots00_5\equiv\dots00_6</math>.
-We know for sure that the units digit will add perfectly every <math>30</math> added or subtracted, because <math>\text{lcm }5,6=30</math>. So we only have to care about cases of <math>N</math> every <math>30</math> subtracted. In each case, <math>2N</math> subtracts <math>6</math>/adds <math>4</math>, <math>N_5</math> subtracts <math>1</math> and <math>N_6</math> adds <math>1</math> for the <math>10</math>'s digit.
+We know for sure that the units digit will add perfectly every <math>30</math> added or subtracted, because <math>\text{lcm }(5, 6)=30</math>. So we only have to care about cases of <math>N</math> every <math>30</math> subtracted. In each case, <math>2N</math> subtracts <math>6</math>/adds <math>4</math>, <math>N_5</math> subtracts <math>1</math> and <math>N_6</math> adds <math>1</math> for the <math>10</math>'s digit.
 <cmath>\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}}</cmath>
@@ Line 81: / Line 81: @@
 As we can see, there are <math>5</math> cases, including the original, that work. These are highlighted in <math>\textcolor{red}{\text{red}}</math>. So, thus, there are <math>5</math> possibilities for each case, and <math>5\cdot 5=\boxed{\textbf{(E) }25}</math>.
+== Solution 3 ==
+Notice that <math>N_5</math> ranges from <math>3</math> to <math>5</math> digits and <math>N_6</math> ranges from <math>3</math> to <math>4</math> digits.
+Then let <math>a_i</math>, <math>b_i</math> denotes the digits of <math>N_5</math>, <math>N_6</math>, respectively such that <cmath>0\le a_i<5,0\le b_i<6</cmath> Thus we have <cmath>N=5^4a_1+5^3a_2+5^2a_3+5a_4+a_5=6^3b_1+6^2b_2+6b_3+b_4</cmath>
+<cmath>625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4</cmath>
+Now we are given <cmath>2N \equiv S \equiv N_5+N_6\pmod{100}</cmath>
+<cmath>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}</cmath>
+<cmath>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}</cmath>
+<cmath>50a_1+50a_2+50a_3+10a_4+2a_5 \equiv 10a_4+10b_3+a_5+b_4\pmod{100}</cmath>
+Canceling out <math>a_5</math> left with
+<cmath>50a_1+50a_2+50a_3+10a_4+a_5 \equiv 10a_4+10b_3+b_4\pmod{100}</cmath>
+Since <math>a_5</math>, <math>b_4</math> determine the unit digits of the two sides of the congruence equation, we have <math>a_5=b_4=0,1,2,3,4</math>. Thus,
+<cmath>50a_1+50a_2+50a_3+10a_4 \equiv 10a_4+10b_3\pmod{100}</cmath> canceling out <math>10a_4</math>, we have
+<cmath>50a_1+50a_2+50a_3 \equiv 10b_3\pmod{100}</cmath>
+<cmath>5a_1+5a_2+5a_3 \equiv b_3\pmod{10}</cmath>
+<cmath>5(a_1+a_2+a_3) \equiv b_3\pmod{10}</cmath>
+Thus <math>b_3</math> is a multiple of <math>5</math>.
+Now going back to our original equation
+<cmath>625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4</cmath>
+Since <math>a_5=b_4</math>,
+<cmath>625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3</cmath>
+<cmath>5(125a_1+25a_2+5a_3+a_4)=6(36b_1+6b_2+b_3)</cmath>
+<cmath>5(125a_1+25a_2+5a_3+a_4)=6[6(6b_1+b_2)+b_3]</cmath>
+Since the left side is a multiple of <math>5</math>, then so does the right side. Thus <math>5\mid6(6b_1+b_2)+b_3</math>.
+Since we already know that <math>5\mid b_3</math>, then <math>5\mid6(6b_1+b_2)</math>, from where we also know that <math>5\mid6b_1+b_2</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>216b_1</math> exceeds <math>1000</math> which is not possible as <math>N</math> is a three digit 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 ordered pairs <math>(b_1,b_2)</math>, there is respectively one and only one solution <math>(a_1,a_2,a_3,a_4)</math> 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 to 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{\textbf{(E) }25}</math>
+~ Nafer
+==Solution 4==
+Observe that the maximum possible value of the sum of the last two digits of the base <math>5</math> number and the base <math>6</math> number is <math>44+55=99</math>.
+Let <math>N \equiv a \pmod {25}</math> and <math>N \equiv b \pmod {36}</math>.
+If <math>a < \frac{25}{2}</math>, <math>2N \equiv 2a \pmod {25}</math> and if <math>a > \frac{25}{2}</math>, <math>2N \equiv 2a - 25 \pmod {25}</math>.
+Using the same logic for <math>b</math>, if <math>b < 18</math>, <math>2N \equiv 2b \pmod {36}</math>, and in the other case <math>2N \equiv 2b - 36 \pmod {36}</math>.
+We can do four cases:
+Case 1: <math>a + b = 2a - 25 + 2b - 36 \implies a + b = 61</math>.
+For this case, there is trivially only one possible solution, <math>(a, b) = (25, 36)</math>, which is equivalent to <math>(a, b) = (0, 0)</math>.
+Case 2: <math>a + b = 2a - 25 + 2b \implies a + b = 25</math>.
+Note that in this case, <math>a \geq 13</math> must hold, and <math>b < 18</math> must hold.
+We find the possible ordered pairs to be: <math>(13, 12), (14, 11), (15, 10), ..., (24, 1)</math> for a total of <math>12</math> ordered pairs.
+Case 3: <math>a + b = 2a + 2b - 36 \implies a + b = 36</math>.
+Note that in this case, <math>b \geq 18</math> must hold, and <math>a < 13</math> must hold.
+We find the possible ordered pairs to be: <math>(24, 12), (25, 11), (26, 10), ..., (35, 1)</math> for a total of <math>12</math> ordered pairs.
+Case 4: <math>a + b = 2a + 2b</math>.
+Trivially no solutions except <math>(a, b) = (0, 0)</math>, which matches the solution in Case 1, which makes this an overcount.
+By CRT, each solution <math>(a, b)</math> corresponds exactly one positive integer in a set of exactly <math>\text{lcm} (25, 36) = 900</math> consecutive positive integers, and since there are <math>900</math> positive integers between <math>100</math> and <math>999</math>, our induction is complete, and our answer is <math>1 + 12 + 12 = \boxed{\textbf{(E) }25}</math>.
+~ fidgetboss_4000
+==Video Solution==
+https://www.youtube.com/watch?v=tgCK-H5jsOE&t=497s
+==See Also==
 {{AMC12 box|year=2013|ab=B|num-b=22|num-a=24}}

2013 AMC 12B (Problems • Answer Key • Resources)
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 (Problems • Answer Key • Resources)
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

Page

Toolbox

Search