https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Jimy&feedformat=atom AoPS Wiki - User contributions [en] 2021-06-19T11:34:29Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_11&diff=155564 2018 AIME I Problems/Problem 11 2021-06-08T12:47:03Z <p>Jimy: /* Modular Arithmetic Solution- Strange (MASS) */</p> <hr /> <div><br /> ==Problem==<br /> Find the least positive integer &lt;math&gt;n&lt;/math&gt; such that when &lt;math&gt;3^n&lt;/math&gt; is written in base &lt;math&gt;143&lt;/math&gt;, its two right-most digits in base &lt;math&gt;143&lt;/math&gt; are &lt;math&gt;01&lt;/math&gt;.<br /> <br /> ==Solutions==<br /> <br /> ==Modular Arithmetic Solution- Strange (MASS)==<br /> Note that the given condition is equivalent to &lt;math&gt;3^n \equiv 1 \pmod{143^2}&lt;/math&gt; and &lt;math&gt;143=11\cdot 13&lt;/math&gt;. Because &lt;math&gt;\gcd(11^2, 13^2) = 1&lt;/math&gt;, the desired condition is equivalent to &lt;math&gt;3^n \equiv 1 \pmod{121}&lt;/math&gt; and &lt;math&gt;3^n \equiv 1 \pmod{169}&lt;/math&gt;.<br /> <br /> If &lt;math&gt;3^n \equiv 1 \pmod{121}&lt;/math&gt;, one can see the sequence &lt;math&gt;1, 3, 9, 27, 81, 1, 3, 9...&lt;/math&gt; so &lt;math&gt;5|n&lt;/math&gt;.<br /> <br /> Now if &lt;math&gt;3^n \equiv 1 \pmod{169}&lt;/math&gt;, it is harder. But we do observe that &lt;math&gt;3^3 \equiv 1 \pmod{13}&lt;/math&gt;, therefore &lt;math&gt;3^3 = 13a + 1&lt;/math&gt; for some integer &lt;math&gt;a&lt;/math&gt;. So our goal is to find the first number &lt;math&gt;p_1&lt;/math&gt; such that &lt;math&gt;(13a+1)^ {p_1} \equiv 1 \pmod{169}&lt;/math&gt;. Then, &lt;math&gt;p_1 \equiv 0 \pmod{13}, &lt;/math&gt; which follows from the binomial theorem. It is not difficult to see that the smallest &lt;math&gt;p_1=13&lt;/math&gt;, so ultimately &lt;math&gt;3^{39} \equiv 1 \pmod{169}&lt;/math&gt;. Therefore, &lt;math&gt;39|n&lt;/math&gt;.<br /> <br /> The first &lt;math&gt;n&lt;/math&gt; satisfying both criteria is thus &lt;math&gt;5\cdot 39=\boxed{195}&lt;/math&gt;.<br /> <br /> -expiLnCalc<br /> <br /> ==Solution 2==<br /> Note that Euler's Totient Theorem would not necessarily lead to the smallest &lt;math&gt;n&lt;/math&gt; and that in this case that &lt;math&gt;n&lt;/math&gt; is greater than &lt;math&gt;1000&lt;/math&gt;. <br /> <br /> We wish to find the least &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;3^n \equiv 1 \pmod{143^2}&lt;/math&gt;. This factors as &lt;math&gt;143^2=11^{2}*13^{2}&lt;/math&gt;. Because &lt;math&gt;gcd(121, 169) = 1&lt;/math&gt;, we can simply find the least &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;3^n \equiv 1 \pmod{121}&lt;/math&gt; and &lt;math&gt;3^n \equiv 1 \pmod{169}&lt;/math&gt;.<br /> <br /> Quick inspection yields &lt;math&gt;3^5 \equiv 1 \pmod{121}&lt;/math&gt; and &lt;math&gt;3^3 \equiv 1 \pmod{13}&lt;/math&gt;. Now we must find the smallest &lt;math&gt;k&lt;/math&gt; such that &lt;math&gt;3^{3k} \equiv 1 \pmod{13}&lt;/math&gt;. Euler's gives &lt;math&gt;3^{156} \equiv 1 \pmod{169}&lt;/math&gt;. So &lt;math&gt;3k&lt;/math&gt; is a factor of &lt;math&gt;156&lt;/math&gt;. This gives &lt;math&gt;k=1,2, 4, 13, 26, 52&lt;/math&gt;. Some more inspection yields &lt;math&gt;k=13&lt;/math&gt; is the smallest valid &lt;math&gt;k&lt;/math&gt;. So &lt;math&gt;3^5 \equiv 1 \pmod{121}&lt;/math&gt; and &lt;math&gt;3^{39} \equiv 1 \pmod{169}&lt;/math&gt;. The least &lt;math&gt;n&lt;/math&gt; satisfying both is &lt;math&gt;lcm(5, 39)=\boxed{195}&lt;/math&gt;. (RegularHexagon)<br /> <br /> ==Solution 3 (Big Bash)==<br /> Listing out the powers of &lt;math&gt;3&lt;/math&gt;, modulo &lt;math&gt;169&lt;/math&gt; and modulo &lt;math&gt;121&lt;/math&gt;, we have:<br /> &lt;cmath&gt;\begin{array}{c|c|c}<br /> n &amp; 3^n\mod{169} &amp; 3^n\mod{121}\\ \hline<br /> 0 &amp; 1 &amp; 1\\<br /> 1 &amp; 3 &amp; 3\\<br /> 2 &amp; 9 &amp; 9\\<br /> 3 &amp; 27 &amp; 27\\<br /> 4 &amp; 81 &amp; 81\\<br /> 5 &amp; 74 &amp; 1\\<br /> 6 &amp; 53\\<br /> 7 &amp; 159\\<br /> 8 &amp; 139\\<br /> 9 &amp; 79\\<br /> 10 &amp; 68\\<br /> 11 &amp; 35\\<br /> 12 &amp; 105\\<br /> 13 &amp; 146\\<br /> 14 &amp; 100\\<br /> 15 &amp; 131\\<br /> 16 &amp; 55\\<br /> 17 &amp; 165\\<br /> 18 &amp; 157\\<br /> 19 &amp; 133\\<br /> 20 &amp; 61\\<br /> 21 &amp; 14\\<br /> 22 &amp; 42\\<br /> 23 &amp; 126\\<br /> 24 &amp; 40\\<br /> 25 &amp; 120\\<br /> 26 &amp; 22\\<br /> 27 &amp; 66\\<br /> 28 &amp; 29\\<br /> 29 &amp; 87\\<br /> 30 &amp; 92\\<br /> 31 &amp; 107\\<br /> 32 &amp; 152\\<br /> 33 &amp; 118\\<br /> 34 &amp; 16\\<br /> 35 &amp; 48\\<br /> 36 &amp; 144\\<br /> 37 &amp; 94\\<br /> 38 &amp; 113\\<br /> 39 &amp; 1\\<br /> \end{array}&lt;/cmath&gt;<br /> <br /> The powers of &lt;math&gt;3&lt;/math&gt; repeat in cycles of &lt;math&gt;5&lt;/math&gt; an &lt;math&gt;39&lt;/math&gt; in modulo &lt;math&gt;121&lt;/math&gt; and modulo &lt;math&gt;169&lt;/math&gt;, respectively. The answer is &lt;math&gt;\text{lcm}(5, 39) = \boxed{195}&lt;/math&gt;.<br /> <br /> ==Solution 4(Order+Bash)==<br /> We have that &lt;cmath&gt;3^n \equiv 1 \pmod{143^2}.&lt;/cmath&gt;Now, &lt;math&gt;3^{110} \equiv 1 \pmod{11^2}&lt;/math&gt; so by the Fundamental Theorem of Orders, &lt;math&gt;\text{ord}_{11^2}(3)|110&lt;/math&gt; and with some bashing, we get that it is &lt;math&gt;5&lt;/math&gt;. Similarly, we get that &lt;math&gt;\text{ord}_{13^2}(3)=39&lt;/math&gt;. Now, &lt;math&gt;\text{lcm}(39,5)=\boxed{195}&lt;/math&gt; which is our desired solution.<br /> <br /> ==Solution 5 (Easy Binomial Theorem)==<br /> We wish to find the smallest &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;3^n\equiv 1\pmod{143^2}&lt;/math&gt;, so we want &lt;math&gt;n\equiv 1\pmod{121}&lt;/math&gt; and &lt;math&gt;n\equiv 1\pmod{169}&lt;/math&gt;. Note that &lt;math&gt;3^5\equiv 1\pmod{121}&lt;/math&gt;, so &lt;math&gt;3^n&lt;/math&gt; repeats &lt;math&gt;121&lt;/math&gt; with a period of &lt;math&gt;5&lt;/math&gt;, so &lt;math&gt;5|n&lt;/math&gt;. Now, in order for &lt;math&gt;n\equiv 1\pmod{169}&lt;/math&gt;, then &lt;math&gt;n\equiv 1\pmod{13}&lt;/math&gt;. Because &lt;math&gt;3^3\equiv 1\pmod{13}&lt;/math&gt;, &lt;math&gt;3^n&lt;/math&gt; repeats with a period of &lt;math&gt;3&lt;/math&gt;, so &lt;math&gt;3|n&lt;/math&gt;. <br /> Hence, we have that for some positive integer &lt;math&gt;p&lt;/math&gt;, &lt;math&gt;3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}&lt;/math&gt;, so &lt;math&gt;26p\equiv 0\pmod{169}&lt;/math&gt; and &lt;math&gt;p\equiv 0\pmod{13}&lt;/math&gt;. Thus, we have that &lt;math&gt;5|n&lt;/math&gt;, &lt;math&gt;3|n&lt;/math&gt;, and &lt;math&gt;13|n&lt;/math&gt;, so the smallest possible value of &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;3\times5\times13=\boxed{195}&lt;/math&gt;.<br /> -Stormersyle<br /> <br /> ==Solution 6(LTE)==<br /> We can see that &lt;math&gt;3^n-1 = 143^2*x&lt;/math&gt;, which means that &lt;math&gt;v_{11}(3^n-1) \geq 2&lt;/math&gt;, &lt;math&gt;v_{13}(3^n-1) \geq 2&lt;/math&gt;. &lt;math&gt;v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})&lt;/math&gt;, &lt;math&gt;v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})&lt;/math&gt; by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as &lt;math&gt;v_{13}(3^n-1) \geq 2&lt;/math&gt;. Therefore the minimum possible value of n is &lt;math&gt;3\times5\times13=\boxed{195}&lt;/math&gt;.<br /> <br /> -bradleyguo<br /> <br /> ==Solution 7==<br /> Note that the problem is basically asking for the least positive integer &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;11^2 \cdot 13^2 | 3^n - 1.&lt;/math&gt; It is easy to see that &lt;math&gt;n = \text{lcm } (a, b),&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the least positive integer satisfying &lt;math&gt;11^2 | 3^a - 1&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; the least positive integer satisfying &lt;math&gt;13^2 | 3^b - 1&lt;/math&gt;. Luckily, finding &lt;math&gt;a&lt;/math&gt; is a relatively trivial task, as one can simply notice that &lt;math&gt;3^5 = 243 \equiv 1 \mod 121&lt;/math&gt;. However, finding &lt;math&gt;b&lt;/math&gt; is slightly more nontrivial. The order of &lt;math&gt;3^k&lt;/math&gt; modulo &lt;math&gt;13&lt;/math&gt; (which is &lt;math&gt;3&lt;/math&gt;) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of &lt;math&gt;3&lt;/math&gt; by &lt;math&gt;13&lt;/math&gt;, or one can notice that &lt;math&gt;3^3 = 27 \equiv 1 \mod 13&lt;/math&gt; (the latter which is the definition of period/orders by FLT). We can thus rewrite &lt;math&gt;3^3&lt;/math&gt; as &lt;math&gt;(2 \cdot 13 + 1) \mod 13^2&lt;/math&gt;. Now suppose that &lt;cmath&gt;3^{3k} \equiv (13n + 1) \mod 13^2. &lt;/cmath&gt; I claim that &lt;math&gt;3^{3(k+1)} \equiv (13(n+2) + 1) \mod 13^2. &lt;/math&gt;<br /> <br /> Proof:<br /> To find &lt;math&gt;3^{3(k+1)}, &lt;/math&gt; we can simply multiply &lt;math&gt;3^{3k}&lt;/math&gt; by &lt;math&gt;3^3, &lt;/math&gt; which is congruent to &lt;math&gt;2 \cdot 13 + 1&lt;/math&gt; modulo &lt;math&gt;13^2&lt;/math&gt;.<br /> By expanding the product out, we obtain &lt;cmath&gt;3^{3(k+1)} \equiv (13n + 1)(2 \cdot 13 + 1) = 13^2 \cdot 2n + 13n + 2 \cdot 13 + 1 \mod 13^2, &lt;/cmath&gt; and since the &lt;math&gt;13^2&lt;/math&gt; on the LHS cancels out, we're left with &lt;cmath&gt;13n + 2 \cdot 13 + 1 \mod 13^2 \implies 13(n+2) + 1 \mod 13^2&lt;/cmath&gt;. Thus, our claim is proven.<br /> Let &lt;math&gt;f(n)&lt;/math&gt; be the second to last digit when &lt;math&gt;3^{3k}&lt;/math&gt; is written in base &lt;math&gt;13^2&lt;/math&gt;. <br /> Using our proof, it is easy to see that &lt;math&gt;f(n)&lt;/math&gt; satisfies the recurrence &lt;math&gt;f(1) = 2&lt;/math&gt; and &lt;math&gt;f(n+1) = f(n) + 2&lt;/math&gt;. Since this implies &lt;math&gt;f(n) = 2n, &lt;/math&gt; we just have to find the least positive integer &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;2n&lt;/math&gt; is a multiple of &lt;math&gt;13&lt;/math&gt;, which is trivially obtained as &lt;math&gt;13&lt;/math&gt;.<br /> The least integer &lt;math&gt;n&lt;/math&gt; such that &lt;math&gt;3^n - 1&lt;/math&gt; is divisible by &lt;math&gt;13^2&lt;/math&gt; is &lt;math&gt;3 \cdot 13 = 39, &lt;/math&gt; so our final answer is &lt;math&gt;\text{lcm } (5, 39) = \boxed{195}.&lt;/math&gt;<br /> <br /> -fidgetboss_4000<br /> -minor edits made by srisainandan6<br /> <br /> ==Solution 8 (Official MAA)==<br /> The requested positive integer is the least value of &lt;math&gt;n&gt;0&lt;/math&gt; such that &lt;math&gt;3^n\equiv 1\pmod{143^2}.&lt;/math&gt; Note that &lt;math&gt;143=11\cdot 13.&lt;/math&gt; The least power of &lt;math&gt;3&lt;/math&gt; that is congruent to &lt;math&gt;1&lt;/math&gt; modulo &lt;math&gt;11^2&lt;/math&gt; is &lt;math&gt;3^5=243=2\cdot 11^2+1.&lt;/math&gt; It follows that. &lt;math&gt;3^n\equiv 1\pmod {11^2}&lt;/math&gt; if and only if &lt;math&gt;n=5j&lt;/math&gt; for some positive integer &lt;math&gt;j&lt;/math&gt;.<br /> <br /> The least power of &lt;math&gt;3&lt;/math&gt; that is congruent to &lt;math&gt;1&lt;/math&gt; modulo &lt;math&gt;13&lt;/math&gt; is &lt;math&gt;3^3=27=2\cdot 13+1.&lt;/math&gt; It follows that &lt;math&gt;3^n\equiv 1\pmod{13}&lt;/math&gt; if and only if &lt;math&gt;n=3k&lt;/math&gt; for some positive integer &lt;math&gt;k&lt;/math&gt;. Additionally, for some positive integer &lt;math&gt;k&lt;/math&gt;, the Binomial Theorem shows that &lt;math&gt;3^{3k}=(26+1)^k=26\cdot k+1 \pmod{13^2}&lt;/math&gt;. In particular, &lt;math&gt;3^n=3^{3k}\equiv 1\pmod {13^2}&lt;/math&gt; if and only if &lt;math&gt;k=13m&lt;/math&gt; for some positive integer &lt;math&gt;m&lt;/math&gt;, that is, if and only if &lt;math&gt;n=39m.&lt;/math&gt;<br /> <br /> Because &lt;math&gt;11^2&lt;/math&gt; and &lt;math&gt;13^2&lt;/math&gt; are relatively prime, &lt;math&gt;3^n\equiv 1\pmod {143^2}&lt;/math&gt; if and only if &lt;math&gt;3^n\equiv 1\pmod{11^2}&lt;/math&gt; and &lt;math&gt;3^n \equiv 1\pmod {13^2}&lt;/math&gt;. This occurs if and only if &lt;math&gt;n&lt;/math&gt; is a multiple of both of the relatively prime integers &lt;math&gt;5&lt;/math&gt; and &lt;math&gt;39&lt;/math&gt;, so the least possible value of &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;5\cdot 39=195.&lt;/math&gt;<br /> ==Video solution==<br /> https://www.youtube.com/watch?v=mF4qij3CNM8 - aopsuser305<br /> <br /> ==See Also==<br /> {{AIME box|year=2018|n=I|num-b=10|num-a=12}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=154134 2021 AIME I Problems/Problem 14 2021-05-23T15:20:37Z <p>Jimy: /* Solution 4 (Along the line of Solution 1) */</p> <hr /> <div>==Problem==<br /> For any positive integer &lt;math&gt;a, \sigma(a)&lt;/math&gt; denotes the sum of the positive integer divisors of &lt;math&gt;a&lt;/math&gt;. Let &lt;math&gt;n&lt;/math&gt; be the least positive integer such that &lt;math&gt;\sigma(a^n)-1&lt;/math&gt; is divisible by &lt;math&gt;2021&lt;/math&gt; for all positive integers &lt;math&gt;a&lt;/math&gt;. Find the sum of the prime factors in the prime factorization of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> ==Solution==<br /> We first claim that &lt;math&gt;n&lt;/math&gt; must be divisible by 42. Since &lt;math&gt;\sigma(a^n)-1&lt;/math&gt; is divisible by 2021 for all positive integers &lt;math&gt;a&lt;/math&gt;, we can first consider the special case where &lt;math&gt;a \neq 0,1 \pmod{43}&lt;/math&gt;.<br /> <br /> Then &lt;math&gt;\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)&lt;/math&gt;. In order for this expression to be divisible by &lt;math&gt;2021=43\times 47&lt;/math&gt;, a necessary condition is &lt;math&gt;a^n - 1 \equiv 0 \pmod{43}&lt;/math&gt;. By [[Fermat's Little Theorem]], &lt;math&gt;a^{42} \equiv 1 \pmod{43}&lt;/math&gt;. Moreover, if &lt;math&gt;a&lt;/math&gt; is a primitive root modulo 43, then &lt;math&gt;\text{ord}_{43}(a) = 42&lt;/math&gt;, so &lt;math&gt;n&lt;/math&gt; must be divisible by 42.<br /> <br /> By similar reasoning, &lt;math&gt;n&lt;/math&gt; must be divisible by 46, by considering &lt;math&gt;a \neq 0,1 \pmod{47}&lt;/math&gt;.<br /> <br /> We next claim that &lt;math&gt;n&lt;/math&gt; must be divisible by 43 and 47. Consider the case &lt;math&gt;a=2022&lt;/math&gt;. Then &lt;math&gt;\sigma(a^n) \equiv n \pmod{2021}&lt;/math&gt;, so &lt;math&gt;\sigma(2022^n)-1&lt;/math&gt; is divisible by 2021 if and only if &lt;math&gt;n&lt;/math&gt; is divisible by 2021.<br /> <br /> Lastly, we claim that if &lt;math&gt;n = \text{lcm}(42, 46, 43, 47)&lt;/math&gt;, then &lt;math&gt;\sigma(a^n) - 1&lt;/math&gt; is divisible by 2021 for all positive integers &lt;math&gt;a&lt;/math&gt;. The claim is trivially true for &lt;math&gt;a=1&lt;/math&gt; so suppose &lt;math&gt;a&gt;1&lt;/math&gt;. Let &lt;math&gt;a = p_1^{e_1}\ldots p_k^{e_k}&lt;/math&gt; be the prime factorization of &lt;math&gt;a&lt;/math&gt;. Since &lt;math&gt;\sigma&lt;/math&gt; is [[multiplicative function|multiplicative]], we have<br /> &lt;cmath&gt;\sigma(a^n) - 1 = \prod_{i=1}^k \sigma(p_i^{e_in}) - 1.&lt;/cmath&gt;<br /> We can show that &lt;math&gt;\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}&lt;/math&gt; for all primes &lt;math&gt;p_i&lt;/math&gt; and integers &lt;math&gt;e_i \ge 1&lt;/math&gt;, where<br /> &lt;cmath&gt;\sigma(p_i^{e_in}) = 1 + (p_i + p_i^2 + \ldots + p_i^n) + (p_i^{n+1} + \ldots + p_i^{2n}) + \ldots + (p_i^{n(e_i-1)+1} + \ldots + p_i^{e_in})&lt;/cmath&gt;<br /> where each expression in parentheses contains &lt;math&gt;n&lt;/math&gt; terms. It is easy to verify that if &lt;math&gt;p_i = 43&lt;/math&gt; or &lt;math&gt;p_i = 47&lt;/math&gt; then &lt;math&gt;\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}&lt;/math&gt; for this choice of &lt;math&gt;n&lt;/math&gt;, so suppose &lt;math&gt;p_i \not\equiv 0 \pmod{43}&lt;/math&gt; and &lt;math&gt;p_i \not\equiv 0 \pmod{47}&lt;/math&gt;. Each expression in parentheses equals &lt;math&gt;\frac{p_i^n - 1}{p_i - 1}&lt;/math&gt; multiplied by some power of &lt;math&gt;p_i&lt;/math&gt;. If &lt;math&gt;p_i \neq 1 \pmod{43}&lt;/math&gt;, then FLT implies &lt;math&gt;p_i^n - 1 \equiv 0 \pmod{43}&lt;/math&gt;, and if &lt;math&gt;p_i \equiv 1 \pmod{43}&lt;/math&gt;, then &lt;math&gt;p_i + p_i^2 + \ldots + p_i^n \equiv 1 + 1 + \ldots + 1 \equiv 0 \pmod{43}&lt;/math&gt; (since &lt;math&gt;n&lt;/math&gt; is also a multiple of 43, by definition). Similarly, we can show &lt;math&gt;\sigma(p_i^{e_in}) \equiv 1 \pmod{47}&lt;/math&gt;, and a simple [[Chinese Remainder Theorem|CRT]] argument shows &lt;math&gt;\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}&lt;/math&gt;. Then &lt;math&gt;\sigma(a^n) \equiv 1^k \equiv 1 \pmod{2021}&lt;/math&gt;.<br /> <br /> Then the prime factors of &lt;math&gt;n&lt;/math&gt; are &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, &lt;math&gt;7&lt;/math&gt;, &lt;math&gt;23&lt;/math&gt;, &lt;math&gt;43&lt;/math&gt;, and &lt;math&gt;47&lt;/math&gt;, and the answer is &lt;math&gt;2+3+7+23+43+47 = \boxed{125}&lt;/math&gt;. ~scrabbler94<br /> <br /> ==Solution 2 (cheap and not very reliable)==<br /> Since the problem works for all positive integers &lt;math&gt;a&lt;/math&gt;, let's plug in &lt;math&gt;a=2&lt;/math&gt; and see what we get. Since &lt;math&gt;\sigma({2^n}) = 2^{n+1}-1,&lt;/math&gt; we have &lt;math&gt;2^{n+1} \equiv 2 \pmod{2021}.&lt;/math&gt; Simplifying using CRT and [[Fermat's Little Theorem]], we get that &lt;math&gt;2^n \equiv 0 \pmod{42}&lt;/math&gt; and &lt;math&gt;2^n \equiv 0 \pmod{46}.&lt;/math&gt; Then, we can look at &lt;math&gt;a=2022&lt;/math&gt; just like in Solution 1 to find that &lt;math&gt;43&lt;/math&gt; and &lt;math&gt;47&lt;/math&gt; also divide &lt;math&gt;n&lt;/math&gt;. There don't seem to be any other odd &quot;numbers&quot; to check, so we can hopefully assume that the answer is the sum of the prime factors of &lt;math&gt;\text{lcm(42, 43, 46, 47)}.&lt;/math&gt; From here, follow solution 1 to get the final answer.<br /> <br /> -PureSwag<br /> <br /> ==Solution 3 (Kind of similar to Sol 2 and kind of what cosmicgenius said)==<br /> It says the problem implies that it works for all positive integers &lt;math&gt;a&lt;/math&gt;, we basically know that If &lt;math&gt;p \equiv 1 \pmod q&lt;/math&gt;, than from &quot;USEMO 2019 Problem 4 which was &lt;math&gt;p^n + p^{n-1} + ... + 1 \equiv 1&lt;/math&gt; (mod &lt;math&gt;q&lt;/math&gt;) we have that &lt;cmath&gt;\frac{p^{en+1}-1}{p-1} \equiv p^{en} + p^{en-1} + \dots + 1 \equiv en + 1 \equiv 1 \pmod q,&lt;/cmath&gt;. From here we can just let &lt;math&gt;\sigma(2^n)&lt;/math&gt; or be a power of 2 which we can do &lt;cmath&gt;\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1&lt;/cmath&gt; which is a geo series. We can plug in &lt;math&gt;a=2^a&lt;/math&gt; like in Solution 2 and use CRT which when we prime factorize we get that &lt;math&gt;2021 = 43 \cdot 47&lt;/math&gt; which like everyone knows. We use CRT to find that \begin{align*} 2^n &amp;\equiv 1 \pmod{43}, \\ 2^n &amp;\equiv 1 \pmod{47}. \end{align*}. We see that this is just FLT which is &lt;math&gt;a^{p-1} \equiv 1 \pmod p&lt;/math&gt; we see all multiples of 42 will work for first and 46 for the second. We can figure out that it is just &lt;math&gt;\text{lcm}(43-1,47-1)\cdot43\cdot47&lt;/math&gt; which when we add up we get that it's just the sum of the prime factors of lcm(42,43,46,47) which you can just look at Solution 1 to find out the sum of the prime factors and get the answer. <br /> <br /> Remarks: This was kind of used in what cosmicgenius and Solution 2 said and what mathisawesome2169 said and It &quot;Reminded me of 2019 USEMO Problem 4 when solving the &lt;math&gt;p^n + p^{n-1} + ... + 1 \equiv 1&lt;/math&gt; which gave &lt;math&gt;p \equiv 1&lt;/math&gt; &lt;math&gt;q&lt;/math&gt;. Sorry if it's bad I need to do something else so I kind of rushed.<br /> <br /> ==Solution 4 (Along the line of Solution 1)==<br /> &lt;math&gt;n&lt;/math&gt; only needs to satisfy &lt;math&gt;\sigma(a^n)\equiv 1 \pmod{43}&lt;/math&gt; and &lt;math&gt;\sigma(a^n)\equiv 1 \pmod{47}&lt;/math&gt; for all &lt;math&gt;a&lt;/math&gt;. Let's work on the first requirement (mod 43) first. All &lt;math&gt;n&lt;/math&gt; works for &lt;math&gt;a=1&lt;/math&gt;. If &lt;math&gt;a&gt;1&lt;/math&gt;, let &lt;math&gt;a&lt;/math&gt;'s prime factorization be &lt;math&gt;a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}&lt;/math&gt;. The following 3 statements are the same.<br /> &lt;cmath&gt;\text{for all }a, \sigma(a^n)=\prod_{i=1}^k(1+p_i+\cdots+p_i^{ne_i})\equiv1\pmod{43}&lt;/cmath&gt;<br /> &lt;cmath&gt;\text{for all }e&gt;0\text{ and prime }p, 1+p+\cdots+p^{ne}\equiv1\pmod{43}&lt;/cmath&gt;<br /> &lt;cmath&gt;\text{for all prime }p, p+p^2+\cdots+p^n \equiv 0 \pmod{43}&lt;/cmath&gt;<br /> <br /> <br /> (1) For &lt;math&gt;p\equiv0\pmod{43}&lt;/math&gt;, no matter &lt;math&gt;n&lt;/math&gt;, it is true<br /> &lt;cmath&gt;p+p^2+\cdots+p^n \equiv 0 \pmod{43}&lt;/cmath&gt;<br /> <br /> (2) For all &lt;math&gt;p\equiv1\pmod{43}&lt;/math&gt;,<br /> &lt;cmath&gt;p+p^2+\cdots+p^n \equiv n \equiv 0 \pmod{43}&lt;/cmath&gt;<br /> One can either use brute force or Dirichlet's Theorem to show such &lt;math&gt;p&lt;/math&gt; exists. Therefore<br /> &lt;cmath&gt;43|n.&lt;/cmath&gt;<br /> <br /> (3) For all &lt;math&gt;p\not\equiv0,1\pmod{43}&lt;/math&gt;,<br /> &lt;cmath&gt;p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}&lt;/cmath&gt;<br /> According to Fermat's Little Theorem, &lt;math&gt;42|n&lt;/math&gt; is sufficient. To show it's necessary we just need to show 43 has a prime primitive root. This can be done either by brute force or as follows. 43 is prime and it must have a primitive root &lt;math&gt;t\neq 1&lt;/math&gt; that's coprime to 43. All numbers of the form &lt;math&gt;43k+t&lt;/math&gt; are also primitive roots of 43. According to Dirichlet's Theorem there must be primes among them.<br /> <br /> Similar arguments for (mod 47) lead to &lt;math&gt;46|n&lt;/math&gt; and &lt;math&gt;47|n&lt;/math&gt;. Therefore<br /> &lt;cmath&gt;n=\text{lcm}[42,43,46,47]&lt;/cmath&gt;<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=I|num-b=13|num-a=15}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_4&diff=149959 2021 AIME II Problems/Problem 4 2021-03-23T07:59:20Z <p>Jimy: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> There are real numbers &lt;math&gt;a, b, c,&lt;/math&gt; and &lt;math&gt;d&lt;/math&gt; such that &lt;math&gt;-20&lt;/math&gt; is a root of &lt;math&gt;x^3 + ax + b&lt;/math&gt; and &lt;math&gt;-21&lt;/math&gt; is a root of &lt;math&gt;x^3 + cx^2 + d.&lt;/math&gt; These two polynomials share a complex root &lt;math&gt;m + \sqrt{n} \cdot i,&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers and &lt;math&gt;i = \sqrt{-1}.&lt;/math&gt; Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> By the &lt;b&gt;Complex Conjugate Root Theorem&lt;/b&gt;, the imaginary roots for each of &lt;math&gt;x^3+ax+b&lt;/math&gt; and &lt;math&gt;x^3+cx^2+d&lt;/math&gt; are a pair of complex conjugates. Let &lt;math&gt;z=m+\sqrt{n}\cdot i&lt;/math&gt; and &lt;math&gt;\overline{z}=m-\sqrt{n}\cdot i.&lt;/math&gt; It follows that the roots of &lt;math&gt;x^3+ax+b&lt;/math&gt; are &lt;math&gt;-20,z,\overline{z},&lt;/math&gt; and the roots of &lt;math&gt;x^3+cx^2+d&lt;/math&gt; are &lt;math&gt;-21,z,\overline{z}.&lt;/math&gt;<br /> <br /> By Vieta's Formulas on &lt;math&gt;x^3+ax+b,&lt;/math&gt; we have &lt;math&gt;-20+z+\overline{z}=0,&lt;/math&gt; from which<br /> &lt;cmath&gt;\begin{align*}<br /> z+\overline{z}&amp;=20 \ \ \ \ \ \ \ \ \ (1) \\<br /> \left(m+\sqrt{n}\cdot i\right)+\left(m+\sqrt{n}\cdot i\right)&amp;=20 \\<br /> 2m&amp;=20 \\<br /> m&amp;=10. \ \ \ \ \ \ \ \ (2)<br /> \end{align*}&lt;/cmath&gt;<br /> <br /> By Vieta's Formulas on &lt;math&gt;x^3+cx^2+d,&lt;/math&gt; we have &lt;math&gt;-21z-21\overline{z}+z\overline{z}=0,&lt;/math&gt; from which<br /> &lt;cmath&gt;\begin{align*}<br /> -21\left(z+\overline{z}\right)+z\overline{z}&amp;=0 \\<br /> -21\underbrace{\left(20\right)}_{\text{by (1)}}+\underbrace{|z|^2}_{\substack{z\overline{z}=|z|^2 \\ \text{ Identity}}}&amp;=0 \\<br /> |z|^2&amp;=420 \\<br /> m^2+n&amp;=420 \\<br /> {\underbrace{10}_{\text{by (2)}}}^2+n&amp;=420 \\<br /> n&amp;=320. \hspace{24.5mm} (3)<br /> \end{align*}&lt;/cmath&gt;<br /> Finally, we get &lt;math&gt;m+n=\boxed{330}&lt;/math&gt; by &lt;math&gt;(2)&lt;/math&gt; and &lt;math&gt;(3).&lt;/math&gt;<br /> <br /> ~MRENTHUSIASM<br /> <br /> ==Solution 3 (Somewhat Bashy)==<br /> &lt;math&gt;(-20)^{3} + (-20)a + b = 0&lt;/math&gt;, hence &lt;math&gt;-20a + b = 8000&lt;/math&gt;<br /> <br /> Also, &lt;math&gt;(-21)^{3} + c(-21)^{2} + d = 0&lt;/math&gt;, hence &lt;math&gt;441c + d = 9261&lt;/math&gt;<br /> <br /> &lt;math&gt;m + i \sqrt{n}&lt;/math&gt; satisfies both &lt;math&gt;\Rightarrow&lt;/math&gt; we can put it in both equations and equate to 0.<br /> <br /> In the first equation, we get<br /> &lt;math&gt;(m + i \sqrt{n})^{3} + a(m + i \sqrt{n}) + b = 0&lt;/math&gt;<br /> Simplifying this further, we get &lt;math&gt;(m^{3} - 3mn + am + b) + i(3m^{2} \sqrt{n} - n\sqrt{n} + a\sqrt{n}) = 0&lt;/math&gt;<br /> <br /> Hence, &lt;math&gt;m^{3} - 3mn + am + b = 0&lt;/math&gt; and &lt;math&gt;3m^{2} \sqrt{n} - n\sqrt{n} + a\sqrt{n} = 0 \Rightarrow 3m^{2} - n + a = 0 \rightarrow (1)&lt;/math&gt;<br /> <br /> In the second equation, we get<br /> &lt;math&gt;(m + i \sqrt{n})^{3} + c(m + i \sqrt{n})^{2} + d = 0&lt;/math&gt;<br /> Simplifying this further, we get &lt;math&gt;(m^{3} + m^{2}c - nc - 3mn + d) + i(3m^{2} \sqrt{n} - n\sqrt{n} + 2mc\sqrt{n}) = 0&lt;/math&gt;<br /> <br /> Hence, &lt;math&gt;m^{3} + m^{2}c - nc - 3mn + d = 0&lt;/math&gt; and &lt;math&gt;3m^{2} \sqrt{n} - n\sqrt{n} + 2mc\sqrt{n} = 0 \Rightarrow 3m^{2} - n + 2mc = 0 \rightarrow (2)&lt;/math&gt;<br /> <br /> Comparing (1) and (2),<br /> <br /> &lt;math&gt;a = 2mc&lt;/math&gt; and &lt;math&gt;am + b = m^{2}c - nc + d \rightarrow (3)&lt;/math&gt;<br /> <br /> &lt;math&gt;b = 8000 + 20a \Rightarrow b = 40mc + 8000&lt;/math&gt;; <br /> &lt;math&gt;d = 9261 - 441c&lt;/math&gt;<br /> <br /> Substituting these in &lt;math&gt;(3)&lt;/math&gt; gives, &lt;math&gt;2m^{2}c + 8000 + 40mc = m^{2}c - nc + 9261 - 441c&lt;/math&gt;<br /> <br /> This simplifies to &lt;math&gt;m^{2}c + nc + 40mc + 441c = 1261 \Rightarrow c(m^{2} + n + 40m + 441) = 1261&lt;/math&gt;<br /> <br /> Hence, &lt;math&gt;c|1261 \Rightarrow c \in {1,13,97,1261}&lt;/math&gt;<br /> <br /> <br /> Consider case of &lt;math&gt;c = 1&lt;/math&gt;:<br /> <br /> &lt;math&gt;c = 1 \Rightarrow d = 8820&lt;/math&gt;<br /> Also, &lt;math&gt;a = 2m, b = 8000 + 40m&lt;/math&gt;<br /> <br /> &lt;math&gt;am + b = m^{2} - n + 8820&lt;/math&gt; (because c = 1)<br /> Also, &lt;math&gt;m^{2} + n + 40m = 820 \rightarrow (4)&lt;/math&gt;<br /> Also, Equation (2) gives &lt;math&gt;3m^{2} - n + 2m = 0 \rightarrow (5)&lt;/math&gt;<br /> <br /> Solving (4) and (5) simultaneously gives &lt;math&gt;m = 10, n = 320&lt;/math&gt;<br /> <br /> [AIME can not have more than one answer, so we can stop here also 😁... Not suitable for Subjective exam]<br /> <br /> Hence, &lt;math&gt;m + n = 10 + 320 = \boxed{330}&lt;/math&gt;<br /> <br /> -Arnav Nigam<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=II|num-b=3|num-a=5}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_4&diff=149894 2021 AIME II Problems/Problem 4 2021-03-23T03:37:18Z <p>Jimy: /* Solution */</p> <hr /> <div>==Problem==<br /> There are real numbers &lt;math&gt;a, b, c,&lt;/math&gt; and &lt;math&gt;d&lt;/math&gt; such that &lt;math&gt;-20&lt;/math&gt; is a root of &lt;math&gt;x^3 + ax + b&lt;/math&gt; and &lt;math&gt;-21&lt;/math&gt; is a root of &lt;math&gt;x^3 + cx^2 + d.&lt;/math&gt; These two polynomials share a complex root &lt;math&gt;m + \sqrt{n} \cdot i,&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers and &lt;math&gt;i = \sqrt{-1}.&lt;/math&gt; Find &lt;math&gt;m+n.&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Conjugate root theorem<br /> <br /> Solution in progress<br /> <br /> ~JimY<br /> <br /> ==Solution 2==<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=II|num-b=3|num-a=5}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_2&diff=149844 2021 AIME II Problems/Problem 2 2021-03-23T00:15:30Z <p>Jimy: /* Solution */</p> <hr /> <div>==Problem==<br /> Equilateral triangle &lt;math&gt;ABC&lt;/math&gt; has side length &lt;math&gt;840&lt;/math&gt;. Point &lt;math&gt;D&lt;/math&gt; lies on the same side of line &lt;math&gt;BC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;\overline{BD} \perp \overline{BC}&lt;/math&gt;. The line &lt;math&gt;\ell&lt;/math&gt; through &lt;math&gt;D&lt;/math&gt; parallel to line &lt;math&gt;BC&lt;/math&gt; intersects sides &lt;math&gt;\overline{AB}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt; at points &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;F&lt;/math&gt;, respectively. Point &lt;math&gt;G&lt;/math&gt; lies on &lt;math&gt;\ell&lt;/math&gt; such that &lt;math&gt;F&lt;/math&gt; is between &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;G&lt;/math&gt;, &lt;math&gt;\triangle AFG&lt;/math&gt; is isosceles, and the ratio of the area of &lt;math&gt;\triangle AFG&lt;/math&gt; to the area of &lt;math&gt;\triangle BED&lt;/math&gt; is &lt;math&gt;8:9&lt;/math&gt;. Find &lt;math&gt;AF&lt;/math&gt;.<br /> <br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,G;<br /> B=origin;<br /> A=5*dir(60);<br /> C=(5,0);<br /> E=0.6*A+0.4*B;<br /> F=0.6*A+0.4*C;<br /> G=rotate(240,F)*A;<br /> D=extension(E,F,B,dir(90));<br /> draw(D--G--A,grey);<br /> draw(B--0.5*A+rotate(60,B)*A*0.5,grey);<br /> draw(A--B--C--cycle,linewidth(1.5));<br /> dot(A^^B^^C^^D^^E^^F^^G);<br /> label(&quot;$A$&quot;,A,dir(90));<br /> label(&quot;$B$&quot;,B,dir(225));<br /> label(&quot;$C$&quot;,C,dir(-45));<br /> label(&quot;$D$&quot;,D,dir(180));<br /> label(&quot;$E$&quot;,E,dir(-45));<br /> label(&quot;$F$&quot;,F,dir(225));<br /> label(&quot;$G$&quot;,G,dir(0));<br /> label(&quot;$\ell$&quot;,midpoint(E--F),dir(90));<br /> &lt;/asy&gt;<br /> <br /> ==Solution==<br /> SOMEBODY DELETED A SOLUTION - PLEASE WAIT FOR THE ORIGINAL AUTHOR TO COME BACK ~ARCTICTURN<br /> <br /> <br /> <br /> ==Solution==<br /> We express the ares of &lt;math&gt;\triangle BED&lt;/math&gt; and &lt;math&gt;\triangle AFG&lt;/math&gt; in terms of &lt;math&gt;AF&lt;/math&gt; in order to solve for &lt;math&gt;AF. &lt;/math&gt;<br /> <br /> We let &lt;math&gt;x = AF. &lt;/math&gt; Because &lt;math&gt;\triangle AFG&lt;/math&gt; is isoceles and &lt;math&gt;\triangle AEF&lt;/math&gt; is equilateral, &lt;math&gt;AF = FG = EF = AE = x. &lt;/math&gt; <br /> <br /> Let the height of &lt;math&gt;\triangle ABC&lt;/math&gt; be &lt;math&gt;h&lt;/math&gt; and the height of &lt;math&gt;\triangle AEF&lt;/math&gt; be &lt;math&gt;h'. &lt;/math&gt; Then we have that &lt;math&gt;h = \frac{\sqrt{3}}{2}(840) = 420\sqrt{3}&lt;/math&gt; and &lt;math&gt;h' = \frac{\sqrt{3}}{2}(EF) = \frac{\sqrt{3}}{2}x. &lt;/math&gt; <br /> <br /> Now we can find &lt;math&gt;DB&lt;/math&gt; and &lt;math&gt;BE&lt;/math&gt; in terms of &lt;math&gt;x. &lt;/math&gt; &lt;math&gt;DB = h - h' = 420\sqrt{3} - \frac{\sqrt{3}}{2}x, &lt;/math&gt; &lt;math&gt;BE = AB - AE = 840 - x. &lt;/math&gt; Because we are given that &lt;math&gt;\angle DBC = 90, &lt;/math&gt; &lt;math&gt;\angle DBE = 30. &lt;/math&gt; This allows us to use the sin formula for triangle area: the area of &lt;math&gt;\triangle BED&lt;/math&gt; is &lt;math&gt;\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x). &lt;/math&gt; Similarly, because &lt;math&gt;\angle AFG = 120, &lt;/math&gt; the area of &lt;math&gt;\triangle AFG = \frac{1}{2}(\sin 120)(x^2). &lt;/math&gt;<br /> <br /> Now we can make an equation:<br /> <br /> &lt;cmath&gt;\frac{\triangle AFG}{\triangle BED} = \frac{8}{9}&lt;/cmath&gt;<br /> &lt;cmath&gt;\frac{\frac{1}{2}(\sin 120)(x^2)}{\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x)} = \frac{8}{9}&lt;/cmath&gt;<br /> &lt;cmath&gt;\frac{x^2}{(420 - \frac{x}{2})(840-x)} = \frac{8}{9}&lt;/cmath&gt;<br /> <br /> To make further calculations easier, we scale everything down by &lt;math&gt;420&lt;/math&gt; (while keeping the same variable names, so keep that in mind). <br /> <br /> &lt;cmath&gt;\frac{x^2}{(1-\frac{x}{2})(2-x)} = \frac{8}{9}&lt;/cmath&gt;<br /> &lt;cmath&gt;8(1-\frac{x}{2})(2-x) = 9x^2&lt;/cmath&gt;<br /> &lt;cmath&gt;16-16x + 4x^2 = 9x^2&lt;/cmath&gt;<br /> &lt;cmath&gt;5x^2 + 16x -16 = 0&lt;/cmath&gt;<br /> &lt;cmath&gt;(5x-4)(x+4) = 0&lt;/cmath&gt;<br /> <br /> <br /> Thus &lt;math&gt;x = \frac{4}{5}. &lt;/math&gt; Because we scaled down everything by &lt;math&gt;420, &lt;/math&gt; the actual value of &lt;math&gt;AF&lt;/math&gt; is &lt;math&gt;(420)\frac{4}{5} = \boxed{336}. &lt;/math&gt;<br /> <br /> ~JimY<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=II|num-b=1|num-a=3}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_2&diff=149835 2021 AIME II Problems/Problem 2 2021-03-22T23:47:35Z <p>Jimy: /* Solution */</p> <hr /> <div>==Problem==<br /> Equilateral triangle &lt;math&gt;ABC&lt;/math&gt; has side length &lt;math&gt;840&lt;/math&gt;. Point &lt;math&gt;D&lt;/math&gt; lies on the same side of line &lt;math&gt;BC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;\overline{BD} \perp \overline{BC}&lt;/math&gt;. The line &lt;math&gt;\ell&lt;/math&gt; through &lt;math&gt;D&lt;/math&gt; parallel to line &lt;math&gt;BC&lt;/math&gt; intersects sides &lt;math&gt;\overline{AB}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt; at points &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;F&lt;/math&gt;, respectively. Point &lt;math&gt;G&lt;/math&gt; lies on &lt;math&gt;\ell&lt;/math&gt; such that &lt;math&gt;F&lt;/math&gt; is between &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;G&lt;/math&gt;, &lt;math&gt;\triangle AFG&lt;/math&gt; is isosceles, and the ratio of the area of &lt;math&gt;\triangle AFG&lt;/math&gt; to the area of &lt;math&gt;\triangle BED&lt;/math&gt; is &lt;math&gt;8:9&lt;/math&gt;. Find &lt;math&gt;AF&lt;/math&gt;.<br /> <br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,G;<br /> B=origin;<br /> A=5*dir(60);<br /> C=(5,0);<br /> E=0.6*A+0.4*B;<br /> F=0.6*A+0.4*C;<br /> G=rotate(240,F)*A;<br /> D=extension(E,F,B,dir(90));<br /> draw(D--G--A,grey);<br /> draw(B--0.5*A+rotate(60,B)*A*0.5,grey);<br /> draw(A--B--C--cycle,linewidth(1.5));<br /> dot(A^^B^^C^^D^^E^^F^^G);<br /> label(&quot;$A$&quot;,A,dir(90));<br /> label(&quot;$B$&quot;,B,dir(225));<br /> label(&quot;$C$&quot;,C,dir(-45));<br /> label(&quot;$D$&quot;,D,dir(180));<br /> label(&quot;$E$&quot;,E,dir(-45));<br /> label(&quot;$F$&quot;,F,dir(225));<br /> label(&quot;$G$&quot;,G,dir(0));<br /> label(&quot;$\ell$&quot;,midpoint(E--F),dir(90));<br /> &lt;/asy&gt;<br /> <br /> ==Solution==<br /> SOMEBODY DELETED A SOLUTION - PLEASE WAIT FOR THE ORIGINAL AUTHOR TO COME BACK ~ARCTICTURN<br /> <br /> <br /> <br /> ==Solution==<br /> We express the ares of &lt;math&gt;\triangle BED&lt;/math&gt; and &lt;math&gt;\triangle AFG&lt;/math&gt; in terms of &lt;math&gt;AF&lt;/math&gt; in order to solve for &lt;math&gt;AF. &lt;/math&gt;<br /> <br /> We let &lt;math&gt;x = AF. &lt;/math&gt; Because &lt;math&gt;\triangle AFG&lt;/math&gt; is isoceles and &lt;math&gt;\triangle AEF&lt;/math&gt; is equilateral, &lt;math&gt;AF = FG = EF = AE = x. &lt;/math&gt; <br /> <br /> Let the height of &lt;math&gt;\triangle ABC&lt;/math&gt; be &lt;math&gt;h&lt;/math&gt; and the height of &lt;math&gt;\triangle AEF&lt;/math&gt; be &lt;math&gt;h'. &lt;/math&gt; Then we have that &lt;math&gt;h = \frac{\sqrt{3}}{2}(840) = 420\sqrt{3}&lt;/math&gt; and &lt;math&gt;h' = \frac{\sqrt{3}}{2}(EF) = \frac{\sqrt{3}}{2}x. &lt;/math&gt; <br /> <br /> Now we can find &lt;math&gt;DB&lt;/math&gt; and &lt;math&gt;BE&lt;/math&gt; in terms of &lt;math&gt;x. &lt;/math&gt; &lt;math&gt;DB = h - h' = 420\sqrt{3} - \frac{\sqrt{3}}{2}x, &lt;/math&gt; &lt;math&gt;BE = AB - AE = 840 - x. &lt;/math&gt; Because we are given that &lt;math&gt;\angle DBC = 90, &lt;/math&gt; &lt;math&gt;\angle DBE = 30. &lt;/math&gt; This allows us to use the sin formula for triangle area: the area of &lt;math&gt;\triangle BED&lt;/math&gt; is &lt;math&gt;\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x). &lt;/math&gt; Similarly, because &lt;math&gt;\angle AFG = 120, &lt;/math&gt; the area of &lt;math&gt;\triangle AFG = \frac{1}{2}(\sin 120)(x^2). &lt;/math&gt;<br /> <br /> Now we can make an equation:<br /> <br /> \begin{align*}<br /> \frac{\triangle AFG}{\triangle BED} &amp;= \frac{8}{9}\\<br /> \frac{\frac{1}{2}(\sin 120)(x^2)}{\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x)} &amp;= \frac{8}{9}\\<br /> \frac{x^2}{(420 - \frac{x}{2})(840-x)} &amp;= \frac{8}{9}\\<br /> \end{align*}<br /> <br /> To make further calculations easier, we scale everything down by &lt;math&gt;420&lt;/math&gt; (while keeping the same variable names, so keep that in mind). <br /> <br /> LATEX FIXING IN PROGRESS:<br /> <br /> \begin{align*}<br /> \frac{x^2}{(1-\frac{x}{2})(2-x)} &amp;= \frac{8}{9}\\<br /> 8(1-\frac{x}{2})(2-x) &amp;= 9x^2\\<br /> 16-16x + 4x^2 &amp;= 9x^2\\<br /> 5x^2 + 16x -16 &amp;= 0\\<br /> (5x-4)(x+4) &amp;= 0\\<br /> \end{align*}<br /> <br /> <br /> <br /> Thus &lt;math&gt;x = \frac{4}{5}. &lt;/math&gt; Because we scaled down everything by &lt;math&gt;420, &lt;/math&gt; the actual value of &lt;math&gt;AF&lt;/math&gt; is &lt;math&gt;(420)\frac{4}{5} = \boxed{336}. &lt;/math&gt;<br /> <br /> ~JimY<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=II|num-b=1|num-a=3}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_2&diff=149833 2021 AIME II Problems/Problem 2 2021-03-22T23:46:10Z <p>Jimy: /* Problem */</p> <hr /> <div>==Problem==<br /> Equilateral triangle &lt;math&gt;ABC&lt;/math&gt; has side length &lt;math&gt;840&lt;/math&gt;. Point &lt;math&gt;D&lt;/math&gt; lies on the same side of line &lt;math&gt;BC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;\overline{BD} \perp \overline{BC}&lt;/math&gt;. The line &lt;math&gt;\ell&lt;/math&gt; through &lt;math&gt;D&lt;/math&gt; parallel to line &lt;math&gt;BC&lt;/math&gt; intersects sides &lt;math&gt;\overline{AB}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt; at points &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;F&lt;/math&gt;, respectively. Point &lt;math&gt;G&lt;/math&gt; lies on &lt;math&gt;\ell&lt;/math&gt; such that &lt;math&gt;F&lt;/math&gt; is between &lt;math&gt;E&lt;/math&gt; and &lt;math&gt;G&lt;/math&gt;, &lt;math&gt;\triangle AFG&lt;/math&gt; is isosceles, and the ratio of the area of &lt;math&gt;\triangle AFG&lt;/math&gt; to the area of &lt;math&gt;\triangle BED&lt;/math&gt; is &lt;math&gt;8:9&lt;/math&gt;. Find &lt;math&gt;AF&lt;/math&gt;.<br /> <br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,G;<br /> B=origin;<br /> A=5*dir(60);<br /> C=(5,0);<br /> E=0.6*A+0.4*B;<br /> F=0.6*A+0.4*C;<br /> G=rotate(240,F)*A;<br /> D=extension(E,F,B,dir(90));<br /> draw(D--G--A,grey);<br /> draw(B--0.5*A+rotate(60,B)*A*0.5,grey);<br /> draw(A--B--C--cycle,linewidth(1.5));<br /> dot(A^^B^^C^^D^^E^^F^^G);<br /> label(&quot;$A$&quot;,A,dir(90));<br /> label(&quot;$B$&quot;,B,dir(225));<br /> label(&quot;$C$&quot;,C,dir(-45));<br /> label(&quot;$D$&quot;,D,dir(180));<br /> label(&quot;$E$&quot;,E,dir(-45));<br /> label(&quot;$F$&quot;,F,dir(225));<br /> label(&quot;$G$&quot;,G,dir(0));<br /> label(&quot;$\ell$&quot;,midpoint(E--F),dir(90));<br /> &lt;/asy&gt;<br /> <br /> ==Solution==<br /> SOMEBODY DELETED A SOLUTION - PLEASE WAIT FOR THE ORIGINAL AUTHOR TO COME BACK ~ARCTICTURN<br /> <br /> ==See also==<br /> {{AIME box|year=2021|n=II|num-b=1|num-a=3}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=Easter_Egg&diff=146610 Easter Egg 2021-02-14T14:16:15Z <p>Jimy: </p> <hr /> <div>Hi! This is an Easter Egg. That's something usually in games that players find in a weird place that gives them something. Feel free to edit this page<br /> <br /> there is another easter egg in the aops wiki, find it. It has something to do with a blackhole. <br /> <br /> centslordm was here<br /> <br /> MathFan335 was here<br /> <br /> Hello<br /> <br /> robotsEMAN was here<br /> <br /> pomme_de_terre_ was here<br /> <br /> [[User:RedFireTruck|&lt;font color=&quot;#FF0000&quot;&gt;RedFireTruck&lt;/font&gt;]] ([[User talk:RedFireTruck|&lt;font color=&quot;#FF0000&quot;&gt;talk&lt;/font&gt;]]) 19:59, 1 February 2021 (EST) was here<br /> <br /> samuel1234 was here<br /> <br /> JimY was here<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> And another that has to do with a whitehole. <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> And one that has to do with a wormhole.<br /> <br /> Getting trypophobia now, aren't you?</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2021_AMC_12B_Problems/Problem_25&diff=146377 2021 AMC 12B Problems/Problem 25 2021-02-13T08:59:27Z <p>Jimy: /* Solution */</p> <hr /> <div>==Problem==<br /> <br /> Let &lt;math&gt;S&lt;/math&gt; be the set of lattice points in the coordinate plane, both of whose coordinates are integers between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;30,&lt;/math&gt; inclusive. Exactly &lt;math&gt;300&lt;/math&gt; points in &lt;math&gt;S&lt;/math&gt; lie on or below a line with equation &lt;math&gt;y=mx.&lt;/math&gt; The possible values of &lt;math&gt;m&lt;/math&gt; lie in an interval of length &lt;math&gt;\frac ab,&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are relatively prime positive integers. What is &lt;math&gt;a+b?&lt;/math&gt;<br /> <br /> &lt;math&gt;\textbf{(A)} ~31 \qquad \textbf{(B)} ~47 \qquad \textbf{(C)} ~62\qquad \textbf{(D)} ~72 \qquad \textbf{(E)} ~85&lt;/math&gt;<br /> <br /> <br /> ==Solution 1==<br /> First, we find a numerical representation for the number of lattice points in &lt;math&gt;S&lt;/math&gt; that are under the line &lt;math&gt;y=mx. &lt;/math&gt; For any value of &lt;math&gt;x,&lt;/math&gt; the highest lattice point under &lt;math&gt;y=mx&lt;/math&gt; is &lt;math&gt;\lfloor mx \rfloor. &lt;/math&gt; Because every lattice point from &lt;math&gt;(x, 1)&lt;/math&gt; to &lt;math&gt;(x, \lfloor mx \rfloor)&lt;/math&gt; is under the line, the total number of lattice points under the line is &lt;math&gt;\sum_{x=1}^{30}(\lfloor mx \rfloor). &lt;/math&gt;<br /> <br /> Now, we proceed by finding lower and upper bounds for &lt;math&gt;m. &lt;/math&gt; To find the lower bound, we start with an approximation. If &lt;math&gt;300&lt;/math&gt; lattice points are below the line, then around &lt;math&gt;\frac{1}{3}&lt;/math&gt; of the area formed by &lt;math&gt;S&lt;/math&gt; is under the line. By using the formula for a triangle's area, we find that when &lt;math&gt;x=30, y \approx 20. &lt;/math&gt; Solving for &lt;math&gt;m&lt;/math&gt; assuming that &lt;math&gt;(30, 20)&lt;/math&gt; is a point on the line, we get &lt;math&gt;m = \frac{2}{3}. &lt;/math&gt; Plugging in &lt;math&gt;m&lt;/math&gt; to &lt;math&gt;\sum_{x=1}^{30}(\lfloor mx \rfloor), &lt;/math&gt; we get: <br /> <br /> &lt;cmath&gt;\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20&lt;/cmath&gt;<br /> <br /> We have a repeat every &lt;math&gt;3&lt;/math&gt; values (every time &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; goes through a lattice point). Thus, we can use arithmetic sequences to calculate the value above:<br /> <br /> &lt;cmath&gt;\sum_{x=1}^{30}(\lfloor \frac{2}{3}x \rfloor) = 0 + 1 + 2 + 2 + 3 + \cdots + 18 + 18 + 19 + 20&lt;/cmath&gt;&lt;cmath&gt;=\frac{20(21)}{2} + 2 + 4 + 6 + \cdots + 18 &lt;/cmath&gt;&lt;cmath&gt;=210 + \frac{20}{2}\cdot 9&lt;/cmath&gt;&lt;cmath&gt;=300&lt;/cmath&gt;<br /> <br /> This means that &lt;math&gt;\frac{2}{3}&lt;/math&gt; is a possible value of &lt;math&gt;m. &lt;/math&gt; Furthermore, it is the lower bound for &lt;math&gt;m. &lt;/math&gt; This is because &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; goes through many points (such as &lt;math&gt;(21, 14)&lt;/math&gt;). If &lt;math&gt;m&lt;/math&gt; was lower, &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; would no longer go through some of these points, and there would be less than &lt;math&gt;300&lt;/math&gt; lattice points under it. <br /> <br /> Now, we find an upper bound for &lt;math&gt;m. &lt;/math&gt; Imagine increasing &lt;math&gt;m&lt;/math&gt; slowly and rotati<br /> ng the line &lt;math&gt;y=mx, &lt;/math&gt; starting from the lower bound of &lt;math&gt;m=\frac{2}{3}. &lt;/math&gt;The upper bound for &lt;math&gt;m&lt;/math&gt; occurs when &lt;math&gt;y=mx&lt;/math&gt; intersects a lattice point again (look at this problem to get a better idea of what's happening: https://artofproblemsolving.com/wiki/index.php/2011_AMC_10B_Problems/Problem_24). <br /> <br /> <br /> In other words, we are looking for the first &lt;math&gt;m &gt; \frac{2}{3}&lt;/math&gt; that is expressible as a ratio of positive integers &lt;math&gt;\frac{p}{q}&lt;/math&gt; with &lt;math&gt;q \le 30. &lt;/math&gt; For each &lt;math&gt;q=1,\dots,30&lt;/math&gt;, the smallest multiple of &lt;math&gt;\frac{1}{q}&lt;/math&gt; which exceeds &lt;math&gt;\frac{2}{3}&lt;/math&gt; is &lt;math&gt;1, \frac{2}{2}, \frac{3}{3}, \frac{3}{4}, \frac{4}{5}, \cdots , \frac{19}{27}, \frac{19}{28}, \frac{20}{29}, \frac{21}{30}&lt;/math&gt; respectively, and the smallest of these is &lt;math&gt;\frac{19}{28}. &lt;/math&gt; <br /> Note: start listing the multiples of &lt;math&gt;\frac{1}{q}&lt;/math&gt; from &lt;math&gt;\frac{21}{30}&lt;/math&gt; and observe that they get further and further away from &lt;math&gt;\frac{2}{3}. &lt;/math&gt;<br /> Alternatively, see the method of finding upper bounds in solution 2. <br /> <br /> <br /> The lower bound is &lt;math&gt;\frac{2}{3}&lt;/math&gt; and the upper bound is &lt;math&gt;\frac{19}{28}. &lt;/math&gt; Their difference is &lt;math&gt;\frac{1}{84}, &lt;/math&gt; so the answer is &lt;math&gt;1 + 84 = \boxed{85}. &lt;/math&gt;<br /> <br /> ~JimY<br /> <br /> ==Solution 2==<br /> I know that I want about &lt;math&gt;\frac{2}{3}&lt;/math&gt; of the box of integer coordinates above my line. There are a total of 30 integer coordinates in the desired range for each axis which gives a total of 900 lattice points. I estimate that the slope, m, is &lt;math&gt;\frac{2}{3}&lt;/math&gt;. Now, although there is probably an easier solution, I would try to count the number of points above the line to see if there are 600 points above the line. The line &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; separates the area inside the box so that &lt;math&gt;\frac{2}{3}&lt;/math&gt; of the are is above the line. <br /> <br /> I find that the number of coordinates with &lt;math&gt;x=1&lt;/math&gt; above the line is 30, and the number of coordinates with &lt;math&gt;x=2&lt;/math&gt; above the line is 29. Every time the line &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; hits a y-value with an integer coordinate, the number of points above the line decreases by one. I wrote out the sum of 30 terms in hopes of finding a pattern. I graphed the first couple positive integer x-coordinates, and found that the sum of the integers above the line is &lt;math&gt;30+29+28+28+27+26+26 \ldots+ 10&lt;/math&gt;. The even integer repeats itself every third term in the sum. I found that the average of each of the terms is 20, and there are 30 of them which means that exactly 600 above the line as desired. This give a lower bound because if the slope decreases a little bit, then the points that the line goes through will be above the line. <br /> <br /> To find the upper bound, notice that each point with an integer-valued x-coordinate is either &lt;math&gt;\frac{1}{3}&lt;/math&gt; or &lt;math&gt;\frac{2}{3}&lt;/math&gt; above the line. Since the slope through a point is the y-coordinate divided by the x-coordinate, a shift in the slope will increase the y-value of the higher x-coordinates. We turn our attention to &lt;math&gt;x=28, 29, 30&lt;/math&gt; which the line &lt;math&gt;y=\frac{2}{3}x&lt;/math&gt; intersects at &lt;math&gt;y= \frac{56}{3}, \frac{58}{3}, 20&lt;/math&gt;. The point (30,20) is already counted below the line, and we can clearly see that if we slowly increase the slope of the line, we will hit the point (28,19) since (28, &lt;math&gt;\frac{56}{3}&lt;/math&gt;) is closer to the lattice point. The slope of the line which goes through both the origin and (28,19) is &lt;math&gt;y=\frac{19}{28}x&lt;/math&gt;. This gives an upper bound of &lt;math&gt;m=\frac{19}{28}&lt;/math&gt;. <br /> <br /> Taking the upper bound of m and subtracting the lower bound yields &lt;math&gt;\frac{19}{28}-\frac{2}{3}=\frac{1}{84}&lt;/math&gt;. This is answer &lt;math&gt;1+84=&lt;/math&gt; &lt;math&gt;\boxed{\textbf{(E)} ~85}&lt;/math&gt;.<br /> <br /> <br /> ===Diagram===<br /> &lt;asy&gt;<br /> /* Created by Brendanb4321 */<br /> import graph;<br /> size(16cm);<br /> defaultpen(fontsize(9pt));<br /> xaxis(0,30,Ticks(1.0));<br /> yaxis(0,25,Ticks(1.0));<br /> <br /> draw((0,0)--(30,20));<br /> draw((0,0)--(30,30/28*19), dotted);<br /> int c = 0;<br /> for (int i = 1; i&lt;=30; ++i)<br /> {<br /> for (int j = 1; j&lt;=2/3*i+1; ++j)<br /> {<br /> dot((i,j));<br /> }<br /> }<br /> dot((28,19), red);<br /> label(&quot;$m=2/3$&quot;, (32,20));<br /> label(&quot;$m=19/28$&quot;, (32.3,20.8));<br /> &lt;/asy&gt;<br /> <br /> ==See also==<br /> {{AMC12 box|year=2021|ab=B|num-b=24|after=Last problem}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{AMC10 box|year=2021|ab=B|num-b=24|after=Last problem}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2007_AMC_12A_Problems/Problem_9&diff=138732 2007 AMC 12A Problems/Problem 9 2020-11-29T14:46:06Z <p>Jimy: /* Simple Solution */</p> <hr /> <div>{{duplicate|[[2007 AMC 12A Problems|2007 AMC 12A #9]] and [[2007 AMC 10A Problems/Problem 13|2007 AMC 10A #13]]}}<br /> ==Problem==<br /> Yan is somewhere between his home and the stadium. To get to the stadium he can walk directly to the stadium, or else he can walk home and then ride his bicycle to the stadium. He rides 7 times as fast as he walks, and both choices require the same amount of time. What is the [[ratio]] of Yan's distance from his home to his distance from the stadium?<br /> <br /> &lt;math&gt;\mathrm{(A)}\ \frac 23\qquad \mathrm{(B)}\ \frac 34\qquad \mathrm{(C)}\ \frac 45\qquad \mathrm{(D)}\ \frac 56\qquad \mathrm{(E)}\ \frac 78&lt;/math&gt;<br /> <br /> ==Simple Solution==<br /> Let &lt;math&gt;x&lt;/math&gt; represent the distance from home to the stadium, and let &lt;math&gt;r&lt;/math&gt; represent the distance from Yan to home. Our goal is to find &lt;math&gt;\frac{r}{x-r}&lt;/math&gt;. If Yan walks directly to the stadium, then assuming he walks at a rate of &lt;math&gt;1&lt;/math&gt;, it will take him &lt;math&gt;x-r&lt;/math&gt; units of time. Similarly, if he walks back home it will take him &lt;math&gt;r + \frac{x}{7}&lt;/math&gt; units of time. Because the two times are equal, we can create the following equation: &lt;math&gt;x-r = r + \frac{x}{7}&lt;/math&gt;. We get &lt;math&gt;x-2r=\frac{x}{7}&lt;/math&gt;, so &lt;math&gt;\frac{6}{7}x = 2r&lt;/math&gt;, and &lt;math&gt;\frac{x}{r} = \frac{7}{3}&lt;/math&gt;. This minus one is the reciprocal of what we want to find: &lt;math&gt;\frac{7}{3}-1 = \frac{4}{3}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{\frac{3}{4}}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Let the distance from Yan's initial position to the stadium be &lt;math&gt;a&lt;/math&gt; and the distance from Yan's initial position to home be &lt;math&gt;b&lt;/math&gt;. We are trying to find &lt;math&gt;b/a&lt;/math&gt;, and we have the following identity given by the problem:<br /> <br /> &lt;cmath&gt;\begin{align*}a &amp;= b + \frac{a+b}{7}\\<br /> \frac{6a}{7} &amp;= \frac{8b}{7} \Longrightarrow 6a = 8b\end{align*}&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;b/a = 6/8 = 3/4&lt;/math&gt; and the answer is &lt;math&gt;\mathrm{(B)}\ \frac{3}{4}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> Another way of solving this problem is by setting the distance between Yan's home and the stadium, thus filling in one variable.<br /> Let us set the distance between the two places to be &lt;math&gt;42z&lt;/math&gt;, where &lt;math&gt;z&lt;/math&gt; is a random measurement (cause life, why not?) The distance to going to his home then riding his bike, which is &lt;math&gt;7&lt;/math&gt; times faster, is equal to him just walking to the stadium. So the equation would be:<br /> Let &lt;math&gt;x=&lt;/math&gt; the distance from Yan's position to his home. <br /> Let &lt;math&gt;42z=&lt;/math&gt; the distance from Yan's home to the stadium.<br /> <br /> &lt;math&gt;42-x=x+42/7&lt;/math&gt;<br /> <br /> &lt;math&gt;42-x=x+6&lt;/math&gt;<br /> <br /> &lt;math&gt;36=2x&lt;/math&gt;<br /> <br /> &lt;math&gt;x=18&lt;/math&gt;<br /> <br /> But we're still not done with the question. We know that Yan is &lt;math&gt;18z&lt;/math&gt; from his home, and is &lt;math&gt;42z-18z&lt;/math&gt; or &lt;math&gt;24z&lt;/math&gt; from the stadium.<br /> &lt;math&gt;18z/24z&lt;/math&gt;, the &lt;math&gt;z&lt;/math&gt;'s cancel out, and we are left with &lt;math&gt;3/4&lt;/math&gt;.<br /> Thus, the answer is &lt;math&gt;\mathrm{(B)}\ \frac{3}{4}&lt;/math&gt;<br /> <br /> ~ProGameXD<br /> <br /> == Solution 3 ==<br /> <br /> Assume that the distance from the home and stadium is 1, and the distance from Yan to home is &lt;math&gt;b&lt;/math&gt;. Also assume that the speed of walking is 1, so the speed of biking is 7. Thus<br /> &lt;math&gt;1-b=b+1/7&lt;/math&gt;<br /> &lt;math&gt;b=3/7&lt;/math&gt;<br /> We need &lt;math&gt;b/1-b&lt;/math&gt;<br /> <br /> &lt;math&gt;3/7&lt;/math&gt; divided by &lt;math&gt;4/7&lt;/math&gt;=&lt;math&gt;\mathrm{(B)}\ \frac{3}{4}&lt;/math&gt;<br /> <br /> ==Solution 4==<br /> &lt;asy&gt;<br /> draw((0,0)--(7,0));<br /> dot((0,0)); dot((3,0)); dot((6,0)); dot((7,0));<br /> label(&quot;$H$&quot;,(0,0),S);<br /> label(&quot;$Y$&quot;,(3,0),S);<br /> label(&quot;$P$&quot;,(6,0),S);<br /> label(&quot;$S$&quot;,(7,0),S);<br /> &lt;/asy&gt;<br /> Let &lt;math&gt;H&lt;/math&gt; represent Yan's home, &lt;math&gt;S&lt;/math&gt; represent the stadium, and &lt;math&gt;Y&lt;/math&gt; represent Yan's current position. If Yan walks directly to the stadium, he will reach Point &lt;math&gt;P&lt;/math&gt; the same time he will reach &lt;math&gt;H&lt;/math&gt; if he is walking home. <br /> Since he bikes &lt;math&gt;7&lt;/math&gt; times as fast as he walks and the time is the same, the distance from his home to the stadium must be &lt;math&gt;7&lt;/math&gt; times the distance from &lt;math&gt;P&lt;/math&gt; to the stadium. If &lt;math&gt;PS=x&lt;/math&gt;, then &lt;math&gt;HS=7x&lt;/math&gt; and &lt;math&gt;HP=6x&lt;/math&gt;. Since Y is the midpoint of &lt;math&gt;\overline{HP}&lt;/math&gt;, &lt;math&gt;HY=YP=3x&lt;/math&gt;. Therefore, the ratio of Yan's distance from his home to his distance from the stadium is &lt;math&gt;\frac{YH}{YS}=\frac{3x}{4x}=\boxed{\mathrm{(B)}\ \frac{3}{4}}&lt;/math&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/b0pxcJH-984<br /> <br /> ~savannahsolver<br /> <br /> ==See also==<br /> {{AMC12 box|year=2007|ab=A|num-b=8|num-a=10}}<br /> {{AMC10 box|year=2007|ab=A|num-b=12|num-a=14}}<br /> <br /> [[Category:Introductory Algebra Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10A_Problems/Problem_14&diff=135231 2018 AMC 10A Problems/Problem 14 2020-10-18T12:04:20Z <p>Jimy: /* Solution 9 */</p> <hr /> <div>==Problem==<br /> <br /> What is the greatest integer less than or equal to &lt;cmath&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}?&lt;/cmath&gt;<br /> <br /> &lt;math&gt;<br /> \textbf{(A) }80\qquad<br /> \textbf{(B) }81 \qquad<br /> \textbf{(C) }96 \qquad<br /> \textbf{(D) }97 \qquad<br /> \textbf{(E) }625\qquad<br /> &lt;/math&gt;<br /> <br /> ==Solution 1==<br /> We write<br /> &lt;cmath&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}=\frac{3^{96}}{3^{96}+2^{96}}\cdot\frac{3^{100}}{3^{96}}+\frac{2^{96}}{3^{96}+2^{96}}\cdot\frac{2^{100}}{2^{96}}=\frac{3^{96}}{3^{96}+2^{96}}\cdot 81+\frac{2^{96}}{3^{96}+2^{96}}\cdot 16.&lt;/cmath&gt;<br /> Hence we see that our number is a weighted average of 81 and 16, extremely heavily weighted toward 81. Hence the number is ever so slightly less than 81, so the answer is &lt;math&gt;\boxed{\textbf{(A) }80}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> Let's set this value equal to &lt;math&gt;x&lt;/math&gt;. We can write<br /> &lt;cmath&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}=x.&lt;/cmath&gt;<br /> Multiplying by &lt;math&gt;3^{96}+2^{96}&lt;/math&gt; on both sides, we get <br /> &lt;cmath&gt;3^{100}+2^{100}=x(3^{96}+2^{96}).&lt;/cmath&gt;<br /> Now let's take a look at the answer choices. We notice that &lt;math&gt;81&lt;/math&gt;, choice &lt;math&gt;B&lt;/math&gt;, can be written as &lt;math&gt;3^4&lt;/math&gt;. Plugging this into our equation above, we get<br /> &lt;cmath&gt;3^{100}+2^{100} \stackrel{?}{=} 3^4(3^{96}+2^{96}) \Rightarrow 3^{100}+2^{100} \stackrel{?}{=} 3^{100}+3^4\cdot 2^{96}.&lt;/cmath&gt;<br /> The right side is larger than the left side because <br /> &lt;cmath&gt;2^{100} \leq 2^{96}\cdot 3^4.&lt;/cmath&gt;<br /> This means that our original value, &lt;math&gt;x&lt;/math&gt;, must be less than &lt;math&gt;81&lt;/math&gt;. The only answer that is less than &lt;math&gt;81&lt;/math&gt; is &lt;math&gt;80&lt;/math&gt; so our answer is &lt;math&gt;\boxed{A}&lt;/math&gt;.<br /> <br /> ~Nivek, ~VERY minor spelling correction by ericshi1685<br /> <br /> ==Solution 3==<br /> &lt;math&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}=\frac{2^{96}(\frac{3^{100}}{2^{96}})+2^{96}(2^{4})}{2^{96}(\frac{3}{2})^{96}+2^{96}(1)}=\frac{\frac{3^{100}}{2^{96}}+2^{4}}{(\frac{3}{2})^{96}+1}=\frac{\frac{3^{100}}{2^{100}}*2^{4}+2^{4}}{(\frac{3}{2})^{96}+1}=\frac{2^{4}(\frac{3^{100}}{2^{100}}+1)}{(\frac{3}{2})^{96}+1}&lt;/math&gt;.<br /> <br /> We can ignore the 1's on the end because they won't really affect the fraction. So, the answer is very very very close but less than the new fraction.<br /> <br /> &lt;math&gt;\frac{2^{4}(\frac{3^{100}}{2^{100}}+1)}{(\frac{3}{2})^{96}+1}&lt;\frac{2^{4}(\frac{3^{100}}{2^{100}})}{(\frac{3}{2})^{96}}&lt;/math&gt;<br /> <br /> &lt;math&gt;\frac{2^{4}(\frac{3^{100}}{2^{100}})}{(\frac{3}{2})^{96}}=\frac{3^{4}}{2^{4}}*2^{4}=3^{4}=81&lt;/math&gt;<br /> <br /> So, our final answer is very close but not quite 81, and therefore the greatest integer less than the number is &lt;math&gt;\boxed{(A) 80}&lt;/math&gt;<br /> <br /> ==Solution 4==<br /> <br /> Let &lt;math&gt;x=3^{96}&lt;/math&gt; and &lt;math&gt;y=2^{96}&lt;/math&gt;. Then our fraction can be written as<br /> &lt;math&gt;\frac{81x+16y}{x+y}=\frac{16x+16y}{x+y}+\frac{65x}{x+y}=16+\frac{65x}{x+y}&lt;/math&gt;.<br /> Notice that <br /> &lt;math&gt;\frac{65x}{x+y}&lt;\frac{65x}{x}=65&lt;/math&gt;.<br /> So ,<br /> &lt;math&gt;16+\frac{65x}{x+y}&lt;16+65=81&lt;/math&gt;.<br /> And our only answer choice less than 81 is &lt;math&gt;\boxed{(A) 80}&lt;/math&gt; (RegularHexagon)<br /> <br /> ==Solution 5==<br /> Let &lt;math&gt;x=\frac{3^{100}+2^{100}}{3^{96}+2^{96}}&lt;/math&gt;. Multiply both sides by &lt;math&gt;(3^{96}+2^{96})&lt;/math&gt;, and expand. Rearranging the terms, we get &lt;math&gt;3^{96}(3^4-x)+2^{96}(2^4-x)=0&lt;/math&gt;. The left side is decreasing, and it is negative when &lt;math&gt;x=81&lt;/math&gt;. This means that the answer must be less than &lt;math&gt;81&lt;/math&gt;; therefore the answer is &lt;math&gt;\boxed{(A)}&lt;/math&gt;.<br /> <br /> ==Solution 6 (eyeball it)==<br /> A faster solution. Recognize that for exponents of this size &lt;math&gt;3^{n}&lt;/math&gt; will be enormously greater than &lt;math&gt;2^{n}&lt;/math&gt;, so the terms involving &lt;math&gt;2&lt;/math&gt; will actually have very little effect on the quotient. Now we know the answer will be very close to &lt;math&gt;81&lt;/math&gt;.<br /> <br /> Notice that the terms being added on to the top and bottom are in the ratio &lt;math&gt;\frac{1}{16}&lt;/math&gt; with each other, so they must pull the ratio down from 81 very slightly. (In the same way that a new test score lower than your current cumulative grade always must pull that grade downward.) Answer: &lt;math&gt;\boxed{(A)}&lt;/math&gt;.<br /> <br /> ==Solution 7 (Using the answer choices)==<br /> We can compare the given value to each of our answer choices. We already know that it is greater than &lt;math&gt;80&lt;/math&gt; because otherwise there would have been a smaller answer, so we move onto &lt;math&gt;81&lt;/math&gt;. We get:<br /> <br /> &lt;math&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}} \text{ ? } 3^4&lt;/math&gt;<br /> <br /> Cross multiply to get:<br /> <br /> &lt;math&gt;3^{100}+2^{100} \text{ ? }3^{100}+(2^{96})(3^4)&lt;/math&gt;<br /> <br /> Cancel out &lt;math&gt;3^{100}&lt;/math&gt; and divide by &lt;math&gt;2^{96}&lt;/math&gt; to get &lt;math&gt;2^{4} \text{ ? }3^4&lt;/math&gt;. We know that &lt;math&gt;2^4 &lt; 3^4&lt;/math&gt;, which means the expression is less than &lt;math&gt;81&lt;/math&gt; so the answer is &lt;math&gt;\boxed{(A)}&lt;/math&gt;.<br /> <br /> ==Solution 8 (The Slick Solution)==<br /> Notice how &lt;math&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}&lt;/math&gt; can be rewritten as &lt;math&gt;\frac{81(3^{96})+16(2^{96})}{3^{96}+2^{96}}=\frac{81(3^{96})+81(2^{96})}{3^{96}+2^{96}}-\frac{65(2^{96})}{3^{96}+2^{96}}=81-\frac{65(2^{96})}{3^{96}+2^{96}}&lt;/math&gt;. Note that &lt;math&gt;\frac{65(2^{96})}{3^{96}+2^{96}}&lt;1&lt;/math&gt;, so the greatest integer less than or equal to &lt;math&gt;\frac{3^{100}+2^{100}}{3^{96}+2^{96}}&lt;/math&gt; is &lt;math&gt;80&lt;/math&gt; or &lt;math&gt;\boxed{\textbf{(A)}}&lt;/math&gt;<br /> ~blitzkrieg21<br /> <br /> ==Solution 9==<br /> For positive &lt;math&gt;a, b, c, d&lt;/math&gt;, if &lt;math&gt;\frac{a}{b}&lt;\frac{c}{d}&lt;/math&gt; then &lt;math&gt;\frac{c+a}{d+b}&lt;\frac{c}{d}&lt;/math&gt;. Let &lt;math&gt;a=2^{100}, b=2^{96}, c=3^{100}, d=3^{96}&lt;/math&gt;. Then &lt;math&gt;\frac{c}{d}=3^4&lt;/math&gt;. So answer is less than 81, which leaves only one choice, 80.<br /> * Note that the algebra here is synonymous to the explanation given in Solution 6. This is the algebraic reason to the logic of if you get a test score with a lower percentage than your average (no matter how many points/percentage of your total grade it was worth), it will pull your overall grade down.<br /> <br /> ~ ccx09<br /> <br /> ==Solution 10==<br /> Try long division, and notice putting &lt;math&gt;3^4=81&lt;/math&gt; as the denominator is too big and putting &lt;math&gt;3^4-1=80&lt;/math&gt; is too small. So we know that the answer is between &lt;math&gt;80&lt;/math&gt; and &lt;math&gt;81&lt;/math&gt;, yielding &lt;math&gt;80&lt;/math&gt; as our answer.<br /> <br /> ==Solution 11(Using the Answer Choices)==<br /> We know this will be between 16 and 81 because &lt;math&gt;\frac{3^{100}}{3^{96}} = 3^4 = 81&lt;/math&gt; and &lt;math&gt;\frac{2^{100}}{2^{96}} = 2^4 = 16&lt;/math&gt;. &lt;math&gt;80=\boxed{(A)}&lt;/math&gt; is the only option choice in this range.<br /> ~Latex edits by Argonauts16<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2018|ab=A|num-b=13|num-a=15}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_10B_Problems/Problem_23&diff=135067 2011 AMC 10B Problems/Problem 23 2020-10-15T06:42:33Z <p>Jimy: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> <br /> What is the hundreds digit of &lt;math&gt;2011^{2011}?&lt;/math&gt;<br /> <br /> &lt;math&gt;\textbf{(A) } 1 \qquad \textbf{(B) } 4 \qquad \textbf{(C) }5 \qquad \textbf{(D) } 6 \qquad \textbf{(E) } 9&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Since &lt;math&gt;2011 \equiv 11 \pmod{1000},&lt;/math&gt; we know that &lt;math&gt;2011^{2011} \equiv 11^{2011} \pmod{1000}.&lt;/math&gt;<br /> <br /> To compute this, we use a clever application of the [[binomial theorem]].<br /> <br /> &lt;math&gt;\begin{aligned} 11^{2011} &amp;= (1+10)^{2011} \\ &amp;= 1 + \dbinom{2011}{1} \cdot 10 + \dbinom{2011}{2} \cdot 10^2 + \cdots \end{aligned}&lt;/math&gt;<br /> <br /> In all of the other terms, the power of &lt;math&gt;10&lt;/math&gt; is greater than &lt;math&gt;3&lt;/math&gt; and so is equivalent to &lt;math&gt;0&lt;/math&gt; modulo &lt;math&gt;1000,&lt;/math&gt; which means we can ignore it. We have:<br /> <br /> &lt;math&gt;\begin{aligned}11^{2011} &amp;\equiv 1 + 2011\cdot 10 + \dfrac{2011 \cdot 2010}{2} \cdot 100 \\ &amp;\equiv 1+20110 + \dfrac{11\cdot 10}{2} \cdot 100\\ &amp;= 1 + 20110 + 5500\\ &amp;\equiv 1 + 110 + 500\\&amp;=611 \pmod{1000} \end{aligned}&lt;/math&gt;<br /> <br /> Therefore, the hundreds digit is &lt;math&gt;\boxed{\textbf{(D) } 6}.&lt;/math&gt;<br /> <br /> Sidenote: By [[Euler's Totient Theorem]], &lt;math&gt;a^{\phi (1000)} \equiv 1 \pmod{1000}&lt;/math&gt; for any &lt;math&gt;a&lt;/math&gt;, so &lt;math&gt;a^{400} \equiv 1 \pmod{1000}&lt;/math&gt; and &lt;math&gt;11^{2011} \equiv 11^{11} \pmod{1000}&lt;/math&gt;. We can then proceed using the clever application of the Binomial Theorem.<br /> <br /> == Solution 2 ==<br /> <br /> We need to compute &lt;math&gt;2011^{2011} \pmod{1000}.&lt;/math&gt; By the [[Chinese Remainder Theorem]], it suffices to compute &lt;math&gt;2011^{2011} \pmod{8}&lt;/math&gt; and &lt;math&gt;2011^{2011} \pmod{125}.&lt;/math&gt;<br /> <br /> In modulo &lt;math&gt;8,&lt;/math&gt; we have &lt;math&gt;2011^4 \equiv 1 \pmod{8}&lt;/math&gt; by Euler's Theorem, and also &lt;math&gt;2011 \equiv 3 \pmod{8},&lt;/math&gt; so we have &lt;cmath&gt;2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.&lt;/cmath&gt;<br /> <br /> In modulo &lt;math&gt;125,&lt;/math&gt; we have &lt;math&gt;2011^{100} \equiv 1 \pmod{125}&lt;/math&gt; by Euler's Theorem, and also &lt;math&gt;2011 \equiv 11 \pmod{125}.&lt;/math&gt; Therefore, we have &lt;math&gt;\begin{aligned} 2011^{2011} &amp;= (2011^{100})^{20} \cdot 2011^{11} \\ &amp;\equiv 1^{20} \cdot 11^{11} \\ &amp;= 121^5 \cdot 11 \\ &amp;= (-4)^5 \cdot 11 = -1024 \cdot 11 \\ &amp;\equiv -24 \cdot 11 = -264 \\ &amp;\equiv 111 \pmod{125}. \end{aligned} &lt;/math&gt;<br /> <br /> After finding the solution &lt;math&gt;2011^{2011} \equiv 611 \pmod{1000},&lt;/math&gt; we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is &lt;math&gt;\boxed{\textbf{(D) } 6}.&lt;/math&gt;<br /> <br /> == Solution 3 ==<br /> <br /> Notice that the hundreds digit of &lt;math&gt;2011^{2011}&lt;/math&gt; won't be affected by &lt;math&gt;2000&lt;/math&gt;. Essentially we could solve the problem by finding the hundreds digit of &lt;math&gt;11^{2011}&lt;/math&gt;. Powers of &lt;math&gt;11&lt;/math&gt; are special because they can be represented by the Pascal's Triangle. Drawing the triangle, there is a theorem that states the powers of &lt;math&gt;11&lt;/math&gt; can be found by reading rows of the triangle and adding extra numbers up. [add source] For example, the sixth row of the triangle is &lt;math&gt;1, 5, 10, 10, 5,&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Adding all numbers from right to left, we get &lt;math&gt;161051&lt;/math&gt;, which is also &lt;math&gt;11^5&lt;/math&gt;. In other words, each number is &lt;math&gt;10^n&lt;/math&gt; steps from the right side of the row. The hundreds digit is &lt;math&gt;0&lt;/math&gt;. We can do the same for &lt;math&gt;11^{2011}&lt;/math&gt;, but we only need to find the &lt;math&gt;3&lt;/math&gt; digits from the right. Observing, every &lt;math&gt;3&lt;/math&gt; number from the right is &lt;math&gt;1 + 2 + 3... + n&lt;/math&gt;. So to find the third number from the right on the row of &lt;math&gt;11^{2011}&lt;/math&gt;, &lt;cmath&gt;f(11^n) = 1 + 2 + 3... + (n-1),&lt;/cmath&gt; or &lt;math&gt;\frac{(2010 \cdot 2011)}{2}&lt;/math&gt;, or &lt;math&gt;2021055&lt;/math&gt;. The last digit is five, but we must remember to add the number on the right of it, which, by observing other rows is obviously &lt;math&gt;2011&lt;/math&gt;. We must carry the &lt;math&gt;1&lt;/math&gt; in &lt;math&gt;2011&lt;/math&gt;'s tens digit to the &lt;math&gt;5&lt;/math&gt; in &lt;math&gt;2021055&lt;/math&gt;'s unit digit to get &lt;math&gt;\boxed{\textbf{(D) } 6}&lt;/math&gt;. The one at the very end of the row doesn't affect anything, so we can leave it alone.<br /> <br /> <br /> -jackshi2006<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2011|ab=B|num-a=24|num-b=22}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=135066 Fermat's Little Theorem 2020-10-15T06:02:26Z <p>Jimy: /* Proof 3 (Combinatorics) */</p> <hr /> <div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br /> <br /> <br /> == Statement ==<br /> <br /> If &lt;math&gt;{a}&lt;/math&gt; is an [[integer]], &lt;math&gt;{p}&lt;/math&gt; is a [[prime number]] and &lt;math&gt;{a}&lt;/math&gt; is not [[divisibility|divisible]] by &lt;math&gt;{p}&lt;/math&gt;, then &lt;math&gt;a^{p-1}\equiv 1 \pmod {p}&lt;/math&gt;.<br /> <br /> A frequently used corollary of Fermat's Little Theorem is &lt;math&gt; a^p \equiv a \pmod {p}&lt;/math&gt;. As you can see, it is derived by multipling both sides of the theorem by &lt;math&gt;a&lt;/math&gt;. The restated form is nice because we no longer need to restrict ourselves to integers &lt;math&gt;{a}&lt;/math&gt; not divisible by &lt;math&gt;{p}&lt;/math&gt;.<br /> <br /> This theorem is a special case of [[Euler's Totient Theorem]], which states that if &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are integers, then &lt;math&gt;a^{\varphi(n)} \equiv 1 \pmod{n}&lt;/math&gt;, where &lt;math&gt;\varphi(n)&lt;/math&gt; denotes [[Euler's totient function]]. In particular, &lt;math&gt;\varphi(p) = p-1&lt;/math&gt; for prime numbers &lt;math&gt;p&lt;/math&gt;. In turn, this is a special case of [[Lagrange's Theorem]].<br /> <br /> In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br /> <br /> == Proof ==<br /> We offer several proofs using different techniques to prove the statement &lt;math&gt;a^p \equiv a \pmod{p}&lt;/math&gt;. If &lt;math&gt;\text{gcd}\,(a,p) = 1&lt;/math&gt;, then we can cancel a factor of &lt;math&gt;a&lt;/math&gt; from both sides and retrieve the first version of the theorem. <br /> <br /> === Proof 1 (Induction) ===<br /> <br /> The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix &lt;math&gt;p&lt;/math&gt; as a prime number. The base case, &lt;math&gt;1^p \equiv 1 \pmod{p}&lt;/math&gt;, is obviously true. Suppose the statement &lt;math&gt;a^p \equiv a \pmod{p}&lt;/math&gt; is true. Then, by the [[binomial theorem]], <br /> <br /> &lt;center&gt;&lt;cmath&gt;(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.&lt;/cmath&gt;&lt;/center&gt;<br /> <br /> Note that &lt;math&gt;p&lt;/math&gt; divides into any binomial coefficient of the form &lt;math&gt;{p \choose k}&lt;/math&gt; for &lt;math&gt;1 \le k \le p-1&lt;/math&gt;. This follows by the definition of the binomial coefficient as &lt;math&gt;{p \choose k} = \frac{p!}{k! (p-k)!}&lt;/math&gt;; since &lt;math&gt;p&lt;/math&gt; is prime, then &lt;math&gt;p&lt;/math&gt; divides the numerator, but not the denominator. <br /> <br /> Taken &lt;math&gt;\mod p&lt;/math&gt;, all of the middle terms disappear, and we end up with &lt;math&gt;(a+1)^p \equiv a^p + 1 \pmod{p}&lt;/math&gt;. Since we also know that &lt;math&gt;a^p \equiv a\pmod{p}&lt;/math&gt;, then &lt;math&gt;(a+1)^p \equiv a+1 \pmod{p}&lt;/math&gt;, as desired. <br /> <br /> === Proof 2 (Inverses) ===<br /> <br /> Let &lt;math&gt;S = \{1,2,3,\cdots, p-1\}&lt;/math&gt;. Then, we claim that the set &lt;math&gt;a \cdot S&lt;/math&gt;, consisting of the product of the elements of &lt;math&gt;S&lt;/math&gt; with &lt;math&gt;a&lt;/math&gt;, taken modulo &lt;math&gt;p&lt;/math&gt;, is simply a permutation of &lt;math&gt;S&lt;/math&gt;. In other words, <br /> <br /> &lt;center&gt;&lt;cmath&gt;S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.&lt;/cmath&gt;&lt;/center&gt;&lt;br&gt;<br /> <br /> Clearly none of the &lt;math&gt;ia&lt;/math&gt; for &lt;math&gt;1 \le i \le p-1&lt;/math&gt; are divisible by &lt;math&gt;p&lt;/math&gt;, so it suffices to show that all of the elements in &lt;math&gt;a \cdot S&lt;/math&gt; are distinct. Suppose that &lt;math&gt;ai \equiv aj \pmod{p}&lt;/math&gt;. Since &lt;math&gt;\text{gcd}\, (a,p) = 1&lt;/math&gt;, by the cancellation rule, that reduces to &lt;math&gt;i \equiv j \pmod{p},&lt;/math&gt; which means &lt;math&gt;i = j&lt;/math&gt; as &lt;math&gt;1 \leq i, j \leq p-1.&lt;/math&gt; <br /> <br /> Thus, &lt;math&gt;\mod{p}&lt;/math&gt;, we have that the product of the elements of &lt;math&gt;S&lt;/math&gt; is <br /> <br /> &lt;center&gt;&lt;cmath&gt;1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.&lt;/cmath&gt;&lt;/center&gt; &lt;br&gt;<br /> <br /> Cancelling the factors &lt;math&gt;1, 2, 3, \ldots, p-1&lt;/math&gt; from both sides, we are left with the statement &lt;math&gt;a^{p-1} \equiv 1 \pmod{p}&lt;/math&gt;.&lt;br&gt;<br /> <br /> A similar version can be used to prove [[Euler's Totient Theorem]], if we let &lt;math&gt;S = \{\text{natural numbers relatively prime to and less than}\ n\}&lt;/math&gt;.<br /> <br /> === Proof 3 (Combinatorics) ===<br /> &lt;center&gt;&lt;asy&gt; <br /> real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br /> void necklace(pair k, pen colors[]){<br /> draw(shift(k)*unitcircle); <br /> for(int i = 0; i &lt; colors.length; ++i){<br /> pair p = k+expi(pi/2+2*pi*i/colors.length);<br /> fill(Circle(p,r),colors[i]);<br /> draw(Circle(p,r));<br /> }<br /> }<br /> <br /> pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br /> necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br /> &lt;/asy&gt;&lt;br&gt; An illustration of the case &lt;math&gt;p=3,a=2&lt;/math&gt;.&lt;br&gt;&lt;/center&gt;<br /> <br /> Consider a necklace with &lt;math&gt;p&lt;/math&gt; beads, each bead of which can be colored in &lt;math&gt;a&lt;/math&gt; different ways. There are &lt;math&gt;a^p&lt;/math&gt; ways to pick the colors of the beads. &lt;math&gt;a&lt;/math&gt; of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly &lt;math&gt;p-1&lt;/math&gt; more necklaces that are rotationally equivalent to this necklace. It follows that &lt;math&gt;a^p-a&lt;/math&gt; must be divisible by &lt;math&gt;p&lt;/math&gt;. Written in another way, &lt;math&gt;a^p \equiv a \pmod{p}&lt;/math&gt;.<br /> <br /> [https://www.khanacademy.org/computing/computer-science/cryptography/random-algorithms-probability/v/fermat-s-little-theorem-visualization Video explanation]<br /> <br /> === Proof 4 (Geometry) ===<br /> &lt;center&gt;&lt;asy&gt;<br /> void match(int i, int j){ <br /> draw(shift((i,j))*unitsquare,linewidth(1));<br /> draw(shift((j,i))*unitsquare,linewidth(1));<br /> draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br /> }<br /> int n = 6;<br /> for(int i = 0; i &lt; n; ++i){<br /> for(int j = 0; j &lt; n; ++j)<br /> draw(shift((i,j))*unitsquare, linewidth(0.5));<br /> }<br /> draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br /> &lt;/asy&gt;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;asy&gt;<br /> import three; currentprojection = perspective(3,-2,4);<br /> void match(int i, int j, int k){ <br /> draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br /> draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br /> draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br /> draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br /> }<br /> int n = 4;<br /> for(int i = 0; i &lt; n; ++i){<br /> for(int j = 0; j &lt; n; ++j)<br /> for(int k = 0; k &lt; n; ++k)<br /> draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br /> }<br /> draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); &lt;/asy&gt;For &lt;math&gt;p=2,3&lt;/math&gt; and &lt;math&gt;a=6,4&lt;/math&gt;, respectively.&lt;/center&gt;<br /> We imbed a [[hypercube]] of side length &lt;math&gt;a&lt;/math&gt; in &lt;math&gt;\mathbb{R}^p&lt;/math&gt; (the &lt;math&gt;p&lt;/math&gt;-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at &lt;math&gt;(\pm a/2,\pm a/2, \ldots, \pm a/2)&lt;/math&gt;. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of &lt;math&gt;a^p&lt;/math&gt; separate unit hypercubes, with centers consisting of the points <br /> <br /> &lt;center&gt;&lt;cmath&gt;P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),&lt;/cmath&gt;&lt;/center&gt;&lt;br&gt;<br /> <br /> where each &lt;math&gt;x_i&lt;/math&gt; is an integer from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;a&lt;/math&gt;. Besides the &lt;math&gt;a&lt;/math&gt; centers of the unit hypercubes in the main diagonal (from &lt;math&gt;(-a/2, -a/2, \ldots, -a/2)&lt;/math&gt; to &lt;math&gt;(a/2, a/2, \ldots, a/2)&lt;/math&gt;), the transformation carrying <br /> <br /> &lt;cmath&gt;P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)&lt;/cmath&gt;&lt;br&gt;<br /> <br /> maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size &lt;math&gt;p&lt;/math&gt;, from which it follows that &lt;math&gt;a^p \equiv a \pmod{p}&lt;/math&gt;. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hypercube.<br /> <br /> == Problems ==<br /> === Introductory ===<br /> * Compute some examples, for example find &lt;math&gt;3^{31} \pmod{7}, 29^{25} \pmod{11}&lt;/math&gt;, and &lt;math&gt;128^{129} \pmod{17}&lt;/math&gt;, and check your answers by calculator where possible.<br /> <br /> * Let &lt;math&gt;k = 2008^2 + 2^{2008}&lt;/math&gt;. What is the units digit of &lt;math&gt;k^2 + 2^k&lt;/math&gt;? ([[2008 AMC 12A Problems/Problem 15]])<br /> <br /> * Find &lt;math&gt;2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}&lt;/math&gt; mod &lt;math&gt;7&lt;/math&gt;. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&amp;t=304326 Discussion]).<br /> <br /> === Intermediate ===<br /> * One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that &lt;math&gt;133^5+110^5+84^5+27^5=n^5&lt;/math&gt;. Find the value of &lt;math&gt;{n}&lt;/math&gt;. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])&lt;br&gt;&lt;br&gt;<br /> <br /> *If &lt;math&gt;f(x) = x^{x^{x^x}}&lt;/math&gt;, find the last two digits of &lt;math&gt;f(17) + f(18) + f(19) + f(20)&lt;/math&gt;. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#5])<br /> <br /> === Advanced ===<br /> *Is it true that if &lt;math&gt;p&lt;/math&gt; is a prime number, and &lt;math&gt;k&lt;/math&gt; is an integer &lt;math&gt;2 \le k \le p&lt;/math&gt;, then the sum of the products of each &lt;math&gt;k&lt;/math&gt;-element subset of &lt;math&gt;\{1, 2, \ldots, p\}&lt;/math&gt; will be divisible by &lt;math&gt;p&lt;/math&gt;? &lt;br&gt;&lt;br&gt;<br /> <br /> == Hints/Solutions ==<br /> Introductory: <br /> * Hint: For the first example, we have &lt;math&gt;3^6 \equiv 1 \pmod{7}&lt;/math&gt; by FLT (Fermat's Little Theorem). It follows that &lt;math&gt;3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}&lt;/math&gt;.<br /> <br /> Intermediate:<br /> * Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders &lt;math&gt;n&lt;/math&gt; can have after division by certain numbers. By Fermat's Little Theorem, we know &lt;math&gt;{n^{5}}&lt;/math&gt; is congruent to &lt;math&gt;n&lt;/math&gt; [[modulo]] 5. Hence,&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;3 + 0 + 4 + 7 \equiv n\pmod{5}&lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;4 \equiv n\pmod{5}&lt;/math&gt;&lt;/center&gt;<br /> &lt;br&gt;&lt;br&gt;<br /> :Continuing, we examine the equation modulo 3,<br /> &lt;center&gt;&lt;math&gt;-1 + 1 + 0 + 0 \equiv n\pmod{3}&lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;0 \equiv n\pmod{3}&lt;/math&gt;&lt;/center&gt;<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> :Thus, &lt;math&gt;n&lt;/math&gt; is divisible by three and leaves a remainder of four when divided by 5. It's obvious that &lt;math&gt;n&gt;133&lt;/math&gt;, so the only possibilities are &lt;math&gt;n = 144&lt;/math&gt; or &lt;math&gt;n = 174&lt;/math&gt;. It quickly becomes apparent that 174 is much too large, so &lt;math&gt;n&lt;/math&gt; must be 144.<br /> <br /> Advanced:<br /> * Hint: try to establish the identity &lt;math&gt;x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}&lt;/math&gt;, and then apply [[Vieta's formulas]]. <br /> <br /> ==Extensions==<br /> <br /> If &lt;math&gt;{a}&lt;/math&gt; is an [[integer]], &lt;math&gt;{p}&lt;/math&gt; is a [[prime number]] and &lt;math&gt;{a}&lt;/math&gt; is not [[divisibility|divisible]] by &lt;math&gt;{p}&lt;/math&gt;, then &lt;math&gt;a^{(p-1)k}\equiv 1 \pmod {p}&lt;/math&gt;. <br /> <br /> The above follows from the exponent rule &lt;math&gt;(a^b)^c=a^{bc}&lt;/math&gt;<br /> <br /> An extension of the Collary given above is that :<br /> &lt;cmath&gt;(a^p)^w \equiv a^w \pmod {p}&lt;/cmath&gt;<br /> <br /> Immediately by normal exponent rules, it follows that if: &lt;cmath&gt;z=(d_1d_2\ldots d_f)_p&lt;/cmath&gt; Then, &lt;cmath&gt;a^z\equiv a^{d_1+d_2+\cdots +d_f}\pmod p&lt;/cmath&gt; Which means, by repeating the process, we have that we can reduce the exponent to its digital root base &lt;math&gt;p&lt;/math&gt; . <br /> <br /> <br /> <br /> <br /> == See also ==<br /> * [[Number theory]]<br /> * [[Modular arithmetic]]<br /> * [[Euler's Totient Theorem]]<br /> * [[Order (group theory)]]<br /> <br /> [[Category:Number theory]]<br /> [[Category:Theorems]]</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_10A_Problems/Problem_21&diff=134592 2013 AMC 10A Problems/Problem 21 2020-10-04T10:49:53Z <p>Jimy: /* Video Solution by Richard Rusczyk */</p> <hr /> <div>==Problem==<br /> <br /> A group of &lt;math&gt;12&lt;/math&gt; pirates agree to divide a treasure chest of gold coins among themselves as follows. The &lt;math&gt;k^{\text{th}}&lt;/math&gt; pirate to take a share takes &lt;math&gt;\frac{k}{12}&lt;/math&gt; of the coins that remain in the chest. The number of coins initially in the chest is the smallest number for which this arrangement will allow each pirate to receive a positive whole number of coins. How many coins does the &lt;math&gt;12^{\text{th}}&lt;/math&gt; pirate receive?<br /> <br /> <br /> &lt;math&gt; \textbf{(A)}\ 720\qquad\textbf{(B)}\ 1296\qquad\textbf{(C)}\ 1728\qquad\textbf{(D)}\ 1925\qquad\textbf{(E)}\ 3850 &lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Let &lt;math&gt;x&lt;/math&gt; be the number of coins. After the &lt;math&gt;k^{\text{th}}&lt;/math&gt; pirate takes his share, &lt;math&gt;\frac{12-k}{12}&lt;/math&gt; of the original amount is left. Thus, we know that<br /> <br /> &lt;math&gt;x \cdot \frac{11}{12} \cdot \frac{10}{12} \cdot \frac{9}{12} \cdot \frac{8}{12} \cdot \frac{7}{12} \cdot \frac{6}{12} \cdot \frac{5}{12} \cdot \frac{4}{12} \cdot \frac{3}{12} \cdot \frac{2}{12} \cdot \frac{1}{12}&lt;/math&gt; must be an integer. Simplifying, we get<br /> <br /> <br /> &lt;math&gt;x \cdot \frac{11}{12} \cdot \frac{5}{6} \cdot \frac{1}{2} \cdot \frac{7}{12} \cdot \frac{1}{2} \cdot \frac{5}{12} \cdot \frac{1}{3} \cdot \frac{1}{4} \cdot \frac{1}{6} \cdot \frac{1}{12}&lt;/math&gt;. Now, the minimal &lt;math&gt;x&lt;/math&gt; is the denominator of this fraction multiplied out, obviously. We mentioned before that this product must be an integer. Specifically, it is an integer and it is the amount that the &lt;math&gt;12^{\text{th}}&lt;/math&gt; pirate receives, as he receives &lt;math&gt;\frac{12}{12} = 1 =&lt;/math&gt; all of what is remaining. <br /> <br /> Thus, we know the denominator is canceled out, so the number of gold coins received is going to be the product of the numerators, &lt;math&gt;11 \cdot 5 \cdot 7 \cdot 5 = \boxed{\textbf{(D) }1925}&lt;/math&gt;.<br /> <br /> ==Solution 2 (Using the answer choices)==<br /> <br /> Solution &lt;math&gt;1&lt;/math&gt; mentioned the expression &lt;math&gt;x \cdot \frac{11}{12} \cdot \frac{10}{12} \cdot ... \cdot \frac{1}{12}&lt;/math&gt;. Note that this is equivalent to &lt;math&gt; \frac{x \cdot 11!}{12^{11}}&lt;/math&gt;. <br /> <br /> <br /> We can compute the amount of factors of &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, &lt;math&gt;5&lt;/math&gt;, etc. but this is not necessary. To minimize this expression, we must take out factors of &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;3&lt;/math&gt;, since &lt;math&gt;12^{11}=2^{22} \cdot 3^{11}&lt;/math&gt;. &lt;math&gt;11!&lt;/math&gt; has neither &lt;math&gt;22&lt;/math&gt; factors of &lt;math&gt;2&lt;/math&gt;, nor &lt;math&gt;11&lt;/math&gt; factors of &lt;math&gt;3&lt;/math&gt;. This means that if &lt;math&gt;11!&lt;/math&gt; contains &lt;math&gt;a&lt;/math&gt; factors of &lt;math&gt;2&lt;/math&gt;, then &lt;math&gt;x&lt;/math&gt; will contain &lt;math&gt;22-a&lt;/math&gt; factors of &lt;math&gt;2&lt;/math&gt;. This also holds for factors of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> <br /> Thus, once simplified, the expression will have no factors of &lt;math&gt;2&lt;/math&gt;. It will also have no factors of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> <br /> Looking at the answer choices, there is only one answer which is not even, which is &lt;math&gt;\boxed{\textbf{(D) }1925}&lt;/math&gt;.<br /> <br /> == Solution 3 ==<br /> <br /> We know that the 11th pirate takes &lt;math&gt;\frac{11}{12}&lt;/math&gt; of what is left from the 10th pirate, so we have the 12th pirate taking &lt;cmath&gt;\frac{12}{12}\cdot(1-\frac{11}{12})=1\cdot\frac{1}{12}&lt;/cmath&gt; of what is left from the 10th pirate. Similarly, since the 10th pirate takes &lt;math&gt;\frac{10}{12}&lt;/math&gt; of what is left from the 9th pirate, we have the 11th pirate taking &lt;cmath&gt;\frac{11}{12}\cdot(1-\frac{10}{12})=\frac{11}{12}\cdot\frac{2}{12}&lt;/cmath&gt; of what is left from the 9th pirate. Thus, the 12th pirate takes &lt;cmath&gt;1\cdot\frac{1}{12}\cdot\frac{2}{12}&lt;/cmath&gt; of what is left from the 9th pirate. Repeating the method, we can find that the 12th pirate takes &lt;cmath&gt;1\cdot\frac{1}{12}\cdot\frac{2}{12}\cdot\frac{3}{12}\cdot...\cdot\frac{10}{12}\cdot\frac{11}{12}&lt;/cmath&gt; of what is left from the 1st pirate, or &lt;cmath&gt;1\cdot\frac{1}{12}\cdot\frac{2}{12}\cdot\frac{3}{12}\cdot...\cdot\frac{10}{12}\cdot\frac{11}{12}\cdot\frac{12}{12}&lt;/cmath&gt; of the total amount of coins. <br /> <br /> Now canceling out the denominator with the numerator as possible, we are left with &lt;math&gt;\frac{1\cdot5\cdot7\cdot5\cdot11}{...}=\frac{1925}{...}&lt;/math&gt; with some factors of 12 in the denominator. For this fraction to be an integer, the smallest possible number of coins is the same as the denominator, so the numerator is the number of coins taken by the 12th pirate, or &lt;math&gt;1925 \boxed{\mathrm{(D)}}&lt;/math&gt;<br /> <br /> ~ Nafer<br /> <br /> ==Video Solution by Richard Rusczyk==<br /> https://www.youtube.com/watch?v=-3d31c-7xm8<br /> <br /> ~dolphin7<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2013|ab=A|num-b=20|num-a=22}}<br /> {{AMC12 box|year=2013|ab=A|num-b=16|num-a=18}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2003_AMC_12A_Problems/Problem_12&diff=134590 2003 AMC 12A Problems/Problem 12 2020-10-04T07:25:28Z <p>Jimy: </p> <hr /> <div>{{duplicate|[[2003 AMC 12A Problems|2003 AMC 12A #12]] and [[2003 AMC 10A Problems|2003 AMC 10A #24]]}}<br /> == Problem ==<br /> Sally has five red cards numbered &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;5&lt;/math&gt; and four blue cards numbered &lt;math&gt;3&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt;. She stacks the cards so that the colors alternate and so that the number on each red card divides evenly into the number on each neighboring blue card. What is the sum of the numbers on the middle three cards? <br /> <br /> &lt;math&gt; \mathrm{(A) \ } 8\qquad \mathrm{(B) \ } 9\qquad \mathrm{(C) \ } 10\qquad \mathrm{(D) \ } 11\qquad \mathrm{(E) \ } 12 &lt;/math&gt;<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=Q30Dt8q7vm4&amp;feature=youtu.be<br /> <br /> <br /> == Solution ==<br /> Let &lt;math&gt;R_i&lt;/math&gt; and &lt;math&gt;B_j&lt;/math&gt; designate the red card numbered &lt;math&gt;i&lt;/math&gt; and the blue card numbered &lt;math&gt;j&lt;/math&gt;, respectively. <br /> <br /> &lt;math&gt;B_5&lt;/math&gt; is the only blue card that &lt;math&gt;R_5&lt;/math&gt; evenly divides, so &lt;math&gt;R_5&lt;/math&gt; must be at one end of the stack and &lt;math&gt;B_5&lt;/math&gt; must be the card next to it. <br /> <br /> &lt;math&gt;R_1&lt;/math&gt; is the only other red card that evenly divides &lt;math&gt;B_5&lt;/math&gt;, so &lt;math&gt;R_1&lt;/math&gt; must be the other card next to &lt;math&gt;B_5&lt;/math&gt;. <br /> <br /> &lt;math&gt;B_4&lt;/math&gt; is the only blue card that &lt;math&gt;R_4&lt;/math&gt; evenly divides, so &lt;math&gt;R_4&lt;/math&gt; must be at one end of the stack and &lt;math&gt;B_4&lt;/math&gt; must be the card next to it. <br /> <br /> &lt;math&gt;R_2&lt;/math&gt; is the only other red card that evenly divides &lt;math&gt;B_4&lt;/math&gt;, so &lt;math&gt;R_2&lt;/math&gt; must be the other card next to &lt;math&gt;B_4&lt;/math&gt;. <br /> <br /> &lt;math&gt;R_2&lt;/math&gt; doesn't evenly divide &lt;math&gt;B_3&lt;/math&gt;, so &lt;math&gt;B_3&lt;/math&gt; must be next to &lt;math&gt;R_1&lt;/math&gt;, &lt;math&gt;B_6&lt;/math&gt; must be next to &lt;math&gt;R_2&lt;/math&gt;, and &lt;math&gt;R_3&lt;/math&gt; must be in the middle. <br /> <br /> This yields the following arrangement from top to bottom: &lt;math&gt;\{R_5,B_5,R_1,B_3,R_3,B_6,R_2,B_4,R_4\}&lt;/math&gt;<br /> <br /> Therefore, the sum of the numbers on the middle three cards is &lt;math&gt;3+3+6=\boxed{\mathrm{(E)}\ 12}&lt;/math&gt;.<br /> <br /> == See Also ==<br /> {{AMC10 box|year=2003|ab=A|num-b=23|num-a=25}}<br /> {{AMC12 box|year=2003|ab=A|num-b=11|num-a=13}}<br /> <br /> [[Category:Introductory Algebra Problems]]<br /> [[Category:Introductory Number Theory Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_10B_Problems/Problem_11&diff=134145 2006 AMC 10B Problems/Problem 11 2020-09-27T11:12:39Z <p>Jimy: /* Solution */</p> <hr /> <div>== Problem ==<br /> What is the tens digit in the sum &lt;math&gt; 7!+8!+9!+...+2006!&lt;/math&gt;<br /> <br /> &lt;math&gt; \mathrm{(A) \ } 1\qquad \mathrm{(B) \ } 3\qquad \mathrm{(C) \ } 4\qquad \mathrm{(D) \ } 6\qquad \mathrm{(E) \ } 9 &lt;/math&gt;<br /> <br /> == Solution ==<br /> Since &lt;math&gt;10!&lt;/math&gt; is [[divisibility | divisible]] by &lt;math&gt;100&lt;/math&gt;, any [[factorial]] greater than &lt;math&gt;10!&lt;/math&gt; is also divisible by &lt;math&gt;100&lt;/math&gt;. The last two [[digit]]s of all factorials greater than &lt;math&gt;10!&lt;/math&gt; are &lt;math&gt;00&lt;/math&gt;, so the last two digits of &lt;math&gt;10!+11!+...+2006!&lt;/math&gt; are &lt;math&gt;00&lt;/math&gt;. <br /> (*)<br /> <br /> So all that is needed is the tens digit of the sum &lt;math&gt;7!+8!+9!&lt;/math&gt;<br /> <br /> &lt;math&gt;7!+8!+9!=5040+40320+362880=408240&lt;/math&gt;<br /> <br /> So the tens digit is &lt;math&gt;4 \Rightarrow C&lt;/math&gt;<br /> <br /> (*) A slightly faster method would have to take the &lt;math&gt;\pmod {100}&lt;/math&gt; residue of &lt;math&gt;7! + 8! + 9!.&lt;/math&gt; Since &lt;math&gt;7! = 5040,&lt;/math&gt; we can rewrite the sum as &lt;cmath&gt; 5040 + 8\cdot 5040 + 72\cdot 5040 \equiv 40 + 8\cdot 40 + 72\cdot 40 = 40 + 320 + 2880 \equiv 40 \pmod{100}. &lt;/cmath&gt; Since the last two digits of the sum is &lt;math&gt;40&lt;/math&gt;, the tens digit is &lt;math&gt;\fbox{4}.&lt;/math&gt;<br /> <br /> == See Also ==<br /> {{AMC10 box|year=2006|ab=B|num-b=10|num-a=12}}<br /> <br /> [[Category:Introductory Number Theory Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_10B_Problems/Problem_25&diff=131204 2013 AMC 10B Problems/Problem 25 2020-08-09T10:51:52Z <p>Jimy: /* Solution 1 */</p> <hr /> <div>{{duplicate|[[2013 AMC 12B Problems|2013 AMC 12B #23]] and [[2013 AMC 10B Problems|2013 AMC 10B #25]]}}<br /> <br /> ==Problem==<br /> <br /> Bernardo chooses a three-digit positive integer &lt;math&gt;N&lt;/math&gt; 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 &lt;math&gt;S&lt;/math&gt;. For example, if &lt;math&gt;N = 749&lt;/math&gt;, Bernardo writes the numbers &lt;math&gt;10,\!444&lt;/math&gt; and &lt;math&gt;3,\!245&lt;/math&gt;, and LeRoy obtains the sum &lt;math&gt;S = 13,\!689&lt;/math&gt;. For how many choices of &lt;math&gt;N&lt;/math&gt; are the two rightmost digits of &lt;math&gt;S&lt;/math&gt;, in order, the same as those of &lt;math&gt;2N&lt;/math&gt;?<br /> <br /> &lt;math&gt; \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 10 \qquad\textbf{(C)}\ 15 \qquad\textbf{(D)}\ 20 \qquad\textbf{(E)}\ 25&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities.<br /> <br /> Say that &lt;math&gt;N \equiv a \pmod{6}&lt;/math&gt;<br /> <br /> also that &lt;math&gt;N \equiv b \pmod{5}&lt;/math&gt;<br /> <br /> Substituting these equations into the question and setting the units digits of &lt;math&gt;2N&lt;/math&gt; and &lt;math&gt;S&lt;/math&gt; equal to each other, it can be seen that &lt;math&gt;b &lt; 5&lt;/math&gt; (because otherwise &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; will have different parities), and thus &lt;math&gt;a=b&lt;/math&gt;.<br /> &lt;math&gt;N \equiv a \pmod{6}&lt;/math&gt;,<br /> &lt;math&gt;N \equiv a \pmod{5}&lt;/math&gt;,<br /> &lt;math&gt;\implies N=a \pmod{30}&lt;/math&gt;,<br /> &lt;math&gt;0 \le a \le 4 &lt;/math&gt;<br /> <br /> Therefore, &lt;math&gt;N&lt;/math&gt; can be written as &lt;math&gt;30x+y&lt;/math&gt;<br /> and &lt;math&gt;2N&lt;/math&gt; can be written as &lt;math&gt;60x+2y&lt;/math&gt; <br /> <br /> Just keep in mind that &lt;math&gt;y&lt;/math&gt; can be one of five choices: &lt;math&gt;0, 1, 2, 3,&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;, ;<br /> Also, we have already found which digits of &lt;math&gt;y&lt;/math&gt; will add up into the units digits of &lt;math&gt;2N&lt;/math&gt;.<br /> <br /> Now, examine the tens digit, &lt;math&gt;x&lt;/math&gt; by using &lt;math&gt;\mod{25}&lt;/math&gt; and &lt;math&gt;\mod{36}&lt;/math&gt; to find the tens digit (units digits can be disregarded because &lt;math&gt;y=0,1,2,3,4&lt;/math&gt; will always work)<br /> Then we take &lt;math&gt;N=30x+y&lt;/math&gt; &lt;math&gt;\mod{25}&lt;/math&gt; and &lt;math&gt;\mod{36}&lt;/math&gt; to find the last two digits in the base &lt;math&gt;5&lt;/math&gt; and &lt;math&gt;6&lt;/math&gt; representation.<br /> &lt;cmath&gt;N \equiv 30x \pmod{36}&lt;/cmath&gt;<br /> &lt;cmath&gt;N \equiv 30x \equiv 5x \pmod{25}&lt;/cmath&gt; <br /> Both of those must add up to <br /> &lt;cmath&gt;2N\equiv60x \pmod{100}&lt;/cmath&gt;<br /> <br /> (&lt;math&gt;33 \ge x \ge 4&lt;/math&gt;)<br /> <br /> Now, since &lt;math&gt;y=0,1,2,3,4&lt;/math&gt; will always work if &lt;math&gt;x&lt;/math&gt; works, then we can treat &lt;math&gt;x&lt;/math&gt; as a units digit instead of a tens digit in the respective bases and decrease the mods so that &lt;math&gt;x&lt;/math&gt; is now the units digit.<br /> &lt;cmath&gt;N \equiv 5x \pmod{6}&lt;/cmath&gt; <br /> &lt;cmath&gt;N \equiv 6x \equiv x \pmod{5}&lt;/cmath&gt; <br /> &lt;cmath&gt;2N\equiv 6x \pmod{10}&lt;/cmath&gt;<br /> <br /> Say that &lt;math&gt;x=5m+n&lt;/math&gt; (m is between 0-6, n is 0-4 because of constraints on x)<br /> Then <br /> <br /> &lt;cmath&gt;N \equiv 5m+n \pmod{5}&lt;/cmath&gt; <br /> &lt;cmath&gt;N \equiv 25m+5n \pmod{6}&lt;/cmath&gt; <br /> &lt;cmath&gt;2N\equiv30m + 6n \pmod{10}&lt;/cmath&gt;<br /> <br /> and this simplifies to <br /> <br /> &lt;cmath&gt;N \equiv n \pmod{5}&lt;/cmath&gt; <br /> &lt;cmath&gt;N \equiv m+5n \pmod{6}&lt;/cmath&gt;<br /> &lt;cmath&gt;2N\equiv 6n \pmod{10}&lt;/cmath&gt;<br /> <br /> From careful inspection, this is true when<br /> <br /> &lt;math&gt;n=0, m=6&lt;/math&gt;<br /> <br /> &lt;math&gt;n=1, m=6&lt;/math&gt;<br /> <br /> &lt;math&gt;n=2, m=2&lt;/math&gt;<br /> <br /> &lt;math&gt;n=3, m=2&lt;/math&gt;<br /> <br /> &lt;math&gt;n=4, m=4&lt;/math&gt;<br /> <br /> This gives you &lt;math&gt;5&lt;/math&gt; choices for &lt;math&gt;x&lt;/math&gt;, and &lt;math&gt;5&lt;/math&gt; choices for &lt;math&gt;y&lt;/math&gt;, so the answer is <br /> &lt;math&gt;5* 5 = \boxed{\textbf{(E) }25}&lt;/math&gt;<br /> <br /> ==Solution 2==<br /> Notice that there are exactly &lt;math&gt;1000-100=900=5^2\cdot 6^2&lt;/math&gt; possible values of &lt;math&gt;N&lt;/math&gt;. This means, in &lt;math&gt;100\le N\le 999&lt;/math&gt;, every possible combination of &lt;math&gt;2&lt;/math&gt; digits will happen exactly once. We know that &lt;math&gt;N=900,901,902,903,904&lt;/math&gt; works because &lt;math&gt;900\equiv\dots00_5\equiv\dots00_6&lt;/math&gt;.<br /> <br /> We know for sure that the units digit will add perfectly every &lt;math&gt;30&lt;/math&gt; added or subtracted, because &lt;math&gt;\text{lcm }5,6=30&lt;/math&gt;. So we only have to care about cases of &lt;math&gt;N&lt;/math&gt; every &lt;math&gt;30&lt;/math&gt; subtracted. In each case, &lt;math&gt;2N&lt;/math&gt; subtracts &lt;math&gt;6&lt;/math&gt;/adds &lt;math&gt;4&lt;/math&gt;, &lt;math&gt;N_5&lt;/math&gt; subtracts &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;N_6&lt;/math&gt; adds &lt;math&gt;1&lt;/math&gt; for the &lt;math&gt;10&lt;/math&gt;'s digit.<br /> <br /> &lt;cmath&gt;\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}}&lt;/cmath&gt;<br /> <br /> &lt;cmath&gt;\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}}&lt;/cmath&gt;<br /> <br /> &lt;cmath&gt;\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}}&lt;/cmath&gt;<br /> <br /> As we can see, there are &lt;math&gt;5&lt;/math&gt; cases, including the original, that work. These are highlighted in &lt;math&gt;\textcolor{red}{\text{red}}&lt;/math&gt;. So, thus, there are &lt;math&gt;5&lt;/math&gt; possibilities for each case, and &lt;math&gt;5\cdot 5=\boxed{\textbf{(E) }25}&lt;/math&gt;.<br /> <br /> == Solution 3 ==<br /> <br /> Notice that &lt;math&gt;N_5&lt;/math&gt; ranges from &lt;math&gt;3&lt;/math&gt; to &lt;math&gt;5&lt;/math&gt; digits and &lt;math&gt;N_6&lt;/math&gt; ranges from &lt;math&gt;3&lt;/math&gt; to &lt;math&gt;4&lt;/math&gt; digits.<br /> <br /> Then let &lt;math&gt;a_i&lt;/math&gt;, &lt;math&gt;b_i&lt;/math&gt; denotes the digits of &lt;math&gt;N_5&lt;/math&gt;, &lt;math&gt;N_6&lt;/math&gt;, respectively such that &lt;cmath&gt;0\le a_i&lt;5,0\le b_i&lt;6&lt;/cmath&gt; Thus we have &lt;cmath&gt;N=5^4a_1+5^3a_2+5^2a_3+5a_4+a_5=6^3b_1+6^2b_2+6b_3+b_4&lt;/cmath&gt;<br /> &lt;cmath&gt;625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4&lt;/cmath&gt; <br /> Now we are given &lt;cmath&gt;2N \equiv S \equiv N_5+N_6\pmod{100}&lt;/cmath&gt;<br /> &lt;cmath&gt;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}&lt;/cmath&gt;<br /> &lt;cmath&gt;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}&lt;/cmath&gt;<br /> &lt;cmath&gt;50a_1+50a_2+50a_3+10a_4+2a_5 \equiv 10a_4+10b_3+a_5+b_4\pmod{100}&lt;/cmath&gt;<br /> Canceling out &lt;math&gt;a_5&lt;/math&gt; left with<br /> &lt;cmath&gt;50a_1+50a_2+50a_3+10a_4+a_5 \equiv 10a_4+10b_3+b_4\pmod{100}&lt;/cmath&gt;<br /> <br /> Since &lt;math&gt;a_5&lt;/math&gt;, &lt;math&gt;b_4&lt;/math&gt; determine the unit digits of the two sides of the congruence equation, we have &lt;math&gt;a_5=b_4=0,1,2,3,4&lt;/math&gt;. Thus,<br /> <br /> &lt;cmath&gt;50a_1+50a_2+50a_3+10a_4 \equiv 10a_4+10b_3\pmod{100}&lt;/cmath&gt; canceling out &lt;math&gt;10a_4&lt;/math&gt;, we have <br /> &lt;cmath&gt;50a_1+50a_2+50a_3 \equiv 10b_3\pmod{100}&lt;/cmath&gt;<br /> &lt;cmath&gt;5a_1+5a_2+5a_3 \equiv b_3\pmod{10}&lt;/cmath&gt;<br /> &lt;cmath&gt;5(a_1+a_2+a_3) \equiv b_3\pmod{10}&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;b_3&lt;/math&gt; is a multiple of &lt;math&gt;5&lt;/math&gt;.<br /> <br /> Now going back to our original equation <br /> &lt;cmath&gt;625a_1+125a_2+25a_3+5a_4+a_5=216b_1+36b_2+6b_3+b_4&lt;/cmath&gt; <br /> Since &lt;math&gt;a_5=b_4&lt;/math&gt;,<br /> &lt;cmath&gt;625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3&lt;/cmath&gt; <br /> &lt;cmath&gt;5(125a_1+25a_2+5a_3+a_4)=6(36b_1+6b_2+b_3)&lt;/cmath&gt; <br /> &lt;cmath&gt;5(125a_1+25a_2+5a_3+a_4)=6[6(6b_1+b_2)+b_3]&lt;/cmath&gt; <br /> <br /> Since the left side is a multiple of &lt;math&gt;5&lt;/math&gt;, then so does the right side. Thus &lt;math&gt;5\mid6(6b_1+b_2)+b_3&lt;/math&gt;.<br /> <br /> Since we already know that &lt;math&gt;5\mid b_3&lt;/math&gt;, then &lt;math&gt;5\mid6(6b_1+b_2)&lt;/math&gt;, from where we also know that &lt;math&gt;5\mid6b_1+b_2&lt;/math&gt;.<br /> <br /> For &lt;math&gt;b_1,b_2&lt;6&lt;/math&gt;, there is a total of 7 ordered pairs that satisfy the condition. Namely,<br /> <br /> &lt;cmath&gt;(b_1,b_2)=(0,0),(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)&lt;/cmath&gt;<br /> <br /> Since &lt;math&gt;N_6&lt;/math&gt; has at least &lt;math&gt;3&lt;/math&gt; digits, &lt;math&gt;(b_1,b_2)=(0,0)&lt;/math&gt; doesn't work. Furthermore, when &lt;math&gt;b_1=5&lt;/math&gt;, &lt;math&gt;216b_1&lt;/math&gt; exceeds &lt;math&gt;1000&lt;/math&gt; which is not possible as &lt;math&gt;N&lt;/math&gt; is a three digit number, thus &lt;math&gt;(b_1,b_2)=(5,0)&lt;/math&gt; won't work as well. <br /> <br /> Since we know that &lt;math&gt;a_i&lt;5&lt;/math&gt;, for each of the ordered pairs &lt;math&gt;(b_1,b_2)&lt;/math&gt;, there is respectively one and only one solution &lt;math&gt;(a_1,a_2,a_3,a_5)&lt;/math&gt; that satisfies the equation <br /> <br /> &lt;cmath&gt;625a_1+125a_2+25a_3+5a_4=216b_1+36b_2+6b_3&lt;/cmath&gt;<br /> <br /> Thus there are five solutions to the equation. Also since we have 5 possibilities for &lt;math&gt;a_5=b_4&lt;/math&gt;, we have a total of &lt;math&gt;5\cdot5=25&lt;/math&gt; values for &lt;math&gt;N&lt;/math&gt;. &lt;math&gt;\boxed{\textbf{(E) }25}&lt;/math&gt;<br /> <br /> ~ Nafer<br /> <br /> ==Solution 4==<br /> <br /> Observe that the maximum possible value of the sum of the last two digits of the base &lt;math&gt;5&lt;/math&gt; number and the base &lt;math&gt;6&lt;/math&gt; number is &lt;math&gt;44+55=99&lt;/math&gt;. <br /> Let &lt;math&gt;N \equiv a \mod 25&lt;/math&gt; and &lt;math&gt;N \equiv b \mod 36&lt;/math&gt;. <br /> <br /> If &lt;math&gt;a &lt; \frac{25}{2}&lt;/math&gt;, &lt;math&gt;2N \equiv 2a \mod 25&lt;/math&gt; and if &lt;math&gt;a &gt; \frac{25}{2}&lt;/math&gt;, &lt;math&gt;2N \equiv 2a - 25 \mod 25&lt;/math&gt;.<br /> <br /> Using the same logic for &lt;math&gt;b&lt;/math&gt;, if &lt;math&gt;b &lt; 18&lt;/math&gt;, &lt;math&gt;2N \equiv 2b \mod 36&lt;/math&gt;, and in the other case &lt;math&gt;2N \equiv 2b - 36 \mod 36&lt;/math&gt;.<br /> <br /> We can do four cases:<br /> <br /> Case 1: &lt;math&gt;a + b = 2a - 25 + 2b - 36 \implies a + b = 61&lt;/math&gt;.<br /> <br /> For this case, there is trivially only one possible solution, &lt;math&gt;(a, b) = (25, 36)&lt;/math&gt;, which is equivalent to &lt;math&gt;(a, b) = (0, 0)&lt;/math&gt;. <br /> <br /> Case 2: &lt;math&gt;a + b = 2a - 25 + 2b \implies a + b = 25&lt;/math&gt;.<br /> <br /> Note that in this case, &lt;math&gt;a \geq 13&lt;/math&gt; must hold, and &lt;math&gt;b &lt; 18&lt;/math&gt; must hold. <br /> We find the possible ordered pairs to be: &lt;math&gt;(13, 12), (14, 11), (15, 10), ..., (24, 1)&lt;/math&gt; for a total of &lt;math&gt;12&lt;/math&gt; ordered pairs.<br /> <br /> Case 3: &lt;math&gt;a + b = 2a + 2b - 36 \implies a + b = 36&lt;/math&gt;.<br /> <br /> Note that in this case, &lt;math&gt;b \geq 18&lt;/math&gt; must hold, and &lt;math&gt;a &lt; 13&lt;/math&gt; must hold.<br /> We find the possible ordered pairs to be: &lt;math&gt;(24, 12), (25, 11), (26, 10), ..., (35, 1)&lt;/math&gt; for a total of &lt;math&gt;12&lt;/math&gt; ordered pairs.<br /> <br /> Case 4: &lt;math&gt;a + b = 2a + 2b&lt;/math&gt;.<br /> <br /> Trivially no solutions except &lt;math&gt;(a, b) = (0, 0)&lt;/math&gt;, which matches the solution in Case 1, which makes this an overcount.<br /> <br /> By CRT, each solution &lt;math&gt;(a, b)&lt;/math&gt; corresponds exactly one positive integer in a set of exactly &lt;math&gt;\text{lcm} (25, 36) = 900&lt;/math&gt; consecutive positive integers, and since there are &lt;math&gt;900&lt;/math&gt; positive integers between &lt;math&gt;100&lt;/math&gt; and &lt;math&gt;999&lt;/math&gt;, our induction is complete, and our answer is &lt;math&gt;1 + 12 + 12 = \boxed{\textbf{(E) }25}&lt;/math&gt;.<br /> <br /> -fidgetboss_4000<br /> <br /> {{AMC12 box|year=2013|ab=B|num-b=22|num-a=24}}<br /> <br /> {{AMC10 box|year=2013|ab=B|num-b=24|after=Last Question}}<br /> <br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_23&diff=131202 2016 AMC 10B Problems/Problem 23 2020-08-09T06:38:08Z <p>Jimy: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> In regular hexagon &lt;math&gt;ABCDEF&lt;/math&gt;, points &lt;math&gt;W&lt;/math&gt;, &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, and &lt;math&gt;Z&lt;/math&gt; are chosen on sides &lt;math&gt;\overline{BC}&lt;/math&gt;, &lt;math&gt;\overline{CD}&lt;/math&gt;, &lt;math&gt;\overline{EF}&lt;/math&gt;, and &lt;math&gt;\overline{FA}&lt;/math&gt; respectively, so lines &lt;math&gt;AB&lt;/math&gt;, &lt;math&gt;ZW&lt;/math&gt;, &lt;math&gt;YX&lt;/math&gt;, and &lt;math&gt;ED&lt;/math&gt; are parallel and equally spaced. What is the ratio of the area of hexagon &lt;math&gt;WCXYFZ&lt;/math&gt; to the area of hexagon &lt;math&gt;ABCDEF&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ \frac{1}{3}\qquad\textbf{(B)}\ \frac{10}{27}\qquad\textbf{(C)}\ \frac{11}{27}\qquad\textbf{(D)}\ \frac{4}{9}\qquad\textbf{(E)}\ \frac{13}{27}&lt;/math&gt;<br /> <br /> <br /> ==Solution 1==<br /> We draw a diagram to make our work easier:<br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,W,X,Y,Z;<br /> A=(0,0);<br /> B=(1,0);<br /> C=(3/2,sqrt(3)/2);<br /> D=(1,sqrt(3));<br /> E=(0,sqrt(3));<br /> F=(-1/2,sqrt(3)/2);<br /> W=(4/3,2sqrt(3)/3);<br /> X=(4/3,sqrt(3)/3);<br /> Y=(-1/3,sqrt(3)/3);<br /> Z=(-1/3,2sqrt(3)/3);<br /> draw(A--B--C--D--E--F--cycle);<br /> draw(W--Z);<br /> draw(X--Y);<br /> <br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,ESE);<br /> label(&quot;$D$&quot;,D,NE);<br /> label(&quot;$E$&quot;,E,NW);<br /> label(&quot;$F$&quot;,F,WSW);<br /> label(&quot;$W$&quot;,W,ENE);<br /> label(&quot;$X$&quot;,X,ESE);<br /> label(&quot;$Y$&quot;,Y,WSW);<br /> label(&quot;$Z$&quot;,Z,WNW);<br /> &lt;/asy&gt;<br /> <br /> Assume that &lt;math&gt;AB&lt;/math&gt; is of length &lt;math&gt;1&lt;/math&gt;. Therefore, the area of &lt;math&gt;ABCDEF&lt;/math&gt; is &lt;math&gt;\frac{3\sqrt 3}2&lt;/math&gt;. To find the area of &lt;math&gt;WCXYFZ&lt;/math&gt;, we draw &lt;math&gt;\overline{CF}&lt;/math&gt;, and find the area of the trapezoids &lt;math&gt;WCFZ&lt;/math&gt; and &lt;math&gt;CXYF&lt;/math&gt;. <br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,W,X,Y,Z;<br /> A=(0,0);<br /> B=(1,0);<br /> C=(3/2,sqrt(3)/2);<br /> D=(1,sqrt(3));<br /> E=(0,sqrt(3));<br /> F=(-1/2,sqrt(3)/2);<br /> W=(4/3,2sqrt(3)/3);<br /> X=(4/3,sqrt(3)/3);<br /> Y=(-1/3,sqrt(3)/3);<br /> Z=(-1/3,2sqrt(3)/3);<br /> draw(A--B--C--D--E--F--cycle);<br /> draw(W--Z);<br /> draw(X--Y);<br /> draw(F--C--B--E--D--A);<br /> <br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,ESE);<br /> label(&quot;$D$&quot;,D,NE);<br /> label(&quot;$E$&quot;,E,NW);<br /> label(&quot;$F$&quot;,F,WSW);<br /> label(&quot;$W$&quot;,W,ENE);<br /> label(&quot;$X$&quot;,X,ESE);<br /> label(&quot;$Y$&quot;,Y,WSW);<br /> label(&quot;$Z$&quot;,Z,WNW);<br /> &lt;/asy&gt;<br /> <br /> From this, we know that &lt;math&gt;CF=2&lt;/math&gt;. We also know that the combined heights of the trapezoids is &lt;math&gt;\frac{\sqrt 3}3&lt;/math&gt;, since &lt;math&gt;\overline{ZW}&lt;/math&gt; and &lt;math&gt;\overline{YX}&lt;/math&gt; are equally spaced, and the height of each of the trapezoids is &lt;math&gt;\frac{\sqrt 3}6&lt;/math&gt;. From this, we know &lt;math&gt;\overline{ZW}&lt;/math&gt; and &lt;math&gt;\overline{YX}&lt;/math&gt; are each &lt;math&gt;\frac 13&lt;/math&gt; of the way from &lt;math&gt;\overline{CF}&lt;/math&gt; to &lt;math&gt;\overline{DE}&lt;/math&gt; and &lt;math&gt;\overline{AB}&lt;/math&gt;, respectively. We know that these are both equal to &lt;math&gt;\frac 53&lt;/math&gt;.<br /> <br /> We find the area of each of the trapezoids, which both happen to be &lt;math&gt;\frac{11}6 \cdot \frac{\sqrt 3}6=\frac{11\sqrt 3}{36}&lt;/math&gt;, and the combined area is &lt;math&gt;\frac{11\sqrt 3}{18}&lt;/math&gt;.<br /> <br /> We find that &lt;math&gt;\dfrac{\frac{11\sqrt 3}{18}}{\frac{3\sqrt 3}2}&lt;/math&gt; is equal to &lt;math&gt;\frac{22}{54}=\boxed{\textbf{(C)}\ \frac{11}{27}}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,W,X,Y,Z;<br /> A=(0,0);<br /> B=(1,0);<br /> C=(3/2,sqrt(3)/2);<br /> D=(1,sqrt(3));<br /> E=(0,sqrt(3));<br /> F=(-1/2,sqrt(3)/2);<br /> W=(4/3,2sqrt(3)/3);<br /> X=(4/3,sqrt(3)/3);<br /> Y=(-1/3,sqrt(3)/3);<br /> Z=(-1/3,2sqrt(3)/3);<br /> draw(A--B--C--D--E--F--cycle);<br /> draw(W--Z);<br /> draw(X--Y);<br /> draw(F--C--B--E--D--A);<br /> <br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,ESE);<br /> label(&quot;$D$&quot;,D,NE);<br /> label(&quot;$E$&quot;,E,NW);<br /> label(&quot;$F$&quot;,F,WSW);<br /> label(&quot;$W$&quot;,W,ENE);<br /> label(&quot;$X$&quot;,X,ESE);<br /> label(&quot;$Y$&quot;,Y,WSW);<br /> label(&quot;$Z$&quot;,Z,WNW);<br /> &lt;/asy&gt;<br /> <br /> First, like in the first solution, split the large hexagon into 6 equilateral triangles. Each equilateral triangle can be split into three rows of smaller equilateral triangles. The first row will have one triangle, the second three, the third five. Once you have drawn these lines, it's just a matter of counting triangles. There are &lt;math&gt;22&lt;/math&gt; small triangles in hexagon &lt;math&gt;ZWCXYF&lt;/math&gt;, and &lt;math&gt;9 \cdot 6 = 54&lt;/math&gt; small triangles in the whole hexagon. <br /> <br /> Thus, the answer is &lt;math&gt;\frac{22}{54}=\boxed{\textbf{(C)}\ \frac{11}{27}}&lt;/math&gt;.<br /> <br /> ==Solution 3 (Similar Triangles)==<br /> &lt;asy&gt;<br /> pair A,B,C,D,E,F,W,X,Y,Z;<br /> A=(0,0);<br /> B=(1,0);<br /> C=(3/2,sqrt(3)/2);<br /> D=(1,sqrt(3));<br /> E=(0,sqrt(3));<br /> F=(-1/2,sqrt(3)/2);<br /> W=(4/3,2sqrt(3)/3);<br /> X=(4/3,sqrt(3)/3);<br /> Y=(-1/3,sqrt(3)/3);<br /> Z=(-1/3,2sqrt(3)/3);<br /> pair G = (0.5, sqrt(3)*3/2);<br /> draw(A--B--C--D--E--F--cycle);<br /> draw(W--Z);<br /> draw(X--Y);<br /> draw(E--G--D);<br /> draw(F--C);<br /> <br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,ESE);<br /> label(&quot;$D$&quot;,D,NE);<br /> label(&quot;$E$&quot;,E,NW);<br /> label(&quot;$F$&quot;,F,WSW);<br /> label(&quot;$W$&quot;,W,ENE);<br /> label(&quot;$X$&quot;,X,ESE);<br /> label(&quot;$Y$&quot;,Y,WSW);<br /> label(&quot;$Z$&quot;,Z,WNW);<br /> label(&quot;$G$&quot;,G,N);<br /> &lt;/asy&gt;<br /> Extend &lt;math&gt;\overline{EF}&lt;/math&gt; and &lt;math&gt;\overline{CD}&lt;/math&gt; to meet at point &lt;math&gt;G&lt;/math&gt;, as shown in the diagram. Then &lt;math&gt;\triangle GZW \sim \triangle GFC&lt;/math&gt;. Then &lt;math&gt;[GZW] = \left(\dfrac53\right)^2[GED]&lt;/math&gt; and &lt;math&gt;[GFC] = 2^2[GED]&lt;/math&gt;. Subtracting &lt;math&gt;[GED]&lt;/math&gt;, we find that &lt;math&gt;[EDWZ] = \dfrac{16}{9}[GED]&lt;/math&gt; and &lt;math&gt;[EDCF] = 3[GED]&lt;/math&gt;. Subtracting again, we find that &lt;cmath&gt;[ZWCF] = [EDCF] - [EDWZ] = \dfrac{11}{9}[GED].&lt;/cmath&gt;Finally, &lt;cmath&gt;\dfrac{[WCXYFZ]}{[ABCDEF]} = \dfrac{[ZWCF]}{[EDCF]} = \dfrac{\dfrac{11}{9}[GED]}{3[GED]} = \textbf{(C) } \dfrac{11}{27}.&lt;/cmath&gt;<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2016|ab=B|num-b=22|num-a=24}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_20&diff=131200 2016 AMC 10B Problems/Problem 20 2020-08-09T05:58:52Z <p>Jimy: /* Problem */</p> <hr /> <div>==Problem==<br /> <br /> A dilation of the plane—that is, a size transformation with a positive scale factor—sends the circle of radius &lt;math&gt;2&lt;/math&gt; centered at &lt;math&gt;A(2,2)&lt;/math&gt; to the circle of radius &lt;math&gt;3&lt;/math&gt; centered at &lt;math&gt;A’(5,6)&lt;/math&gt;. What distance does the origin &lt;math&gt;O(0,0)&lt;/math&gt;, move under this transformation?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 0\qquad\textbf{(B)}\ 3\qquad\textbf{(C)}\ \sqrt{13}\qquad\textbf{(D)}\ 4\qquad\textbf{(E)}\ 5&lt;/math&gt;<br /> <br /> ==Solutions==<br /> ===Solution 1: Algebraic===<br /> The center of dilation must lie on the line &lt;math&gt;A A'&lt;/math&gt;, which can be expressed as &lt;math&gt;y = \dfrac{4x}{3} - \dfrac{2}{3}&lt;/math&gt;. Note that the center of dilation must have an &lt;math&gt;x&lt;/math&gt;-coordinate less than &lt;math&gt;2&lt;/math&gt;; if the &lt;math&gt;x&lt;/math&gt;-coordinate were otherwise, than the circle under the transformation would not have an increased &lt;math&gt;x&lt;/math&gt;-coordinate in the coordinate plane. Also, the ratio of dilation must be equal to &lt;math&gt;\dfrac{3}{2}&lt;/math&gt;, which is the ratio of the radii of the circles. Thus, we are looking for a point &lt;math&gt;(x,y)&lt;/math&gt; such that &lt;math&gt;\dfrac{3}{2} \left( 2 - x \right) = 5 - x&lt;/math&gt; (for the &lt;math&gt;x&lt;/math&gt;-coordinates), and &lt;math&gt;\dfrac{3}{2} \left( 2 - y \right) = 6 - y&lt;/math&gt;. We do not have to include absolute value symbols because we know that the center of dilation has a lower &lt;math&gt;x&lt;/math&gt;-coordinate, and hence a lower &lt;math&gt;y&lt;/math&gt;-coordinate, from our reasoning above. Solving the two equations, we get &lt;math&gt;x = -4&lt;/math&gt; and &lt;math&gt;y = - 6&lt;/math&gt;. This means that any point &lt;math&gt;(a,b)&lt;/math&gt; on the plane will dilate to the point &lt;math&gt;\left( \dfrac{3}{2} (a + 4) - 4, \dfrac{3}{2} (b + 6) - 6 \right)&lt;/math&gt;, which means that the point &lt;math&gt;(0,0)&lt;/math&gt; dilates to &lt;math&gt;\left( 6 - 4, 9 - 6 \right) = (2,3)&lt;/math&gt;. Thus, the origin moves &lt;math&gt;\sqrt{2^2 + 3^2} = \boxed{\sqrt{13}}&lt;/math&gt; units.<br /> <br /> ===Solution 2: Geometric===<br /> &lt;asy&gt; /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */<br /> /* by adihaya */<br /> import graph; size(13cm); <br /> real labelscalefactor = 0.5; /* changes label-to-point distance */<br /> pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ real xmin = -7., xmax = 9., ymin = -7., ymax = 9.6; /* image dimensions */<br /> pen xdxdff = rgb(0.49019607843137253,50.49019607843137253,1.); pen uuuuuu = rgb(0.666666666,0.26666666666666666,0.26666666666666666); pen qqzzff = rgb(0.,0.6,1.); pen ffwwqq = rgb(1.,0.4,0.); pen qqwuqq = rgb(0.,0.39215686274509803,0.); <br /> pair O = (3.,0.), A = (6.,2.), B = (2.,1.), C = (4.203155585,5.592712848525), D = (5.,4.), F = (-3.999634206191805,-5.999512274922407), G = (-3.999634206191812,-5.9995122749224175); <br /> /* by adihaya */<br /> draw((2.482656878,0.)---(4.482568783,0.48268779)--(2.,0.48272202065687797)--B--cycle, qqwuqq); <br /> draw((5.482722020656878,0.)--(7.4827220878,1.48277797)--(5.,0.48272687797)--(5.,0.)--cycle, qqwuqq); <br /> Label laxis; laxis.p = fontsize(10); <br /> xaxis(xmin, xmax, Ticks(laxis, Step = 2., Size = 2, NoZero),EndArrow(6), above = true); <br /> yaxis(ymin, ymax, Ticks(laxis, Step = 2., Size = 2, NoZero),EndArrow(6), above = true); /* draws axes; NoZero hides '0' label */ <br /> /* draw figures */<br /> draw(shift(A) * scale(2., 2.)*unitcircle); <br /> draw(shift((5.,6.)) * scale(3.000060969351735, 3.000060969351735)*unitcircle); <br /> draw((xmin, 1.3333333333333333*xmin-0.6666666666666666)--(xmax, 1.3333333333333333*xmax-0.6666666666666666)); /* line */<br /> draw((2.,ymin)--(2.,ymax)); /* line */<br /> draw((5.,ymin)--(5.,ymax)); /* line */<br /> draw((xmin, 1.6666869897839114*xmin + 0.6666260204321771)--(xmax, 1.6666869897839114*xmax + 0.6666260204321771)); /* line */<br /> draw(O--F, qqzzff); <br /> draw(F--A, ffwwqq); <br /> /* dots and labels */<br /> dot(O,blue); <br /> label(&quot;$O$&quot;, (0.08696973475182286,0.23426871275979863), NE * labelscalefactor,blue); <br /> dot(A,blue); <br /> label(&quot;$A$&quot;, (2.089474351594523,2.23677332960249), NE * labelscalefactor,blue); <br /> dot((5.,6.),blue); <br /> label(&quot;$A'$&quot;, (5.093231276858573,6.2190268290055695), NE * labelscalefactor,blue); <br /> dot(B,xdxdff); <br /> label(&quot;$B$&quot;, (2.089474351594523,0.23426871275979863), NE * labelscalefactor,xdxdff); <br /> label(&quot;$c$&quot;, (0.9971991060439592,3.2607813723061394), NE * labelscalefactor); <br /> dot(C,xdxdff); <br /> label(&quot;$C$&quot;, (3.2955282685566036,3.829674729363722), NE * labelscalefactor,xdxdff); <br /> label(&quot;$d$&quot;, (3.477574142815031,8.107752774436745), NE * labelscalefactor); <br /> label(&quot;$a$&quot;, (7.255026033677397,9.404829628528034), NE * labelscalefactor); <br /> label(&quot;$b$&quot;, (2.1804972887237364,9.404829628528034), NE * labelscalefactor); <br /> label(&quot;$e$&quot;, (4.615360856930201,9.404829628528034), NE * labelscalefactor); <br /> dot(D,linewidth(3.pt) + uuuuuu); <br /> /* Solution by adihaya */<br /> label(&quot;$D$&quot;, (2.089474351594523,4.125499275033665), NE * labelscalefactor,uuuuuu); <br /> dot((5.,9.000060969351734),linewidth(3.pt) + uuuuuu); <br /> label(&quot;$E$&quot;, (5.093231276858573,9.131760817140394), NE * labelscalefactor,uuuuuu); <br /> label(&quot;$f$&quot;, (4.933941136882449,9.404829628528034), NE * labelscalefactor); <br /> dot(F,linewidth(3.pt) + uuuuuu); <br /> label(&quot;$\Large{(-4,-6)}$&quot;, (-3.73599362467515,-6.273871291978948), NE * labelscalefactor,uuuuuu); <br /> label(&quot;$\Large{2\sqrt{13}}$&quot;, (-2.916787190512227,-2.0868161840351394), NE * labelscalefactor,qqzzff); <br /> dot(G,linewidth(3.pt) + uuuuuu); <br /> label(&quot;$G$&quot;, (-3.9180394989335774,-5.864268074897489), NE * labelscalefactor,uuuuuu); <br /> label(&quot;$\Large{10}$&quot;, (0.2690156090102501,-0.6759606585323339), NE * labelscalefactor,ffwwqq); <br /> clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); <br /> /* re-scale y/x */<br /> currentpicture = yscale(0.9090909090909091) * currentpicture; <br /> /* end of picture */&lt;/asy&gt;<br /> Using analytic geometry, we find that the center of dilation is at &lt;math&gt;(-4,-6)&lt;/math&gt; and the coefficient/factor is &lt;math&gt;1.5&lt;/math&gt;. Then, we see that the origin is &lt;math&gt;2\sqrt{13}&lt;/math&gt; from the center, and will be &lt;math&gt;1.5 \times 2\sqrt{13} = 3\sqrt{13}&lt;/math&gt; from it afterwards.<br /> <br /> Thus, it will move &lt;math&gt;3\sqrt{13} - 2\sqrt{13} = \boxed{\sqrt{13}}&lt;/math&gt;.<br /> <br /> ===Solution 3: Logic and Geometry===<br /> <br /> Using the ratios of radii of the circles, &lt;math&gt;\frac{3}{2}&lt;/math&gt;, we find that the scale factor is &lt;math&gt;1.5&lt;/math&gt;. If the origin had not moved, this indicates that the center of the<br /> circle would be &lt;math&gt;(3,3)&lt;/math&gt;, simply because of &lt;math&gt;(2 \cdot 1.5, 2 \cdot 1.5)&lt;/math&gt;. Since the center has moved from &lt;math&gt;(3,3)&lt;/math&gt; to &lt;math&gt;(5,6)&lt;/math&gt;, we apply the distance formula and get: &lt;math&gt;\sqrt{(6-3)^2 + (5-3)^2} = \boxed{\sqrt{13}}&lt;/math&gt;.<br /> <br /> ===Solution 4: Simple and Practical===<br /> <br /> Start with the size transformation. Transforming the circle from &lt;math&gt;r=2&lt;/math&gt; to &lt;math&gt;r=3&lt;/math&gt; would mean the origin point now transforms into the point &lt;math&gt;(-1,-1)&lt;/math&gt;. Now apply the position shift: &lt;math&gt;3&lt;/math&gt; to the right and &lt;math&gt;4&lt;/math&gt; up. This gets you the point &lt;math&gt;(2,3)&lt;/math&gt;. Now simply apply the Pythagorean theorem with the points &lt;math&gt;(0,0)&lt;/math&gt; and &lt;math&gt;(2,3)&lt;/math&gt; to find the requested distance.<br /> <br /> ===Solution 5: Using the Axes===<br /> <br /> Before dilation, notice that the two axes are tangent to the circle with center &lt;math&gt;(2,2)&lt;/math&gt;. Using this, we can draw new axes tangent to the radius 3 circle with center &lt;math&gt;(5,6)&lt;/math&gt;, resulting in a &quot;new origin&quot; that is 3 units left and 3 units down from the center &lt;math&gt;(5,6)&lt;/math&gt;, or &lt;math&gt;(2,3)&lt;/math&gt;. Using the distance formula, the distance from &lt;math&gt;(0,0)&lt;/math&gt; and &lt;math&gt;(2,3)&lt;/math&gt; is &lt;math&gt;\boxed{\sqrt{13}}&lt;/math&gt;.<br /> ~Mightyeagle<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2016|ab=B|num-b=19|num-a=21}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_25&diff=131199 2016 AMC 10B Problems/Problem 25 2020-08-09T05:54:43Z <p>Jimy: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> <br /> Let &lt;math&gt;f(x)=\sum_{k=2}^{10}(\lfloor kx \rfloor -k \lfloor x \rfloor)&lt;/math&gt;, where &lt;math&gt;\lfloor r \rfloor&lt;/math&gt; denotes the greatest integer less than or equal to &lt;math&gt;r&lt;/math&gt;. How many distinct values does &lt;math&gt;f(x)&lt;/math&gt; assume for &lt;math&gt;x \ge 0&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 32\qquad\textbf{(B)}\ 36\qquad\textbf{(C)}\ 45\qquad\textbf{(D)}\ 46\qquad\textbf{(E)}\ \text{infinitely many}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Since &lt;math&gt;x = \lfloor x \rfloor + \{ x \}&lt;/math&gt;, we have <br /> <br /> &lt;cmath&gt;f(x) = \sum_{k=2}^{10} (\lfloor k \lfloor x \rfloor +k \{ x \} \rfloor - k \lfloor x \rfloor)&lt;/cmath&gt;<br /> <br /> The function can then be simplified into <br /> <br /> &lt;cmath&gt;f(x) = \sum_{k=2}^{10} ( k \lfloor x \rfloor + \lfloor k \{ x \} \rfloor - k \lfloor x \rfloor)&lt;/cmath&gt;<br /> <br /> which becomes<br /> <br /> &lt;cmath&gt;f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor&lt;/cmath&gt;<br /> <br /> We can see that for each value of &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;\lfloor k \{ x \} \rfloor&lt;/math&gt; can equal integers from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;k-1&lt;/math&gt;. <br /> <br /> Clearly, the value of &lt;math&gt;\lfloor k \{ x \} \rfloor&lt;/math&gt; changes only when &lt;math&gt;\{ x \}&lt;/math&gt; is equal to any of the fractions &lt;math&gt;\frac{1}{k}, \frac{2}{k} \dots \frac{k-1}{k}&lt;/math&gt;.<br /> <br /> So we want to count how many distinct fractions less than &lt;math&gt;1&lt;/math&gt; have the form &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;n \le 10&lt;/math&gt;. We can find this easily by computing<br /> <br /> &lt;cmath&gt;\sum_{k=2}^{10} \phi(k)&lt;/cmath&gt;<br /> <br /> where &lt;math&gt;\phi(k)&lt;/math&gt; is the [[Euler Totient Function]]. Basically &lt;math&gt;\phi(k)&lt;/math&gt; counts the number of fractions with &lt;math&gt;k&lt;/math&gt; as its denominator (after simplification). This comes out to be &lt;math&gt;31&lt;/math&gt;.<br /> <br /> Because the value of &lt;math&gt;f(x)&lt;/math&gt; is at least &lt;math&gt;0&lt;/math&gt; and can increase &lt;math&gt;31&lt;/math&gt; times, there are a total of &lt;math&gt;\fbox{\textbf{(A)}\ 32}&lt;/math&gt; different possible values of &lt;math&gt;f(x)&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> <br /> &lt;math&gt;x = \lfloor x \rfloor + \{ x \}&lt;/math&gt; so we have &lt;cmath&gt;f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor.&lt;/cmath&gt; Clearly, the value of &lt;math&gt;\lfloor k \{ x \} \rfloor&lt;/math&gt; changes only when &lt;math&gt;x&lt;/math&gt; is equal to any of the fractions &lt;math&gt;\frac{1}{k}, \frac{2}{k} \dots \frac{k-1}{k}&lt;/math&gt;. To get all the fractions, Graphing this function gives us &lt;math&gt;46&lt;/math&gt; different fractions but on an average, &lt;math&gt;3&lt;/math&gt; in each of the &lt;math&gt;5&lt;/math&gt; intervals don’t work. This means there are a total of &lt;math&gt;\fbox{\textbf{(A)}\ 32}&lt;/math&gt; different possible values of &lt;math&gt;f(x)&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2016|ab=B|num-b=24|after=Last Problem}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_10A_Problems/Problem_25&diff=131120 2013 AMC 10A Problems/Problem 25 2020-08-08T04:54:39Z <p>Jimy: /* Video Solution by Richard Rusczyk */</p> <hr /> <div>==Problem==<br /> <br /> All &lt;math&gt;20&lt;/math&gt; diagonals are drawn in a regular octagon. At how many distinct points in the interior<br /> of the octagon (not on the boundary) do two or more diagonals intersect?<br /> <br /> &lt;math&gt; \textbf{(A)}\ 49\qquad\textbf{(B)}\ 65\qquad\textbf{(C)}\ 70\qquad\textbf{(D)}\ 96\qquad\textbf{(E)}\ 128 &lt;/math&gt;<br /> [[Category: Introductory Geometry Problems]]<br /> <br /> ==Solution 1 (Drawing)==<br /> <br /> If you draw a clear diagram like the one below, it is easy to see that there are &lt;math&gt;\boxed{\textbf{(A) }49}&lt;/math&gt; points.<br /> <br /> &lt;asy&gt;<br /> size(14cm);<br /> pathpen = brown + 1.337;<br /> // Initialize octagon<br /> pair[] A;<br /> for (int i=0; i&lt;8; ++i) {<br /> A[i] = dir(45*i);<br /> }<br /> D(CR( (0,0), 1));<br /> // Draw diagonals<br /> // choose pen colors<br /> pen[] colors;<br /> colors = orange + 1.337;<br /> colors = purple;<br /> colors = green;<br /> colors = black;<br /> for (int d=1; d&lt;=4; ++d) {<br /> pathpen = colors[d];<br /> for (int j=0; j&lt;8; ++j) {<br /> D(A[j]--A[(j+d) % 8]);<br /> }<br /> }<br /> pathpen = blue + 2;<br /> // Draw all the intersections<br /> pointpen = red + 7;<br /> for (int x1=0; x1&lt;8; ++x1) {<br /> for (int x2=x1+1; x2&lt;8; ++x2) {<br /> for (int x3=x2+1; x3&lt;8; ++x3) {<br /> for (int x4=x3+1; x4&lt;8; ++x4) {<br /> D(IP(A[x1]--A[x2], A[x3]--A[x4]));<br /> D(IP(A[x1]--A[x3], A[x4]--A[x2]));<br /> D(IP(A[x1]--A[x4], A[x2]--A[x3]));<br /> }<br /> }<br /> }<br /> }&lt;/asy&gt;<br /> <br /> ==Solution 2 (Working Backwards)==<br /> <br /> Let the number of intersections be &lt;math&gt;x&lt;/math&gt;. We know that &lt;math&gt;x\le \dbinom{8}{4} = 70&lt;/math&gt;, as every &lt;math&gt;4&lt;/math&gt; vertices on the octagon forms a quadrilateral with intersecting diagonals which is an intersection point. However, four diagonals intersect in the center, so we need to subtract &lt;math&gt;\dbinom{4}{2} -1 = 5&lt;/math&gt; from this count, &lt;math&gt;70-5 = 65&lt;/math&gt;. Note that diagonals like &lt;math&gt;\overline{AD}&lt;/math&gt;, &lt;math&gt;\overline{CG}&lt;/math&gt;, and &lt;math&gt;\overline{BE}&lt;/math&gt; all intersect at the same point. There are &lt;math&gt;8&lt;/math&gt; of this type with three diagonals intersecting at the same point, so we need to subtract &lt;math&gt;2&lt;/math&gt; of the &lt;math&gt;\dbinom{3}{2}&lt;/math&gt; (one is kept as the actual intersection). In the end, we obtain &lt;math&gt;65 - 16 = \boxed{\textbf{(A) }49}&lt;/math&gt;.<br /> <br /> ==Solution 3 (Answer choices and reasoning)==<br /> We know that the amount of intersection points is at most &lt;math&gt;\dbinom{8}{4} = 70&lt;/math&gt;, as in solution &lt;math&gt;2&lt;/math&gt;. There's probably going to be more than &lt;math&gt;5&lt;/math&gt; (to get &lt;math&gt;\textbf{(B) }65&lt;/math&gt;), leading us to the only reasonable answer, &lt;math&gt;\boxed{\textbf{(A) }49}&lt;/math&gt;.<br /> -Lcz<br /> <br /> ==Solution 4 (Drawing but easier)==<br /> Like solution one, we may draw. Except note that the octagon has eight regions, and each region has an equal number of points, so drawing only one of the eight regions and the intersection points suffices. One of the eight regions contains &lt;math&gt;8&lt;/math&gt; points (not including the octagon center). However each adjacent region share one side in common and that side contains &lt;math&gt;2&lt;/math&gt; intersection points, so in actuality there are &lt;math&gt;8 - 2 = 6&lt;/math&gt; points per region. We multiply this by &lt;math&gt;8&lt;/math&gt; to get &lt;math&gt;6\cdot 8 = 48&lt;/math&gt; and add the one center point to get &lt;math&gt;48 + 1 = \boxed{\textbf{(A) }49}&lt;/math&gt;.<br /> <br /> ~skyscraper<br /> <br /> ==Video Solution by Richard Rusczyk==<br /> https://artofproblemsolving.com/videos/amc/2013amc10a/359<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2013|ab=A|num-b=24|after=Last Problem}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2013_AMC_10A_Problems/Problem_24&diff=131119 2013 AMC 10A Problems/Problem 24 2020-08-08T04:42:44Z <p>Jimy: /* Video Solution by Richard Rusczyk */</p> <hr /> <div>==Problem==<br /> <br /> Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?<br /> <br /> &lt;math&gt; \textbf{(A)}\ 540\qquad\textbf{(B)}\ 600\qquad\textbf{(C)}\ 720\qquad\textbf{(D)}\ 810\qquad\textbf{(E)}\ 900&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Let us label the players of the first team &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, and &lt;math&gt;C&lt;/math&gt;, and those of the second team, &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, and &lt;math&gt;Z&lt;/math&gt;. <br /> <br /> &lt;math&gt;\textbf{1}&lt;/math&gt;. One way of scheduling all six distinct rounds could be:<br /> <br /> Round 1----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 2----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> Round 3----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 4----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> Round 5----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> Round 6----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> <br /> The above mentioned schedule ensures that each player of one team plays twice with each player from another team. Now you can generate a completely new schedule by permutating those &lt;math&gt;6&lt;/math&gt; rounds and that can be done in &lt;math&gt;6!=720&lt;/math&gt; ways.<br /> <br /> &lt;math&gt;\textbf{2}&lt;/math&gt;. One can also make the schedule in such a way that two rounds are repeated. <br /> <br /> (a)<br /> Round 1----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> Round 2----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> Round 3----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 4----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 5----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> Round 6----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> <br /> (b)<br /> Round 1----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 2----&gt;&lt;math&gt;AX&lt;/math&gt; &lt;math&gt;BY&lt;/math&gt; &lt;math&gt;CZ&lt;/math&gt;<br /> Round 3----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> Round 4----&gt;&lt;math&gt;AY&lt;/math&gt; &lt;math&gt;BZ&lt;/math&gt; &lt;math&gt;CX&lt;/math&gt;<br /> Round 5----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> Round 6----&gt;&lt;math&gt;AZ&lt;/math&gt; &lt;math&gt;BX&lt;/math&gt; &lt;math&gt;CY&lt;/math&gt;<br /> <br /> As mentioned earlier any permutation of (a) and (b) will also give us a new schedule. For both (a) and (b) the number of permutations are<br /> &lt;math&gt;\frac{6!}{2!2!2!}&lt;/math&gt; = &lt;math&gt;90&lt;/math&gt;<br /> <br /> <br /> So the total number of schedules is &lt;math&gt;720+90+90&lt;/math&gt; =&lt;math&gt;\boxed{\textbf{(E)} 900}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> Label the players of the first team &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, and &lt;math&gt;C&lt;/math&gt;, and those of the second team, &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, and &lt;math&gt;Z&lt;/math&gt;. We can start by assigning an opponent to person &lt;math&gt;A&lt;/math&gt; for all &lt;math&gt;6&lt;/math&gt; games. Since &lt;math&gt;A&lt;/math&gt; has to play each of &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, and &lt;math&gt;Z&lt;/math&gt; twice, there are &lt;math&gt;\frac{6!}{2!2!2!} = 90&lt;/math&gt; ways to do this. We can assume that the opponents for &lt;math&gt;A&lt;/math&gt; in the &lt;math&gt;6&lt;/math&gt; rounds are &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, &lt;math&gt;Z&lt;/math&gt;, &lt;math&gt;Z&lt;/math&gt; and multiply by &lt;math&gt;90&lt;/math&gt; afterwards.<br /> <br /> <br /> Notice that for every valid assignment of the opponents of &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt;, there is only &lt;math&gt;1&lt;/math&gt; valid assignment of opponents for &lt;math&gt;C&lt;/math&gt;. More specifically, the opponents for &lt;math&gt;C&lt;/math&gt; are the leftover opponents after the opponents for &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; are chosen in each round. Therefore, all we have to do is assign the opponents for &lt;math&gt;B&lt;/math&gt;. This is the same as finding the number of permutations of &lt;math&gt;X&lt;/math&gt;, &lt;math&gt;Y&lt;/math&gt;, and &lt;math&gt;Z&lt;/math&gt; that do not have a &lt;math&gt;X&lt;/math&gt; in the first two spots, an &lt;math&gt;Y&lt;/math&gt; in the next two spots, and a &lt;math&gt;Z&lt;/math&gt; in the final two spots.<br /> <br /> <br /> <br /> We can use casework to find this by using the fact that after we put down the &lt;math&gt;X&lt;/math&gt;'s and &lt;math&gt;Y&lt;/math&gt;'s first there is &lt;math&gt;1&lt;/math&gt; way to put down the &lt;math&gt;Z&lt;/math&gt;'s (the two remaining spots).<br /> <br /> If &lt;math&gt;X&lt;/math&gt;'s are put in the middle &lt;math&gt;2&lt;/math&gt; spots, then there is &lt;math&gt;1&lt;/math&gt; way to assign spots to &lt;math&gt;Y&lt;/math&gt;, namely the last &lt;math&gt;2&lt;/math&gt; spots. (If one of the last two spots are left empty, there will have to be a &lt;math&gt;Z&lt;/math&gt; there, which which not valid).<br /> <br /> If &lt;math&gt;X&lt;/math&gt;'s are put in the last &lt;math&gt;2&lt;/math&gt; spots, then there is &lt;math&gt;1&lt;/math&gt; way to assign spots to &lt;math&gt;Y&lt;/math&gt;.<br /> <br /> Finally, if one &lt;math&gt;X&lt;/math&gt; was put in on of the middle two spots and one &lt;math&gt;X&lt;/math&gt; was put in one of the last two spots, there are &lt;math&gt;2\cdot2&lt;/math&gt; ways to assign spots to &lt;math&gt;X&lt;/math&gt; and &lt;math&gt;2\cdot1&lt;/math&gt; ways to assign spots to &lt;math&gt;Y&lt;/math&gt; (one of the first two spots and the remaining spot in the last &lt;math&gt;2&lt;/math&gt;).<br /> <br /> There are &lt;math&gt;1+1+2\cdot2\cdot2\cdot1 = 10&lt;/math&gt; ways to assign opponents to &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;90\cdot10 = 900&lt;/math&gt; ways to order the games. &lt;math&gt;\boxed{\textbf{(E)} 900}&lt;/math&gt;<br /> ==Video Solution by Richard Rusczyk==<br /> https://artofproblemsolving.com/videos/amc/2013amc10a/358<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2013|ab=A|num-b=23|num-a=25}}<br /> <br /> [[Category:Introductory Combinatorics Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_10B_Problems/Problem_1&diff=131116 2011 AMC 10B Problems/Problem 1 2020-08-08T03:47:23Z <p>Jimy: /* Solution */</p> <hr /> <div>== Problem==<br /> <br /> What is &lt;cmath&gt;\dfrac{2+4+6}{1+3+5} - \dfrac{1+3+5}{2+4+6} ?&lt;/cmath&gt;<br /> <br /> &lt;math&gt; \textbf{(A)}\ -1\qquad\textbf{(B)}\ \frac{5}{36}\qquad\textbf{(C)}\ \frac{7}{12}\qquad\textbf{(D)}\ \frac{147}{60}\qquad\textbf{(E)}\ \frac{43}{3} &lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> &lt;math&gt;\dfrac{2+4+6}{1+3+5} - \dfrac{1+3+5}{2+4+6} = \dfrac{12}{9} - \dfrac{9}{12} = \dfrac{4}{3} - \dfrac{3}{4} = \boxed{\dfrac{7}{12}\; \textbf{(C)}}&lt;/math&gt;<br /> <br /> <br /> Note: This exact problem was reused in 2013 AMC 10B: <br /> <br /> https://artofproblemsolving.com/wiki/index.php/2013_AMC_10B_Problems/Problem_1<br /> <br /> == See Also ==<br /> <br /> {{AMC10 box|year=2011|ab=B|before=First Problem|num-a=2}}<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_10A_Problems/Problem_19&diff=130760 2012 AMC 10A Problems/Problem 19 2020-08-06T10:30:45Z <p>Jimy: /* Solution 2 (Easy process of elimination) */</p> <hr /> <div>{{duplicate|[[2012 AMC 12A Problems|2012 AMC 12A #13]] and [[2012 AMC 10A Problems|2012 AMC 10A #19]]}}<br /> <br /> ==Problem 19==<br /> <br /> Paula the painter and her two helpers each paint at constant, but different, rates. They always start at 8:00 AM, and all three always take the same amount of time to eat lunch. On Monday the three of them painted 50% of a house, quitting at 4:00 PM. On Tuesday, when Paula wasn't there, the two helpers painted only 24% of the house and quit at 2:12 PM. On Wednesday Paula worked by herself and finished the house by working until 7:12 P.M. How long,in minutes, was each day's lunch break?<br /> <br /> &lt;math&gt; \textbf{(A)}\ 30\qquad\textbf{(B)}\ 36\qquad\textbf{(C)}\ 42\qquad\textbf{(D)}\ 48\qquad\textbf{(E)}\ 60 &lt;/math&gt;<br /> <br /> ==Solution==<br /> Let Paula work at a rate of &lt;math&gt;p&lt;/math&gt;, the two helpers work at a combined rate of &lt;math&gt;h&lt;/math&gt;, and the time it takes to eat lunch be &lt;math&gt;L&lt;/math&gt;, where &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;h&lt;/math&gt; are in house/hours and L is in hours. Then the labor on Monday, Tuesday, and Wednesday can be represented by the three following equations:<br /> <br /> &lt;cmath&gt;(8-L)(p+h)=50&lt;/cmath&gt;<br /> <br /> &lt;cmath&gt;(6.2-L)h=24&lt;/cmath&gt;<br /> <br /> &lt;cmath&gt;(11.2-L)p=26&lt;/cmath&gt;<br /> <br /> With three equations and three variables, we need to find the value of &lt;math&gt;L&lt;/math&gt;.<br /> Adding the second and third equations together gives us &lt;math&gt;6.2h+11.2p-L(p+h)=50&lt;/math&gt;. Subtracting the first equation from this new one gives us &lt;math&gt;-1.8h+3.2p=0&lt;/math&gt;, so we get &lt;math&gt;h=\frac{16}{9}p&lt;/math&gt;. <br /> Plugging into the second equation:<br /> <br /> &lt;cmath&gt;(6.2-L)\frac{16}{9}p=24&lt;/cmath&gt;<br /> &lt;cmath&gt;(6.2-L)p=\frac{27}{2}&lt;/cmath&gt;<br /> <br /> We can then subtract this from the third equation:<br /> <br /> &lt;cmath&gt;5p=26-\frac{27}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;p=\frac{5}{2}&lt;/cmath&gt;<br /> Plugging &lt;math&gt;p&lt;/math&gt; into our third equation gives: &lt;cmath&gt;L=\frac{4}{5}&lt;/cmath&gt;<br /> <br /> Converting &lt;math&gt;L&lt;/math&gt; from hours to minutes gives us &lt;math&gt;L=48&lt;/math&gt; minutes, which is &lt;math&gt;\boxed{\textbf{(D)}\ 48}&lt;/math&gt;.<br /> <br /> ==Solution 2 (Easy process of elimination)==<br /> Because Paula worked from &lt;cmath&gt;8:00 A.M.&lt;/cmath&gt; to &lt;cmath&gt;7:12 P.M.&lt;/cmath&gt;, she worked for 11 hours and 12 minutes = 672 minutes. Since there is &lt;math&gt;100-50-24=26&lt;/math&gt;% of the house left, we get the equation &lt;math&gt;26a=672&lt;/math&gt;. Because &lt;math&gt;672&lt;/math&gt; is &lt;math&gt;22&lt;/math&gt; mod &lt;math&gt;26&lt;/math&gt;, looking at out answer choices, the only answer that is &lt;math&gt;22&lt;/math&gt; &lt;math&gt;\text{mod}&lt;/math&gt; &lt;math&gt;26&lt;/math&gt; is &lt;math&gt;48&lt;/math&gt;. So the answer is &lt;math&gt;\boxed{\textbf{(D)}\ 48}&lt;/math&gt;.<br /> <br /> == See Also ==<br /> <br /> {{AMC10 box|year=2012|ab=A|num-b=18|num-a=20}}<br /> {{AMC12 box|year=2012|ab=A|num-b=12|num-a=14}}<br /> <br /> [[Category:Introductory Algebra Problems]]<br /> {{MAA Notice}}</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=Ceva%27s_Theorem&diff=129028 Ceva's Theorem 2020-07-24T06:35:20Z <p>Jimy: /* Proof */</p> <hr /> <div>'''Ceva's Theorem''' is a criterion for the [[concurrence]] of [[cevian]]s in a [[triangle]].<br /> <br /> <br /> == Statement ==<br /> <br /> [[Image:Ceva1.PNG|thumb|right]]<br /> Let &lt;math&gt;ABC &lt;/math&gt; be a triangle, and let &lt;math&gt;D, E, F &lt;/math&gt; be points on lines &lt;math&gt;BC, CA, AB &lt;/math&gt;, respectively. Lines &lt;math&gt;AD, BE, CF &lt;/math&gt; are [[concurrent]] if and only if<br /> &lt;br&gt;&lt;center&gt;<br /> &lt;math&gt;\frac{BD}{DC} \cdot \frac{CE}{EA}\cdot \frac{AF}{FB} = 1 &lt;/math&gt;,<br /> &lt;/center&gt;&lt;br&gt;<br /> where lengths are [[directed segments | directed]]. This also works for the [[reciprocal]] of each of the ratios, as the reciprocal of &lt;math&gt;1&lt;/math&gt; is &lt;math&gt;1&lt;/math&gt;.<br /> <br /> <br /> (Note that the cevians do not necessarily lie within the triangle, although they do in this diagram.)<br /> <br /> <br /> The proof using [[Routh's Theorem]] is extremely trivial, so we will not include it.<br /> <br /> == Proof ==<br /> <br /> We will use the notation &lt;math&gt;[ABC] &lt;/math&gt; to denote the area of a triangle with vertices &lt;math&gt;A,B,C &lt;/math&gt;.<br /> <br /> First, suppose &lt;math&gt;AD, BE, CF &lt;/math&gt; meet at a point &lt;math&gt;X &lt;/math&gt;. We note that triangles &lt;math&gt;ABD, ADC &lt;/math&gt; have the same altitude to line &lt;math&gt;BC &lt;/math&gt;, but bases &lt;math&gt;BD &lt;/math&gt; and &lt;math&gt;DC &lt;/math&gt;. It follows that &lt;math&gt; \frac {BD}{DC} = \frac{[ABD]}{[ADC]} &lt;/math&gt;. The same is true for triangles &lt;math&gt;XBD, XDC &lt;/math&gt;, so <br /> <br /> &lt;center&gt;&lt;math&gt; \frac{BD}{DC} = \frac{[ABD]}{[ADC]} = \frac{[XBD]}{[XDC]} = \frac{[ABD]- [XBD]}{[ADC]-[XDC]} = \frac{[ABX]}{[AXC]} &lt;/math&gt;. &lt;/center&gt;<br /> Similarly, &lt;math&gt; \frac{CE}{EA} = \frac{[BCX]}{[BXA]} &lt;/math&gt; and &lt;math&gt; \frac{AF}{FB} = \frac{[CAX]}{[CXB]} &lt;/math&gt;,<br /> so<br /> &lt;center&gt;<br /> &lt;math&gt; \frac{BD}{DC} \cdot \frac{CE}{EA} \cdot \frac{AF}{FB} = \frac{[ABX]}{[AXC]} \cdot \frac{[BCX]}{[BXA]} \cdot \frac{[CAX]}{[CXB]} = 1 &lt;/math&gt;.<br /> &lt;/center&gt;<br /> <br /> Now, suppose &lt;math&gt;D, E,F &lt;/math&gt; satisfy Ceva's criterion, and suppose &lt;math&gt;AD, BE &lt;/math&gt; intersect at &lt;math&gt;X &lt;/math&gt;. Suppose the line &lt;math&gt;CX &lt;/math&gt; intersects line &lt;math&gt;AB &lt;/math&gt; at &lt;math&gt;F' &lt;/math&gt;. We have proven that &lt;math&gt;F' &lt;/math&gt; must satisfy Ceva's criterion. This means that &lt;center&gt;&lt;math&gt; \frac{AF'}{F'B} = \frac{AF}{FB} &lt;/math&gt;, &lt;/center&gt; so &lt;center&gt;&lt;math&gt;F' = F &lt;/math&gt;, &lt;/center&gt; and line &lt;math&gt;CF &lt;/math&gt; concurs with &lt;math&gt;AD &lt;/math&gt; and &lt;math&gt;BE &lt;/math&gt;. {{Halmos}}<br /> <br /> ==Proof by [[Barycentric coordinates]]==<br /> <br /> Since &lt;math&gt;D\in BC&lt;/math&gt;, we can write its coordinates as &lt;math&gt;(0,d,1-d)&lt;/math&gt;. The equation of line &lt;math&gt;AD&lt;/math&gt; is then &lt;math&gt;z=\frac{1-d}{d}y&lt;/math&gt;. <br /> <br /> Similarly, since &lt;math&gt;E=(1-e,0,e)&lt;/math&gt;, and &lt;math&gt;F=(f,1-f,0)&lt;/math&gt;, we can see that the equations of &lt;math&gt;BE&lt;/math&gt; and &lt;math&gt;CF&lt;/math&gt; respectively are &lt;math&gt;x=\frac{1-e}{e}z&lt;/math&gt; and &lt;math&gt;y=\frac{1-f}{f}x&lt;/math&gt;<br /> <br /> [[Multiplying]] the three together yields the solution to the equation:<br /> <br /> &lt;math&gt;xyz=\frac{1-e}{e}\cdot{z}\cdot\frac{1-f}{f}\cdot{x}\cdot\frac{1-d}{d}y&lt;/math&gt;<br /> <br /> Dividing by &lt;math&gt;xyz&lt;/math&gt; yields:<br /> <br /> <br /> &lt;math&gt;1=\frac{1-e}{e}\cdot\frac{1-f}{f}\cdot\frac{1-d}{d}&lt;/math&gt;, which is equivalent to Ceva's theorem<br /> <br /> QED<br /> <br /> == Trigonometric Form ==<br /> <br /> The [[trig | trigonometric]] form of Ceva's Theorem (Trig Ceva) states that cevians &lt;math&gt;AD,BE,CF&lt;/math&gt; concur if and only if<br /> &lt;center&gt;<br /> &lt;math&gt; \frac{\sin BAD}{\sin DAC} \cdot \frac{\sin CBE}{\sin EBA} \cdot \frac{\sin ACF}{\sin FCB} = 1.&lt;/math&gt;<br /> &lt;/center&gt;<br /> <br /> === Proof ===<br /> <br /> First, suppose &lt;math&gt;AD, BE, CF &lt;/math&gt; concur at a point &lt;math&gt;X &lt;/math&gt;. We note that<br /> &lt;center&gt;<br /> &lt;math&gt; \frac{[BAX]}{[XAC]} = \frac{ \frac{1}{2}AB \cdot AX \cdot \sin BAX}{ \frac{1}{2}AX \cdot AC \cdot \sin XAC} = \frac{AB \cdot \sin BAD}{AC \cdot \sin DAC} &lt;/math&gt;, &lt;/center&gt;<br /> and similarly,<br /> &lt;center&gt;<br /> &lt;math&gt; \frac{[CBX]}{[XBA]} = \frac{BC \cdot \sin CBE}{BA \cdot \sin EBA} ;\; \frac{[ACX]}{[XCB]} = \frac{CA \cdot \sin ACF}{CB \cdot \sin FCB} &lt;/math&gt;. &lt;/center&gt;<br /> It follows that<br /> &lt;center&gt;<br /> &lt;math&gt; \frac{\sin BAD}{\sin DAC} \cdot \frac{\sin CBE}{\sin EBA} \cdot \frac{\sin ACF}{\sin FCB} = \frac{AB \cdot \sin BAD}{AC \cdot \sin DAC} \cdot \frac{BC \cdot \sin CBE}{BA \cdot \sin EBA} \cdot \frac{CA \cdot \sin ACF}{CB \cdot \sin FCB} &lt;/math&gt; &lt;br&gt; &lt;br&gt; &lt;math&gt; \qquad = \frac{[BAX]}{[XAC]} \cdot \frac{[CBX]}{[XBA]} \cdot \frac{[ACX]}{[XCB]} = 1 &lt;/math&gt;.<br /> &lt;/center&gt;<br /> <br /> Here, sign is irrelevant, as we may interpret the sines of [[directed angles]] mod &lt;math&gt;\pi &lt;/math&gt; to be either positive or negative.<br /> <br /> The converse follows by an argument almost identical to that used for the first form of Ceva's Theorem. {{Halmos}}<br /> <br /> == Problems ==<br /> ===Introductory===<br /> *Suppose &lt;math&gt;AB, AC&lt;/math&gt;, and &lt;math&gt;BC&lt;/math&gt; have lengths &lt;math&gt;13, 14&lt;/math&gt;, and &lt;math&gt;15&lt;/math&gt;, respectively. If &lt;math&gt;\frac{AF}{FB} = \frac{2}{5}&lt;/math&gt; and &lt;math&gt;\frac{CE}{EA} = \frac{5}{8}&lt;/math&gt;, find &lt;math&gt;BD&lt;/math&gt; and &lt;math&gt;DC&lt;/math&gt;. ([[Ceva's Theorem/Problems|Source]])<br /> <br /> ===Intermediate===<br /> *In &lt;math&gt;\Delta ABC, AD, BE, CF&lt;/math&gt; are concurrent lines. &lt;math&gt;P, Q, R&lt;/math&gt; are points on &lt;math&gt;EF, FD, DE&lt;/math&gt; such that &lt;math&gt;DP, EQ, FR&lt;/math&gt; are concurrent. Prove that (using ''plane geometry'') &lt;math&gt;AP, BQ, CR&lt;/math&gt; are concurrent. (&lt;url&gt;viewtopic.php?f=151&amp;t=543574 &lt;/url&gt;)<br /> <br /> == See also ==<br /> * [[Stewart's Theorem]]<br /> * [[Menelaus' Theorem]]<br /> <br /> [[Category:Geometry]]<br /> <br /> [[Category:Theorems]]</div> Jimy https://artofproblemsolving.com/wiki/index.php?title=1985_AJHSME_Problems/Problem_1&diff=122858 1985 AJHSME Problems/Problem 1 2020-05-23T11:00:54Z <p>Jimy: /* Solution */</p> <hr /> <div>==Problem==<br /> <br /> &lt;math&gt;\frac{3\times 5}{9\times 11}\times \frac{7\times 9\times 11}{3\times 5\times 7}=&lt;/math&gt;<br /> <br /> &lt;math&gt;\text{(A)}\ 1 \qquad \text{(B)}\ 0 \qquad \text{(C)}\ 49 \qquad \text{(D)}\ \frac{1}{49} \qquad \text{(E)}\ 50&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Noticing that multiplying and dividing by the same number is the equivalent of multiplying (or dividing) by &lt;math&gt;1&lt;/math&gt;, we can rearrange the numbers in the numerator and the denominator ([[Commutative property|commutative property of multiplication]]) so that it looks like &lt;cmath&gt;\frac{3}{3} \times \frac{5}{5} \times \frac{7}{7} \times \frac{9}{9} \times \frac{11}{11}&lt;/cmath&gt;<br /> <br /> Notice that each number is still there, and nothing has been changed - other than the order.<br /> <br /> Finally, since all of the fractions are equal to one, we have &lt;math&gt;1\times1\times1\times1\times1&lt;/math&gt;, which is equal to &lt;math&gt;1&lt;/math&gt;.<br /> <br /> Thus, &lt;math&gt;\boxed{\text{A}}&lt;/math&gt; is the answer.<br /> <br /> ==Solution 2 (Brute force)==<br /> <br /> If you want to multiply it out, then it would be &lt;cmath&gt;\frac{15}{99} \times \frac{693}{105}&lt;/cmath&gt;.<br /> <br /> That would be &lt;cmath&gt;\frac{10395}{10395}&lt;/cmath&gt;, which is 1. Therefore, the answer is &lt;math&gt;\boxed{\text{A}}&lt;/math&gt;<br /> <br /> ==See Also==<br /> <br /> {{AJHSME box|year=1985|before=First &lt;br&gt; Question|num-a=2}}<br /> <br /> [[Category:Introductory Algebra Problems]]<br /> <br /> <br /> {{MAA Notice}}</div> Jimy