https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Dragonrider01&feedformat=atom AoPS Wiki - User contributions [en] 2021-10-22T20:30:46Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10A_Problems/Problem_19&diff=154454 2018 AMC 10A Problems/Problem 19 2021-05-30T01:34:28Z <p>Dragonrider01: /* Solution 3 */</p> <hr /> <div>==Problem==<br /> <br /> A number &lt;math&gt;m&lt;/math&gt; is randomly selected from the set &lt;math&gt;\{11,13,15,17,19\}&lt;/math&gt;, and a number &lt;math&gt;n&lt;/math&gt; is randomly selected from &lt;math&gt;\{1999,2000,2001,\ldots,2018\}&lt;/math&gt;. What is the probability that &lt;math&gt;m^n&lt;/math&gt; has a units digit of &lt;math&gt;1&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) } \frac{1}{5} \qquad \textbf{(B) } \frac{1}{4} \qquad \textbf{(C) } \frac{3}{10} \qquad \textbf{(D) } \frac{7}{20} \qquad \textbf{(E) } \frac{2}{5} &lt;/math&gt;<br /> <br /> == Solution 1 ==<br /> Since we only care about the units digit, our set &lt;math&gt;\{11,13,15,17,19 \}&lt;/math&gt; can be turned into &lt;math&gt;\{1,3,5,7,9 \}&lt;/math&gt;. Call this set &lt;math&gt;A&lt;/math&gt; and call &lt;math&gt;\{1999, 2000, 2001, \cdots , 2018 \}&lt;/math&gt; set &lt;math&gt;B&lt;/math&gt;. Let's do casework on the element of &lt;math&gt;A&lt;/math&gt; that we choose. Since &lt;math&gt;1\cdot 1=1&lt;/math&gt;, any number from &lt;math&gt;B&lt;/math&gt; can be paired with &lt;math&gt;1&lt;/math&gt; to make &lt;math&gt;1^n&lt;/math&gt; have a units digit of &lt;math&gt;1&lt;/math&gt;. Therefore, the probability of this case happening is &lt;math&gt;\frac{1}{5}&lt;/math&gt; since there is a &lt;math&gt;\frac{1}{5}&lt;/math&gt; chance that the number &lt;math&gt;1&lt;/math&gt; is selected from &lt;math&gt;A&lt;/math&gt;. Let us consider the case where the number &lt;math&gt;3&lt;/math&gt; is selected from &lt;math&gt;A&lt;/math&gt;. Let's look at the unit digit when we repeatedly multiply the number &lt;math&gt;3&lt;/math&gt; by itself:<br /> &lt;cmath&gt;3\cdot 3=9&lt;/cmath&gt;<br /> &lt;cmath&gt;9\cdot 3=7&lt;/cmath&gt; <br /> &lt;cmath&gt;7\cdot 3=1&lt;/cmath&gt;<br /> &lt;cmath&gt;1\cdot 3=3&lt;/cmath&gt;<br /> We see that the unit digit of &lt;math&gt;3^x&lt;/math&gt;, for some integer &lt;math&gt;x&lt;/math&gt;, will only be &lt;math&gt;1&lt;/math&gt; when &lt;math&gt;x&lt;/math&gt; is a multiple of &lt;math&gt;4&lt;/math&gt;. Now, let's count how many numbers in &lt;math&gt;B&lt;/math&gt; are divisible by &lt;math&gt;4&lt;/math&gt;. This can be done by simply listing:<br /> &lt;cmath&gt;2000,2004,2008,2012,2016.&lt;/cmath&gt;<br /> There are &lt;math&gt;5&lt;/math&gt; numbers in &lt;math&gt;B&lt;/math&gt; divisible by &lt;math&gt;4&lt;/math&gt; out of the &lt;math&gt;2018-1999+1=20&lt;/math&gt; total numbers. Therefore, the probability that &lt;math&gt;3&lt;/math&gt; is picked from &lt;math&gt;A&lt;/math&gt; and a number divisible by &lt;math&gt;4&lt;/math&gt; is picked from &lt;math&gt;B&lt;/math&gt; is &lt;math&gt;\frac{1}{5}\cdot \frac{5}{20}=\frac{1}{20}.&lt;/math&gt;<br /> Similarly, we can look at the repeating units digit for &lt;math&gt;7&lt;/math&gt;:<br /> &lt;cmath&gt;7\cdot 7=9&lt;/cmath&gt;<br /> &lt;cmath&gt;9\cdot 7=3&lt;/cmath&gt;<br /> &lt;cmath&gt;3\cdot 7=1&lt;/cmath&gt;<br /> &lt;cmath&gt;1\cdot 7=7&lt;/cmath&gt;<br /> We see that the unit digit of &lt;math&gt;7^y&lt;/math&gt;, for some integer &lt;math&gt;y&lt;/math&gt;, will only be &lt;math&gt;1&lt;/math&gt; when &lt;math&gt;y&lt;/math&gt; is a multiple of &lt;math&gt;4&lt;/math&gt;. This is exactly the same conditions as our last case with &lt;math&gt;3&lt;/math&gt; so the probability of this case is also &lt;math&gt;\frac{1}{20}&lt;/math&gt;. <br /> Since &lt;math&gt;5\cdot 5=25&lt;/math&gt; and &lt;math&gt;25&lt;/math&gt; ends in &lt;math&gt;5&lt;/math&gt;, the units digit of &lt;math&gt;5^w&lt;/math&gt;, for some integer, &lt;math&gt;w&lt;/math&gt; will always be &lt;math&gt;5&lt;/math&gt;. Thus, the probability in this case is &lt;math&gt;0&lt;/math&gt;.<br /> The last case we need to consider is when the number &lt;math&gt;9&lt;/math&gt; is chosen from &lt;math&gt;A&lt;/math&gt;. This happens with probability &lt;math&gt;\frac{1}{5}.&lt;/math&gt; We list out the repeating units digit for &lt;math&gt;9&lt;/math&gt; as we have done for &lt;math&gt;3&lt;/math&gt; and &lt;math&gt;7&lt;/math&gt;:<br /> &lt;cmath&gt;9\cdot 9=1&lt;/cmath&gt;<br /> &lt;cmath&gt;1\cdot 9=9&lt;/cmath&gt;<br /> We see that the units digit of &lt;math&gt;9^z&lt;/math&gt;, for some integer &lt;math&gt;z&lt;/math&gt;, is &lt;math&gt;1&lt;/math&gt; only when &lt;math&gt;z&lt;/math&gt; is an even number. From the &lt;math&gt;20&lt;/math&gt; numbers in &lt;math&gt;B&lt;/math&gt;, we see that exactly half of them are even. The probability in this case is &lt;math&gt;\frac{1}{5}\cdot \frac{1}{2}=\frac{1}{10}.&lt;/math&gt;<br /> Finally, we can add all of our probabilities together to get <br /> &lt;cmath&gt;\frac{1}{5}+\frac{1}{20}+\frac{1}{20}+\frac{1}{10}=\boxed{\frac{2}{5}}.&lt;/cmath&gt;<br /> <br /> ~Nivek<br /> <br /> ~very minor edits by virjoy2001<br /> <br /> == Solution 2 ==<br /> Since only the units digit is relevant, we can turn the first set into &lt;math&gt;\{1,3,5,7,9\}&lt;/math&gt;. Note that &lt;math&gt;x^4 \equiv 1 \mod 10&lt;/math&gt; for all odd digits &lt;math&gt;x&lt;/math&gt;, except for 5. Looking at the second set, we see that it is a set of all integers between 1999 and 2018. There are 20 members of this set, which means that, &lt;math&gt;\mod 4&lt;/math&gt;, this set has 5 values which correspond to &lt;math&gt;\{0,1,2,3\}&lt;/math&gt;, making the probability equal for all of them. Next, check the values for which it is equal to &lt;math&gt;1 \mod 10&lt;/math&gt;. There are &lt;math&gt;4+1+0+1+2=8&lt;/math&gt; values for which it is equal to 1, remembering that &lt;math&gt;5^{4n} \equiv 1 \mod 10&lt;/math&gt; only if &lt;math&gt;n=0&lt;/math&gt;, which it is not. There are 20 values in total, and simplifying &lt;math&gt;\frac{8}{20}&lt;/math&gt; gives us &lt;math&gt;\boxed{\frac{2}{5}}&lt;/math&gt; or &lt;math&gt;\boxed{E}&lt;/math&gt;.<br /> <br /> &lt;math&gt;QED\blacksquare&lt;/math&gt;<br /> ==Solution 3==<br /> By Euler's Theorem, we have that &lt;math&gt;a^{4}=1 \pmod {10}&lt;/math&gt;, if &lt;math&gt;\gcd(a,10)=1&lt;/math&gt;. <br /> Hence &lt;math&gt;m=11,13,17,19&lt;/math&gt;, &lt;math&gt;n=2000,2004,2008,2012,2016&lt;/math&gt; work. <br /> <br /> Also note that &lt;math&gt;11^{\text{any positive integer}}\equiv 1 \pmod {10}&lt;/math&gt; because &lt;math&gt;11^b=(10+1)^b=10^b+10^{b-1}1+...+10(1)+1&lt;/math&gt;, and the latter &lt;math&gt;\pmod {10}&lt;/math&gt; is clearly &lt;math&gt;1&lt;/math&gt;. So &lt;math&gt;m=11&lt;/math&gt;, &lt;math&gt;n=1999,2001,2002,2003,2005,...,2018&lt;/math&gt; work (not counting multiples of 4 as we would be double counting if we did). <br /> <br /> We can also note that &lt;math&gt;19^{2a}\equiv 1 \pmod {10}&lt;/math&gt; because &lt;math&gt;19^{2a}=361^{a}&lt;/math&gt;, and by the same logic as why &lt;math&gt;11^{\text{any positive integer}}\equiv 1 \pmod {10}&lt;/math&gt;, we are done. Hence &lt;math&gt;m=19&lt;/math&gt;, and &lt;math&gt;n=2002, 2006, 2010, 2014, 2018&lt;/math&gt; work (not counting any of the aforementioned cases as that would be double counting). <br /> <br /> We cannot make any more observations that add more &lt;math&gt;m^n&lt;/math&gt; with units digit &lt;math&gt;1&lt;/math&gt;, hence the number of &lt;math&gt;m^n&lt;/math&gt; that have units digit one is &lt;math&gt;4\cdot 5+1\cdot 15+1\cdot 5=40&lt;/math&gt;. And the total number of combinations of an element of the set of all &lt;math&gt;m&lt;/math&gt; and an element of the set of all &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;5\cdot 20=100&lt;/math&gt;. Hence the desired probability is &lt;math&gt;\frac{40}{100}=\frac{2}{5}&lt;/math&gt;, which is answer choice &lt;math&gt;\textbf{(E)}&lt;/math&gt;. <br /> ~vsamc<br /> <br /> ==Video Solution==<br /> https://youtu.be/M22S82Am2zM?t=630<br /> ~IceMatrix<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2018|ab=A|num-b=18|num-a=20}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Introductory Number Theory Problems]]<br /> [[Category:Introductory Probability Problems]]</div> Dragonrider01