https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Mysteryguy6647&feedformat=atom AoPS Wiki - User contributions [en] 2021-11-29T16:12:32Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&diff=130652 2020 AIME II Problems/Problem 14 2020-08-05T08:08:32Z <p>Mysteryguy6647: /* Solution 2 (Official MAA) */</p> <hr /> <div>==Problem==<br /> For real number &lt;math&gt;x&lt;/math&gt; let &lt;math&gt;\lfloor x\rfloor&lt;/math&gt; be the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;, and define &lt;math&gt;\{x\} = x - \lfloor x \rfloor&lt;/math&gt; to be the fractional part of &lt;math&gt;x&lt;/math&gt;. For example, &lt;math&gt;\{3\} = 0&lt;/math&gt; and &lt;math&gt;\{4.56\} = 0.56&lt;/math&gt;. Define &lt;math&gt;f(x)=x\{x\}&lt;/math&gt;, and let &lt;math&gt;N&lt;/math&gt; be the number of real-valued solutions to the equation &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; for &lt;math&gt;0\leq x\leq 2020&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> It's not too hard to see that, &lt;math&gt;N&lt;/math&gt; is<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> .&lt;/cmath&gt;<br /> One can see an easy combinatorical argument exists which is the official solution, but I will present another solution here for the sake of variety.<br /> <br /> Applying algebraic manipulation and the hockey-stick identity &lt;math&gt;3&lt;/math&gt; times gives<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \binom{2021-x}{2}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\binom{2005}{3}<br /> &lt;/cmath&gt;<br /> <br /> ==Solution 2==<br /> <br /> To solve &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;, we need to solve &lt;math&gt;f(x) = y&lt;/math&gt; where &lt;math&gt;f(f(y))=17&lt;/math&gt;, and to solve that we need to solve &lt;math&gt;f(y) = z&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt;.<br /> <br /> It is clear to see for some integer &lt;math&gt;a \geq 17&lt;/math&gt; there is exactly one value of &lt;math&gt;z&lt;/math&gt; in the interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt; To understand this, imagine the graph of &lt;math&gt;f(z)&lt;/math&gt; on the interval &lt;math&gt;[a, a+1)&lt;/math&gt; The graph starts at &lt;math&gt;0&lt;/math&gt;, is continuous and increasing, and approaches &lt;math&gt;a+1&lt;/math&gt;. So as long as &lt;math&gt;a+1 &gt; 17&lt;/math&gt;, there will be a solution for &lt;math&gt;z&lt;/math&gt; in the interval.<br /> <br /> Using this logic, we can find the number of solutions to &lt;math&gt;f(x) = y&lt;/math&gt;. For every interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;a \geq \left \lfloor{y}\right \rfloor &lt;/math&gt; there will be one solution for x in that interval. However, the question states &lt;math&gt;0 \leq x \leq 2020&lt;/math&gt;, but because &lt;math&gt;x=2020&lt;/math&gt; doesn't work we can change it to &lt;math&gt;0 \leq x &lt; 2020&lt;/math&gt;. Therefore, &lt;math&gt;\left \lfloor{y}\right \rfloor \leq a \leq 2019&lt;/math&gt;, and there are &lt;math&gt;2020 - \left \lfloor{y}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(x) = y&lt;/math&gt;.<br /> <br /> We can solve &lt;math&gt;f(y) = z&lt;/math&gt; similarly. &lt;math&gt;0 \leq y &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;x&lt;/math&gt;, so there are &lt;math&gt;2020 - \left \lfloor{z}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(y) = z&lt;/math&gt;, and &lt;math&gt;0 \leq z &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;y&lt;/math&gt;.<br /> <br /> Going back to &lt;math&gt;f(z) = 17&lt;/math&gt;, there is a single solution for z in the interval &lt;math&gt;[a, a+1)&lt;/math&gt;, where &lt;math&gt;17 \leq a \leq 2019&lt;/math&gt;. (We now have an upper bound for &lt;math&gt;a&lt;/math&gt; because we know &lt;math&gt;z &lt; 2020&lt;/math&gt;.) There are &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;z&lt;/math&gt;, and the floors of these solutions create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;<br /> <br /> Lets first look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;. Then &lt;math&gt;f(y) = z&lt;/math&gt; would have &lt;math&gt;2003&lt;/math&gt; solutions, and the floors of these solutions would also create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;.<br /> <br /> If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 17&lt;/math&gt;, there would be &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;f(x) = y&lt;/math&gt;. If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;2002&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on. So for the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;, there will be &lt;math&gt;2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;<br /> <br /> If we now look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;\binom{2003}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;. If we looked at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 19&lt;/math&gt;, there would be &lt;math&gt;\binom{2002}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on.<br /> <br /> The total number of solutions to &lt;math&gt;x&lt;/math&gt; is &lt;math&gt;\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}&lt;/math&gt;. Using the hockey stick theorem, we see this equals &lt;math&gt;\binom{2005}{3}&lt;/math&gt;, and when we take the remainder of that number when divided by &lt;math&gt;1000&lt;/math&gt;, we get the answer, &lt;math&gt;\boxed{10}&lt;/math&gt;<br /> <br /> ~aragornmf<br /> <br /> ==Solution 3 (Official MAA)==<br /> For any nonnegative integer &lt;math&gt;n&lt;/math&gt;, the function &lt;math&gt;f&lt;/math&gt; increases on the interval &lt;math&gt;[n,n+1)&lt;/math&gt;, with &lt;math&gt;f(n)=0&lt;/math&gt; and &lt;math&gt;f(x)&lt;n+1&lt;/math&gt; for every &lt;math&gt;x&lt;/math&gt; in this interval. On this interval &lt;math&gt;f(x)=x(x-n)&lt;/math&gt;, which takes on every real value in the interval &lt;math&gt;[0,n+1)&lt;/math&gt; exactly once. Thus for each nonnegative real number &lt;math&gt;y&lt;/math&gt;, the equation &lt;math&gt;f(x) = y&lt;/math&gt; has exactly one solution &lt;math&gt;x \in [n, n+1)&lt;/math&gt; for every &lt;math&gt;n \ge \lfloor y \rfloor&lt;/math&gt;.<br /> <br /> For each integer &lt;math&gt;a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor x\rfloor=a&lt;/math&gt; such that &lt;math&gt;f(x)=17&lt;/math&gt;; likewise for each integer &lt;math&gt;b\geq a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(x)\rfloor=a&lt;/math&gt; and &lt;math&gt;\lfloor x\rfloor=b&lt;/math&gt; such that &lt;math&gt;f(f(x))=17&lt;/math&gt;. Finally, for each integer &lt;math&gt;c \ge b \ge a \ge 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(f(x)) \rfloor = a&lt;/math&gt;, &lt;math&gt;\lfloor f(x)\rfloor=b&lt;/math&gt;, and &lt;math&gt;\lfloor x\rfloor=c&lt;/math&gt; such that &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;.<br /> <br /> Thus &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; has exactly one solution &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;0\leq x\leq 2020&lt;/math&gt; for each triple of integers &lt;math&gt;(a,b,c)&lt;/math&gt; with &lt;math&gt;17\leq a\leq b\leq c&lt;2020&lt;/math&gt;, noting that &lt;math&gt;x=2020&lt;/math&gt; is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of &lt;math&gt;2003&lt;/math&gt; integers &lt;math&gt;\{17,18,19,\ldots,2019\}&lt;/math&gt;, which can be selected in &lt;math&gt;\binom{2005}3&lt;/math&gt; ways. Thus &lt;cmath&gt;N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/bz5N-jI2e0U?t=515<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=13|num-a=15}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&diff=130651 2020 AIME II Problems/Problem 14 2020-08-05T08:08:17Z <p>Mysteryguy6647: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> For real number &lt;math&gt;x&lt;/math&gt; let &lt;math&gt;\lfloor x\rfloor&lt;/math&gt; be the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;, and define &lt;math&gt;\{x\} = x - \lfloor x \rfloor&lt;/math&gt; to be the fractional part of &lt;math&gt;x&lt;/math&gt;. For example, &lt;math&gt;\{3\} = 0&lt;/math&gt; and &lt;math&gt;\{4.56\} = 0.56&lt;/math&gt;. Define &lt;math&gt;f(x)=x\{x\}&lt;/math&gt;, and let &lt;math&gt;N&lt;/math&gt; be the number of real-valued solutions to the equation &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; for &lt;math&gt;0\leq x\leq 2020&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> It's not too hard to see that, &lt;math&gt;N&lt;/math&gt; is<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> .&lt;/cmath&gt;<br /> One can see an easy combinatorical argument exists which is the official solution, but I will present another solution here for the sake of variety.<br /> <br /> Applying algebraic manipulation and the hockey-stick identity &lt;math&gt;3&lt;/math&gt; times gives<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \binom{2021-x}{2}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\binom{2005}{3}<br /> &lt;/cmath&gt;<br /> <br /> ==Solution 2==<br /> <br /> To solve &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;, we need to solve &lt;math&gt;f(x) = y&lt;/math&gt; where &lt;math&gt;f(f(y))=17&lt;/math&gt;, and to solve that we need to solve &lt;math&gt;f(y) = z&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt;.<br /> <br /> It is clear to see for some integer &lt;math&gt;a \geq 17&lt;/math&gt; there is exactly one value of &lt;math&gt;z&lt;/math&gt; in the interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt; To understand this, imagine the graph of &lt;math&gt;f(z)&lt;/math&gt; on the interval &lt;math&gt;[a, a+1)&lt;/math&gt; The graph starts at &lt;math&gt;0&lt;/math&gt;, is continuous and increasing, and approaches &lt;math&gt;a+1&lt;/math&gt;. So as long as &lt;math&gt;a+1 &gt; 17&lt;/math&gt;, there will be a solution for &lt;math&gt;z&lt;/math&gt; in the interval.<br /> <br /> Using this logic, we can find the number of solutions to &lt;math&gt;f(x) = y&lt;/math&gt;. For every interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;a \geq \left \lfloor{y}\right \rfloor &lt;/math&gt; there will be one solution for x in that interval. However, the question states &lt;math&gt;0 \leq x \leq 2020&lt;/math&gt;, but because &lt;math&gt;x=2020&lt;/math&gt; doesn't work we can change it to &lt;math&gt;0 \leq x &lt; 2020&lt;/math&gt;. Therefore, &lt;math&gt;\left \lfloor{y}\right \rfloor \leq a \leq 2019&lt;/math&gt;, and there are &lt;math&gt;2020 - \left \lfloor{y}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(x) = y&lt;/math&gt;.<br /> <br /> We can solve &lt;math&gt;f(y) = z&lt;/math&gt; similarly. &lt;math&gt;0 \leq y &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;x&lt;/math&gt;, so there are &lt;math&gt;2020 - \left \lfloor{z}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(y) = z&lt;/math&gt;, and &lt;math&gt;0 \leq z &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;y&lt;/math&gt;.<br /> <br /> Going back to &lt;math&gt;f(z) = 17&lt;/math&gt;, there is a single solution for z in the interval &lt;math&gt;[a, a+1)&lt;/math&gt;, where &lt;math&gt;17 \leq a \leq 2019&lt;/math&gt;. (We now have an upper bound for &lt;math&gt;a&lt;/math&gt; because we know &lt;math&gt;z &lt; 2020&lt;/math&gt;.) There are &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;z&lt;/math&gt;, and the floors of these solutions create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;<br /> <br /> Lets first look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;. Then &lt;math&gt;f(y) = z&lt;/math&gt; would have &lt;math&gt;2003&lt;/math&gt; solutions, and the floors of these solutions would also create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;.<br /> <br /> If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 17&lt;/math&gt;, there would be &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;f(x) = y&lt;/math&gt;. If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;2002&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on. So for the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;, there will be &lt;math&gt;2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;<br /> <br /> If we now look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;\binom{2003}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;. If we looked at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 19&lt;/math&gt;, there would be &lt;math&gt;\binom{2002}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on.<br /> <br /> The total number of solutions to &lt;math&gt;x&lt;/math&gt; is &lt;math&gt;\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}&lt;/math&gt;. Using the hockey stick theorem, we see this equals &lt;math&gt;\binom{2005}{3}&lt;/math&gt;, and when we take the remainder of that number when divided by &lt;math&gt;1000&lt;/math&gt;, we get the answer, &lt;math&gt;\boxed{10}&lt;/math&gt;<br /> <br /> ~aragornmf<br /> <br /> ==Solution 2 (Official MAA)==<br /> For any nonnegative integer &lt;math&gt;n&lt;/math&gt;, the function &lt;math&gt;f&lt;/math&gt; increases on the interval &lt;math&gt;[n,n+1)&lt;/math&gt;, with &lt;math&gt;f(n)=0&lt;/math&gt; and &lt;math&gt;f(x)&lt;n+1&lt;/math&gt; for every &lt;math&gt;x&lt;/math&gt; in this interval. On this interval &lt;math&gt;f(x)=x(x-n)&lt;/math&gt;, which takes on every real value in the interval &lt;math&gt;[0,n+1)&lt;/math&gt; exactly once. Thus for each nonnegative real number &lt;math&gt;y&lt;/math&gt;, the equation &lt;math&gt;f(x) = y&lt;/math&gt; has exactly one solution &lt;math&gt;x \in [n, n+1)&lt;/math&gt; for every &lt;math&gt;n \ge \lfloor y \rfloor&lt;/math&gt;.<br /> <br /> For each integer &lt;math&gt;a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor x\rfloor=a&lt;/math&gt; such that &lt;math&gt;f(x)=17&lt;/math&gt;; likewise for each integer &lt;math&gt;b\geq a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(x)\rfloor=a&lt;/math&gt; and &lt;math&gt;\lfloor x\rfloor=b&lt;/math&gt; such that &lt;math&gt;f(f(x))=17&lt;/math&gt;. Finally, for each integer &lt;math&gt;c \ge b \ge a \ge 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(f(x)) \rfloor = a&lt;/math&gt;, &lt;math&gt;\lfloor f(x)\rfloor=b&lt;/math&gt;, and &lt;math&gt;\lfloor x\rfloor=c&lt;/math&gt; such that &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;.<br /> <br /> Thus &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; has exactly one solution &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;0\leq x\leq 2020&lt;/math&gt; for each triple of integers &lt;math&gt;(a,b,c)&lt;/math&gt; with &lt;math&gt;17\leq a\leq b\leq c&lt;2020&lt;/math&gt;, noting that &lt;math&gt;x=2020&lt;/math&gt; is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of &lt;math&gt;2003&lt;/math&gt; integers &lt;math&gt;\{17,18,19,\ldots,2019\}&lt;/math&gt;, which can be selected in &lt;math&gt;\binom{2005}3&lt;/math&gt; ways. Thus &lt;cmath&gt;N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/bz5N-jI2e0U?t=515<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=13|num-a=15}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&diff=130650 2020 AIME II Problems/Problem 14 2020-08-05T08:07:06Z <p>Mysteryguy6647: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> For real number &lt;math&gt;x&lt;/math&gt; let &lt;math&gt;\lfloor x\rfloor&lt;/math&gt; be the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;, and define &lt;math&gt;\{x\} = x - \lfloor x \rfloor&lt;/math&gt; to be the fractional part of &lt;math&gt;x&lt;/math&gt;. For example, &lt;math&gt;\{3\} = 0&lt;/math&gt; and &lt;math&gt;\{4.56\} = 0.56&lt;/math&gt;. Define &lt;math&gt;f(x)=x\{x\}&lt;/math&gt;, and let &lt;math&gt;N&lt;/math&gt; be the number of real-valued solutions to the equation &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; for &lt;math&gt;0\leq x\leq 2020&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> .&lt;/cmath&gt;<br /> A combinatorical argument exists which is the official solution, but I will present another here for the sake of variety.<br /> <br /> Applying algebraic manipulation and the hockey-stick identity &lt;math&gt;3&lt;/math&gt; times gives<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \binom{2021-x}{2}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\binom{2005}{3}<br /> &lt;/cmath&gt;<br /> <br /> ==Solution 2==<br /> <br /> To solve &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;, we need to solve &lt;math&gt;f(x) = y&lt;/math&gt; where &lt;math&gt;f(f(y))=17&lt;/math&gt;, and to solve that we need to solve &lt;math&gt;f(y) = z&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt;.<br /> <br /> It is clear to see for some integer &lt;math&gt;a \geq 17&lt;/math&gt; there is exactly one value of &lt;math&gt;z&lt;/math&gt; in the interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt; To understand this, imagine the graph of &lt;math&gt;f(z)&lt;/math&gt; on the interval &lt;math&gt;[a, a+1)&lt;/math&gt; The graph starts at &lt;math&gt;0&lt;/math&gt;, is continuous and increasing, and approaches &lt;math&gt;a+1&lt;/math&gt;. So as long as &lt;math&gt;a+1 &gt; 17&lt;/math&gt;, there will be a solution for &lt;math&gt;z&lt;/math&gt; in the interval.<br /> <br /> Using this logic, we can find the number of solutions to &lt;math&gt;f(x) = y&lt;/math&gt;. For every interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;a \geq \left \lfloor{y}\right \rfloor &lt;/math&gt; there will be one solution for x in that interval. However, the question states &lt;math&gt;0 \leq x \leq 2020&lt;/math&gt;, but because &lt;math&gt;x=2020&lt;/math&gt; doesn't work we can change it to &lt;math&gt;0 \leq x &lt; 2020&lt;/math&gt;. Therefore, &lt;math&gt;\left \lfloor{y}\right \rfloor \leq a \leq 2019&lt;/math&gt;, and there are &lt;math&gt;2020 - \left \lfloor{y}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(x) = y&lt;/math&gt;.<br /> <br /> We can solve &lt;math&gt;f(y) = z&lt;/math&gt; similarly. &lt;math&gt;0 \leq y &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;x&lt;/math&gt;, so there are &lt;math&gt;2020 - \left \lfloor{z}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(y) = z&lt;/math&gt;, and &lt;math&gt;0 \leq z &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;y&lt;/math&gt;.<br /> <br /> Going back to &lt;math&gt;f(z) = 17&lt;/math&gt;, there is a single solution for z in the interval &lt;math&gt;[a, a+1)&lt;/math&gt;, where &lt;math&gt;17 \leq a \leq 2019&lt;/math&gt;. (We now have an upper bound for &lt;math&gt;a&lt;/math&gt; because we know &lt;math&gt;z &lt; 2020&lt;/math&gt;.) There are &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;z&lt;/math&gt;, and the floors of these solutions create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;<br /> <br /> Lets first look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;. Then &lt;math&gt;f(y) = z&lt;/math&gt; would have &lt;math&gt;2003&lt;/math&gt; solutions, and the floors of these solutions would also create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;.<br /> <br /> If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 17&lt;/math&gt;, there would be &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;f(x) = y&lt;/math&gt;. If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;2002&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on. So for the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;, there will be &lt;math&gt;2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;<br /> <br /> If we now look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;\binom{2003}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;. If we looked at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 19&lt;/math&gt;, there would be &lt;math&gt;\binom{2002}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on.<br /> <br /> The total number of solutions to &lt;math&gt;x&lt;/math&gt; is &lt;math&gt;\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}&lt;/math&gt;. Using the hockey stick theorem, we see this equals &lt;math&gt;\binom{2005}{3}&lt;/math&gt;, and when we take the remainder of that number when divided by &lt;math&gt;1000&lt;/math&gt;, we get the answer, &lt;math&gt;\boxed{10}&lt;/math&gt;<br /> <br /> ~aragornmf<br /> <br /> ==Solution 2 (Official MAA)==<br /> For any nonnegative integer &lt;math&gt;n&lt;/math&gt;, the function &lt;math&gt;f&lt;/math&gt; increases on the interval &lt;math&gt;[n,n+1)&lt;/math&gt;, with &lt;math&gt;f(n)=0&lt;/math&gt; and &lt;math&gt;f(x)&lt;n+1&lt;/math&gt; for every &lt;math&gt;x&lt;/math&gt; in this interval. On this interval &lt;math&gt;f(x)=x(x-n)&lt;/math&gt;, which takes on every real value in the interval &lt;math&gt;[0,n+1)&lt;/math&gt; exactly once. Thus for each nonnegative real number &lt;math&gt;y&lt;/math&gt;, the equation &lt;math&gt;f(x) = y&lt;/math&gt; has exactly one solution &lt;math&gt;x \in [n, n+1)&lt;/math&gt; for every &lt;math&gt;n \ge \lfloor y \rfloor&lt;/math&gt;.<br /> <br /> For each integer &lt;math&gt;a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor x\rfloor=a&lt;/math&gt; such that &lt;math&gt;f(x)=17&lt;/math&gt;; likewise for each integer &lt;math&gt;b\geq a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(x)\rfloor=a&lt;/math&gt; and &lt;math&gt;\lfloor x\rfloor=b&lt;/math&gt; such that &lt;math&gt;f(f(x))=17&lt;/math&gt;. Finally, for each integer &lt;math&gt;c \ge b \ge a \ge 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(f(x)) \rfloor = a&lt;/math&gt;, &lt;math&gt;\lfloor f(x)\rfloor=b&lt;/math&gt;, and &lt;math&gt;\lfloor x\rfloor=c&lt;/math&gt; such that &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;.<br /> <br /> Thus &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; has exactly one solution &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;0\leq x\leq 2020&lt;/math&gt; for each triple of integers &lt;math&gt;(a,b,c)&lt;/math&gt; with &lt;math&gt;17\leq a\leq b\leq c&lt;2020&lt;/math&gt;, noting that &lt;math&gt;x=2020&lt;/math&gt; is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of &lt;math&gt;2003&lt;/math&gt; integers &lt;math&gt;\{17,18,19,\ldots,2019\}&lt;/math&gt;, which can be selected in &lt;math&gt;\binom{2005}3&lt;/math&gt; ways. Thus &lt;cmath&gt;N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/bz5N-jI2e0U?t=515<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=13|num-a=15}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&diff=130649 2020 AIME II Problems/Problem 14 2020-08-05T08:06:38Z <p>Mysteryguy6647: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> For real number &lt;math&gt;x&lt;/math&gt; let &lt;math&gt;\lfloor x\rfloor&lt;/math&gt; be the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;, and define &lt;math&gt;\{x\} = x - \lfloor x \rfloor&lt;/math&gt; to be the fractional part of &lt;math&gt;x&lt;/math&gt;. For example, &lt;math&gt;\{3\} = 0&lt;/math&gt; and &lt;math&gt;\{4.56\} = 0.56&lt;/math&gt;. Define &lt;math&gt;f(x)=x\{x\}&lt;/math&gt;, and let &lt;math&gt;N&lt;/math&gt; be the number of real-valued solutions to the equation &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; for &lt;math&gt;0\leq x\leq 2020&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> .&lt;/cmath&gt;<br /> A combinatorical argument exists which is the official solution, but I will present another here for the sake of variety.<br /> <br /> Applying algebraic manipulation and the hockey-stick identity &lt;math&gt;3&lt;/math&gt; times gives<br /> &lt;cmath&gt;<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\<br /> &lt;/cmath&gt;=\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\<br /> &lt;cmath&gt;<br /> =\sum_{x=17}^{2019} \binom{2021-x}{2}\\<br /> &lt;/cmath&gt;<br /> &lt;cmath&gt;<br /> =\binom{2005}{3}<br /> &lt;/cmath&gt;<br /> \end{align*}<br /> <br /> ==Solution 2==<br /> <br /> To solve &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;, we need to solve &lt;math&gt;f(x) = y&lt;/math&gt; where &lt;math&gt;f(f(y))=17&lt;/math&gt;, and to solve that we need to solve &lt;math&gt;f(y) = z&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt;.<br /> <br /> It is clear to see for some integer &lt;math&gt;a \geq 17&lt;/math&gt; there is exactly one value of &lt;math&gt;z&lt;/math&gt; in the interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt; To understand this, imagine the graph of &lt;math&gt;f(z)&lt;/math&gt; on the interval &lt;math&gt;[a, a+1)&lt;/math&gt; The graph starts at &lt;math&gt;0&lt;/math&gt;, is continuous and increasing, and approaches &lt;math&gt;a+1&lt;/math&gt;. So as long as &lt;math&gt;a+1 &gt; 17&lt;/math&gt;, there will be a solution for &lt;math&gt;z&lt;/math&gt; in the interval.<br /> <br /> Using this logic, we can find the number of solutions to &lt;math&gt;f(x) = y&lt;/math&gt;. For every interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;a \geq \left \lfloor{y}\right \rfloor &lt;/math&gt; there will be one solution for x in that interval. However, the question states &lt;math&gt;0 \leq x \leq 2020&lt;/math&gt;, but because &lt;math&gt;x=2020&lt;/math&gt; doesn't work we can change it to &lt;math&gt;0 \leq x &lt; 2020&lt;/math&gt;. Therefore, &lt;math&gt;\left \lfloor{y}\right \rfloor \leq a \leq 2019&lt;/math&gt;, and there are &lt;math&gt;2020 - \left \lfloor{y}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(x) = y&lt;/math&gt;.<br /> <br /> We can solve &lt;math&gt;f(y) = z&lt;/math&gt; similarly. &lt;math&gt;0 \leq y &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;x&lt;/math&gt;, so there are &lt;math&gt;2020 - \left \lfloor{z}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(y) = z&lt;/math&gt;, and &lt;math&gt;0 \leq z &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;y&lt;/math&gt;.<br /> <br /> Going back to &lt;math&gt;f(z) = 17&lt;/math&gt;, there is a single solution for z in the interval &lt;math&gt;[a, a+1)&lt;/math&gt;, where &lt;math&gt;17 \leq a \leq 2019&lt;/math&gt;. (We now have an upper bound for &lt;math&gt;a&lt;/math&gt; because we know &lt;math&gt;z &lt; 2020&lt;/math&gt;.) There are &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;z&lt;/math&gt;, and the floors of these solutions create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;<br /> <br /> Lets first look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;. Then &lt;math&gt;f(y) = z&lt;/math&gt; would have &lt;math&gt;2003&lt;/math&gt; solutions, and the floors of these solutions would also create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;.<br /> <br /> If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 17&lt;/math&gt;, there would be &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;f(x) = y&lt;/math&gt;. If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;2002&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on. So for the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;, there will be &lt;math&gt;2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;<br /> <br /> If we now look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;\binom{2003}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;. If we looked at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 19&lt;/math&gt;, there would be &lt;math&gt;\binom{2002}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on.<br /> <br /> The total number of solutions to &lt;math&gt;x&lt;/math&gt; is &lt;math&gt;\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}&lt;/math&gt;. Using the hockey stick theorem, we see this equals &lt;math&gt;\binom{2005}{3}&lt;/math&gt;, and when we take the remainder of that number when divided by &lt;math&gt;1000&lt;/math&gt;, we get the answer, &lt;math&gt;\boxed{10}&lt;/math&gt;<br /> <br /> ~aragornmf<br /> <br /> ==Solution 2 (Official MAA)==<br /> For any nonnegative integer &lt;math&gt;n&lt;/math&gt;, the function &lt;math&gt;f&lt;/math&gt; increases on the interval &lt;math&gt;[n,n+1)&lt;/math&gt;, with &lt;math&gt;f(n)=0&lt;/math&gt; and &lt;math&gt;f(x)&lt;n+1&lt;/math&gt; for every &lt;math&gt;x&lt;/math&gt; in this interval. On this interval &lt;math&gt;f(x)=x(x-n)&lt;/math&gt;, which takes on every real value in the interval &lt;math&gt;[0,n+1)&lt;/math&gt; exactly once. Thus for each nonnegative real number &lt;math&gt;y&lt;/math&gt;, the equation &lt;math&gt;f(x) = y&lt;/math&gt; has exactly one solution &lt;math&gt;x \in [n, n+1)&lt;/math&gt; for every &lt;math&gt;n \ge \lfloor y \rfloor&lt;/math&gt;.<br /> <br /> For each integer &lt;math&gt;a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor x\rfloor=a&lt;/math&gt; such that &lt;math&gt;f(x)=17&lt;/math&gt;; likewise for each integer &lt;math&gt;b\geq a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(x)\rfloor=a&lt;/math&gt; and &lt;math&gt;\lfloor x\rfloor=b&lt;/math&gt; such that &lt;math&gt;f(f(x))=17&lt;/math&gt;. Finally, for each integer &lt;math&gt;c \ge b \ge a \ge 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(f(x)) \rfloor = a&lt;/math&gt;, &lt;math&gt;\lfloor f(x)\rfloor=b&lt;/math&gt;, and &lt;math&gt;\lfloor x\rfloor=c&lt;/math&gt; such that &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;.<br /> <br /> Thus &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; has exactly one solution &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;0\leq x\leq 2020&lt;/math&gt; for each triple of integers &lt;math&gt;(a,b,c)&lt;/math&gt; with &lt;math&gt;17\leq a\leq b\leq c&lt;2020&lt;/math&gt;, noting that &lt;math&gt;x=2020&lt;/math&gt; is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of &lt;math&gt;2003&lt;/math&gt; integers &lt;math&gt;\{17,18,19,\ldots,2019\}&lt;/math&gt;, which can be selected in &lt;math&gt;\binom{2005}3&lt;/math&gt; ways. Thus &lt;cmath&gt;N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/bz5N-jI2e0U?t=515<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=13|num-a=15}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&diff=130648 2020 AIME II Problems/Problem 14 2020-08-05T08:05:43Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>==Problem==<br /> For real number &lt;math&gt;x&lt;/math&gt; let &lt;math&gt;\lfloor x\rfloor&lt;/math&gt; be the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;, and define &lt;math&gt;\{x\} = x - \lfloor x \rfloor&lt;/math&gt; to be the fractional part of &lt;math&gt;x&lt;/math&gt;. For example, &lt;math&gt;\{3\} = 0&lt;/math&gt; and &lt;math&gt;\{4.56\} = 0.56&lt;/math&gt;. Define &lt;math&gt;f(x)=x\{x\}&lt;/math&gt;, and let &lt;math&gt;N&lt;/math&gt; be the number of real-valued solutions to the equation &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; for &lt;math&gt;0\leq x\leq 2020&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> $<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> .$<br /> A combinatorical argument exists which is the official solution, but I will present another here for the sake of variety.<br /> <br /> Applying algebraic manipulation and the hockey-stick identity &lt;math&gt;3&lt;/math&gt; times gives<br /> \begin{align*}<br /> \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\<br /> =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\<br /> =\sum_{x=17}^{2019} \binom{2021-x}{2}\\<br /> =\binom{2005}{3}<br /> \end{align*}<br /> ==Solution 2==<br /> <br /> To solve &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;, we need to solve &lt;math&gt;f(x) = y&lt;/math&gt; where &lt;math&gt;f(f(y))=17&lt;/math&gt;, and to solve that we need to solve &lt;math&gt;f(y) = z&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt;.<br /> <br /> It is clear to see for some integer &lt;math&gt;a \geq 17&lt;/math&gt; there is exactly one value of &lt;math&gt;z&lt;/math&gt; in the interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;f(z) = 17&lt;/math&gt; To understand this, imagine the graph of &lt;math&gt;f(z)&lt;/math&gt; on the interval &lt;math&gt;[a, a+1)&lt;/math&gt; The graph starts at &lt;math&gt;0&lt;/math&gt;, is continuous and increasing, and approaches &lt;math&gt;a+1&lt;/math&gt;. So as long as &lt;math&gt;a+1 &gt; 17&lt;/math&gt;, there will be a solution for &lt;math&gt;z&lt;/math&gt; in the interval.<br /> <br /> Using this logic, we can find the number of solutions to &lt;math&gt;f(x) = y&lt;/math&gt;. For every interval &lt;math&gt;[a, a+1)&lt;/math&gt; where &lt;math&gt;a \geq \left \lfloor{y}\right \rfloor &lt;/math&gt; there will be one solution for x in that interval. However, the question states &lt;math&gt;0 \leq x \leq 2020&lt;/math&gt;, but because &lt;math&gt;x=2020&lt;/math&gt; doesn't work we can change it to &lt;math&gt;0 \leq x &lt; 2020&lt;/math&gt;. Therefore, &lt;math&gt;\left \lfloor{y}\right \rfloor \leq a \leq 2019&lt;/math&gt;, and there are &lt;math&gt;2020 - \left \lfloor{y}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(x) = y&lt;/math&gt;.<br /> <br /> We can solve &lt;math&gt;f(y) = z&lt;/math&gt; similarly. &lt;math&gt;0 \leq y &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;x&lt;/math&gt;, so there are &lt;math&gt;2020 - \left \lfloor{z}\right \rfloor&lt;/math&gt; solutions to &lt;math&gt;f(y) = z&lt;/math&gt;, and &lt;math&gt;0 \leq z &lt; 2020&lt;/math&gt; to satisfy the bounds of &lt;math&gt;y&lt;/math&gt;.<br /> <br /> Going back to &lt;math&gt;f(z) = 17&lt;/math&gt;, there is a single solution for z in the interval &lt;math&gt;[a, a+1)&lt;/math&gt;, where &lt;math&gt;17 \leq a \leq 2019&lt;/math&gt;. (We now have an upper bound for &lt;math&gt;a&lt;/math&gt; because we know &lt;math&gt;z &lt; 2020&lt;/math&gt;.) There are &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;z&lt;/math&gt;, and the floors of these solutions create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;<br /> <br /> Lets first look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;. Then &lt;math&gt;f(y) = z&lt;/math&gt; would have &lt;math&gt;2003&lt;/math&gt; solutions, and the floors of these solutions would also create the sequence &lt;math&gt;17, 18, 19, ..., 2018, 2019&lt;/math&gt;.<br /> <br /> If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 17&lt;/math&gt;, there would be &lt;math&gt;2003&lt;/math&gt; solutions for &lt;math&gt;f(x) = y&lt;/math&gt;. If we used the solution of &lt;math&gt;y&lt;/math&gt; where &lt;math&gt;\left \lfloor{y}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;2002&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on. So for the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 17&lt;/math&gt;, there will be &lt;math&gt;2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;<br /> <br /> If we now look at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 18&lt;/math&gt;, there would be &lt;math&gt;\binom{2003}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;. If we looked at the solution of &lt;math&gt;z&lt;/math&gt; where &lt;math&gt;\left \lfloor{z}\right \rfloor = 19&lt;/math&gt;, there would be &lt;math&gt;\binom{2002}{2}&lt;/math&gt; solutions for &lt;math&gt;x&lt;/math&gt;, and so on.<br /> <br /> The total number of solutions to &lt;math&gt;x&lt;/math&gt; is &lt;math&gt;\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}&lt;/math&gt;. Using the hockey stick theorem, we see this equals &lt;math&gt;\binom{2005}{3}&lt;/math&gt;, and when we take the remainder of that number when divided by &lt;math&gt;1000&lt;/math&gt;, we get the answer, &lt;math&gt;\boxed{10}&lt;/math&gt;<br /> <br /> ~aragornmf<br /> <br /> ==Solution 2 (Official MAA)==<br /> For any nonnegative integer &lt;math&gt;n&lt;/math&gt;, the function &lt;math&gt;f&lt;/math&gt; increases on the interval &lt;math&gt;[n,n+1)&lt;/math&gt;, with &lt;math&gt;f(n)=0&lt;/math&gt; and &lt;math&gt;f(x)&lt;n+1&lt;/math&gt; for every &lt;math&gt;x&lt;/math&gt; in this interval. On this interval &lt;math&gt;f(x)=x(x-n)&lt;/math&gt;, which takes on every real value in the interval &lt;math&gt;[0,n+1)&lt;/math&gt; exactly once. Thus for each nonnegative real number &lt;math&gt;y&lt;/math&gt;, the equation &lt;math&gt;f(x) = y&lt;/math&gt; has exactly one solution &lt;math&gt;x \in [n, n+1)&lt;/math&gt; for every &lt;math&gt;n \ge \lfloor y \rfloor&lt;/math&gt;.<br /> <br /> For each integer &lt;math&gt;a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor x\rfloor=a&lt;/math&gt; such that &lt;math&gt;f(x)=17&lt;/math&gt;; likewise for each integer &lt;math&gt;b\geq a\geq 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(x)\rfloor=a&lt;/math&gt; and &lt;math&gt;\lfloor x\rfloor=b&lt;/math&gt; such that &lt;math&gt;f(f(x))=17&lt;/math&gt;. Finally, for each integer &lt;math&gt;c \ge b \ge a \ge 17&lt;/math&gt; there is exactly one &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;\lfloor f(f(x)) \rfloor = a&lt;/math&gt;, &lt;math&gt;\lfloor f(x)\rfloor=b&lt;/math&gt;, and &lt;math&gt;\lfloor x\rfloor=c&lt;/math&gt; such that &lt;math&gt;f(f(f(x)))=17&lt;/math&gt;.<br /> <br /> Thus &lt;math&gt;f(f(f(x)))=17&lt;/math&gt; has exactly one solution &lt;math&gt;x&lt;/math&gt; with &lt;math&gt;0\leq x\leq 2020&lt;/math&gt; for each triple of integers &lt;math&gt;(a,b,c)&lt;/math&gt; with &lt;math&gt;17\leq a\leq b\leq c&lt;2020&lt;/math&gt;, noting that &lt;math&gt;x=2020&lt;/math&gt; is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of &lt;math&gt;2003&lt;/math&gt; integers &lt;math&gt;\{17,18,19,\ldots,2019\}&lt;/math&gt;, which can be selected in &lt;math&gt;\binom{2005}3&lt;/math&gt; ways. Thus &lt;cmath&gt;N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.&lt;/cmath&gt;<br /> <br /> ==Video Solution==<br /> https://youtu.be/bz5N-jI2e0U?t=515<br /> <br /> ==See Also==<br /> {{AIME box|year=2020|n=II|num-b=13|num-a=15}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_13&diff=130092 2018 AIME II Problems/Problem 13 2020-08-01T12:56:39Z <p>Mysteryguy6647: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> <br /> Misha rolls a standard, fair six-sided die until she rolls &lt;math&gt;1-2-3&lt;/math&gt; in that order on three consecutive rolls. The probability that she will roll the die an odd number of times is &lt;math&gt;\dfrac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> ==Solution 0==<br /> Let &lt;math&gt;P_i&lt;/math&gt; be the probability of getting it in an &lt;math&gt;n&lt;/math&gt; number of times. Let &lt;math&gt;x = P_3+P_5+...=1-(P_4+P_6+..)&lt;/math&gt;. It's easy to see that<br /> &lt;cmath&gt;P_{2n+1}=P_{2n}-\frac{P_{2n-2}}{6^3}&lt;/cmath&gt;<br /> for all positive integers &lt;math&gt;n \ge 2&lt;/math&gt;. Summing for &lt;math&gt;n=2,4,...&lt;/math&gt; gives<br /> &lt;cmath&gt;x-\frac{1}{6^3} = \frac{6^3-1}{6^3}(1-x)&lt;/cmath&gt;<br /> &lt;cmath&gt; \implies x = \frac{216}{431} &lt;/cmath&gt;<br /> ==Solution 1==<br /> Let &lt;math&gt;P_{odd}=\frac{m}{n}&lt;/math&gt;, with the subscript indicating an odd number of rolls. Then &lt;math&gt;P_{even}=1-\frac{m}{n}&lt;/math&gt;.<br /> <br /> The ratio of &lt;math&gt;\frac{P_{odd}}{P_{even}}&lt;/math&gt; is just &lt;math&gt;\frac{P_{odd}}{1-P_{odd}}&lt;/math&gt;.<br /> <br /> We see that &lt;math&gt;P_{odd}&lt;/math&gt; is the sum of &lt;math&gt;P_3&lt;/math&gt;,&lt;math&gt;P_5&lt;/math&gt;,&lt;math&gt;P_7&lt;/math&gt;,... , while &lt;math&gt;P_{even}&lt;/math&gt; is the sum of &lt;math&gt;P_4&lt;/math&gt;, &lt;math&gt;P_6&lt;/math&gt;, &lt;math&gt;P_8&lt;/math&gt;,... .<br /> <br /> &lt;math&gt;P_3&lt;/math&gt;, the probability of getting rolls of 1-2-3 in exactly 3 rolls, is obviously &lt;math&gt;\frac{1}{216}&lt;/math&gt;.<br /> <br /> We set this probability of &lt;math&gt;P_3&lt;/math&gt; aside, meaning we totally remove the chance of getting 1-2-3 in 3 rolls. Now the ratio of &lt;math&gt;P_4+P_6+P_8+...&lt;/math&gt; to &lt;math&gt;P_5+P_7+P_9+...&lt;/math&gt; should be equal to the ratio of &lt;math&gt;\frac{P_{odd}}{P_{even}}&lt;/math&gt;, because in this case the 1st roll no longer matters, so we can disregard the very existence of it in counting how many times of rolls, and thus, 4 rolls, 6 rolls, 8 rolls... would become an odd number of rolls (while 5 rolls, 7 rolls, 9 rolls... would become even number of rolls).<br /> <br /> Notice &lt;math&gt;P_4+P_6+P_8+...=P_{even}&lt;/math&gt;, and also &lt;math&gt;P_5+P_7+P_9+...=P_{odd}-P_3=P_{odd}-\frac{1}{216}&lt;/math&gt;<br /> <br /> So we have &lt;math&gt;\frac{P_{even}}{P_{odd}-\frac{1}{216}}=\frac{P_{odd}}{P_{even}}&lt;/math&gt;.<br /> <br /> Finally, we get &lt;math&gt;P_{odd}=\frac{m}{n}=\frac{216}{431}&lt;/math&gt;. <br /> Therefore, &lt;math&gt;m+n = \boxed{647}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> Call the probability you win on a certain toss &lt;math&gt;f_n&lt;/math&gt;, where &lt;math&gt;n&lt;/math&gt; is the toss number.<br /> Obviously, since the sequence has length 3, &lt;math&gt;f_1=0&lt;/math&gt; and &lt;math&gt;f_2=0&lt;/math&gt;.<br /> Additionally, &lt;math&gt;f_3=\left(\frac{1}{6}\right)^3&lt;/math&gt;. We can call this value &lt;math&gt;x&lt;/math&gt;, to keep our further equations looking clean.<br /> We can now write our general form for &lt;math&gt;f&lt;/math&gt; as &lt;math&gt;f_n=x(1-\sum_{i=1}^{n-3}f_i)&lt;/math&gt;. This factors the probability of the last 3 rolls being 1-2-3, and the important probability that the sequence has not been rolled in the past (because then the game would already be over).<br /> Note that &lt;math&gt;\sum_{i=1}^{\infty}f_i=1&lt;/math&gt; since you'll win at some point.<br /> An intermediate step here is figuring out &lt;math&gt;f_n-f_{n+1}&lt;/math&gt;. This is equal to &lt;math&gt;x(1-\sum_{i=1}^{n-3}f_i)-x(1-\sum_{i=1}^{n-2}f_i)=x(\sum_{i=1}^{n-2}f_i-\sum_{i=1}^{n-3}f_i)=xf_{n-2}&lt;/math&gt;.<br /> Adding up all the differences, i.e. &lt;math&gt;\sum_{i=2}^{\infty}(f_{2n-1}-f_{2n})&lt;/math&gt; will give us the amount by which the odds probability exceeds the even probability. Since they sum to 1, that means the odds probability will be half of the difference above one-half. Subbing in our earlier result from the intermediate step, the odd probability is equal to &lt;math&gt;\frac{1}{2}+\frac{1}{2}x\sum_{i=2}^{\infty}f_{2n-3}&lt;/math&gt;.<br /> Another way to find the odd probability is simply summing it up, which turns out to be &lt;math&gt;\sum_{i=1}^{\infty}f_{2n-1}&lt;/math&gt;. Note the infinite sums in both expressions are equal; let's call it &lt;math&gt;P&lt;/math&gt;. Equating them gives &lt;math&gt;\frac{1}{2}+\frac{1}{2}xP=P&lt;/math&gt;, or &lt;math&gt;P=\frac{1}{2-x}&lt;/math&gt;.<br /> Finally, substituting &lt;math&gt;x=\frac{1}{216}&lt;/math&gt;, we find that &lt;math&gt;P=\frac{216}{431}&lt;/math&gt;, giving us a final answer of &lt;math&gt;216 + 431 = \boxed{647}&lt;/math&gt;.<br /> --DanDan0101<br /> <br /> ==Solution 3==<br /> Let &lt;math&gt;S(n)&lt;/math&gt; be the number of strings of length &lt;math&gt;n&lt;/math&gt; containing the digits &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;6&lt;/math&gt; that do not contain the string &lt;math&gt;123&lt;/math&gt;. Then we have &lt;math&gt;S(n) = 6 \cdot S(n-1) - S(n-3)&lt;/math&gt; because we can add any digit to end of a string with length &lt;math&gt;n-1&lt;/math&gt; but we have to subtract all the strings that end in &lt;math&gt;123&lt;/math&gt;. We rewrite this as<br /> &lt;cmath&gt;\begin{align*}<br /> S(n) &amp;= 6 \cdot S(n-1) - S(n-3) \\ &amp;= 6 \cdot (6 \cdot S(n-2) - S(n-4)) - (6 \cdot (S(n-4) - S(n-6)) \\ &amp;= 36 \cdot S(n-2) - 12 \cdot S(n-4) + S(n-6)<br /> \end{align*}&lt;/cmath&gt; We wish to compute &lt;math&gt;P=\sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}}&lt;/math&gt; since the last three rolls are &lt;math&gt;123&lt;/math&gt; for the game to end. Summing over the recursion, we obtain<br /> &lt;cmath&gt;\sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}} =36 \cdot \sum_{n=0}^\infty \frac{S(2n-2)}{6^{2n+3}} - 12 \cdot \sum_{n=0}^\infty \frac{S(2n-4)}{6^{2n+3}}+ \sum_{n=0}^\infty \frac{S(2n-6)}{6^{2n+3}} &lt;/cmath&gt;Now shift the indices so that the inside term is the same:<br /> &lt;cmath&gt;\begin{align*}<br /> \sum_{n=3}^\infty \frac{S(2n)}{6^{2n+3}} &amp;= \frac{36}{6^2} \cdot \sum_{n=2}^\infty \frac{S(2n)}{6^{2n+3}} - \frac{12}{6^4} \cdot \sum_{n=1}^\infty \frac{S(2n)}{6^{2n+3}} + \frac{1}{6^6} \cdot \sum_{n=0}^\infty \frac{S(2n)}{6^{2n+3}} \\ \left(P - \frac{S(0)}{6^3} - \frac{S(2)}{6^5} -\frac{S(4)}{6^7} \right) &amp;= \frac{36}{6^2} \cdot \left( P - \frac{S(0)}{6^3} - \frac{S(2)}{6^5}\right) - \frac{12}{6^4} \cdot \left( P - \frac{S(0)}{6^3} \right) + \frac{1}{6^6} \cdot P <br /> \end{align*}&lt;/cmath&gt;Note that &lt;math&gt;S(0) = 1, S(2) = 36&lt;/math&gt; and &lt;math&gt;S(4) = 6^4 - 2 \cdot 6 = 1284&lt;/math&gt;. Therefore,<br /> &lt;cmath&gt;\begin{align*}<br /> \left(P - \frac{1}{6^3} - \frac{36}{6^5} -\frac{1284}{6^7} \right) = \frac{36}{6^2} \cdot \left( P - \frac{1}{6^3} - \frac{36}{6^5}\right) - \frac{12}{6^4} \cdot \left( P - \frac{1}{6^3} \right) + \frac{1}{6^6} \cdot P <br /> \end{align*}&lt;/cmath&gt;Solving for &lt;math&gt;P&lt;/math&gt;, we obtain &lt;math&gt;P = \frac{216}{431} \implies m+n = \boxed{647}&lt;/math&gt;. <br /> <br /> -Vfire<br /> <br /> ==Solution 4==<br /> Let &lt;math&gt;A=\frac{1}{6} \begin{bmatrix}<br /> 5 &amp; 1 &amp; 0 &amp; 0 \\<br /> 4 &amp; 1 &amp; 1 &amp; 0 \\<br /> 4 &amp; 1 &amp; 0 &amp; 1 \\<br /> 0 &amp; 0 &amp; 0 &amp; 0 \\<br /> \end{bmatrix}&lt;/math&gt;. &lt;math&gt;A&lt;/math&gt; is a transition matrix for the prefix of 1-2-3 matched so far. The state corresponding to a complete match has no outgoing probability mass. The probability that we roll the dice exactly &lt;math&gt;k&lt;/math&gt; times is &lt;math&gt;(A^k)_{1,4}&lt;/math&gt;. Thus the probability that we roll the dice an odd number of times is &lt;math&gt;1-\left(\sum_{k=0}^\infty A^{2k}\right)_{1,4} = 1-\left((I - A^2)^{-1}\right)_{1,4} = \frac{216}{431}&lt;/math&gt;. Thus the answer is &lt;math&gt;216+431=\boxed{647}&lt;/math&gt;.<br /> ==Solution 5 quick cheat ==<br /> Consider it as a contest of Odd and Even. Let &lt;math&gt;P_o&lt;/math&gt; and &lt;math&gt;P_e&lt;/math&gt; be probability that Odd and Even wins, respectively. If we consider every 3 rolls as an atomic action, then we can have a simple solution. If the rolls is 1-2-3, Odd wins; otherwise, Odd and Even switch the odds of winning. Therefore, we have<br /> &lt;cmath&gt; P_o = \frac{1}{216} + \frac{215}{216}P_e&lt;/cmath&gt;<br /> Plug in &lt;math&gt;P_e = 1 - P_o&lt;/math&gt; and we can easily solve for &lt;math&gt;Po=\frac{216}{431}&lt;/math&gt;. <br /> <br /> &lt;math&gt;\boxed{647}&lt;/math&gt;.<br /> <br /> Of course this is not a rigorous solution. I think it works because the requirement is a strict sequence of pure random events.<br /> <br /> -Mathdummy<br /> <br /> ==Solution 6 Elementary Probability ==<br /> Consider it a contest for Odd or Even to win. Let &lt;math&gt;P_o&lt;/math&gt;, &lt;math&gt;P_e&lt;/math&gt; be the winning probabilities respectively. We call Odd is &quot;in position&quot; when a new sequence of 1-2-3 starts at odd position, and likewise, call Even is &quot;in position&quot; when a new sequence starts at even position. Now consider the situation when the first roll is 1. The conditional probability for Odd or Even to eventually win out depends on whose is in position. So let's denote by &lt;math&gt;P_o(1), P_e(1)&lt;/math&gt; the probabilities of Odd and Even winning out, respectively, both when Odd is in position. Remember that the probabilities simply switch if Even is in position. Similarly, after 1-2 is rolled, we denote by &lt;math&gt;P_o(2), P_e(2)&lt;/math&gt; the conditional probabilities of Odd and Even winning out, when Odd is in position.<br /> <br /> Consider the first roll. If it's not a 1, the sequence restart, but Even is now in position; if it's a 1, then Odd's winning probability becomes &lt;math&gt;P_o(1)&lt;/math&gt;. So,<br /> &lt;cmath&gt;P_o = \frac{1}{6}P_o(1) + \frac{5}{6}P_e&lt;/cmath&gt;<br /> In the next roll, there are 3 outcomes. If the roll is 2, then Odd's winning probability becomes &lt;math&gt;P_o(2)&lt;/math&gt;; if the roll is 1, then we stay in the sequence, but Even is now in position, so the probability of Odd winning now becomes P_e(1); if the rolls is any other number, then the sequence restarts, and Odd is still in position. So,<br /> &lt;cmath&gt; P_o(1) = \frac{1}{6}P_o(2) + \frac{1}{6}P_e(1) + \frac{4}{6}P_o&lt;/cmath&gt;<br /> In the next roll after a 1-2 sequence, there are 3 outcomes. If the roll is a 3, Odd wins; if it's a 1, we go back to the state when 1 is just rolled, and Odd is in position; if it's any other number, then the sequence restarts, and Even is in position. So,<br /> &lt;cmath&gt; P_o(2) = \frac{1}{6} + \frac{1}{6}P_o(1) + \frac{4}{6}P_e&lt;/cmath&gt;<br /> <br /> Plug in &lt;math&gt;P_e = 1-P_o&lt;/math&gt; and &lt;math&gt;P_e(1) = 1 - P_o(1)&lt;/math&gt;, we have a 3-equation linear system which is not hard to solve. The final answer is &lt;math&gt;Po=\frac{216}{431}&lt;/math&gt;. &lt;math&gt;\boxed{647}&lt;/math&gt;.<br /> <br /> -Mathdummy<br /> <br /> {{AIME box|year=2018|n=II|num-b=12|num-a=14}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_12&diff=129503 2018 AIME I Problems/Problem 12 2020-07-27T13:39:35Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>==Problem==<br /> For every subset &lt;math&gt;T&lt;/math&gt; of &lt;math&gt;U = \{ 1,2,3,\ldots,18 \}&lt;/math&gt;, let &lt;math&gt;s(T)&lt;/math&gt; be the sum of the elements of &lt;math&gt;T&lt;/math&gt;, with &lt;math&gt;s(\emptyset)&lt;/math&gt; defined to be &lt;math&gt;0&lt;/math&gt;. If &lt;math&gt;T&lt;/math&gt; is chosen at random among all subsets of &lt;math&gt;U&lt;/math&gt;, the probability that &lt;math&gt;s(T)&lt;/math&gt; is divisible by &lt;math&gt;3&lt;/math&gt; is &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Ignore the &lt;math&gt;0&lt;/math&gt;'s because we're gonna multiply &lt;math&gt;\binom{6}{0}+..+\binom{6}{6}=2^6&lt;/math&gt; at the end. Let &lt;math&gt;a&lt;/math&gt; be the &lt;math&gt;1's&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; be the &lt;math&gt;2's&lt;/math&gt;. The key here is that &lt;math&gt;2 \equiv -1 \pmod{3}&lt;/math&gt; so the difference between the number of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> 1. Counted twice because &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; can be switched:<br /> <br /> &lt;math&gt;6a&lt;/math&gt;<br /> <br /> &lt;math&gt;6a,3b&lt;/math&gt;<br /> <br /> &lt;math&gt;5a,2b&lt;/math&gt;<br /> <br /> &lt;math&gt;4a,b&lt;/math&gt;<br /> <br /> &lt;math&gt;3a&lt;/math&gt;<br /> <br /> 2. Counted once:<br /> <br /> &lt;math&gt;6a,6b&lt;/math&gt;<br /> ...<br /> &lt;math&gt;0a,0b&lt;/math&gt;<br /> <br /> By Vandermonde's identity on the second case, this is &lt;math&gt;2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Rewrite the set after mod 3<br /> <br /> 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0<br /> <br /> All 0s can be omitted <br /> <br /> Case 1<br /> No 1 No 2<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 2<br /> &lt;math&gt;222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 3<br /> &lt;math&gt;222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 4<br /> &lt;math&gt;12&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 5<br /> &lt;math&gt;12222&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 6<br /> &lt;math&gt;1122&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 7<br /> &lt;math&gt;1122222&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 8<br /> &lt;math&gt;111&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 9<br /> &lt;math&gt;111222&lt;/math&gt;<br /> &lt;math&gt;20*20=400&lt;/math&gt;<br /> <br /> Case 10<br /> &lt;math&gt;111222222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 11<br /> &lt;math&gt;11112&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 12<br /> &lt;math&gt;11112222&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 13<br /> &lt;math&gt;1111122&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 14<br /> &lt;math&gt;1111122222&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 15<br /> &lt;math&gt;111111&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 16<br /> &lt;math&gt;111111222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 17<br /> &lt;math&gt;111111222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Total &lt;math&gt;1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366&lt;/math&gt;<br /> <br /> &lt;math&gt;P=\frac{1366}{2^{12}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ANS=&lt;math&gt;\boxed{683}&lt;/math&gt;<br /> <br /> By SpecialBeing2017<br /> <br /> ==Solution 2==<br /> Consider the numbers &lt;math&gt;\{1,4,7,10,13,16\}&lt;/math&gt;. Each of those are congruent to &lt;math&gt;1 \pmod 3&lt;/math&gt;. There is &lt;math&gt;{6 \choose 0}=1&lt;/math&gt; way to choose zero numbers &lt;math&gt;{6 \choose 1}=6&lt;/math&gt; ways to choose &lt;math&gt;1&lt;/math&gt; and so on. There ends up being &lt;math&gt;{6 \choose 0}+{6 \choose 3}+{6 \choose 6} = 22&lt;/math&gt; possible subsets congruent to &lt;math&gt;0\pmod 3&lt;/math&gt;. There are &lt;math&gt;2^6=64&lt;/math&gt; possible subsets of these numbers. By symmetry there are &lt;math&gt;21&lt;/math&gt; subsets each for &lt;math&gt;1 \pmod 3&lt;/math&gt; and &lt;math&gt;2 \pmod3&lt;/math&gt;.<br /> <br /> We get the same numbers for the subsets of &lt;math&gt;\{2,5,8,11,14,17\}&lt;/math&gt;.<br /> <br /> For &lt;math&gt;\{3,6,9,12,15,18\}&lt;/math&gt;, all &lt;math&gt;2^6&lt;/math&gt; subsets are &lt;math&gt;0 \pmod3&lt;/math&gt;.<br /> <br /> So the probability is: &lt;math&gt;\frac{(22\cdot22+2\cdot21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ==Solution 3==<br /> Notice that six numbers are &lt;math&gt;0\pmod3&lt;/math&gt;, six are &lt;math&gt;1\pmod3&lt;/math&gt;, and six are &lt;math&gt;2\pmod3&lt;/math&gt;. Having numbers &lt;math&gt;0\pmod3&lt;/math&gt; will not change the remainder when &lt;math&gt;s(T)&lt;/math&gt; is divided by &lt;math&gt;3&lt;/math&gt;, so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are &lt;math&gt;1\pmod3&lt;/math&gt;, minus the number of numbers that are &lt;math&gt;2\pmod3&lt;/math&gt;, must be a multiple of &lt;math&gt;3&lt;/math&gt;, possibly zero or negative. We can now split into cases based on how many numbers that are &lt;math&gt;1\pmod3&lt;/math&gt; are in the set.<br /> <br /> Case 1- &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers: There can be &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom60+\binom63+\binom66\right)\cdot\left(\binom60+\binom63+\binom66\right)=(1+20+1)^2=484&lt;/math&gt; ways.<br /> <br /> Case 2- &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers: There can be &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom61+\binom64\right)\cdot\left(\binom62+\binom65\right)=(6+15)^2=441&lt;/math&gt; ways.<br /> <br /> Case 3- &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers: There can be &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441&lt;/math&gt; ways.<br /> <br /> Adding these up, we get that there are &lt;math&gt;1366&lt;/math&gt; ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of &lt;math&gt;3&lt;/math&gt; in our set, we have that there are &lt;math&gt;1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66\right)=1366\cdot2^6&lt;/math&gt; subsets &lt;math&gt;T&lt;/math&gt; with a sum that is a multiple of &lt;math&gt;3&lt;/math&gt;. Since there are &lt;math&gt;2^{18}&lt;/math&gt; total subsets, the probability is &lt;math&gt;\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> We use generating functions. Each element of &lt;math&gt;U&lt;/math&gt; has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given &lt;math&gt;n\in U&lt;/math&gt;, the probability generating function is<br /> &lt;cmath&gt;\frac{1}{2}+\frac{1}{2}x^n.&lt;/cmath&gt;<br /> Therefore, in the generating function<br /> &lt;cmath&gt;\frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18}),&lt;/cmath&gt;<br /> the coefficient of &lt;math&gt;x^k&lt;/math&gt; represents the probability of obtaining a sum of &lt;math&gt;k&lt;/math&gt;. We wish to find the sum of the coefficients of all terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. If &lt;math&gt;\omega=e^{2\pi i/3}&lt;/math&gt; is a cube root of unity, then it is well know that for a polynomial &lt;math&gt;P(x)&lt;/math&gt;, <br /> &lt;cmath&gt;\frac{P(1)+P(\omega)+P(\omega^2)}{3}&lt;/cmath&gt;<br /> will yield the sum of the coefficients of the terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. Then we find<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> \frac{1}{2^{18}}(1+1)(1+1^2)(1+1^3)\cdots (1+1^{18})&amp;=1\\\frac{1}{2^{18}}(1+\omega)(1+\omega^2)(1+\omega^3)\cdots (1+\omega^{18})&amp;=\frac{1}{2^{12}}\\\frac{1}{2^{18}}(1+\omega^2)(1+\omega^4)(1+\omega^6)\cdots (1+\omega^{36})&amp;=\frac{1}{2^{12}}.<br /> \end{align*}&lt;/cmath&gt;<br /> To evaluate the last two products, we utilized the facts that &lt;math&gt;\omega^3=1&lt;/math&gt; and &lt;math&gt;1+\omega+\omega^2=0&lt;/math&gt;. Therefore, the desired probability is<br /> &lt;cmath&gt;\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.&lt;/cmath&gt;<br /> Thus the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 5==<br /> Define a set that &quot;works&quot; to be a set for which the sum of the terms is &lt;math&gt;0&lt;/math&gt; mod &lt;math&gt;3&lt;/math&gt;. The given set mod &lt;math&gt;3&lt;/math&gt; is<br /> &lt;cmath&gt;\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> Let &lt;math&gt;w(N)&lt;/math&gt; be the number of subsets of the first &lt;math&gt;N&lt;/math&gt; terms of this set that &quot;work.&quot;<br /> Consider just the first &lt;math&gt;3&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0\}.&lt;/cmath&gt;<br /> There are &lt;math&gt;2^3=8&lt;/math&gt; total subsets, and &lt;math&gt;w(3)=4&lt;/math&gt; (the subsets are &lt;math&gt;\emptyset, \{0\}, \{1,2\},&lt;/math&gt; and &lt;math&gt;\{1,2,0\}&lt;/math&gt;). Now consider the first &lt;math&gt;6&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> To find &lt;math&gt;w(6)&lt;/math&gt;, we set aside the last &lt;math&gt;3&lt;/math&gt; terms as a &quot;reserve&quot; that we can pair with subsets of the first &lt;math&gt;3&lt;/math&gt; terms (which we looked at earlier). <br /> <br /> First, all &lt;math&gt;2^3&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms can either be paired with a &lt;math&gt;1&lt;/math&gt; or a &lt;math&gt;2&lt;/math&gt; (or nothing) from the &quot;reserve&quot; terms so that they &quot;work,&quot; creating &lt;math&gt;2^3&lt;/math&gt; subsets that &quot;work&quot; already. But for each of these, we have the option to add a &lt;math&gt;0&lt;/math&gt; from the reserve, so we now have &lt;math&gt;2\cdot2^3&lt;/math&gt; subsets that &quot;work.&quot; For each of the &lt;math&gt;w(3)=4&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms that &quot;work&quot;, we can also add on a &lt;math&gt;\{1,2\}&lt;/math&gt; or a &lt;math&gt;\{1,2,0\}&lt;/math&gt; from the reserves, creating &lt;math&gt;2w(3)&lt;/math&gt; new subsets that &quot;work.&quot; And that covers all of them. With all of this information, we can write &lt;math&gt;w(6)&lt;/math&gt; as<br /> &lt;cmath&gt;w(6)=2\cdot2^3+2w(3)=2(2^3+w(3)).&lt;/cmath&gt;<br /> The same process can be used to calculate &lt;math&gt;w(9)&lt;/math&gt; then &lt;math&gt;w(12)&lt;/math&gt; etc. so we can generalize it to<br /> &lt;cmath&gt;w(N)=2(2^{N-3}+w(N-3)).&lt;/cmath&gt;<br /> Thus, we calculate &lt;math&gt;w(18)&lt;/math&gt; with this formula:<br /> &lt;cmath&gt;w(18)=2( 2^{15} + 2( 2^{12} + 2( 2^9 + 2( 2^6 + 2( 2^3 + 4 ) ) ) ) )=87424.&lt;/cmath&gt;<br /> Because there are &lt;math&gt;2^{18}&lt;/math&gt; total possible subsets, the desired probability is<br /> &lt;cmath&gt;\frac{w(3)}{2^{18}}=\frac{87424}{2^{18}}=\frac{683}{2048},&lt;/cmath&gt;<br /> so the answer is &lt;math&gt;\boxed{683}.&lt;/math&gt;<br /> <br /> ==Solution 6==<br /> Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if &lt;math&gt;U&lt;/math&gt; is of a small size. <br /> <br /> If &lt;math&gt;U = \{ 1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;4&lt;/math&gt; out of &lt;math&gt;8&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac12&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;24&lt;/math&gt; out of &lt;math&gt;64&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac38&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;176&lt;/math&gt; out of &lt;math&gt;512&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac{11}{32}&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;a_n&lt;/math&gt; be the numerator of the desired probability if &lt;math&gt;U&lt;/math&gt; is of size &lt;math&gt;3n&lt;/math&gt;. Then &lt;math&gt;a_1 = 1, a_2 = 3,&lt;/math&gt; and &lt;math&gt;a_3 = 11&lt;/math&gt;. Noticing that the denominators are multiplied by &lt;math&gt;4&lt;/math&gt; each time, we can conclude that the pattern of the numerators is &lt;math&gt;a_n = 4a_{n-1} - 1&lt;/math&gt;, so &lt;math&gt;a_6 = \boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 7 (Quick guesswork for about 2 minutes remaining)==<br /> <br /> <br /> We conjecture that the difference from the probability will be as small as possible from 1/3<br /> <br /> (The value approached as n--&gt;infinity, where n is the number of terms in the largest subset.)<br /> <br /> <br /> We also see that there are 2^18 subsets and know the denominator will be a power of 2<br /> (since the numerator is an integer).<br /> <br /> We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 &lt;1000 can be plugged in to get the solution of round(2^n/3)<br /> <br /> <br /> We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.<br /> <br /> ==See Also==<br /> {{AIME box|year=2018|n=I|num-b=11|num-a=13}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_12&diff=129502 2018 AIME I Problems/Problem 12 2020-07-27T13:39:04Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>==Problem==<br /> For every subset &lt;math&gt;T&lt;/math&gt; of &lt;math&gt;U = \{ 1,2,3,\ldots,18 \}&lt;/math&gt;, let &lt;math&gt;s(T)&lt;/math&gt; be the sum of the elements of &lt;math&gt;T&lt;/math&gt;, with &lt;math&gt;s(\emptyset)&lt;/math&gt; defined to be &lt;math&gt;0&lt;/math&gt;. If &lt;math&gt;T&lt;/math&gt; is chosen at random among all subsets of &lt;math&gt;U&lt;/math&gt;, the probability that &lt;math&gt;s(T)&lt;/math&gt; is divisible by &lt;math&gt;3&lt;/math&gt; is &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Ignore the &lt;math&gt;0&lt;/math&gt;'s because we're gonna multiply &lt;math&gt;\binom{6}{0}+..+\binom{6}{6}=2^6&lt;/math&gt; at the end. Let &lt;math&gt;a&lt;/math&gt; be the &lt;math&gt;1's&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; be the &lt;math&gt;2's&lt;/math&gt;. The key here is that &lt;math&gt;2 \equiv -1 \pmod{3}&lt;/math&gt; so the difference between the number of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> 1. Counted twice because &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; can be switched: <br /> &lt;math&gt;6a&lt;/math&gt;<br /> &lt;math&gt;6a,3b&lt;/math&gt;<br /> &lt;math&gt;5a,2b&lt;/math&gt;<br /> &lt;math&gt;4a,b&lt;/math&gt;<br /> &lt;math&gt;3a&lt;/math&gt;<br /> 2. Counted once:<br /> &lt;math&gt;6a,6b&lt;/math&gt;<br /> ...<br /> &lt;math&gt;0a,0b&lt;/math&gt;<br /> <br /> By Vandermonde's identity on the second case, this is &lt;math&gt;2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> Rewrite the set after mod 3<br /> <br /> 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0<br /> <br /> All 0s can be omitted <br /> <br /> Case 1<br /> No 1 No 2<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 2<br /> &lt;math&gt;222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 3<br /> &lt;math&gt;222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 4<br /> &lt;math&gt;12&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 5<br /> &lt;math&gt;12222&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 6<br /> &lt;math&gt;1122&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 7<br /> &lt;math&gt;1122222&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 8<br /> &lt;math&gt;111&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 9<br /> &lt;math&gt;111222&lt;/math&gt;<br /> &lt;math&gt;20*20=400&lt;/math&gt;<br /> <br /> Case 10<br /> &lt;math&gt;111222222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 11<br /> &lt;math&gt;11112&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 12<br /> &lt;math&gt;11112222&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 13<br /> &lt;math&gt;1111122&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 14<br /> &lt;math&gt;1111122222&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 15<br /> &lt;math&gt;111111&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 16<br /> &lt;math&gt;111111222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 17<br /> &lt;math&gt;111111222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Total &lt;math&gt;1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366&lt;/math&gt;<br /> <br /> &lt;math&gt;P=\frac{1366}{2^{12}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ANS=&lt;math&gt;\boxed{683}&lt;/math&gt;<br /> <br /> By SpecialBeing2017<br /> <br /> ==Solution 2==<br /> Consider the numbers &lt;math&gt;\{1,4,7,10,13,16\}&lt;/math&gt;. Each of those are congruent to &lt;math&gt;1 \pmod 3&lt;/math&gt;. There is &lt;math&gt;{6 \choose 0}=1&lt;/math&gt; way to choose zero numbers &lt;math&gt;{6 \choose 1}=6&lt;/math&gt; ways to choose &lt;math&gt;1&lt;/math&gt; and so on. There ends up being &lt;math&gt;{6 \choose 0}+{6 \choose 3}+{6 \choose 6} = 22&lt;/math&gt; possible subsets congruent to &lt;math&gt;0\pmod 3&lt;/math&gt;. There are &lt;math&gt;2^6=64&lt;/math&gt; possible subsets of these numbers. By symmetry there are &lt;math&gt;21&lt;/math&gt; subsets each for &lt;math&gt;1 \pmod 3&lt;/math&gt; and &lt;math&gt;2 \pmod3&lt;/math&gt;.<br /> <br /> We get the same numbers for the subsets of &lt;math&gt;\{2,5,8,11,14,17\}&lt;/math&gt;.<br /> <br /> For &lt;math&gt;\{3,6,9,12,15,18\}&lt;/math&gt;, all &lt;math&gt;2^6&lt;/math&gt; subsets are &lt;math&gt;0 \pmod3&lt;/math&gt;.<br /> <br /> So the probability is: &lt;math&gt;\frac{(22\cdot22+2\cdot21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ==Solution 3==<br /> Notice that six numbers are &lt;math&gt;0\pmod3&lt;/math&gt;, six are &lt;math&gt;1\pmod3&lt;/math&gt;, and six are &lt;math&gt;2\pmod3&lt;/math&gt;. Having numbers &lt;math&gt;0\pmod3&lt;/math&gt; will not change the remainder when &lt;math&gt;s(T)&lt;/math&gt; is divided by &lt;math&gt;3&lt;/math&gt;, so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are &lt;math&gt;1\pmod3&lt;/math&gt;, minus the number of numbers that are &lt;math&gt;2\pmod3&lt;/math&gt;, must be a multiple of &lt;math&gt;3&lt;/math&gt;, possibly zero or negative. We can now split into cases based on how many numbers that are &lt;math&gt;1\pmod3&lt;/math&gt; are in the set.<br /> <br /> Case 1- &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers: There can be &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom60+\binom63+\binom66\right)\cdot\left(\binom60+\binom63+\binom66\right)=(1+20+1)^2=484&lt;/math&gt; ways.<br /> <br /> Case 2- &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers: There can be &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom61+\binom64\right)\cdot\left(\binom62+\binom65\right)=(6+15)^2=441&lt;/math&gt; ways.<br /> <br /> Case 3- &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers: There can be &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441&lt;/math&gt; ways.<br /> <br /> Adding these up, we get that there are &lt;math&gt;1366&lt;/math&gt; ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of &lt;math&gt;3&lt;/math&gt; in our set, we have that there are &lt;math&gt;1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66\right)=1366\cdot2^6&lt;/math&gt; subsets &lt;math&gt;T&lt;/math&gt; with a sum that is a multiple of &lt;math&gt;3&lt;/math&gt;. Since there are &lt;math&gt;2^{18}&lt;/math&gt; total subsets, the probability is &lt;math&gt;\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> We use generating functions. Each element of &lt;math&gt;U&lt;/math&gt; has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given &lt;math&gt;n\in U&lt;/math&gt;, the probability generating function is<br /> &lt;cmath&gt;\frac{1}{2}+\frac{1}{2}x^n.&lt;/cmath&gt;<br /> Therefore, in the generating function<br /> &lt;cmath&gt;\frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18}),&lt;/cmath&gt;<br /> the coefficient of &lt;math&gt;x^k&lt;/math&gt; represents the probability of obtaining a sum of &lt;math&gt;k&lt;/math&gt;. We wish to find the sum of the coefficients of all terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. If &lt;math&gt;\omega=e^{2\pi i/3}&lt;/math&gt; is a cube root of unity, then it is well know that for a polynomial &lt;math&gt;P(x)&lt;/math&gt;, <br /> &lt;cmath&gt;\frac{P(1)+P(\omega)+P(\omega^2)}{3}&lt;/cmath&gt;<br /> will yield the sum of the coefficients of the terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. Then we find<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> \frac{1}{2^{18}}(1+1)(1+1^2)(1+1^3)\cdots (1+1^{18})&amp;=1\\\frac{1}{2^{18}}(1+\omega)(1+\omega^2)(1+\omega^3)\cdots (1+\omega^{18})&amp;=\frac{1}{2^{12}}\\\frac{1}{2^{18}}(1+\omega^2)(1+\omega^4)(1+\omega^6)\cdots (1+\omega^{36})&amp;=\frac{1}{2^{12}}.<br /> \end{align*}&lt;/cmath&gt;<br /> To evaluate the last two products, we utilized the facts that &lt;math&gt;\omega^3=1&lt;/math&gt; and &lt;math&gt;1+\omega+\omega^2=0&lt;/math&gt;. Therefore, the desired probability is<br /> &lt;cmath&gt;\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.&lt;/cmath&gt;<br /> Thus the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 5==<br /> Define a set that &quot;works&quot; to be a set for which the sum of the terms is &lt;math&gt;0&lt;/math&gt; mod &lt;math&gt;3&lt;/math&gt;. The given set mod &lt;math&gt;3&lt;/math&gt; is<br /> &lt;cmath&gt;\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> Let &lt;math&gt;w(N)&lt;/math&gt; be the number of subsets of the first &lt;math&gt;N&lt;/math&gt; terms of this set that &quot;work.&quot;<br /> Consider just the first &lt;math&gt;3&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0\}.&lt;/cmath&gt;<br /> There are &lt;math&gt;2^3=8&lt;/math&gt; total subsets, and &lt;math&gt;w(3)=4&lt;/math&gt; (the subsets are &lt;math&gt;\emptyset, \{0\}, \{1,2\},&lt;/math&gt; and &lt;math&gt;\{1,2,0\}&lt;/math&gt;). Now consider the first &lt;math&gt;6&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> To find &lt;math&gt;w(6)&lt;/math&gt;, we set aside the last &lt;math&gt;3&lt;/math&gt; terms as a &quot;reserve&quot; that we can pair with subsets of the first &lt;math&gt;3&lt;/math&gt; terms (which we looked at earlier). <br /> <br /> First, all &lt;math&gt;2^3&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms can either be paired with a &lt;math&gt;1&lt;/math&gt; or a &lt;math&gt;2&lt;/math&gt; (or nothing) from the &quot;reserve&quot; terms so that they &quot;work,&quot; creating &lt;math&gt;2^3&lt;/math&gt; subsets that &quot;work&quot; already. But for each of these, we have the option to add a &lt;math&gt;0&lt;/math&gt; from the reserve, so we now have &lt;math&gt;2\cdot2^3&lt;/math&gt; subsets that &quot;work.&quot; For each of the &lt;math&gt;w(3)=4&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms that &quot;work&quot;, we can also add on a &lt;math&gt;\{1,2\}&lt;/math&gt; or a &lt;math&gt;\{1,2,0\}&lt;/math&gt; from the reserves, creating &lt;math&gt;2w(3)&lt;/math&gt; new subsets that &quot;work.&quot; And that covers all of them. With all of this information, we can write &lt;math&gt;w(6)&lt;/math&gt; as<br /> &lt;cmath&gt;w(6)=2\cdot2^3+2w(3)=2(2^3+w(3)).&lt;/cmath&gt;<br /> The same process can be used to calculate &lt;math&gt;w(9)&lt;/math&gt; then &lt;math&gt;w(12)&lt;/math&gt; etc. so we can generalize it to<br /> &lt;cmath&gt;w(N)=2(2^{N-3}+w(N-3)).&lt;/cmath&gt;<br /> Thus, we calculate &lt;math&gt;w(18)&lt;/math&gt; with this formula:<br /> &lt;cmath&gt;w(18)=2( 2^{15} + 2( 2^{12} + 2( 2^9 + 2( 2^6 + 2( 2^3 + 4 ) ) ) ) )=87424.&lt;/cmath&gt;<br /> Because there are &lt;math&gt;2^{18}&lt;/math&gt; total possible subsets, the desired probability is<br /> &lt;cmath&gt;\frac{w(3)}{2^{18}}=\frac{87424}{2^{18}}=\frac{683}{2048},&lt;/cmath&gt;<br /> so the answer is &lt;math&gt;\boxed{683}.&lt;/math&gt;<br /> <br /> ==Solution 6==<br /> Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if &lt;math&gt;U&lt;/math&gt; is of a small size. <br /> <br /> If &lt;math&gt;U = \{ 1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;4&lt;/math&gt; out of &lt;math&gt;8&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac12&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;24&lt;/math&gt; out of &lt;math&gt;64&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac38&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;176&lt;/math&gt; out of &lt;math&gt;512&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac{11}{32}&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;a_n&lt;/math&gt; be the numerator of the desired probability if &lt;math&gt;U&lt;/math&gt; is of size &lt;math&gt;3n&lt;/math&gt;. Then &lt;math&gt;a_1 = 1, a_2 = 3,&lt;/math&gt; and &lt;math&gt;a_3 = 11&lt;/math&gt;. Noticing that the denominators are multiplied by &lt;math&gt;4&lt;/math&gt; each time, we can conclude that the pattern of the numerators is &lt;math&gt;a_n = 4a_{n-1} - 1&lt;/math&gt;, so &lt;math&gt;a_6 = \boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 7 (Quick guesswork for about 2 minutes remaining)==<br /> <br /> <br /> We conjecture that the difference from the probability will be as small as possible from 1/3<br /> <br /> (The value approached as n--&gt;infinity, where n is the number of terms in the largest subset.)<br /> <br /> <br /> We also see that there are 2^18 subsets and know the denominator will be a power of 2<br /> (since the numerator is an integer).<br /> <br /> We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 &lt;1000 can be plugged in to get the solution of round(2^n/3)<br /> <br /> <br /> We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.<br /> <br /> ==See Also==<br /> {{AIME box|year=2018|n=I|num-b=11|num-a=13}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_12&diff=129501 2018 AIME I Problems/Problem 12 2020-07-27T13:38:43Z <p>Mysteryguy6647: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> For every subset &lt;math&gt;T&lt;/math&gt; of &lt;math&gt;U = \{ 1,2,3,\ldots,18 \}&lt;/math&gt;, let &lt;math&gt;s(T)&lt;/math&gt; be the sum of the elements of &lt;math&gt;T&lt;/math&gt;, with &lt;math&gt;s(\emptyset)&lt;/math&gt; defined to be &lt;math&gt;0&lt;/math&gt;. If &lt;math&gt;T&lt;/math&gt; is chosen at random among all subsets of &lt;math&gt;U&lt;/math&gt;, the probability that &lt;math&gt;s(T)&lt;/math&gt; is divisible by &lt;math&gt;3&lt;/math&gt; is &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Ignore the &lt;math&gt;0&lt;/math&gt;'s because we're gonna multiply &lt;math&gt;2^6&lt;/math&gt; at the end. Let &lt;math&gt;a&lt;/math&gt; be the &lt;math&gt;1's&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; be the &lt;math&gt;2's&lt;/math&gt;. The key here is that &lt;math&gt;2 \equiv -1 \pmod{3}&lt;/math&gt; so the difference between the number of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> 1. Counted twice because &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; can be switched: <br /> &lt;math&gt;6a&lt;/math&gt;<br /> &lt;math&gt;6a,3b&lt;/math&gt;<br /> &lt;math&gt;5a,2b&lt;/math&gt;<br /> &lt;math&gt;4a,b&lt;/math&gt;<br /> &lt;math&gt;3a&lt;/math&gt;<br /> 2. Counted once:<br /> &lt;math&gt;6a,6b&lt;/math&gt;<br /> ...<br /> &lt;math&gt;0a,0b&lt;/math&gt;<br /> <br /> By Vandermonde's identity on the second case, this is &lt;math&gt;2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}&lt;/math&gt;<br /> ==Solution 1==<br /> Rewrite the set after mod 3<br /> <br /> 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0<br /> <br /> All 0s can be omitted <br /> <br /> Case 1<br /> No 1 No 2<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 2<br /> &lt;math&gt;222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 3<br /> &lt;math&gt;222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 4<br /> &lt;math&gt;12&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 5<br /> &lt;math&gt;12222&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 6<br /> &lt;math&gt;1122&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 7<br /> &lt;math&gt;1122222&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 8<br /> &lt;math&gt;111&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 9<br /> &lt;math&gt;111222&lt;/math&gt;<br /> &lt;math&gt;20*20=400&lt;/math&gt;<br /> <br /> Case 10<br /> &lt;math&gt;111222222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 11<br /> &lt;math&gt;11112&lt;/math&gt;<br /> &lt;math&gt;15*6=90&lt;/math&gt;<br /> <br /> Case 12<br /> &lt;math&gt;11112222&lt;/math&gt;<br /> &lt;math&gt;15*15=225&lt;/math&gt;<br /> <br /> Case 13<br /> &lt;math&gt;1111122&lt;/math&gt;<br /> &lt;math&gt;6*15=90&lt;/math&gt;<br /> <br /> Case 14<br /> &lt;math&gt;1111122222&lt;/math&gt;<br /> &lt;math&gt;6*6=36&lt;/math&gt;<br /> <br /> Case 15<br /> &lt;math&gt;111111&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Case 16<br /> &lt;math&gt;111111222&lt;/math&gt;<br /> &lt;math&gt;20&lt;/math&gt;<br /> <br /> Case 17<br /> &lt;math&gt;111111222222&lt;/math&gt;<br /> &lt;math&gt;1&lt;/math&gt;<br /> <br /> Total &lt;math&gt;1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366&lt;/math&gt;<br /> <br /> &lt;math&gt;P=\frac{1366}{2^{12}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ANS=&lt;math&gt;\boxed{683}&lt;/math&gt;<br /> <br /> By SpecialBeing2017<br /> <br /> ==Solution 2==<br /> Consider the numbers &lt;math&gt;\{1,4,7,10,13,16\}&lt;/math&gt;. Each of those are congruent to &lt;math&gt;1 \pmod 3&lt;/math&gt;. There is &lt;math&gt;{6 \choose 0}=1&lt;/math&gt; way to choose zero numbers &lt;math&gt;{6 \choose 1}=6&lt;/math&gt; ways to choose &lt;math&gt;1&lt;/math&gt; and so on. There ends up being &lt;math&gt;{6 \choose 0}+{6 \choose 3}+{6 \choose 6} = 22&lt;/math&gt; possible subsets congruent to &lt;math&gt;0\pmod 3&lt;/math&gt;. There are &lt;math&gt;2^6=64&lt;/math&gt; possible subsets of these numbers. By symmetry there are &lt;math&gt;21&lt;/math&gt; subsets each for &lt;math&gt;1 \pmod 3&lt;/math&gt; and &lt;math&gt;2 \pmod3&lt;/math&gt;.<br /> <br /> We get the same numbers for the subsets of &lt;math&gt;\{2,5,8,11,14,17\}&lt;/math&gt;.<br /> <br /> For &lt;math&gt;\{3,6,9,12,15,18\}&lt;/math&gt;, all &lt;math&gt;2^6&lt;/math&gt; subsets are &lt;math&gt;0 \pmod3&lt;/math&gt;.<br /> <br /> So the probability is: &lt;math&gt;\frac{(22\cdot22+2\cdot21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;<br /> <br /> ==Solution 3==<br /> Notice that six numbers are &lt;math&gt;0\pmod3&lt;/math&gt;, six are &lt;math&gt;1\pmod3&lt;/math&gt;, and six are &lt;math&gt;2\pmod3&lt;/math&gt;. Having numbers &lt;math&gt;0\pmod3&lt;/math&gt; will not change the remainder when &lt;math&gt;s(T)&lt;/math&gt; is divided by &lt;math&gt;3&lt;/math&gt;, so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are &lt;math&gt;1\pmod3&lt;/math&gt;, minus the number of numbers that are &lt;math&gt;2\pmod3&lt;/math&gt;, must be a multiple of &lt;math&gt;3&lt;/math&gt;, possibly zero or negative. We can now split into cases based on how many numbers that are &lt;math&gt;1\pmod3&lt;/math&gt; are in the set.<br /> <br /> Case 1- &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers: There can be &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;6&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom60+\binom63+\binom66\right)\cdot\left(\binom60+\binom63+\binom66\right)=(1+20+1)^2=484&lt;/math&gt; ways.<br /> <br /> Case 2- &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers: There can be &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom61+\binom64\right)\cdot\left(\binom62+\binom65\right)=(6+15)^2=441&lt;/math&gt; ways.<br /> <br /> Case 3- &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; integers: There can be &lt;math&gt;1&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt; integers that are &lt;math&gt;2\pmod3&lt;/math&gt;. We can choose these in &lt;math&gt;\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441&lt;/math&gt; ways.<br /> <br /> Adding these up, we get that there are &lt;math&gt;1366&lt;/math&gt; ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of &lt;math&gt;3&lt;/math&gt; in our set, we have that there are &lt;math&gt;1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66\right)=1366\cdot2^6&lt;/math&gt; subsets &lt;math&gt;T&lt;/math&gt; with a sum that is a multiple of &lt;math&gt;3&lt;/math&gt;. Since there are &lt;math&gt;2^{18}&lt;/math&gt; total subsets, the probability is &lt;math&gt;\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> We use generating functions. Each element of &lt;math&gt;U&lt;/math&gt; has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given &lt;math&gt;n\in U&lt;/math&gt;, the probability generating function is<br /> &lt;cmath&gt;\frac{1}{2}+\frac{1}{2}x^n.&lt;/cmath&gt;<br /> Therefore, in the generating function<br /> &lt;cmath&gt;\frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18}),&lt;/cmath&gt;<br /> the coefficient of &lt;math&gt;x^k&lt;/math&gt; represents the probability of obtaining a sum of &lt;math&gt;k&lt;/math&gt;. We wish to find the sum of the coefficients of all terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. If &lt;math&gt;\omega=e^{2\pi i/3}&lt;/math&gt; is a cube root of unity, then it is well know that for a polynomial &lt;math&gt;P(x)&lt;/math&gt;, <br /> &lt;cmath&gt;\frac{P(1)+P(\omega)+P(\omega^2)}{3}&lt;/cmath&gt;<br /> will yield the sum of the coefficients of the terms of the form &lt;math&gt;x^{3k}&lt;/math&gt;. Then we find<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> \frac{1}{2^{18}}(1+1)(1+1^2)(1+1^3)\cdots (1+1^{18})&amp;=1\\\frac{1}{2^{18}}(1+\omega)(1+\omega^2)(1+\omega^3)\cdots (1+\omega^{18})&amp;=\frac{1}{2^{12}}\\\frac{1}{2^{18}}(1+\omega^2)(1+\omega^4)(1+\omega^6)\cdots (1+\omega^{36})&amp;=\frac{1}{2^{12}}.<br /> \end{align*}&lt;/cmath&gt;<br /> To evaluate the last two products, we utilized the facts that &lt;math&gt;\omega^3=1&lt;/math&gt; and &lt;math&gt;1+\omega+\omega^2=0&lt;/math&gt;. Therefore, the desired probability is<br /> &lt;cmath&gt;\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.&lt;/cmath&gt;<br /> Thus the answer is &lt;math&gt;\boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 5==<br /> Define a set that &quot;works&quot; to be a set for which the sum of the terms is &lt;math&gt;0&lt;/math&gt; mod &lt;math&gt;3&lt;/math&gt;. The given set mod &lt;math&gt;3&lt;/math&gt; is<br /> &lt;cmath&gt;\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> Let &lt;math&gt;w(N)&lt;/math&gt; be the number of subsets of the first &lt;math&gt;N&lt;/math&gt; terms of this set that &quot;work.&quot;<br /> Consider just the first &lt;math&gt;3&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0\}.&lt;/cmath&gt;<br /> There are &lt;math&gt;2^3=8&lt;/math&gt; total subsets, and &lt;math&gt;w(3)=4&lt;/math&gt; (the subsets are &lt;math&gt;\emptyset, \{0\}, \{1,2\},&lt;/math&gt; and &lt;math&gt;\{1,2,0\}&lt;/math&gt;). Now consider the first &lt;math&gt;6&lt;/math&gt; terms:<br /> &lt;cmath&gt;\{1,2,0,1,2,0\}.&lt;/cmath&gt;<br /> To find &lt;math&gt;w(6)&lt;/math&gt;, we set aside the last &lt;math&gt;3&lt;/math&gt; terms as a &quot;reserve&quot; that we can pair with subsets of the first &lt;math&gt;3&lt;/math&gt; terms (which we looked at earlier). <br /> <br /> First, all &lt;math&gt;2^3&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms can either be paired with a &lt;math&gt;1&lt;/math&gt; or a &lt;math&gt;2&lt;/math&gt; (or nothing) from the &quot;reserve&quot; terms so that they &quot;work,&quot; creating &lt;math&gt;2^3&lt;/math&gt; subsets that &quot;work&quot; already. But for each of these, we have the option to add a &lt;math&gt;0&lt;/math&gt; from the reserve, so we now have &lt;math&gt;2\cdot2^3&lt;/math&gt; subsets that &quot;work.&quot; For each of the &lt;math&gt;w(3)=4&lt;/math&gt; subsets of the first &lt;math&gt;3&lt;/math&gt; terms that &quot;work&quot;, we can also add on a &lt;math&gt;\{1,2\}&lt;/math&gt; or a &lt;math&gt;\{1,2,0\}&lt;/math&gt; from the reserves, creating &lt;math&gt;2w(3)&lt;/math&gt; new subsets that &quot;work.&quot; And that covers all of them. With all of this information, we can write &lt;math&gt;w(6)&lt;/math&gt; as<br /> &lt;cmath&gt;w(6)=2\cdot2^3+2w(3)=2(2^3+w(3)).&lt;/cmath&gt;<br /> The same process can be used to calculate &lt;math&gt;w(9)&lt;/math&gt; then &lt;math&gt;w(12)&lt;/math&gt; etc. so we can generalize it to<br /> &lt;cmath&gt;w(N)=2(2^{N-3}+w(N-3)).&lt;/cmath&gt;<br /> Thus, we calculate &lt;math&gt;w(18)&lt;/math&gt; with this formula:<br /> &lt;cmath&gt;w(18)=2( 2^{15} + 2( 2^{12} + 2( 2^9 + 2( 2^6 + 2( 2^3 + 4 ) ) ) ) )=87424.&lt;/cmath&gt;<br /> Because there are &lt;math&gt;2^{18}&lt;/math&gt; total possible subsets, the desired probability is<br /> &lt;cmath&gt;\frac{w(3)}{2^{18}}=\frac{87424}{2^{18}}=\frac{683}{2048},&lt;/cmath&gt;<br /> so the answer is &lt;math&gt;\boxed{683}.&lt;/math&gt;<br /> <br /> ==Solution 6==<br /> Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if &lt;math&gt;U&lt;/math&gt; is of a small size. <br /> <br /> If &lt;math&gt;U = \{ 1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;4&lt;/math&gt; out of &lt;math&gt;8&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac12&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;24&lt;/math&gt; out of &lt;math&gt;64&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac38&lt;/math&gt;.<br /> <br /> If &lt;math&gt;U = \{ 1,2,0,1,2,0,1,2,0\} \pmod 3&lt;/math&gt;, then &lt;math&gt;176&lt;/math&gt; out of &lt;math&gt;512&lt;/math&gt; subsets work, for a probability of &lt;math&gt;\frac{11}{32}&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;a_n&lt;/math&gt; be the numerator of the desired probability if &lt;math&gt;U&lt;/math&gt; is of size &lt;math&gt;3n&lt;/math&gt;. Then &lt;math&gt;a_1 = 1, a_2 = 3,&lt;/math&gt; and &lt;math&gt;a_3 = 11&lt;/math&gt;. Noticing that the denominators are multiplied by &lt;math&gt;4&lt;/math&gt; each time, we can conclude that the pattern of the numerators is &lt;math&gt;a_n = 4a_{n-1} - 1&lt;/math&gt;, so &lt;math&gt;a_6 = \boxed{683}&lt;/math&gt;.<br /> <br /> ==Solution 7 (Quick guesswork for about 2 minutes remaining)==<br /> <br /> <br /> We conjecture that the difference from the probability will be as small as possible from 1/3<br /> <br /> (The value approached as n--&gt;infinity, where n is the number of terms in the largest subset.)<br /> <br /> <br /> We also see that there are 2^18 subsets and know the denominator will be a power of 2<br /> (since the numerator is an integer).<br /> <br /> We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 &lt;1000 can be plugged in to get the solution of round(2^n/3)<br /> <br /> <br /> We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.<br /> <br /> ==See Also==<br /> {{AIME box|year=2018|n=I|num-b=11|num-a=13}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_4&diff=129183 2018 AIME I Problems/Problem 4 2020-07-25T06:26:52Z <p>Mysteryguy6647: /* Solution 1 (No Trig) */</p> <hr /> <div>==Problem 4==<br /> In &lt;math&gt;\triangle ABC, AB = AC = 10&lt;/math&gt; and &lt;math&gt;BC = 12&lt;/math&gt;. Point &lt;math&gt;D&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; on &lt;math&gt;\overline{AB}&lt;/math&gt; and point &lt;math&gt;E&lt;/math&gt; lies strictly between &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; on &lt;math&gt;\overline{AC}&lt;/math&gt; so that &lt;math&gt;AD = DE = EC&lt;/math&gt;. Then &lt;math&gt;AD&lt;/math&gt; can be expressed in the form &lt;math&gt;\dfrac{p}{q}&lt;/math&gt;, where &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> ==Solution==<br /> &lt;math&gt;\cos(A) = \frac{5^2+5^2-6^2}{2*5*5} = \frac{7}{25}&lt;/math&gt;. Let &lt;math&gt;M&lt;/math&gt; be midpoint of &lt;math&gt;AE&lt;/math&gt;, then &lt;math&gt;\frac{7}{25} = \frac{10-x}{2x} \iff x =\frac{250}{39}&lt;/math&gt;.<br /> ==Solution 1 (No Trig)==<br /> &lt;center&gt;<br /> &lt;asy&gt;<br /> import cse5;<br /> unitsize(10mm);<br /> pathpen=black;<br /> dotfactor=3;<br /> <br /> pair B = (0,0), A = (6,8), C = (12,0), D = (2.154,2.872), E = (8.153, 5.128), F=(7.68,5.76), G=(7.077,6.564), H=(5.6,4.3), I=(4.5,6), J=(10,2.66);<br /> pair[] dotted = {A,B,C,D,E,F,G};<br /> <br /> D(A--B);<br /> D(C--B);<br /> D(A--C);<br /> D(D--E);<br /> pathpen=dashed;<br /> D(B--F);<br /> D(D--G);<br /> <br /> dot(dotted);<br /> label(&quot;$A$&quot;,A,N);<br /> label(&quot;$B$&quot;,B,SW);<br /> label(&quot;$C$&quot;,C,SE);<br /> label(&quot;$D$&quot;,D,NW);<br /> label(&quot;$E$&quot;,E,NE);<br /> label(&quot;$F$&quot;,F,NE);<br /> label(&quot;$G$&quot;,G,NE);<br /> label(&quot;$x$&quot;,H,NW);<br /> label(&quot;$x$&quot;,I,NW);<br /> label(&quot;$x$&quot;,J,NE);<br /> &lt;/asy&gt;<br /> &lt;/center&gt;<br /> <br /> We draw the altitude from &lt;math&gt;B&lt;/math&gt; to &lt;math&gt;\overline{AC}&lt;/math&gt; to get point &lt;math&gt;F&lt;/math&gt;. We notice that the triangle's height from &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;\overline{BC}&lt;/math&gt; is 8 because it is a &lt;math&gt;3-4-5&lt;/math&gt; Right Triangle. To find the length of &lt;math&gt;\overline{BF}&lt;/math&gt;, we let &lt;math&gt;h&lt;/math&gt; represent &lt;math&gt;\overline{BF}&lt;/math&gt; and set up an equation by finding two ways to express the area. The equation is &lt;math&gt;(8)(12)=(10)(h)&lt;/math&gt;, which leaves us with &lt;math&gt;h=9.6&lt;/math&gt;. We then solve for the length &lt;math&gt;\overline{AF}&lt;/math&gt;, which is done through pythagorean theorm and get &lt;math&gt;\overline{AF}&lt;/math&gt; = &lt;math&gt;2.8&lt;/math&gt;. We can now see that &lt;math&gt;\triangle ABF&lt;/math&gt; is a &lt;math&gt;7-24-25&lt;/math&gt; Right Triangle. Thus, we set &lt;math&gt;\overline{AG}&lt;/math&gt; as &lt;math&gt;5-&lt;/math&gt;&lt;math&gt;\tfrac{x}{2}&lt;/math&gt;, and yield that &lt;math&gt;\overline{AD}&lt;/math&gt; &lt;math&gt;=&lt;/math&gt; &lt;math&gt;(&lt;/math&gt; &lt;math&gt;5-&lt;/math&gt; &lt;math&gt;\tfrac{x}{2}&lt;/math&gt; &lt;math&gt;)&lt;/math&gt; &lt;math&gt;(&lt;/math&gt; &lt;math&gt;\tfrac{25}{7}&lt;/math&gt; &lt;math&gt;)&lt;/math&gt;. Now, we can see &lt;math&gt;x&lt;/math&gt; = &lt;math&gt;(&lt;/math&gt; &lt;math&gt;5-&lt;/math&gt; &lt;math&gt;\tfrac{x}{2}&lt;/math&gt; &lt;math&gt;)&lt;/math&gt; &lt;math&gt;(&lt;/math&gt; &lt;math&gt;\tfrac{25}{7}&lt;/math&gt; &lt;math&gt;)&lt;/math&gt;. Solving this equation, we yield &lt;math&gt;39x=250&lt;/math&gt;, or &lt;math&gt;x=&lt;/math&gt; &lt;math&gt;\tfrac{250}{39}&lt;/math&gt;. Thus, our final answer is &lt;math&gt;250+39=\boxed{289}&lt;/math&gt;.<br /> ~bluebacon008<br /> <br /> ==Solution 2 (Easy Similar Triangles)==<br /> We start by adding a few points to the diagram. Call &lt;math&gt;F&lt;/math&gt; the midpoint of &lt;math&gt;AE&lt;/math&gt;, and &lt;math&gt;G&lt;/math&gt; the midpoint of &lt;math&gt;BC&lt;/math&gt;. (Note that &lt;math&gt;DF&lt;/math&gt; and &lt;math&gt;AG&lt;/math&gt; are altitudes of their respective triangles). We also call &lt;math&gt;\angle BAC = \theta&lt;/math&gt;. Since triangle &lt;math&gt;ADE&lt;/math&gt; is isosceles, &lt;math&gt;\angle AED = \theta&lt;/math&gt;, and &lt;math&gt;\angle ADF = \angle EDF = 90 - \theta&lt;/math&gt;. Since &lt;math&gt;\angle DEA = \theta&lt;/math&gt;, &lt;math&gt;\angle DEC = 180 - \theta&lt;/math&gt; and &lt;math&gt;\angle EDC = \angle ECD = \frac{\theta}{2}&lt;/math&gt;. Since &lt;math&gt;FDC&lt;/math&gt; is a right triangle, &lt;math&gt;\angle FDC = 180 - 90 - \frac{\theta}{2} = \frac{180-m}{2}&lt;/math&gt;. <br /> <br /> Since &lt;math&gt;\angle BAG = \frac{\theta}{2}&lt;/math&gt; and &lt;math&gt;\angle ABG = \frac{180-m}{2}&lt;/math&gt;, triangles &lt;math&gt;ABG&lt;/math&gt; and &lt;math&gt;CDF&lt;/math&gt; are similar by Angle-Angle similarity. Using similar triangle ratios, we have &lt;math&gt;\frac{AG}{BG} = \frac{CF}{DF}&lt;/math&gt;. &lt;math&gt;AG = 8&lt;/math&gt; and &lt;math&gt;BG = 6&lt;/math&gt; because there are &lt;math&gt;2&lt;/math&gt; &lt;math&gt;6-8-10&lt;/math&gt; triangles in the problem. Call &lt;math&gt;AD = x&lt;/math&gt;. Then &lt;math&gt;CE = x&lt;/math&gt;, &lt;math&gt;AE = 10-x&lt;/math&gt;, and &lt;math&gt;EF = \frac{10-x}{2}&lt;/math&gt;. Thus &lt;math&gt;CF = x + \frac{10-x}{2}&lt;/math&gt;. Our ratio now becomes &lt;math&gt;\frac{8}{6} = \frac{x+ \frac{10-x}{2}}{DF}&lt;/math&gt;. Solving for &lt;math&gt;DF&lt;/math&gt; gives us &lt;math&gt;DF = \frac{30+3x}{8}&lt;/math&gt;. Since &lt;math&gt;DF&lt;/math&gt; is a height of the triangle &lt;math&gt;ADE&lt;/math&gt;, &lt;math&gt;FE^2 + DF^2 = x^2&lt;/math&gt;, or &lt;math&gt;DF = \sqrt{x^2 - (\frac{10-x}{2})^2}&lt;/math&gt;. Solving the equation &lt;math&gt;\frac{30+3x}{8} = \sqrt{x^2 - (\frac{10-x}{2})^2}&lt;/math&gt; gives us &lt;math&gt;x = \frac{250}{39}&lt;/math&gt;, so our answer is &lt;math&gt;250+39 = \boxed{289}&lt;/math&gt;.<br /> <br /> ==Solution 3 (Algebra w/ Law of Cosines)==<br /> As in the diagram, let &lt;math&gt;DE = x&lt;/math&gt;. Consider point &lt;math&gt;G&lt;/math&gt; on the diagram shown above. Our goal is to be able to perform Pythagorean Theorem on &lt;math&gt;DG, GC&lt;/math&gt;, and &lt;math&gt;DC&lt;/math&gt;. Let &lt;math&gt;GE = 10-x&lt;/math&gt;. Therefore, it is trivial to see that &lt;math&gt;GC^2 = \Big(x + \frac{10-x}{2}\Big)^2&lt;/math&gt; (leave everything squared so that it cancels nicely at the end). By Pythagorean Theorem on Triangle &lt;math&gt;DGE&lt;/math&gt;, we know that &lt;math&gt;DG^2 = x^2 - \Big(\frac{10-x}{2}\Big)^2&lt;/math&gt;. Finally, we apply Law of Cosines on Triangle &lt;math&gt;DBC&lt;/math&gt;. We know that &lt;math&gt;\cos(\angle DBC) = \frac{3}{5}&lt;/math&gt;. Therefore, we get that &lt;math&gt;DC^2 = (10-x)^2 + 12^2 - 2(12)(10-x)\frac{3}{5}&lt;/math&gt;. We can now do our final calculation:<br /> &lt;cmath&gt;<br /> DG^2 + GC^2 = DC^2 \implies x^2 - \Big(\frac{10-x}{2}\Big)^2 + \Big(x + \frac{10-x}{2}\Big)^2 = (10-x)^2 + 12^2 - 2(12)(10-x)\frac{3}{5}<br /> &lt;/cmath&gt;<br /> After some quick cleaning up, we get<br /> &lt;cmath&gt;<br /> 30x = \frac{72}{5} + 100 \implies x = \frac{250}{39}<br /> &lt;/cmath&gt;<br /> Therefore, our answer is &lt;math&gt;250+39=\boxed{289}&lt;/math&gt;.<br /> <br /> ~awesome1st<br /> <br /> <br /> ==Solution 4 (Coordinates)==<br /> Let &lt;math&gt;B = (0, 0)&lt;/math&gt;, &lt;math&gt;C = (12, 0)&lt;/math&gt;, and &lt;math&gt;A = (6, 8)&lt;/math&gt;. Then, let &lt;math&gt;x&lt;/math&gt; be in the interval &lt;math&gt;0&lt;x&lt;2&lt;/math&gt; and parametrically define &lt;math&gt;D&lt;/math&gt; and &lt;math&gt;E&lt;/math&gt; as &lt;math&gt;(6-3x, 8-4x)&lt;/math&gt; and &lt;math&gt;(12-3x, 4x)&lt;/math&gt; respectively. Note that &lt;math&gt;AD = 5x&lt;/math&gt;, so &lt;math&gt;DE = 5x&lt;/math&gt;. This means that<br /> &lt;cmath&gt;\begin{align*}<br /> \sqrt{36+(8x-8)^2} &amp;= 5x\\<br /> 36+(8x-8)^2 &amp;= 25x^2\\<br /> 64x^2-128x+100 &amp;= 25x^2\\<br /> 39x^2-128x+100 &amp;= 0\\<br /> x &amp;= \dfrac{128\pm\sqrt{16384-15600}}{78}\\<br /> x &amp;= \dfrac{100}{78}, 2\\<br /> \end{align*}&lt;/cmath&gt;<br /> However, since &lt;math&gt;2&lt;/math&gt; is extraneous by definition, &lt;math&gt;x=\dfrac{50}{39}\implies AD = \dfrac{250}{39}\implies\boxed{289}&lt;/math&gt; ~ mathwiz0803<br /> <br /> ==Solution 5 (Law of Cosines)==<br /> As shown in the diagram, let &lt;math&gt;x&lt;/math&gt; denote &lt;math&gt;\overline{AD}&lt;/math&gt;. Let us denote the foot of the altitude of &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;\overline{BC}&lt;/math&gt; as &lt;math&gt;F&lt;/math&gt;. Note that &lt;math&gt;\overline{AE}&lt;/math&gt; can be expressed as &lt;math&gt;10-x&lt;/math&gt; and &lt;math&gt;\triangle{ABF}&lt;/math&gt; is a &lt;math&gt;6-8-10&lt;/math&gt; triangle . Therefore, &lt;math&gt;\sin(\angle{BAF})=\frac{3}{5}&lt;/math&gt; and &lt;math&gt;\cos(\angle{BAF})=\frac{4}{5}&lt;/math&gt;. Before we can proceed with the Law of Cosines, we must determine &lt;math&gt;\cos(\angle{BAC})=\cos(2\cdot \angle{BAF})=\cos^2(\angle{BAF})-\sin^2(\angle{BAF})=\frac{7}{25}&lt;/math&gt;. Using LOC, we can write the following statement:<br /> &lt;cmath&gt;(\overline{DE})^2=(\overline{AD})^2+\overline{AE}^2-2(\overline{AD})(\overline{AE})\cos(\angle{BAC})\implies&lt;/cmath&gt;<br /> &lt;cmath&gt;x^2=x^2+(10-x)^2-2(x)(10-x)\left(\frac{7}{25}\right)\implies&lt;/cmath&gt;<br /> &lt;cmath&gt;0=(10-x)^2-\frac{14x}{25}(10-x)\implies&lt;/cmath&gt;<br /> &lt;cmath&gt;0=10-x-\frac{14x}{25}\implies&lt;/cmath&gt;<br /> &lt;cmath&gt;10=\frac{39x}{25}\implies x=\frac{250}{39}&lt;/cmath&gt;<br /> Thus, the desired answer is &lt;math&gt;\boxed{289}&lt;/math&gt; ~ blitzkrieg21<br /> <br /> ==Solution 6==<br /> In isosceles triangle, draw the altitude from &lt;math&gt;D&lt;/math&gt; onto &lt;math&gt;\overline{AD}&lt;/math&gt;. Let the point of intersection be &lt;math&gt;X&lt;/math&gt;. Clearly, &lt;math&gt;AE=10-AD&lt;/math&gt;, and hence &lt;math&gt;AX=\frac{10-AD}{2}&lt;/math&gt;.<br /> <br /> Now, we recognise that the perpendicular from &lt;math&gt;A&lt;/math&gt; onto &lt;math&gt;\overline{AD}&lt;/math&gt; gives us two &lt;math&gt;6&lt;/math&gt;-&lt;math&gt;8&lt;/math&gt;-&lt;math&gt;10&lt;/math&gt; triangles. So, we calculate &lt;math&gt;\sin \angle ABC=\frac{4}{5}&lt;/math&gt; and &lt;math&gt;\cos \angle ABC=\frac{3}{5}&lt;/math&gt;<br /> <br /> &lt;math&gt;\angle BAC = 180-2\cdot\angle ABC&lt;/math&gt;. And hence,<br /> <br /> &lt;math&gt;\cos \angle BAC = \cos \angle (180-2\cdot\angle ABC)<br /> = -\cos (2\cdot\angle ABC)<br /> = \sin^2 \angle ABC - \cos^2 \angle ABC<br /> = 2\cos^2 \angle ABC - 1<br /> = \frac{32}{25}-\frac{25}{25}=\frac{7}{25}&lt;/math&gt;<br /> <br /> Inspecting &lt;math&gt;\triangle ADX&lt;/math&gt; gives us &lt;math&gt;\cos \angle BAC = \frac{\frac{10-x}{2}}{x} = \frac{10-x}{2x}&lt;/math&gt;<br /> Solving the equation &lt;math&gt;\frac{10-x}{2x}=\frac{7}{25}&lt;/math&gt; gives &lt;math&gt;x= \frac{250}{39} \implies\boxed{289}&lt;/math&gt;<br /> <br /> ~novus677<br /> <br /> ==Solution 7 (Fastest via Law of Cosines)==<br /> We can have 2 Law of Cosines applied on &lt;math&gt;\angle A&lt;/math&gt; (one from &lt;math&gt;\triangle ADE&lt;/math&gt; and one from &lt;math&gt;\triangle ABC&lt;/math&gt;),<br /> <br /> &lt;math&gt;x^2=x^2+(10-x)^2-2(x)(10-x)\cdot \cos{A}&lt;/math&gt; and &lt;math&gt;12^2=10^2+10^2-2(10)(10)\cdot \cos{A}&lt;/math&gt;<br /> <br /> Solving for &lt;math&gt;\cos{A}&lt;/math&gt; in both equations, we get<br /> <br /> &lt;math&gt;\cos{A} = \frac{(10-x)^2}{(2)(10-x)(x)}&lt;/math&gt; and &lt;math&gt;cos A = \frac{7}{25} \implies \frac{(10-x)^2}{(2)(10-x)(x)} = \frac{7}{25} \implies x = \frac{250}{39}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed {289}&lt;/math&gt; <br /> <br /> '''-RootThreeOverTwo'''<br /> <br /> ==Solution 8 (Easiest way- Coordinates without bash)==<br /> Let &lt;math&gt;B=(0, 0)&lt;/math&gt;, and &lt;math&gt;C=(12, 0)&lt;/math&gt;. From there, we know that &lt;math&gt;A=(6, 8)&lt;/math&gt;, so line &lt;math&gt;AB&lt;/math&gt; is &lt;math&gt;y=\frac{4}{3}x&lt;/math&gt;. Hence, &lt;math&gt;D=(a, \frac{4}{3}a)&lt;/math&gt; for some &lt;math&gt;a&lt;/math&gt;, and &lt;math&gt;BD=\frac{5}{3}a&lt;/math&gt; so &lt;math&gt;AD=10-\frac{5}{3}a&lt;/math&gt;. Now, notice that by symmetry, &lt;math&gt;E=(6+a, 8-\frac{4}{3}a)&lt;/math&gt;, so &lt;math&gt;ED^2=6^2+(8-\frac{8}{3}a)^2&lt;/math&gt;. Because &lt;math&gt;AD=ED&lt;/math&gt;, we now have &lt;math&gt;(10-\frac{5}{3})^2=6^2+(8-\frac{8}{3}a)^2&lt;/math&gt;, which simplifies to &lt;math&gt;\frac{64}{9}a^2-\frac{128}{3}a+100=\frac{25}{9}a^2-\frac{100}{3}a+100&lt;/math&gt;, so &lt;math&gt;\frac{39}{9}a=\frac{13}{3}a=\frac{28}{3}&lt;/math&gt;, and &lt;math&gt;a=\frac{28}{13}&lt;/math&gt;.<br /> It follows that &lt;math&gt;AD=10-\frac{5}{3}\times\frac{28}{13}=10-\frac{140}{39}=\frac{390-140}{39}=\frac{250}{39}&lt;/math&gt;, and our answer is &lt;math&gt;250+39=\boxed{289}&lt;/math&gt;.<br /> <br /> -Stormersyle<br /> <br /> == Solution 9 Even Faster Law of Cosines(1 variable equation)==<br /> <br /> Doing law of cosines we know that &lt;math&gt;\cos A&lt;/math&gt; is &lt;math&gt;\frac{7}{25}.&lt;/math&gt;* Dropping the perpendicular from &lt;math&gt;D&lt;/math&gt; to &lt;math&gt;AE&lt;/math&gt; we get that &lt;cmath&gt;\frac{10-x}{2}=\frac{7x}{25}.&lt;/cmath&gt; <br /> Solving for &lt;math&gt;x&lt;/math&gt; we get &lt;math&gt;\frac{250}{39}&lt;/math&gt; so our answer is &lt;math&gt;289&lt;/math&gt;.<br /> <br /> -harsha12345<br /> <br /> * It is good to remember that doubling the smallest angle of a 3-4-5 triangle gives the larger (not right) angle in a 7-24-25 triangle.<br /> <br /> == Solution 10 (Law of Sines)==<br /> <br /> Let's label &lt;math&gt;\angle A = \theta&lt;/math&gt; and &lt;math&gt;\angle ECD = \alpha&lt;/math&gt;. Using isosceles triangle properties and the triangle angle sum equation, we get &lt;cmath&gt;180-(180-2\theta+\alpha) + \frac{180-\theta}{2} + \left(\frac{180-\theta}{2} - \alpha\right) = 180.&lt;/cmath&gt; Solving, we find &lt;math&gt;\theta = 2 \alpha&lt;/math&gt;. <br /> <br /> <br /> Relabelling our triangle, we get &lt;math&gt;\angle ABC = 90 - \alpha&lt;/math&gt;. Dropping an altitude from &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;BC&lt;/math&gt; and using the Pythagorean theorem, we find &lt;math&gt;[ABC] = 48&lt;/math&gt;. Using the sine area formula, we see &lt;math&gt;\frac12 \cdot 10 \cdot 12 \cdot \sin(90-\alpha) = 48&lt;/math&gt;. Plugging in our sine angle cofunction identity, &lt;math&gt;\sin(90-\alpha) = \cos(\alpha)&lt;/math&gt;, we get &lt;math&gt;\alpha = \cos{^{-1}}{\frac45}&lt;/math&gt;. <br /> <br /> <br /> Now, using the Law of Sines on &lt;math&gt;\triangle ADE&lt;/math&gt;, we get &lt;cmath&gt;\frac{\sin{2\alpha}}{\frac{p}{q}} = \frac{\sin{(180-4\alpha)}}{10-\frac{p}{q}}.&lt;/cmath&gt; After applying numerous trigonometric and algebraic tricks, identities, and simplifications, such as &lt;math&gt;\sin{(180-4\alpha)}=\sin{4\alpha}&lt;/math&gt; and &lt;math&gt;\sin{\left(\cos{^{-1}}{\frac45}\right)} = \frac35&lt;/math&gt;, we find &lt;math&gt;\frac{p}{q} = \frac{10\sin{2\alpha}}{\sin{4\alpha}+\sin{2\alpha}} = \frac{250}{39}&lt;/math&gt;. <br /> <br /> <br /> <br /> Therefore, our answer is &lt;math&gt;250 + 39 = \boxed{289}&lt;/math&gt;.<br /> <br /> <br /> ~Tiblis<br /> <br /> ==Video Solution==<br /> <br /> https://www.youtube.com/watch?v=iE8paW_ICxw<br /> <br /> ==See Also==<br /> {{AIME box|year=2018|n=I|num-b=3|num-a=5}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_9&diff=128936 2019 AIME II Problems/Problem 9 2020-07-23T05:04:13Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>==Problem 9==<br /> Call a positive integer &lt;math&gt;n&lt;/math&gt; &lt;math&gt;k&lt;/math&gt;-&lt;i&gt;pretty&lt;/i&gt; if &lt;math&gt;n&lt;/math&gt; has exactly &lt;math&gt;k&lt;/math&gt; positive divisors and &lt;math&gt;n&lt;/math&gt; is divisible by &lt;math&gt;k&lt;/math&gt;. For example, &lt;math&gt;18&lt;/math&gt; is &lt;math&gt;6&lt;/math&gt;-pretty. Let &lt;math&gt;S&lt;/math&gt; be the sum of positive integers less than &lt;math&gt;2019&lt;/math&gt; that are &lt;math&gt;20&lt;/math&gt;-pretty. Find &lt;math&gt;\tfrac{S}{20}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Every 20-pretty integer can be written in form &lt;math&gt;n = 2^a 5^b k&lt;/math&gt;, where &lt;math&gt;a \ge 2&lt;/math&gt;, &lt;math&gt;b \ge 1&lt;/math&gt;, &lt;math&gt;\gcd(k,10) = 1&lt;/math&gt;, and &lt;math&gt;d(n) = 20&lt;/math&gt;, where &lt;math&gt;d(n)&lt;/math&gt; is the number of divisors of &lt;math&gt;n&lt;/math&gt;. Thus, we have &lt;math&gt;20 = (a+1)(b+1)d(k)&lt;/math&gt;, using the fact that the divisor function is multiplicative. As &lt;math&gt;(a+1)(b+1)&lt;/math&gt; must be a divisor of 20, there are not many cases to check.<br /> <br /> If &lt;math&gt;a+1 = 4&lt;/math&gt;, then &lt;math&gt;b+1 = 5&lt;/math&gt;. But this leads to no solutions, as &lt;math&gt;(a,b) = (3,4)&lt;/math&gt; gives &lt;math&gt;2^3 5^4 &gt; 2019&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 5&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;. The first case gives &lt;math&gt;n = 2^4 \cdot 5^1 \cdot p&lt;/math&gt; where &lt;math&gt;p&lt;/math&gt; is a prime other than 2 or 5. Thus we have &lt;math&gt;80p &lt; 2019 \implies p = 3, 7, 11, 13, 17, 19, 23&lt;/math&gt;. The sum of all such &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;80(3+7+11+13+17+19+23) = 7440&lt;/math&gt;. In the second case &lt;math&gt;b+1 = 4&lt;/math&gt; and &lt;math&gt;d(k) = 1&lt;/math&gt;, and there is one solution &lt;math&gt;n = 2^4 \cdot 5^3 = 2000&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 10&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt;, but this gives &lt;math&gt;2^9 \cdot 5^1 &gt; 2019&lt;/math&gt;. No other values for &lt;math&gt;a+1&lt;/math&gt; work.<br /> <br /> Then we have &lt;math&gt;\frac{S}{20} = \frac{80(3+7+11+13+17+19+23) + 2000}{20} = 372 + 100 = \boxed{472}&lt;/math&gt;.<br /> <br /> -scrabbler94<br /> <br /> ==Solution 2==<br /> For &lt;math&gt;n&lt;/math&gt; to have exactly &lt;math&gt;20&lt;/math&gt; positive divisors, &lt;math&gt;n&lt;/math&gt; can only take on certain prime factorization forms: namely, &lt;math&gt;p^{19}, p^9q, p^4q^3, p^4qr&lt;/math&gt;. No number that is a multiple of &lt;math&gt;20&lt;/math&gt; can be expressed in the first form, and the only integer divisible by &lt;math&gt;20&lt;/math&gt; that has the second form is &lt;math&gt;2^{9}5&lt;/math&gt;, which is greater than &lt;math&gt;2019&lt;/math&gt;. <br /> <br /> For the third form, the only &lt;math&gt;20&lt;/math&gt;-pretty numbers are &lt;math&gt;2^45^3=2000&lt;/math&gt; and &lt;math&gt;2^35^4=5000&lt;/math&gt;, and only &lt;math&gt;2000&lt;/math&gt; is small enough. <br /> <br /> For the fourth form, any number of the form &lt;math&gt;2^45r&lt;/math&gt; where &lt;math&gt;r&lt;/math&gt; is a prime other than &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; will satisfy the &lt;math&gt;20&lt;/math&gt;-pretty requirement. Since &lt;math&gt;n=80r&lt;2019&lt;/math&gt;, &lt;math&gt;r\le 25&lt;/math&gt;. Therefore, &lt;math&gt;r&lt;/math&gt; can take on &lt;math&gt;3, 7, 11, 13, 17, 19,&lt;/math&gt; or &lt;math&gt;23&lt;/math&gt;. <br /> <br /> Thus, &lt;math&gt;\frac{S}{20}=\frac{2000+80(3+7+11+...+23)}{20}=100+4(3+7+11+...+23)=\boxed{472}&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> <br /> The divisors of &lt;math&gt;20&lt;/math&gt; are &lt;math&gt;{1,2,4,5,10,20}&lt;/math&gt;. &lt;math&gt;v_n(2)&lt;/math&gt; must be &lt;math&gt;\ge 2&lt;/math&gt; because &lt;math&gt;20=2^2 \times 5&lt;/math&gt;. This means that &lt;math&gt;v_n(2)&lt;/math&gt; can be exactly &lt;math&gt;3&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;.<br /> <br /> 1. &lt;math&gt;v_n(2) = 3&lt;/math&gt;. Then &lt;math&gt;\frac{20}{4}=5=5\times 1&lt;/math&gt;. The smallest is &lt;math&gt;2^3*5^4&lt;/math&gt; which is &lt;math&gt;&gt; 2019&lt;/math&gt;. Hence there are no solution in this case.<br /> <br /> 2. &lt;math&gt;v_n(2)=4&lt;/math&gt;. Then &lt;math&gt;\frac{20}{5}=4 = 4\times 1 = 2\times 2&lt;/math&gt;.<br /> The &lt;math&gt;4\times 1&lt;/math&gt; case gives one solution, &lt;math&gt;2^4 \times 5^3 = 2000&lt;/math&gt;.<br /> The &lt;math&gt;2\times 2&lt;/math&gt; case gives &lt;math&gt;2^4\times 5 \times (3+7+11+13+17+19+23)&lt;/math&gt;.Using any prime greater than &lt;math&gt;23&lt;/math&gt; will make &lt;math&gt;n&lt;/math&gt; greater than &lt;math&gt;2019&lt;/math&gt;.<br /> <br /> The answer is &lt;math&gt;\frac{1}{20}(2000+80(3+7+..+23)) = 472&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AIME box|year=2019|n=II|num-b=8|num-a=10}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_9&diff=128935 2019 AIME II Problems/Problem 9 2020-07-23T05:00:59Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>==Problem 9==<br /> Call a positive integer &lt;math&gt;n&lt;/math&gt; &lt;math&gt;k&lt;/math&gt;-&lt;i&gt;pretty&lt;/i&gt; if &lt;math&gt;n&lt;/math&gt; has exactly &lt;math&gt;k&lt;/math&gt; positive divisors and &lt;math&gt;n&lt;/math&gt; is divisible by &lt;math&gt;k&lt;/math&gt;. For example, &lt;math&gt;18&lt;/math&gt; is &lt;math&gt;6&lt;/math&gt;-pretty. Let &lt;math&gt;S&lt;/math&gt; be the sum of positive integers less than &lt;math&gt;2019&lt;/math&gt; that are &lt;math&gt;20&lt;/math&gt;-pretty. Find &lt;math&gt;\tfrac{S}{20}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Every 20-pretty integer can be written in form &lt;math&gt;n = 2^a 5^b k&lt;/math&gt;, where &lt;math&gt;a \ge 2&lt;/math&gt;, &lt;math&gt;b \ge 1&lt;/math&gt;, &lt;math&gt;\gcd(k,10) = 1&lt;/math&gt;, and &lt;math&gt;d(n) = 20&lt;/math&gt;, where &lt;math&gt;d(n)&lt;/math&gt; is the number of divisors of &lt;math&gt;n&lt;/math&gt;. Thus, we have &lt;math&gt;20 = (a+1)(b+1)d(k)&lt;/math&gt;, using the fact that the divisor function is multiplicative. As &lt;math&gt;(a+1)(b+1)&lt;/math&gt; must be a divisor of 20, there are not many cases to check.<br /> <br /> If &lt;math&gt;a+1 = 4&lt;/math&gt;, then &lt;math&gt;b+1 = 5&lt;/math&gt;. But this leads to no solutions, as &lt;math&gt;(a,b) = (3,4)&lt;/math&gt; gives &lt;math&gt;2^3 5^4 &gt; 2019&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 5&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;. The first case gives &lt;math&gt;n = 2^4 \cdot 5^1 \cdot p&lt;/math&gt; where &lt;math&gt;p&lt;/math&gt; is a prime other than 2 or 5. Thus we have &lt;math&gt;80p &lt; 2019 \implies p = 3, 7, 11, 13, 17, 19, 23&lt;/math&gt;. The sum of all such &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;80(3+7+11+13+17+19+23) = 7440&lt;/math&gt;. In the second case &lt;math&gt;b+1 = 4&lt;/math&gt; and &lt;math&gt;d(k) = 1&lt;/math&gt;, and there is one solution &lt;math&gt;n = 2^4 \cdot 5^3 = 2000&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 10&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt;, but this gives &lt;math&gt;2^9 \cdot 5^1 &gt; 2019&lt;/math&gt;. No other values for &lt;math&gt;a+1&lt;/math&gt; work.<br /> <br /> Then we have &lt;math&gt;\frac{S}{20} = \frac{80(3+7+11+13+17+19+23) + 2000}{20} = 372 + 100 = \boxed{472}&lt;/math&gt;.<br /> <br /> -scrabbler94<br /> <br /> ==Solution 2==<br /> For &lt;math&gt;n&lt;/math&gt; to have exactly &lt;math&gt;20&lt;/math&gt; positive divisors, &lt;math&gt;n&lt;/math&gt; can only take on certain prime factorization forms: namely, &lt;math&gt;p^{19}, p^9q, p^4q^3, p^4qr&lt;/math&gt;. No number that is a multiple of &lt;math&gt;20&lt;/math&gt; can be expressed in the first form, and the only integer divisible by &lt;math&gt;20&lt;/math&gt; that has the second form is &lt;math&gt;2^{9}5&lt;/math&gt;, which is greater than &lt;math&gt;2019&lt;/math&gt;. <br /> <br /> For the third form, the only &lt;math&gt;20&lt;/math&gt;-pretty numbers are &lt;math&gt;2^45^3=2000&lt;/math&gt; and &lt;math&gt;2^35^4=5000&lt;/math&gt;, and only &lt;math&gt;2000&lt;/math&gt; is small enough. <br /> <br /> For the fourth form, any number of the form &lt;math&gt;2^45r&lt;/math&gt; where &lt;math&gt;r&lt;/math&gt; is a prime other than &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; will satisfy the &lt;math&gt;20&lt;/math&gt;-pretty requirement. Since &lt;math&gt;n=80r&lt;2019&lt;/math&gt;, &lt;math&gt;r\le 25&lt;/math&gt;. Therefore, &lt;math&gt;r&lt;/math&gt; can take on &lt;math&gt;3, 7, 11, 13, 17, 19,&lt;/math&gt; or &lt;math&gt;23&lt;/math&gt;. <br /> <br /> Thus, &lt;math&gt;\frac{S}{20}=\frac{2000+80(3+7+11+...+23)}{20}=100+4(3+7+11+...+23)=\boxed{472}&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> <br /> The divisors of &lt;math&gt;20&lt;/math&gt; are &lt;math&gt;{1,2,4,5,10,20}&lt;/math&gt;. &lt;math&gt;v_n(2)&lt;/math&gt; must be &lt;math&gt;\ge 2&lt;/math&gt; because &lt;math&gt;20=2^2 \times 5&lt;/math&gt;. This means that &lt;math&gt;v_n(2)&lt;/math&gt; can be exactly &lt;math&gt;3&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;.<br /> <br /> 1. &lt;math&gt;v_n(2) = 3&lt;/math&gt;. Then &lt;math&gt;\frac{20}{4}=5=5\times 1&lt;/math&gt;. The smallest is &lt;math&gt;2^3*5^4&lt;/math&gt; which is &lt;math&gt;&gt; 2019&lt;/math&gt;. Hence there are no solution in this case.<br /> <br /> 2. &lt;math&gt;v_n(2)=4&lt;/math&gt;. Then &lt;math&gt;\frac{20}{5}=4 = 4\times 1 = 2\times 2&lt;/math&gt;.<br /> The &lt;math&gt;4\times 1&lt;/math&gt; case gives one solution, &lt;math&gt;2^4 \times 5^3 = 2000&lt;/math&gt;.<br /> The &lt;math&gt;2\times 2&lt;/math&gt; case gives &lt;math&gt;2^4\times 5 \times (3+7+11+13+17+19+23)&lt;/math&gt;. Any prime greater than &lt;math&gt;23&lt;/math&gt; will exceed &lt;math&gt;2019&lt;/math&gt;<br /> <br /> The answer is &lt;math&gt;\frac{1}{20}(2000+80(3+7+..+23)) = 472&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AIME box|year=2019|n=II|num-b=8|num-a=10}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_9&diff=128934 2019 AIME II Problems/Problem 9 2020-07-23T04:59:33Z <p>Mysteryguy6647: /* Solution 2 */</p> <hr /> <div>==Problem 9==<br /> Call a positive integer &lt;math&gt;n&lt;/math&gt; &lt;math&gt;k&lt;/math&gt;-&lt;i&gt;pretty&lt;/i&gt; if &lt;math&gt;n&lt;/math&gt; has exactly &lt;math&gt;k&lt;/math&gt; positive divisors and &lt;math&gt;n&lt;/math&gt; is divisible by &lt;math&gt;k&lt;/math&gt;. For example, &lt;math&gt;18&lt;/math&gt; is &lt;math&gt;6&lt;/math&gt;-pretty. Let &lt;math&gt;S&lt;/math&gt; be the sum of positive integers less than &lt;math&gt;2019&lt;/math&gt; that are &lt;math&gt;20&lt;/math&gt;-pretty. Find &lt;math&gt;\tfrac{S}{20}&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Every 20-pretty integer can be written in form &lt;math&gt;n = 2^a 5^b k&lt;/math&gt;, where &lt;math&gt;a \ge 2&lt;/math&gt;, &lt;math&gt;b \ge 1&lt;/math&gt;, &lt;math&gt;\gcd(k,10) = 1&lt;/math&gt;, and &lt;math&gt;d(n) = 20&lt;/math&gt;, where &lt;math&gt;d(n)&lt;/math&gt; is the number of divisors of &lt;math&gt;n&lt;/math&gt;. Thus, we have &lt;math&gt;20 = (a+1)(b+1)d(k)&lt;/math&gt;, using the fact that the divisor function is multiplicative. As &lt;math&gt;(a+1)(b+1)&lt;/math&gt; must be a divisor of 20, there are not many cases to check.<br /> <br /> If &lt;math&gt;a+1 = 4&lt;/math&gt;, then &lt;math&gt;b+1 = 5&lt;/math&gt;. But this leads to no solutions, as &lt;math&gt;(a,b) = (3,4)&lt;/math&gt; gives &lt;math&gt;2^3 5^4 &gt; 2019&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 5&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;. The first case gives &lt;math&gt;n = 2^4 \cdot 5^1 \cdot p&lt;/math&gt; where &lt;math&gt;p&lt;/math&gt; is a prime other than 2 or 5. Thus we have &lt;math&gt;80p &lt; 2019 \implies p = 3, 7, 11, 13, 17, 19, 23&lt;/math&gt;. The sum of all such &lt;math&gt;n&lt;/math&gt; is &lt;math&gt;80(3+7+11+13+17+19+23) = 7440&lt;/math&gt;. In the second case &lt;math&gt;b+1 = 4&lt;/math&gt; and &lt;math&gt;d(k) = 1&lt;/math&gt;, and there is one solution &lt;math&gt;n = 2^4 \cdot 5^3 = 2000&lt;/math&gt;.<br /> <br /> If &lt;math&gt;a+1 = 10&lt;/math&gt;, then &lt;math&gt;b+1 = 2&lt;/math&gt;, but this gives &lt;math&gt;2^9 \cdot 5^1 &gt; 2019&lt;/math&gt;. No other values for &lt;math&gt;a+1&lt;/math&gt; work.<br /> <br /> Then we have &lt;math&gt;\frac{S}{20} = \frac{80(3+7+11+13+17+19+23) + 2000}{20} = 372 + 100 = \boxed{472}&lt;/math&gt;.<br /> <br /> -scrabbler94<br /> <br /> ==Solution 2==<br /> For &lt;math&gt;n&lt;/math&gt; to have exactly &lt;math&gt;20&lt;/math&gt; positive divisors, &lt;math&gt;n&lt;/math&gt; can only take on certain prime factorization forms: namely, &lt;math&gt;p^{19}, p^9q, p^4q^3, p^4qr&lt;/math&gt;. No number that is a multiple of &lt;math&gt;20&lt;/math&gt; can be expressed in the first form, and the only integer divisible by &lt;math&gt;20&lt;/math&gt; that has the second form is &lt;math&gt;2^{9}5&lt;/math&gt;, which is greater than &lt;math&gt;2019&lt;/math&gt;. <br /> <br /> For the third form, the only &lt;math&gt;20&lt;/math&gt;-pretty numbers are &lt;math&gt;2^45^3=2000&lt;/math&gt; and &lt;math&gt;2^35^4=5000&lt;/math&gt;, and only &lt;math&gt;2000&lt;/math&gt; is small enough. <br /> <br /> For the fourth form, any number of the form &lt;math&gt;2^45r&lt;/math&gt; where &lt;math&gt;r&lt;/math&gt; is a prime other than &lt;math&gt;2&lt;/math&gt; or &lt;math&gt;5&lt;/math&gt; will satisfy the &lt;math&gt;20&lt;/math&gt;-pretty requirement. Since &lt;math&gt;n=80r&lt;2019&lt;/math&gt;, &lt;math&gt;r\le 25&lt;/math&gt;. Therefore, &lt;math&gt;r&lt;/math&gt; can take on &lt;math&gt;3, 7, 11, 13, 17, 19,&lt;/math&gt; or &lt;math&gt;23&lt;/math&gt;. <br /> <br /> Thus, &lt;math&gt;\frac{S}{20}=\frac{2000+80(3+7+11+...+23)}{20}=100+4(3+7+11+...+23)=\boxed{472}&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> <br /> The divisors of &lt;math&gt;20&lt;/math&gt; are &lt;math&gt;{1,2,4,5,10,20}&lt;/math&gt;. &lt;math&gt;v_n(2)&lt;/math&gt; must be &lt;math&gt;\ge 2&lt;/math&gt; because &lt;math&gt;20=2^2 \times 5&lt;/math&gt;. This means that &lt;math&gt;v_n(2)&lt;/math&gt; can be exactly &lt;math&gt;3&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;.<br /> <br /> 1. &lt;math&gt;v_n(2) = 3&lt;/math&gt;. Then &lt;math&gt;\frac{20}{4}=5=5\times 1&lt;/math&gt;. The smallest is &lt;math&gt;2^3*5^4&lt;/math&gt; which is &lt;math&gt;&gt; 2019&lt;/math&gt;. Hence there are no solution in this case<br /> 2. &lt;math&gt;v_n(2)=4&lt;/math&gt;. Then &lt;math&gt;\frac{20}{5}=4 = 4\times 1 = 2\times 2&lt;/math&gt;.<br /> The &lt;math&gt;4\times 1&lt;/math&gt; case gives one solution, &lt;math&gt;2^4 \times 5^3 = 2000&lt;/math&gt;.<br /> The &lt;math&gt;2\times 2&lt;/math&gt; case gives &lt;math&gt;2^4\times 5 \times (3+7+11+13+17+19+23)&lt;/math&gt;. Any prime greater than &lt;math&gt;23&lt;/math&gt; will exceed &lt;math&gt;2019&lt;/math&gt;<br /> <br /> The answer is &lt;math&gt;\frac{1}{20}(2000+80(3+7+..+23)) = 472&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{AIME box|year=2019|n=II|num-b=8|num-a=10}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_2&diff=128735 2019 AIME I Problems/Problem 2 2020-07-20T09:25:29Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>==Problem 2==<br /> Jenn randomly chooses a number &lt;math&gt;J&lt;/math&gt; from &lt;math&gt;1, 2, 3,\ldots, 19, 20&lt;/math&gt;. Bela then randomly chooses a number &lt;math&gt;B&lt;/math&gt; from &lt;math&gt;1, 2, 3,\ldots, 19, 20&lt;/math&gt; distinct from &lt;math&gt;J&lt;/math&gt;. The value of &lt;math&gt;B - J&lt;/math&gt; is at least &lt;math&gt;2&lt;/math&gt; with a probability that can be expressed in the form &lt;math&gt;\frac{m}{n}&lt;/math&gt; where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> ==Solution==<br /> The probability that &lt;math&gt;B-J&lt;0&lt;/math&gt; is &lt;math&gt;\frac{1}{2}&lt;/math&gt; by symmetry.<br /> The probability that &lt;math&gt;B-J= 1&lt;/math&gt; is &lt;math&gt;\frac{19}{20 \times 19} = \frac{1}{20}&lt;/math&gt; because there are 19 pairs: &lt;math&gt;(B,J) = (2,1),.., (20,19)&lt;/math&gt;.<br /> <br /> The probability that &lt;math&gt;B-J &gt;2&lt;/math&gt; is &lt;math&gt;1-\frac{1}{2}-\frac{1}{20} = \frac{9}{20} \implies \boxed{29}&lt;/math&gt;<br /> ==Solution==<br /> By symmetry, the desired probability is equal to the probability that &lt;math&gt;J - B&lt;/math&gt; is at most &lt;math&gt;-2&lt;/math&gt;, which is &lt;math&gt;\frac{1-P}{2}&lt;/math&gt; where &lt;math&gt;P&lt;/math&gt; is the probability that &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt; differ by &lt;math&gt;1&lt;/math&gt; (no zero, because the two numbers are distinct). There are &lt;math&gt;20 * 19 = 380&lt;/math&gt; total possible combinations of &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt;, and &lt;math&gt;1 + 18 * 2 + 1 = 38&lt;/math&gt; ones that form &lt;math&gt;P&lt;/math&gt;, so &lt;math&gt;P = \frac{38}{380} = \frac{1}{10}&lt;/math&gt;. Therefore the answer is &lt;math&gt;\frac{9}{20} \rightarrow \boxed{029}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> This problem is essentially asking how many ways there are to choose &lt;math&gt;2&lt;/math&gt; distinct elements from a &lt;math&gt;20&lt;/math&gt; element set such that no &lt;math&gt;2&lt;/math&gt; elements are adjacent. Using the well-known formula &lt;math&gt;\dbinom{n-k+1}{k}&lt;/math&gt;, there are &lt;math&gt;\dbinom{20-2+1}{2} = \dbinom{19}{2} = 171&lt;/math&gt; ways. Dividing &lt;math&gt;171&lt;/math&gt; by &lt;math&gt;380&lt;/math&gt;, our desired probability is &lt;math&gt;\frac{171}{380} = \frac{9}{20}&lt;/math&gt;. Thus, our answer is &lt;math&gt;9+20=\boxed{029}&lt;/math&gt;.<br /> -Fidgetboss_4000<br /> <br /> ==Solution 3==<br /> Create a grid using graph paper, with &lt;math&gt;20&lt;/math&gt; columns for the values of &lt;math&gt;J&lt;/math&gt; from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;20&lt;/math&gt; and &lt;math&gt;20&lt;/math&gt; rows for the values of &lt;math&gt;B&lt;/math&gt; from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;20&lt;/math&gt;. Since &lt;math&gt;B&lt;/math&gt; cannot equal &lt;math&gt;J&lt;/math&gt;, we cross out the diagonal line from the first column of the first row to the twentieth column of the last row. Now, since &lt;math&gt;B - J&lt;/math&gt; must be at least &lt;math&gt;2&lt;/math&gt;, we can mark the line where &lt;math&gt;B - J = 2&lt;/math&gt;. Now we sum the number of squares that are on this line and below it. We get &lt;math&gt;171&lt;/math&gt;. Then we find the number of total squares, which is &lt;math&gt;400 - 20 = 380&lt;/math&gt;. Finally, we take the ratio &lt;math&gt;\frac{171}{380}&lt;/math&gt;, which simplifies to &lt;math&gt;\frac{9}{20}&lt;/math&gt;. Our answer is &lt;math&gt;9+20=\boxed{029}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> We can see that if &lt;math&gt;B&lt;/math&gt; chooses &lt;math&gt;20&lt;/math&gt;, &lt;math&gt;J&lt;/math&gt; can choose from &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;18&lt;/math&gt; such that &lt;math&gt;B-J\geq 2&lt;/math&gt;. If &lt;math&gt;B&lt;/math&gt; chooses &lt;math&gt;19&lt;/math&gt;, &lt;math&gt;J&lt;/math&gt; has choices &lt;math&gt;1&lt;/math&gt;~&lt;math&gt;17&lt;/math&gt;. By continuing this pattern, &lt;math&gt;B&lt;/math&gt; will choose &lt;math&gt;3&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt; will have &lt;math&gt;1&lt;/math&gt; option. Summing up the total, we get &lt;math&gt;18+17+\cdots+1&lt;/math&gt; as the total number of solutions. The total amount of choices is &lt;math&gt;20\times19&lt;/math&gt; (B and J must choose different numbers), so the probability is &lt;math&gt;\frac{18*19/2}{20*19}=\frac{9}{20}&lt;/math&gt;. Therefore, the answer is &lt;math&gt;9+20=\boxed{029}&lt;/math&gt;<br /> <br /> -eric2020<br /> <br /> ==Solution 5==<br /> Similar to solution 4, we can go through the possible values of &lt;math&gt;J&lt;/math&gt; to find all the values of &lt;math&gt;B&lt;/math&gt; that makes &lt;math&gt;B-J\geq 2&lt;/math&gt;. If &lt;math&gt;J&lt;/math&gt; chooses &lt;math&gt;1&lt;/math&gt;, then &lt;math&gt;B&lt;/math&gt; can choose anything from &lt;math&gt;3&lt;/math&gt; to &lt;math&gt;20&lt;/math&gt;. If &lt;math&gt;J&lt;/math&gt; chooses &lt;math&gt;2&lt;/math&gt;, then &lt;math&gt;B&lt;/math&gt; can choose anything from &lt;math&gt;4&lt;/math&gt; to &lt;math&gt;20&lt;/math&gt;. By continuing this pattern, we can see that there is &lt;math&gt;18+17+\cdots+1&lt;/math&gt; possible solutions. The amount of solutions is, therefore, &lt;math&gt;\frac{18*19}{2}=171&lt;/math&gt;. Now, because &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;J&lt;/math&gt; must be different, we have &lt;math&gt;20\times19=380&lt;/math&gt; possible choices, so the probability is &lt;math&gt;\frac{171}{380}=\frac{9}{20}&lt;/math&gt;. Therefore, the final answer is &lt;math&gt;9+20=\boxed{029}&lt;/math&gt;<br /> <br /> -josephwidjaja<br /> <br /> ==Video Solution ==<br /> https://www.youtube.com/watch?v=lh570eu8E0E<br /> <br /> ==Video Solution 2==<br /> https://youtu.be/TSKcjht8Rfk?t=488<br /> <br /> ~IceMatrix<br /> <br /> ==Video Solution 3==<br /> https://www.youtube.com/watch?v=nbtIBP6Auig&amp;t=460s<br /> <br /> ==See Also==<br /> {{AIME box|year=2019|n=I|num-b=1|num-a=3}}<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2003_AIME_I_Problems/Problem_13&diff=126559 2003 AIME I Problems/Problem 13 2020-06-26T10:34:02Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt; N &lt;/math&gt; be the number of positive integers that are less than or equal to &lt;math&gt;2003&lt;/math&gt; and whose base-&lt;math&gt;2&lt;/math&gt; representation has more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s. Find the [[remainder]] when &lt;math&gt; N &lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> In base-&lt;math&gt;2&lt;/math&gt; representation, all positive numbers have a leftmost digit of &lt;math&gt;1&lt;/math&gt;. Thus there are &lt;math&gt;{n \choose k}&lt;/math&gt; numbers that have &lt;math&gt;n+1&lt;/math&gt; digits in base &lt;math&gt;2&lt;/math&gt; notation, with &lt;math&gt;k+1&lt;/math&gt; of the digits being &lt;math&gt;1&lt;/math&gt;'s. <br /> <br /> In order for there to be more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s, we must have &lt;math&gt;k+1 &gt; \frac{d+1}{2} \Longrightarrow k &gt; \frac{d-1}{2} \Longrightarrow k \ge \frac{d}{2}&lt;/math&gt;. Therefore, the number of such numbers corresponds to the sum of all numbers on or to the right of the vertical line of symmetry in [[Pascal's Triangle]], from rows &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;10&lt;/math&gt; (as &lt;math&gt;2003 &lt; 2^{11}-1&lt;/math&gt;). Since the sum of the elements of the &lt;math&gt;r&lt;/math&gt;th row is &lt;math&gt;2^r&lt;/math&gt;, it follows that the sum of all elements in rows &lt;math&gt;0&lt;/math&gt; through &lt;math&gt;10&lt;/math&gt; is &lt;math&gt;2^0 + 2^1 + \cdots + 2^{10} = 2^{11}-1 = 2047&lt;/math&gt;. The center elements are in the form &lt;math&gt;{2i \choose i}&lt;/math&gt;, so the sum of these elements is &lt;math&gt;\sum_{i=0}^{5} {2i \choose i} = 1 + 2 +6 + 20 + 70 + 252 = 351&lt;/math&gt;.<br /> <br /> The sum of the elements on or to the right of the line of symmetry is thus &lt;math&gt;\frac{2047 + 351}{2} = 1199&lt;/math&gt;. However, we also counted the &lt;math&gt;44&lt;/math&gt; numbers from &lt;math&gt;2004&lt;/math&gt; to &lt;math&gt;2^{11}-1 = 2047&lt;/math&gt;. Indeed, all of these numbers have at least &lt;math&gt;6&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s in their base-&lt;math&gt;2&lt;/math&gt; representation, as all of them are greater than &lt;math&gt;1984 = 11111000000_2&lt;/math&gt;, which has &lt;math&gt;5&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s. Therefore, our answer is &lt;math&gt;1199 - 44 = 1155&lt;/math&gt;, and the remainder is &lt;math&gt;\boxed{155}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> We seek the number of allowed numbers which have &lt;math&gt; k&lt;/math&gt; 1's, not including the leading 1, for &lt;math&gt; k=0, 1, 2, \ldots , 10&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=0,\ldots , 4&lt;/math&gt;, this number is<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{2k}{k}&lt;/math&gt;.<br /> <br /> By the Hockey Stick Identity, this is equal to &lt;math&gt; \binom{2k+1}{k+1}&lt;/math&gt;. So we get<br /> <br /> &lt;math&gt; \binom{1}{1}+\binom{3}{2}+\binom{5}{3}+\binom{7}{4}+\binom{9}{5}=175&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=5,\ldots , 10&lt;/math&gt;, we end on &lt;math&gt; \binom{10}{k}&lt;/math&gt; - we don't want to consider numbers with more than 11 digits. So for each &lt;math&gt; k&lt;/math&gt; we get<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{10}{k}=\binom{11}{k+1}&lt;/math&gt;<br /> <br /> again by the Hockey Stick Identity. So we get<br /> <br /> &lt;math&gt; \binom{11}{6}+\binom{11}{7}+\binom{11}{8}+\binom{11}{9}+\binom{11}{10}+\binom{11}{11}=\frac{2^{11}}{2}=2^{10}=1024&lt;/math&gt;.<br /> <br /> The total is &lt;math&gt; 1024+175=1199&lt;/math&gt;. Subtracting out the &lt;math&gt; 44&lt;/math&gt; numbers between &lt;math&gt; 2003&lt;/math&gt; and &lt;math&gt; 2048&lt;/math&gt; gives &lt;math&gt; 1155&lt;/math&gt;. Thus the answer is &lt;math&gt; 155&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> We will count the number of it &lt;math&gt;&lt; 2^{11}=2048&lt;/math&gt; instead of &lt;math&gt;2003&lt;/math&gt; (In other words, the length of the base-2 representation is at most &lt;math&gt;11&lt;/math&gt;. If there are even digits, &lt;math&gt;2n&lt;/math&gt;, then the leftmost digit is &lt;math&gt;1&lt;/math&gt;, the rest, &lt;math&gt;2n-1&lt;/math&gt;, has odd number of digits. In order for the base-2 representation to have more &lt;math&gt;1&lt;/math&gt;'s, we will need more &lt;math&gt;1&lt;/math&gt; in the remaining &lt;math&gt;2n-1&lt;/math&gt; than &lt;math&gt;0&lt;/math&gt;'s. Using symmetry, this is equal to<br /> &lt;math&gt;\frac{2^9+2^7+..+2^1}{2}&lt;/math&gt;<br /> Using similar argument where there are odd amount of digits. The remaining even amount of digit must contains the number of &lt;math&gt;1&lt;/math&gt;'s at least as the number of &lt;math&gt;0&lt;/math&gt;'s. So it's equal to<br /> &lt;math&gt;\frac{\binom{10}{5}+2^{10}+\binom{8}{4}+2^8+\binom{6}{3}+2^6+...+\binom{0}{0}+2^0}{2}&lt;/math&gt;<br /> Summing both cases, we have &lt;math&gt;\frac{2^0+2^1+..+2^{10}+\binom{0}{0}+..+\binom{10}{5}}{2} = 1199&lt;/math&gt;. There are &lt;math&gt;44&lt;/math&gt; numbers between &lt;math&gt;2004&lt;/math&gt; and &lt;math&gt;2047&lt;/math&gt; inclusive that satisfy it. So the answer is &lt;math&gt;1199-44=1\boxed{155}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2003|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2003_AIME_I_Problems/Problem_13&diff=126558 2003 AIME I Problems/Problem 13 2020-06-26T10:24:44Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt; N &lt;/math&gt; be the number of positive integers that are less than or equal to &lt;math&gt;2003&lt;/math&gt; and whose base-&lt;math&gt;2&lt;/math&gt; representation has more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s. Find the [[remainder]] when &lt;math&gt; N &lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> In base-&lt;math&gt;2&lt;/math&gt; representation, all positive numbers have a leftmost digit of &lt;math&gt;1&lt;/math&gt;. Thus there are &lt;math&gt;{n \choose k}&lt;/math&gt; numbers that have &lt;math&gt;n+1&lt;/math&gt; digits in base &lt;math&gt;2&lt;/math&gt; notation, with &lt;math&gt;k+1&lt;/math&gt; of the digits being &lt;math&gt;1&lt;/math&gt;'s. <br /> <br /> In order for there to be more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s, we must have &lt;math&gt;k+1 &gt; \frac{d+1}{2} \Longrightarrow k &gt; \frac{d-1}{2} \Longrightarrow k \ge \frac{d}{2}&lt;/math&gt;. Therefore, the number of such numbers corresponds to the sum of all numbers on or to the right of the vertical line of symmetry in [[Pascal's Triangle]], from rows &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;10&lt;/math&gt; (as &lt;math&gt;2003 &lt; 2^{11}-1&lt;/math&gt;). Since the sum of the elements of the &lt;math&gt;r&lt;/math&gt;th row is &lt;math&gt;2^r&lt;/math&gt;, it follows that the sum of all elements in rows &lt;math&gt;0&lt;/math&gt; through &lt;math&gt;10&lt;/math&gt; is &lt;math&gt;2^0 + 2^1 + \cdots + 2^{10} = 2^{11}-1 = 2047&lt;/math&gt;. The center elements are in the form &lt;math&gt;{2i \choose i}&lt;/math&gt;, so the sum of these elements is &lt;math&gt;\sum_{i=0}^{5} {2i \choose i} = 1 + 2 +6 + 20 + 70 + 252 = 351&lt;/math&gt;.<br /> <br /> The sum of the elements on or to the right of the line of symmetry is thus &lt;math&gt;\frac{2047 + 351}{2} = 1199&lt;/math&gt;. However, we also counted the &lt;math&gt;44&lt;/math&gt; numbers from &lt;math&gt;2004&lt;/math&gt; to &lt;math&gt;2^{11}-1 = 2047&lt;/math&gt;. Indeed, all of these numbers have at least &lt;math&gt;6&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s in their base-&lt;math&gt;2&lt;/math&gt; representation, as all of them are greater than &lt;math&gt;1984 = 11111000000_2&lt;/math&gt;, which has &lt;math&gt;5&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s. Therefore, our answer is &lt;math&gt;1199 - 44 = 1155&lt;/math&gt;, and the remainder is &lt;math&gt;\boxed{155}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> We seek the number of allowed numbers which have &lt;math&gt; k&lt;/math&gt; 1's, not including the leading 1, for &lt;math&gt; k=0, 1, 2, \ldots , 10&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=0,\ldots , 4&lt;/math&gt;, this number is<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{2k}{k}&lt;/math&gt;.<br /> <br /> By the Hockey Stick Identity, this is equal to &lt;math&gt; \binom{2k+1}{k+1}&lt;/math&gt;. So we get<br /> <br /> &lt;math&gt; \binom{1}{1}+\binom{3}{2}+\binom{5}{3}+\binom{7}{4}+\binom{9}{5}=175&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=5,\ldots , 10&lt;/math&gt;, we end on &lt;math&gt; \binom{10}{k}&lt;/math&gt; - we don't want to consider numbers with more than 11 digits. So for each &lt;math&gt; k&lt;/math&gt; we get<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{10}{k}=\binom{11}{k+1}&lt;/math&gt;<br /> <br /> again by the Hockey Stick Identity. So we get<br /> <br /> &lt;math&gt; \binom{11}{6}+\binom{11}{7}+\binom{11}{8}+\binom{11}{9}+\binom{11}{10}+\binom{11}{11}=\frac{2^{11}}{2}=2^{10}=1024&lt;/math&gt;.<br /> <br /> The total is &lt;math&gt; 1024+175=1199&lt;/math&gt;. Subtracting out the &lt;math&gt; 44&lt;/math&gt; numbers between &lt;math&gt; 2003&lt;/math&gt; and &lt;math&gt; 2048&lt;/math&gt; gives &lt;math&gt; 1155&lt;/math&gt;. Thus the answer is &lt;math&gt; 155&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> We will count the number of it &lt;math&gt;&lt; 2^{11}=2048&lt;/math&gt; instead of &lt;math&gt;2003&lt;/math&gt; (In other words, the length of the base-2 representation is at most &lt;math&gt;11&lt;/math&gt;. If there are even digits, &lt;math&gt;2n&lt;/math&gt;, then the leftmost digit is &lt;math&gt;1&lt;/math&gt;, the rest, &lt;math&gt;2n-1&lt;/math&gt;, has odd number of digits. In order for the base-2 representation to have more &lt;math&gt;1&lt;/math&gt;'s, we will need more &lt;math&gt;1&lt;/math&gt; in the remaining &lt;math&gt;2n-1&lt;/math&gt; than &lt;math&gt;0&lt;/math&gt;'s. Using symmetry, this is equal to<br /> &lt;math&gt;\frac{2^9+2^7+..+2^1}{2}&lt;/math&gt;<br /> Using similar argument where there are odd amount of digits. The remaining even amount of digit must contains the number of &lt;math&gt;1&lt;/math&gt;'s at least as the number of &lt;math&gt;0&lt;/math&gt;'s. So it's equal to<br /> &lt;math&gt;\frac{\binom{10}{5}+2^{10}+\binom{8}{4}+2^8+\binom{6}{3}+2^6+...+\binom{0}{0}+2^0}{2}&lt;/math&gt;<br /> Summing both cases, we have &lt;math&gt;\frac{2^0+2^1+..+2^9+\binom{0}{0}+..+\binom{8}{4}}{2} = 1199&lt;/math&gt;. There are &lt;math&gt;44&lt;/math&gt; numbers between &lt;math&gt;2004&lt;/math&gt; and &lt;math&gt;2047&lt;/math&gt; inclusive that satisfy it. So the answer is &lt;math&gt;1199-44=1\boxed{155}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2003|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2003_AIME_I_Problems/Problem_13&diff=126557 2003 AIME I Problems/Problem 13 2020-06-26T10:21:23Z <p>Mysteryguy6647: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt; N &lt;/math&gt; be the number of positive integers that are less than or equal to &lt;math&gt;2003&lt;/math&gt; and whose base-&lt;math&gt;2&lt;/math&gt; representation has more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s. Find the [[remainder]] when &lt;math&gt; N &lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> In base-&lt;math&gt;2&lt;/math&gt; representation, all positive numbers have a leftmost digit of &lt;math&gt;1&lt;/math&gt;. Thus there are &lt;math&gt;{n \choose k}&lt;/math&gt; numbers that have &lt;math&gt;n+1&lt;/math&gt; digits in base &lt;math&gt;2&lt;/math&gt; notation, with &lt;math&gt;k+1&lt;/math&gt; of the digits being &lt;math&gt;1&lt;/math&gt;'s. <br /> <br /> In order for there to be more &lt;math&gt;1&lt;/math&gt;'s than &lt;math&gt;0&lt;/math&gt;'s, we must have &lt;math&gt;k+1 &gt; \frac{d+1}{2} \Longrightarrow k &gt; \frac{d-1}{2} \Longrightarrow k \ge \frac{d}{2}&lt;/math&gt;. Therefore, the number of such numbers corresponds to the sum of all numbers on or to the right of the vertical line of symmetry in [[Pascal's Triangle]], from rows &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;10&lt;/math&gt; (as &lt;math&gt;2003 &lt; 2^{11}-1&lt;/math&gt;). Since the sum of the elements of the &lt;math&gt;r&lt;/math&gt;th row is &lt;math&gt;2^r&lt;/math&gt;, it follows that the sum of all elements in rows &lt;math&gt;0&lt;/math&gt; through &lt;math&gt;10&lt;/math&gt; is &lt;math&gt;2^0 + 2^1 + \cdots + 2^{10} = 2^{11}-1 = 2047&lt;/math&gt;. The center elements are in the form &lt;math&gt;{2i \choose i}&lt;/math&gt;, so the sum of these elements is &lt;math&gt;\sum_{i=0}^{5} {2i \choose i} = 1 + 2 +6 + 20 + 70 + 252 = 351&lt;/math&gt;.<br /> <br /> The sum of the elements on or to the right of the line of symmetry is thus &lt;math&gt;\frac{2047 + 351}{2} = 1199&lt;/math&gt;. However, we also counted the &lt;math&gt;44&lt;/math&gt; numbers from &lt;math&gt;2004&lt;/math&gt; to &lt;math&gt;2^{11}-1 = 2047&lt;/math&gt;. Indeed, all of these numbers have at least &lt;math&gt;6&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s in their base-&lt;math&gt;2&lt;/math&gt; representation, as all of them are greater than &lt;math&gt;1984 = 11111000000_2&lt;/math&gt;, which has &lt;math&gt;5&lt;/math&gt; &lt;math&gt;1&lt;/math&gt;'s. Therefore, our answer is &lt;math&gt;1199 - 44 = 1155&lt;/math&gt;, and the remainder is &lt;math&gt;\boxed{155}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> We seek the number of allowed numbers which have &lt;math&gt; k&lt;/math&gt; 1's, not including the leading 1, for &lt;math&gt; k=0, 1, 2, \ldots , 10&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=0,\ldots , 4&lt;/math&gt;, this number is<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{2k}{k}&lt;/math&gt;.<br /> <br /> By the Hockey Stick Identity, this is equal to &lt;math&gt; \binom{2k+1}{k+1}&lt;/math&gt;. So we get<br /> <br /> &lt;math&gt; \binom{1}{1}+\binom{3}{2}+\binom{5}{3}+\binom{7}{4}+\binom{9}{5}=175&lt;/math&gt;.<br /> <br /> For &lt;math&gt; k=5,\ldots , 10&lt;/math&gt;, we end on &lt;math&gt; \binom{10}{k}&lt;/math&gt; - we don't want to consider numbers with more than 11 digits. So for each &lt;math&gt; k&lt;/math&gt; we get<br /> <br /> &lt;math&gt; \binom{k}{k}+\binom{k+1}{k}+\ldots+\binom{10}{k}=\binom{11}{k+1}&lt;/math&gt;<br /> <br /> again by the Hockey Stick Identity. So we get<br /> <br /> &lt;math&gt; \binom{11}{6}+\binom{11}{7}+\binom{11}{8}+\binom{11}{9}+\binom{11}{10}+\binom{11}{11}=\frac{2^{11}}{2}=2^{10}=1024&lt;/math&gt;.<br /> <br /> The total is &lt;math&gt; 1024+175=1199&lt;/math&gt;. Subtracting out the &lt;math&gt; 44&lt;/math&gt; numbers between &lt;math&gt; 2003&lt;/math&gt; and &lt;math&gt; 2048&lt;/math&gt; gives &lt;math&gt; 1155&lt;/math&gt;. Thus the answer is &lt;math&gt; 155&lt;/math&gt;.<br /> <br /> ==Solution 3==<br /> We will count the number of it &lt;math&gt;&lt; 2^{11}=2048&lt;/math&gt; instead of &lt;math&gt;2003&lt;/math&gt; (In other words, the length of the base-2 representation is at most &lt;math&gt;11&lt;/math&gt;. If there are even digits, &lt;math&gt;2n&lt;/math&gt;, then the leftmost digit is &lt;math&gt;1&lt;/math&gt;, the rest, &lt;math&gt;2n-1&lt;/math&gt;, has odd number of digits. In order for the base-2 representation to have more &lt;math&gt;1&lt;/math&gt;'s, we will need more &lt;math&gt;1&lt;/math&gt; in the remaining &lt;math&gt;2n-1&lt;/math&gt; than &lt;math&gt;0&lt;/math&gt;'s. Using symmetry, this is equal to<br /> &lt;math&gt;\frac{2^9+2^7+..+2^1}{2}&lt;/math&gt;<br /> Using similar argument where there are odd amount of digits. The remaining even amount of digit must contains the number of &lt;math&gt;1&lt;/math&gt;'s at least as the number of &lt;math&gt;0&lt;/math&gt;'s. So it's equal to<br /> &lt;math&gt;\frac{\binom{8}{4}+2^8+\binom{6}{3}+2^6+...+\binom{0}{0}+2^0}{2}&lt;/math&gt;<br /> Summing both cases, we have &lt;math&gt;\frac{2^0+2^1+..+2^9+\binom{0}{0}+..+\binom{8}{4}}{2} = 1199&lt;/math&gt;. There are &lt;math&gt;44&lt;/math&gt; numbers between &lt;math&gt;2004&lt;/math&gt; and &lt;math&gt;2047&lt;/math&gt; inclusive that satisfy it. So the answer is &lt;math&gt;1199-44=1\boxed{155}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2003|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_II_Problems/Problem_10&diff=126424 2002 AIME II Problems/Problem 10 2020-06-24T23:30:29Z <p>Mysteryguy6647: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> While finding the sine of a certain angle, an absent-minded professor failed to notice that his calculator was not in the correct angular mode. He was lucky to get the right answer. The two least positive real values of &lt;math&gt;x&lt;/math&gt; for which the sine of &lt;math&gt;x&lt;/math&gt; degrees is the same as the sine of &lt;math&gt;x&lt;/math&gt; radians are &lt;math&gt;\frac{m\pi}{n-\pi}&lt;/math&gt; and &lt;math&gt;\frac{p\pi}{q+\pi}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt;, &lt;math&gt;n&lt;/math&gt;, &lt;math&gt;p&lt;/math&gt;, and &lt;math&gt;q&lt;/math&gt; are positive integers. Find &lt;math&gt;m+n+p+q&lt;/math&gt;.<br /> <br /> == Solution 1==<br /> Note that &lt;math&gt;x&lt;/math&gt; degrees is equal to &lt;math&gt;\frac{\pi x}{180}&lt;/math&gt; radians. Also, for &lt;math&gt;\alpha \in \left[0 , \frac{\pi}{2} \right]&lt;/math&gt;, the two least positive angles &lt;math&gt;\theta &gt; \alpha&lt;/math&gt; such that &lt;math&gt;\sin{\theta} = \sin{\alpha}&lt;/math&gt; are &lt;math&gt;\theta = \pi-\alpha&lt;/math&gt;, and &lt;math&gt;\theta = 2\pi + \alpha&lt;/math&gt;. <br /> <br /> Clearly &lt;math&gt;x &gt; \frac{\pi x}{180}&lt;/math&gt; for positive real values of &lt;math&gt;x&lt;/math&gt;. <br /> <br /> &lt;math&gt;\theta = \pi-\alpha&lt;/math&gt; yields: &lt;math&gt;x = \pi - \frac{\pi x}{180} \Rightarrow x = \frac{180\pi}{180+\pi} \Rightarrow (p,q) = (180,180)&lt;/math&gt;. <br /> <br /> &lt;math&gt;\theta = 2\pi + \alpha&lt;/math&gt; yields: &lt;math&gt;x = 2\pi + \frac{\pi x}{180} \Rightarrow x = \frac{360\pi}{180-\pi} \Rightarrow (m,n) = (360,180)&lt;/math&gt;. <br /> <br /> So, &lt;math&gt;m+n+p+q = \boxed{900}&lt;/math&gt;.<br /> == Solution 2 ==<br /> The first case is when the two angles, &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;\frac{\pi x}{180}&lt;/math&gt;, are coterminal. The second case is when they are reflections of the &lt;math&gt;y&lt;/math&gt; axis.<br /> <br /> 1. &lt;math&gt;x+2\pi a = \frac{\pi x}{180}&lt;/math&gt; for any integer &lt;math&gt;a&lt;/math&gt;<br /> So &lt;math&gt;x=\frac{360\pi a }{\pi -180}&lt;/math&gt;<br /> <br /> 2. &lt;math&gt;(2b+1)\pi -x = \frac{\pi x}{180}&lt;/math&gt; for any integer &lt;math&gt;b&lt;/math&gt;<br /> So &lt;math&gt;x = \frac{180(2b+1)\pi}{\pi + 180}&lt;/math&gt;<br /> <br /> Choosing carefully &lt;math&gt;a,b&lt;/math&gt; such that it's the minimum gives the answer same as above.<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=II|num-b=9|num-a=11}}<br /> <br /> [[Category: Intermediate Trigonometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_II_Problems/Problem_10&diff=126423 2002 AIME II Problems/Problem 10 2020-06-24T23:30:10Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>== Problem ==<br /> While finding the sine of a certain angle, an absent-minded professor failed to notice that his calculator was not in the correct angular mode. He was lucky to get the right answer. The two least positive real values of &lt;math&gt;x&lt;/math&gt; for which the sine of &lt;math&gt;x&lt;/math&gt; degrees is the same as the sine of &lt;math&gt;x&lt;/math&gt; radians are &lt;math&gt;\frac{m\pi}{n-\pi}&lt;/math&gt; and &lt;math&gt;\frac{p\pi}{q+\pi}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt;, &lt;math&gt;n&lt;/math&gt;, &lt;math&gt;p&lt;/math&gt;, and &lt;math&gt;q&lt;/math&gt; are positive integers. Find &lt;math&gt;m+n+p+q&lt;/math&gt;.<br /> <br /> == Solution 1==<br /> Note that &lt;math&gt;x&lt;/math&gt; degrees is equal to &lt;math&gt;\frac{\pi x}{180}&lt;/math&gt; radians. Also, for &lt;math&gt;\alpha \in \left[0 , \frac{\pi}{2} \right]&lt;/math&gt;, the two least positive angles &lt;math&gt;\theta &gt; \alpha&lt;/math&gt; such that &lt;math&gt;\sin{\theta} = \sin{\alpha}&lt;/math&gt; are &lt;math&gt;\theta = \pi-\alpha&lt;/math&gt;, and &lt;math&gt;\theta = 2\pi + \alpha&lt;/math&gt;. <br /> <br /> Clearly &lt;math&gt;x &gt; \frac{\pi x}{180}&lt;/math&gt; for positive real values of &lt;math&gt;x&lt;/math&gt;. <br /> <br /> &lt;math&gt;\theta = \pi-\alpha&lt;/math&gt; yields: &lt;math&gt;x = \pi - \frac{\pi x}{180} \Rightarrow x = \frac{180\pi}{180+\pi} \Rightarrow (p,q) = (180,180)&lt;/math&gt;. <br /> <br /> &lt;math&gt;\theta = 2\pi + \alpha&lt;/math&gt; yields: &lt;math&gt;x = 2\pi + \frac{\pi x}{180} \Rightarrow x = \frac{360\pi}{180-\pi} \Rightarrow (m,n) = (360,180)&lt;/math&gt;. <br /> <br /> So, &lt;math&gt;m+n+p+q = \boxed{900}&lt;/math&gt;.<br /> == Solution 2 ==<br /> The first case is when the two angles, &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;\frac{\pi x}{180}&lt;/math&gt;, are coterminal. The second case is when they are reflections of the &lt;math&gt;y&lt;/math&gt; axis.<br /> 1. &lt;math&gt;x+2\pi a = \frac{\pi x}{180}&lt;/math&gt; for any integer &lt;math&gt;a&lt;/math&gt;<br /> So &lt;math&gt;x=\frac{360\pi a }{\pi -180}&lt;/math&gt;<br /> <br /> 2. &lt;math&gt;(2b+1)\pi -x = \frac{\pi x}{180}&lt;/math&gt; for any integer &lt;math&gt;b&lt;/math&gt;<br /> So &lt;math&gt;x = \frac{180(2b+1)\pi}{\pi + 180}&lt;/math&gt;<br /> <br /> Choosing carefully &lt;math&gt;a,b&lt;/math&gt; such that it's the minimum gives the answer same as above.<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=II|num-b=9|num-a=11}}<br /> <br /> [[Category: Intermediate Trigonometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_II_Problems/Problem_6&diff=126321 2002 AIME II Problems/Problem 6 2020-06-24T09:47:02Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>== Problem ==<br /> Find the integer that is closest to &lt;math&gt;1000\sum_{n=3}^{10000}\frac1{n^2-4}&lt;/math&gt;.<br /> <br /> == Solution ==<br /> We know that &lt;math&gt;\frac{4}{n^2 - 4} = \frac{1}{n-2} - \frac{1}{n + 2}&lt;/math&gt;.<br /> <br /> So if we pull the &lt;math&gt;\frac{1}{4}&lt;/math&gt; out of the summation, you get <br /> <br /> &lt;math&gt;250\sum_{n=3}^{10,000} (\frac{1}{n-2} - \frac{1}{n + 2})&lt;/math&gt;.<br /> <br /> Now that telescopes, leaving you with:<br /> <br /> &lt;math&gt;250 (1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} - \frac{1}{9999} - \frac{1}{10000} - \frac{1}{10001} - \frac{1}{10002}) = 250 + 125 + 83.3 + 62.5 - 250 (- \frac{1}{9999} - \frac{1}{10000} - \frac{1}{10001} - \frac{1}{10002})&lt;/math&gt;<br /> <br /> The small fractional terms are not enough to bring &lt;math&gt;520.8&lt;/math&gt; lower than &lt;math&gt;520.5,&lt;/math&gt; so the answer is &lt;math&gt;\fbox{521}&lt;/math&gt;<br /> <br /> <br /> If you didn't know &lt;math&gt;\frac{4}{n^2 - 4} = \frac{1}{n-2} - \frac{1}{n + 2}&lt;/math&gt;, here's how you can find it out:<br /> <br /> We know &lt;math&gt;\frac{1}{n^2 - 4} = \frac{1}{(n+2)(n-2)}&lt;/math&gt;. We can use the process of fractional decomposition to split this into two fractions thus: &lt;math&gt;\frac{1}{(n+2)(n-2)} = \frac{A}{(n+2)} + \frac{B}{(n-2)}&lt;/math&gt; for some A and B. <br /> <br /> Solving for A and B gives &lt;math&gt;1 = (n-2)A + (n+2)B&lt;/math&gt; or &lt;math&gt;1 = n(A+B)+ 2(B-A)&lt;/math&gt;. Since there is no n term on the left hand side, &lt;math&gt; A+B=0&lt;/math&gt; and by inspection &lt;math&gt;1 = 2(B-A)&lt;/math&gt;. Solving yields &lt;math&gt; A=\frac{1}{4}, B=\frac{-1}{4}&lt;/math&gt;<br /> <br /> Then we have &lt;math&gt;\frac{1}{(n+2)(n-2)} = \frac{ \frac{1}{4} }{(n-2)} + \frac{ \frac{-1}{4} }{(n+2)}&lt;/math&gt; and we can continue as before.<br /> == Solution ==<br /> Using the fact that &lt;math&gt;\frac{1}{n(n+k)} = \frac{1}{k} ( \frac{1}{n}-\frac{1}{n+k} )&lt;/math&gt; or by partial fraction decomposition, we both obtained &lt;math&gt;\frac{1}{x^2-4} = \frac{1}{4}(\frac{1}{x-2}-\frac{1}{x+2})&lt;/math&gt;. The denominators of the positive terms are &lt;math&gt;1,2,..,9998&lt;/math&gt;, while the negative ones are &lt;math&gt;5,6,...,10002&lt;/math&gt;. Hence we are left with &lt;math&gt;1000 \cdot 4 (1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} - \frac{1}{9999} - \frac{1}{10000} - \frac{1}{10001} - \frac{1}{10002})&lt;/math&gt;. We can simply ignore the last &lt;math&gt;4&lt;/math&gt; terms, and we get it is approximately &lt;math&gt;1000*\frac{25}{48}&lt;/math&gt;. Computing &lt;math&gt;\frac{25}{48}&lt;/math&gt; which is about &lt;math&gt;0.5208..&lt;/math&gt; and moving the decimal point three times, we get that the answer is &lt;math&gt;521&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=II|num-b=5|num-a=7}}<br /> <br /> [[Category: Intermediate Algebra Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_9&diff=125928 2002 AIME I Problems/Problem 9 2020-06-19T14:23:01Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Harold, Tanya, and Ulysses paint a very long picket fence. <br /> <br /> *Harold starts with the first picket and paints every &lt;math&gt;h&lt;/math&gt; th picket; <br /> *Tanya starts with the second picket and paints every &lt;math&gt;t&lt;/math&gt; th picket; and <br /> *Ulysses starts with the third picket and paints every &lt;math&gt;u&lt;/math&gt; th picket. <br /> <br /> Call the positive integer &lt;math&gt;100h+10t+u&lt;/math&gt; paintable when the triple &lt;math&gt;(h,t,u)&lt;/math&gt; of positive integers results in every picket being painted exactly once. Find the sum of all the paintable integers.<br /> <br /> __TOC__<br /> == Solution ==<br /> === Solution 1 ===<br /> Note that it is impossible for any of &lt;math&gt;h,t,u&lt;/math&gt; to be &lt;math&gt;1&lt;/math&gt;, since then each picket will have been painted one time, and then some will be painted more than once. <br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be &lt;math&gt;2&lt;/math&gt;, or that will result in painting the third picket twice. If &lt;math&gt;h=3&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; may not equal anything not divisible by &lt;math&gt;3&lt;/math&gt;, and the same for &lt;math&gt;u&lt;/math&gt;. Now for fourth and fifth pickets to be painted, &lt;math&gt;t&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;3&lt;/math&gt; as well. This configuration works, so &lt;math&gt;333&lt;/math&gt; is paintable.<br /> <br /> If &lt;math&gt;h&lt;/math&gt; is &lt;math&gt;4&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; must be even. The same for &lt;math&gt;u&lt;/math&gt;, except that it can't be &lt;math&gt;2 \mod 4&lt;/math&gt;. Thus &lt;math&gt;u&lt;/math&gt; is &lt;math&gt;0 \mod 4&lt;/math&gt; and &lt;math&gt;t&lt;/math&gt; is &lt;math&gt;2 \mod 4&lt;/math&gt;. Since this is all &lt;math&gt;\mod 4&lt;/math&gt;, &lt;math&gt;t&lt;/math&gt; must be &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;4&lt;/math&gt;, in order for &lt;math&gt;5,6&lt;/math&gt; to be paint-able. Thus &lt;math&gt;424&lt;/math&gt; is paintable.<br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be greater than &lt;math&gt;5&lt;/math&gt;, since if that were the case then the answer would be greater than &lt;math&gt;999&lt;/math&gt;, which would be impossible for the AIME.<br /> <br /> Thus the sum of all paintable numbers is &lt;math&gt;\boxed{757}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> Again, note that &lt;math&gt;h,t,u \neq 1&lt;/math&gt;. The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. By the [[Chinese Remainder Theorem]], the [[greatest common divisor]] of any pair of the three numbers &lt;math&gt;\{h,t,u\}&lt;/math&gt; cannot be &lt;math&gt;1&lt;/math&gt; (since otherwise [[without loss of generality]] consider &lt;math&gt;\text{gcd}\,(h,t) = 1&lt;/math&gt;; then there will be a common solution &lt;math&gt;\pmod{h \times t}&lt;/math&gt;). <br /> <br /> Now for &lt;math&gt;4&lt;/math&gt; to be paint-able, we require either &lt;math&gt;h = 3&lt;/math&gt; or &lt;math&gt;t=2&lt;/math&gt;, but not both. <br /> *In the former condition, since &lt;math&gt;\text{gcd}\,(h,t),\ \text{gcd}\,(h,u) \neq 1&lt;/math&gt;, it follows that &lt;math&gt;3|t,u&lt;/math&gt;. For &lt;math&gt;5&lt;/math&gt; and &lt;math&gt;6&lt;/math&gt; to be paint-able, we require &lt;math&gt;t = u = 3&lt;/math&gt;, and it is easy to see that &lt;math&gt;333&lt;/math&gt; works.<br /> *In the latter condition, similarly we require that &lt;math&gt;2|h,u&lt;/math&gt;. All even numbers are painted. We now renumber the remaining odd pickets to become the set of all positive integers (&lt;math&gt;1,3,5, \ldots \rightarrow 1',2',3', \ldots&lt;/math&gt;, where &lt;math&gt;n' = \frac{n+1}{2}&lt;/math&gt;), which requires the transformation &lt;math&gt;h' = h/2,\ u' = u/2&lt;/math&gt;, and with the painting starting respectively at &lt;math&gt;1',2'&lt;/math&gt;. Our new number system retains the same conditions as above, except without &lt;math&gt;t&lt;/math&gt;. We thus need &lt;math&gt;\text{gcd}\, (h',u') \neq 1, h',u' \neq 1&lt;/math&gt;. Then for &lt;math&gt;3',4'&lt;/math&gt; to be painted, we require &lt;math&gt;h' = u' = 2&lt;/math&gt;. This translates to &lt;math&gt;424&lt;/math&gt;, which we see works. <br /> <br /> Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> === Solution 3 ===<br /> The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. Note that the smallest number, &lt;math&gt;min \{ h,t,u \}, &lt;/math&gt; divides the other &lt;math&gt;2&lt;/math&gt;, and the next smallest divide the largest number, otherwise there is a common solution by the [[Chinese Remainder Theorem]]. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least &lt;math&gt;5&lt;/math&gt;, otherwise not all picket will be painted. We are left with few cases (we could also exclude &lt;math&gt;1&lt;/math&gt; as the possibility) which could be done quickly. Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=I|num-b=8|num-a=10}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_9&diff=125927 2002 AIME I Problems/Problem 9 2020-06-19T14:22:44Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>== Problem ==<br /> Harold, Tanya, and Ulysses paint a very long picket fence. <br /> <br /> *Harold starts with the first picket and paints every &lt;math&gt;h&lt;/math&gt; th picket; <br /> *Tanya starts with the second picket and paints every &lt;math&gt;t&lt;/math&gt; th picket; and <br /> *Ulysses starts with the third picket and paints every &lt;math&gt;u&lt;/math&gt; th picket. <br /> <br /> Call the positive integer &lt;math&gt;100h+10t+u&lt;/math&gt; paintable when the triple &lt;math&gt;(h,t,u)&lt;/math&gt; of positive integers results in every picket being painted exactly once. Find the sum of all the paintable integers.<br /> <br /> __TOC__<br /> == Solution ==<br /> === Solution 1 ===<br /> Note that it is impossible for any of &lt;math&gt;h,t,u&lt;/math&gt; to be &lt;math&gt;1&lt;/math&gt;, since then each picket will have been painted one time, and then some will be painted more than once. <br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be &lt;math&gt;2&lt;/math&gt;, or that will result in painting the third picket twice. If &lt;math&gt;h=3&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; may not equal anything not divisible by &lt;math&gt;3&lt;/math&gt;, and the same for &lt;math&gt;u&lt;/math&gt;. Now for fourth and fifth pickets to be painted, &lt;math&gt;t&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;3&lt;/math&gt; as well. This configuration works, so &lt;math&gt;333&lt;/math&gt; is paintable.<br /> <br /> If &lt;math&gt;h&lt;/math&gt; is &lt;math&gt;4&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; must be even. The same for &lt;math&gt;u&lt;/math&gt;, except that it can't be &lt;math&gt;2 \mod 4&lt;/math&gt;. Thus &lt;math&gt;u&lt;/math&gt; is &lt;math&gt;0 \mod 4&lt;/math&gt; and &lt;math&gt;t&lt;/math&gt; is &lt;math&gt;2 \mod 4&lt;/math&gt;. Since this is all &lt;math&gt;\mod 4&lt;/math&gt;, &lt;math&gt;t&lt;/math&gt; must be &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;4&lt;/math&gt;, in order for &lt;math&gt;5,6&lt;/math&gt; to be paint-able. Thus &lt;math&gt;424&lt;/math&gt; is paintable.<br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be greater than &lt;math&gt;5&lt;/math&gt;, since if that were the case then the answer would be greater than &lt;math&gt;999&lt;/math&gt;, which would be impossible for the AIME.<br /> <br /> Thus the sum of all paintable numbers is &lt;math&gt;\boxed{757}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> Again, note that &lt;math&gt;h,t,u \neq 1&lt;/math&gt;. The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. By the [[Chinese Remainder Theorem]], the [[greatest common divisor]] of any pair of the three numbers &lt;math&gt;\{h,t,u\}&lt;/math&gt; cannot be &lt;math&gt;1&lt;/math&gt; (since otherwise [[without loss of generality]] consider &lt;math&gt;\text{gcd}\,(h,t) = 1&lt;/math&gt;; then there will be a common solution &lt;math&gt;\pmod{h \times t}&lt;/math&gt;). <br /> <br /> Now for &lt;math&gt;4&lt;/math&gt; to be paint-able, we require either &lt;math&gt;h = 3&lt;/math&gt; or &lt;math&gt;t=2&lt;/math&gt;, but not both. <br /> *In the former condition, since &lt;math&gt;\text{gcd}\,(h,t),\ \text{gcd}\,(h,u) \neq 1&lt;/math&gt;, it follows that &lt;math&gt;3|t,u&lt;/math&gt;. For &lt;math&gt;5&lt;/math&gt; and &lt;math&gt;6&lt;/math&gt; to be paint-able, we require &lt;math&gt;t = u = 3&lt;/math&gt;, and it is easy to see that &lt;math&gt;333&lt;/math&gt; works.<br /> *In the latter condition, similarly we require that &lt;math&gt;2|h,u&lt;/math&gt;. All even numbers are painted. We now renumber the remaining odd pickets to become the set of all positive integers (&lt;math&gt;1,3,5, \ldots \rightarrow 1',2',3', \ldots&lt;/math&gt;, where &lt;math&gt;n' = \frac{n+1}{2}&lt;/math&gt;), which requires the transformation &lt;math&gt;h' = h/2,\ u' = u/2&lt;/math&gt;, and with the painting starting respectively at &lt;math&gt;1',2'&lt;/math&gt;. Our new number system retains the same conditions as above, except without &lt;math&gt;t&lt;/math&gt;. We thus need &lt;math&gt;\text{gcd}\, (h',u') \neq 1, h',u' \neq 1&lt;/math&gt;. Then for &lt;math&gt;3',4'&lt;/math&gt; to be painted, we require &lt;math&gt;h' = u' = 2&lt;/math&gt;. This translates to &lt;math&gt;424&lt;/math&gt;, which we see works. <br /> <br /> Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> === Solution 3 ===<br /> The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. Note that the smallest number, &lt;math&gt;min \{ h,t,u \}, &lt;/math&gt; divides the other &lt;math&gt;2&lt;/math&gt;, and the next smallest divide the largest number, otherwise there is a common solution by the [[Chinese Remainder Theorem]]. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least &lt;math&gt;5&lt;/math&gt;, otherwise not all picket will be painted. We are left with few cases (we could also exclude &lt;math&gt;1&lt;/math&gt; as the possibility) which could be done quickly. Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> <br /> === Solution 3 ===<br /> The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. Note that the smallest number, &lt;math&gt;min \{ h,t,u \}, &lt;/math&gt; divides the other &lt;math&gt;2&lt;/math&gt;, and the next smallest divide the largest number, otherwise there is a common solution by the [[Chinese Remainder Theorem]]. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least &lt;math&gt;5&lt;/math&gt;, otherwise not all picket will be painted. We are left with few cases (we could also exclude &lt;math&gt;1&lt;/math&gt; as the possibility) which could be done quickly. Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=I|num-b=8|num-a=10}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_9&diff=125926 2002 AIME I Problems/Problem 9 2020-06-19T14:22:28Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>== Problem ==<br /> Harold, Tanya, and Ulysses paint a very long picket fence. <br /> <br /> *Harold starts with the first picket and paints every &lt;math&gt;h&lt;/math&gt; th picket; <br /> *Tanya starts with the second picket and paints every &lt;math&gt;t&lt;/math&gt; th picket; and <br /> *Ulysses starts with the third picket and paints every &lt;math&gt;u&lt;/math&gt; th picket. <br /> <br /> Call the positive integer &lt;math&gt;100h+10t+u&lt;/math&gt; paintable when the triple &lt;math&gt;(h,t,u)&lt;/math&gt; of positive integers results in every picket being painted exactly once. Find the sum of all the paintable integers.<br /> <br /> __TOC__<br /> == Solution ==<br /> === Solution 1 ===<br /> Note that it is impossible for any of &lt;math&gt;h,t,u&lt;/math&gt; to be &lt;math&gt;1&lt;/math&gt;, since then each picket will have been painted one time, and then some will be painted more than once. <br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be &lt;math&gt;2&lt;/math&gt;, or that will result in painting the third picket twice. If &lt;math&gt;h=3&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; may not equal anything not divisible by &lt;math&gt;3&lt;/math&gt;, and the same for &lt;math&gt;u&lt;/math&gt;. Now for fourth and fifth pickets to be painted, &lt;math&gt;t&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;3&lt;/math&gt; as well. This configuration works, so &lt;math&gt;333&lt;/math&gt; is paintable.<br /> <br /> If &lt;math&gt;h&lt;/math&gt; is &lt;math&gt;4&lt;/math&gt;, then &lt;math&gt;t&lt;/math&gt; must be even. The same for &lt;math&gt;u&lt;/math&gt;, except that it can't be &lt;math&gt;2 \mod 4&lt;/math&gt;. Thus &lt;math&gt;u&lt;/math&gt; is &lt;math&gt;0 \mod 4&lt;/math&gt; and &lt;math&gt;t&lt;/math&gt; is &lt;math&gt;2 \mod 4&lt;/math&gt;. Since this is all &lt;math&gt;\mod 4&lt;/math&gt;, &lt;math&gt;t&lt;/math&gt; must be &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;u&lt;/math&gt; must be &lt;math&gt;4&lt;/math&gt;, in order for &lt;math&gt;5,6&lt;/math&gt; to be paint-able. Thus &lt;math&gt;424&lt;/math&gt; is paintable.<br /> <br /> &lt;math&gt;h&lt;/math&gt; cannot be greater than &lt;math&gt;5&lt;/math&gt;, since if that were the case then the answer would be greater than &lt;math&gt;999&lt;/math&gt;, which would be impossible for the AIME.<br /> <br /> Thus the sum of all paintable numbers is &lt;math&gt;\boxed{757}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> Again, note that &lt;math&gt;h,t,u \neq 1&lt;/math&gt;. The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. By the [[Chinese Remainder Theorem]], the [[greatest common divisor]] of any pair of the three numbers &lt;math&gt;\{h,t,u\}&lt;/math&gt; cannot be &lt;math&gt;1&lt;/math&gt; (since otherwise [[without loss of generality]] consider &lt;math&gt;\text{gcd}\,(h,t) = 1&lt;/math&gt;; then there will be a common solution &lt;math&gt;\pmod{h \times t}&lt;/math&gt;). <br /> <br /> Now for &lt;math&gt;4&lt;/math&gt; to be paint-able, we require either &lt;math&gt;h = 3&lt;/math&gt; or &lt;math&gt;t=2&lt;/math&gt;, but not both. <br /> *In the former condition, since &lt;math&gt;\text{gcd}\,(h,t),\ \text{gcd}\,(h,u) \neq 1&lt;/math&gt;, it follows that &lt;math&gt;3|t,u&lt;/math&gt;. For &lt;math&gt;5&lt;/math&gt; and &lt;math&gt;6&lt;/math&gt; to be paint-able, we require &lt;math&gt;t = u = 3&lt;/math&gt;, and it is easy to see that &lt;math&gt;333&lt;/math&gt; works.<br /> *In the latter condition, similarly we require that &lt;math&gt;2|h,u&lt;/math&gt;. All even numbers are painted. We now renumber the remaining odd pickets to become the set of all positive integers (&lt;math&gt;1,3,5, \ldots \rightarrow 1',2',3', \ldots&lt;/math&gt;, where &lt;math&gt;n' = \frac{n+1}{2}&lt;/math&gt;), which requires the transformation &lt;math&gt;h' = h/2,\ u' = u/2&lt;/math&gt;, and with the painting starting respectively at &lt;math&gt;1',2'&lt;/math&gt;. Our new number system retains the same conditions as above, except without &lt;math&gt;t&lt;/math&gt;. We thus need &lt;math&gt;\text{gcd}\, (h',u') \neq 1, h',u' \neq 1&lt;/math&gt;. Then for &lt;math&gt;3',4'&lt;/math&gt; to be painted, we require &lt;math&gt;h' = u' = 2&lt;/math&gt;. This translates to &lt;math&gt;424&lt;/math&gt;, which we see works. <br /> <br /> Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> <br /> === Solution 3 ===<br /> The three conditions state that no picket number &lt;math&gt;n&lt;/math&gt; may satisfy any two of the conditions: &lt;math&gt;n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}&lt;/math&gt;. Note that the smallest number, &lt;math&gt;min \{ h,t,u \}, &lt;/math&gt; divides the other &lt;math&gt;2&lt;/math&gt;, and the next smallest divide the largest number, otherwise there is a common solution by the [[Chinese Remainder Theorem]]. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least &lt;math&gt;5&lt;/math&gt;, otherwise not all picket will be painted. We are left with few cases (we could also exclude &lt;math&gt;1&lt;/math&gt; as the possibility) which could be done quickly. Thus the answer is &lt;math&gt;333+424 = \boxed{757}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2002|n=I|num-b=8|num-a=10}}<br /> <br /> [[Category:Intermediate Number Theory Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_13&diff=125783 2001 AIME I Problems/Problem 13 2020-06-18T10:10:03Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> In a certain [[circle]], the [[chord]] of a &lt;math&gt;d&lt;/math&gt;-degree arc is &lt;math&gt;22&lt;/math&gt; centimeters long, and the chord of a &lt;math&gt;2d&lt;/math&gt;-degree arc is &lt;math&gt;20&lt;/math&gt; centimeters longer than the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc, where &lt;math&gt;d &lt; 120.&lt;/math&gt; The length of the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc is &lt;math&gt;- m + \sqrt {n}&lt;/math&gt; centimeters, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers. Find &lt;math&gt;m + n.&lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> &lt;center&gt;[[File:2001AIME13.png]]&lt;/center&gt;<br /> <br /> Note that a cyclic quadrilateral in the form of an isosceles trapezoid can be formed from three chords of three &lt;math&gt;d&lt;/math&gt;-degree arcs and one chord of one &lt;math&gt;3d&lt;/math&gt;-degree arc. The diagonals of this trapezoid turn out to be two chords of two &lt;math&gt;2d&lt;/math&gt;-degree arcs. Let &lt;math&gt;AB&lt;/math&gt;, &lt;math&gt;AC&lt;/math&gt;, and &lt;math&gt;BD&lt;/math&gt; be the chords of the &lt;math&gt;d&lt;/math&gt;-degree arcs, and let &lt;math&gt;CD&lt;/math&gt; be the chord of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Also let &lt;math&gt;x&lt;/math&gt; be equal to the chord length of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Hence, the length of the chords, &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;BC&lt;/math&gt;, of the &lt;math&gt;2d&lt;/math&gt;-degree arcs can be represented as &lt;math&gt;x + 20&lt;/math&gt;, as given in the problem. <br /> <br /> Using Ptolemy's theorem,<br /> <br /> &lt;cmath&gt;AB(CD) + AC(BD) = AD(BC)&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 22(22) = (x + 20)^2&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 484 = x^2 + 40x + 400&lt;/cmath&gt;<br /> &lt;cmath&gt;0 = x^2 + 18x - 84&lt;/cmath&gt;<br /> <br /> We can then apply the quadratic formula to find the positive root to this equation since polygons obviously cannot have sides of negative length.<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{18^2 + 4(84)}}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{660}}{2}&lt;/cmath&gt;<br /> <br /> &lt;math&gt;x&lt;/math&gt; simplifies to &lt;math&gt;\frac{-18 + 2\sqrt{165}}{2},&lt;/math&gt; which equals &lt;math&gt;-9 + \sqrt{165}.&lt;/math&gt; Thus, the answer is &lt;math&gt;9 + 165 = \boxed{174}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; and &lt;math&gt;R&lt;/math&gt; be the circumradius. From the given information, &lt;cmath&gt;2R\sin z=22&lt;/cmath&gt; &lt;cmath&gt;2R(\sin 2z-\sin 3z)=20&lt;/cmath&gt; Dividing the latter by the former, &lt;cmath&gt;\frac{2\sin z\cos z-(3\cos^2z\sin z-\sin^3 z)}{\sin z}=2\cos z-(3\cos^2z-\sin^2z)=1+2\cos z-4\cos^2z=\frac{10}{11}&lt;/cmath&gt; &lt;cmath&gt;4\cos^2z-2\cos z-\frac{1}{11}=0 (1)&lt;/cmath&gt; We want to find &lt;cmath&gt;\frac{22\sin (3z)}{\sin z}=22(3-4\sin^2z)=22(4\cos^2z-1).&lt;/cmath&gt; From &lt;math&gt;(1),&lt;/math&gt; this is equivalent to &lt;math&gt;44\cos z-20.&lt;/math&gt; Using the quadratic formula, we find that the desired length is equal to &lt;math&gt;\sqrt{165}-9,&lt;/math&gt; so our answer is &lt;math&gt;\boxed{174.}&lt;/math&gt;<br /> <br /> ===Solution 3===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2}&lt;/math&gt;, &lt;math&gt;R&lt;/math&gt; be the circumradius, and &lt;math&gt;a&lt;/math&gt; be the length of 3d degree chord. Using the extended sine law, we obtain:<br /> &lt;cmath&gt;22=2Rsin(z)&lt;/cmath&gt;<br /> &lt;cmath&gt;20+a=2Rsin(2z)&lt;/cmath&gt;<br /> &lt;cmath&gt;a=2Rsin(3z)&lt;/cmath&gt;<br /> Dividing the second from the first we get &lt;math&gt;cos(z)=\frac{20+a}{44}&lt;/math&gt;<br /> By the triple angle formula we can manipulate the third equation as follows: &lt;math&gt;a=2R\times sin(3z)=\frac{22}{sin(z)} \times (3sin(z)-4sin^3(z)) = 22(3-4sin^2(z))=22(4cos^2(z)-1)=\frac{(20+a)^2}{22}-22&lt;/math&gt;<br /> Solving the quadratic equation gives the answer.<br /> <br /> == See also ==<br /> {{AIME box|year=2001|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_13&diff=125782 2001 AIME I Problems/Problem 13 2020-06-18T10:09:47Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> In a certain [[circle]], the [[chord]] of a &lt;math&gt;d&lt;/math&gt;-degree arc is &lt;math&gt;22&lt;/math&gt; centimeters long, and the chord of a &lt;math&gt;2d&lt;/math&gt;-degree arc is &lt;math&gt;20&lt;/math&gt; centimeters longer than the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc, where &lt;math&gt;d &lt; 120.&lt;/math&gt; The length of the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc is &lt;math&gt;- m + \sqrt {n}&lt;/math&gt; centimeters, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers. Find &lt;math&gt;m + n.&lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> &lt;center&gt;[[File:2001AIME13.png]]&lt;/center&gt;<br /> <br /> Note that a cyclic quadrilateral in the form of an isosceles trapezoid can be formed from three chords of three &lt;math&gt;d&lt;/math&gt;-degree arcs and one chord of one &lt;math&gt;3d&lt;/math&gt;-degree arc. The diagonals of this trapezoid turn out to be two chords of two &lt;math&gt;2d&lt;/math&gt;-degree arcs. Let &lt;math&gt;AB&lt;/math&gt;, &lt;math&gt;AC&lt;/math&gt;, and &lt;math&gt;BD&lt;/math&gt; be the chords of the &lt;math&gt;d&lt;/math&gt;-degree arcs, and let &lt;math&gt;CD&lt;/math&gt; be the chord of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Also let &lt;math&gt;x&lt;/math&gt; be equal to the chord length of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Hence, the length of the chords, &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;BC&lt;/math&gt;, of the &lt;math&gt;2d&lt;/math&gt;-degree arcs can be represented as &lt;math&gt;x + 20&lt;/math&gt;, as given in the problem. <br /> <br /> Using Ptolemy's theorem,<br /> <br /> &lt;cmath&gt;AB(CD) + AC(BD) = AD(BC)&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 22(22) = (x + 20)^2&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 484 = x^2 + 40x + 400&lt;/cmath&gt;<br /> &lt;cmath&gt;0 = x^2 + 18x - 84&lt;/cmath&gt;<br /> <br /> We can then apply the quadratic formula to find the positive root to this equation since polygons obviously cannot have sides of negative length.<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{18^2 + 4(84)}}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{660}}{2}&lt;/cmath&gt;<br /> <br /> &lt;math&gt;x&lt;/math&gt; simplifies to &lt;math&gt;\frac{-18 + 2\sqrt{165}}{2},&lt;/math&gt; which equals &lt;math&gt;-9 + \sqrt{165}.&lt;/math&gt; Thus, the answer is &lt;math&gt;9 + 165 = \boxed{174}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; and &lt;math&gt;R&lt;/math&gt; be the circumradius. From the given information, &lt;cmath&gt;2R\sin z=22&lt;/cmath&gt; &lt;cmath&gt;2R(\sin 2z-\sin 3z)=20&lt;/cmath&gt; Dividing the latter by the former, &lt;cmath&gt;\frac{2\sin z\cos z-(3\cos^2z\sin z-\sin^3 z)}{\sin z}=2\cos z-(3\cos^2z-\sin^2z)=1+2\cos z-4\cos^2z=\frac{10}{11}&lt;/cmath&gt; &lt;cmath&gt;4\cos^2z-2\cos z-\frac{1}{11}=0 (1)&lt;/cmath&gt; We want to find &lt;cmath&gt;\frac{22\sin (3z)}{\sin z}=22(3-4\sin^2z)=22(4\cos^2z-1).&lt;/cmath&gt; From &lt;math&gt;(1),&lt;/math&gt; this is equivalent to &lt;math&gt;44\cos z-20.&lt;/math&gt; Using the quadratic formula, we find that the desired length is equal to &lt;math&gt;\sqrt{165}-9,&lt;/math&gt; so our answer is &lt;math&gt;\boxed{174.}&lt;/math&gt;<br /> <br /> ===Solution 3===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; R&lt;math&gt; be the circumradius, and &lt;/math&gt;a&lt;math&gt; be the length of 3d degree chord. Using the extended sine law, we obtain:<br /> &lt;cmath&gt;22=2Rsin(z)&lt;/cmath&gt;<br /> &lt;cmath&gt;20+a=2Rsin(2z)&lt;/cmath&gt;<br /> &lt;cmath&gt;a=2Rsin(3z)&lt;/cmath&gt;<br /> Dividing the second from the first we get &lt;/math&gt;cos(z)=\frac{20+a}{44}&lt;math&gt;<br /> By the triple angle formula we can manipulate the third equation as follows:<br /> &lt;/math&gt;a=2R\times sin(3z)=\frac{22}{sin(z)} \times (3sin(z)-4sin^3(z)) = 22(3-4sin^2(z))=22(4cos^2(z))$<br /> Solving it gives the answer.<br /> <br /> == See also ==<br /> {{AIME box|year=2001|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_13&diff=125781 2001 AIME I Problems/Problem 13 2020-06-18T10:07:28Z <p>Mysteryguy6647: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> In a certain [[circle]], the [[chord]] of a &lt;math&gt;d&lt;/math&gt;-degree arc is &lt;math&gt;22&lt;/math&gt; centimeters long, and the chord of a &lt;math&gt;2d&lt;/math&gt;-degree arc is &lt;math&gt;20&lt;/math&gt; centimeters longer than the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc, where &lt;math&gt;d &lt; 120.&lt;/math&gt; The length of the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc is &lt;math&gt;- m + \sqrt {n}&lt;/math&gt; centimeters, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers. Find &lt;math&gt;m + n.&lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> &lt;center&gt;[[File:2001AIME13.png]]&lt;/center&gt;<br /> <br /> Note that a cyclic quadrilateral in the form of an isosceles trapezoid can be formed from three chords of three &lt;math&gt;d&lt;/math&gt;-degree arcs and one chord of one &lt;math&gt;3d&lt;/math&gt;-degree arc. The diagonals of this trapezoid turn out to be two chords of two &lt;math&gt;2d&lt;/math&gt;-degree arcs. Let &lt;math&gt;AB&lt;/math&gt;, &lt;math&gt;AC&lt;/math&gt;, and &lt;math&gt;BD&lt;/math&gt; be the chords of the &lt;math&gt;d&lt;/math&gt;-degree arcs, and let &lt;math&gt;CD&lt;/math&gt; be the chord of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Also let &lt;math&gt;x&lt;/math&gt; be equal to the chord length of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Hence, the length of the chords, &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;BC&lt;/math&gt;, of the &lt;math&gt;2d&lt;/math&gt;-degree arcs can be represented as &lt;math&gt;x + 20&lt;/math&gt;, as given in the problem. <br /> <br /> Using Ptolemy's theorem,<br /> <br /> &lt;cmath&gt;AB(CD) + AC(BD) = AD(BC)&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 22(22) = (x + 20)^2&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 484 = x^2 + 40x + 400&lt;/cmath&gt;<br /> &lt;cmath&gt;0 = x^2 + 18x - 84&lt;/cmath&gt;<br /> <br /> We can then apply the quadratic formula to find the positive root to this equation since polygons obviously cannot have sides of negative length.<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{18^2 + 4(84)}}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{660}}{2}&lt;/cmath&gt;<br /> <br /> &lt;math&gt;x&lt;/math&gt; simplifies to &lt;math&gt;\frac{-18 + 2\sqrt{165}}{2},&lt;/math&gt; which equals &lt;math&gt;-9 + \sqrt{165}.&lt;/math&gt; Thus, the answer is &lt;math&gt;9 + 165 = \boxed{174}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; and &lt;math&gt;R&lt;/math&gt; be the circumradius. From the given information, &lt;cmath&gt;2R\sin z=22&lt;/cmath&gt; &lt;cmath&gt;2R(\sin 2z-\sin 3z)=20&lt;/cmath&gt; Dividing the latter by the former, &lt;cmath&gt;\frac{2\sin z\cos z-(3\cos^2z\sin z-\sin^3 z)}{\sin z}=2\cos z-(3\cos^2z-\sin^2z)=1+2\cos z-4\cos^2z=\frac{10}{11}&lt;/cmath&gt; &lt;cmath&gt;4\cos^2z-2\cos z-\frac{1}{11}=0 (1)&lt;/cmath&gt; We want to find &lt;cmath&gt;\frac{22\sin (3z)}{\sin z}=22(3-4\sin^2z)=22(4\cos^2z-1).&lt;/cmath&gt; From &lt;math&gt;(1),&lt;/math&gt; this is equivalent to &lt;math&gt;44\cos z-20.&lt;/math&gt; Using the quadratic formula, we find that the desired length is equal to &lt;math&gt;\sqrt{165}-9,&lt;/math&gt; so our answer is &lt;math&gt;\boxed{174.}&lt;/math&gt;<br /> <br /> ===Solution 3===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2}&lt;/math&gt;, R&lt;math&gt; be the circumradius, and &lt;/math&gt;a&lt;math&gt; be the length of 3d degree chord. Using the extended sine law, we obtain:<br /> &lt;cmath&gt;22=2Rsin(z)&lt;/cmath&gt;<br /> &lt;cmath&gt;20+a=2Rsin(2z)&lt;/cmath&gt;<br /> &lt;cmath&gt;a=2Rsin(3z)&lt;/cmath&gt;<br /> Dividing the second from the first we get &lt;/math&gt;cos(z)=\frac{20+a}{44}&lt;math&gt;<br /> By the triple angle formula we can manipulate the third equation as follows: &lt;/math&gt;a=2R\times sin(3z)=\frac{22}{sin(z)} \times (3sin(z)-4sin^3(z)) = 22(3-4sin^2(z))=22(4cos^2(z))=\frac{(20+a)^2}{22}-22$<br /> Solving the quadratic equation gives the answer.<br /> <br /> == See also ==<br /> {{AIME box|year=2001|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647 https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_13&diff=125780 2001 AIME I Problems/Problem 13 2020-06-18T10:03:51Z <p>Mysteryguy6647: /* Solution */</p> <hr /> <div>== Problem ==<br /> In a certain [[circle]], the [[chord]] of a &lt;math&gt;d&lt;/math&gt;-degree arc is &lt;math&gt;22&lt;/math&gt; centimeters long, and the chord of a &lt;math&gt;2d&lt;/math&gt;-degree arc is &lt;math&gt;20&lt;/math&gt; centimeters longer than the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc, where &lt;math&gt;d &lt; 120.&lt;/math&gt; The length of the chord of a &lt;math&gt;3d&lt;/math&gt;-degree arc is &lt;math&gt;- m + \sqrt {n}&lt;/math&gt; centimeters, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers. Find &lt;math&gt;m + n.&lt;/math&gt;<br /> <br /> == Solution ==<br /> <br /> === Solution 1 ===<br /> &lt;center&gt;[[File:2001AIME13.png]]&lt;/center&gt;<br /> <br /> Note that a cyclic quadrilateral in the form of an isosceles trapezoid can be formed from three chords of three &lt;math&gt;d&lt;/math&gt;-degree arcs and one chord of one &lt;math&gt;3d&lt;/math&gt;-degree arc. The diagonals of this trapezoid turn out to be two chords of two &lt;math&gt;2d&lt;/math&gt;-degree arcs. Let &lt;math&gt;AB&lt;/math&gt;, &lt;math&gt;AC&lt;/math&gt;, and &lt;math&gt;BD&lt;/math&gt; be the chords of the &lt;math&gt;d&lt;/math&gt;-degree arcs, and let &lt;math&gt;CD&lt;/math&gt; be the chord of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Also let &lt;math&gt;x&lt;/math&gt; be equal to the chord length of the &lt;math&gt;3d&lt;/math&gt;-degree arc. Hence, the length of the chords, &lt;math&gt;AD&lt;/math&gt; and &lt;math&gt;BC&lt;/math&gt;, of the &lt;math&gt;2d&lt;/math&gt;-degree arcs can be represented as &lt;math&gt;x + 20&lt;/math&gt;, as given in the problem. <br /> <br /> Using Ptolemy's theorem,<br /> <br /> &lt;cmath&gt;AB(CD) + AC(BD) = AD(BC)&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 22(22) = (x + 20)^2&lt;/cmath&gt;<br /> &lt;cmath&gt;22x + 484 = x^2 + 40x + 400&lt;/cmath&gt;<br /> &lt;cmath&gt;0 = x^2 + 18x - 84&lt;/cmath&gt;<br /> <br /> We can then apply the quadratic formula to find the positive root to this equation since polygons obviously cannot have sides of negative length.<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{18^2 + 4(84)}}{2}&lt;/cmath&gt;<br /> &lt;cmath&gt;x = \frac{-18 + \sqrt{660}}{2}&lt;/cmath&gt;<br /> <br /> &lt;math&gt;x&lt;/math&gt; simplifies to &lt;math&gt;\frac{-18 + 2\sqrt{165}}{2},&lt;/math&gt; which equals &lt;math&gt;-9 + \sqrt{165}.&lt;/math&gt; Thus, the answer is &lt;math&gt;9 + 165 = \boxed{174}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; and &lt;math&gt;R&lt;/math&gt; be the circumradius. From the given information, &lt;cmath&gt;2R\sin z=22&lt;/cmath&gt; &lt;cmath&gt;2R(\sin 2z-\sin 3z)=20&lt;/cmath&gt; Dividing the latter by the former, &lt;cmath&gt;\frac{2\sin z\cos z-(3\cos^2z\sin z-\sin^3 z)}{\sin z}=2\cos z-(3\cos^2z-\sin^2z)=1+2\cos z-4\cos^2z=\frac{10}{11}&lt;/cmath&gt; &lt;cmath&gt;4\cos^2z-2\cos z-\frac{1}{11}=0 (1)&lt;/cmath&gt; We want to find &lt;cmath&gt;\frac{22\sin (3z)}{\sin z}=22(3-4\sin^2z)=22(4\cos^2z-1).&lt;/cmath&gt; From &lt;math&gt;(1),&lt;/math&gt; this is equivalent to &lt;math&gt;44\cos z-20.&lt;/math&gt; Using the quadratic formula, we find that the desired length is equal to &lt;math&gt;\sqrt{165}-9,&lt;/math&gt; so our answer is &lt;math&gt;\boxed{174.}&lt;/math&gt;<br /> <br /> ===Solution 3===<br /> <br /> Let &lt;math&gt;z=\frac{d}{2},&lt;/math&gt; R&lt;math&gt; be the circumradius, and &lt;/math&gt;a&lt;math&gt; be the length of 3d degree chord. Using the extended sine law, we obtain:<br /> &lt;cmath&gt;22=2Rsin(z)&lt;/cmath&gt;<br /> &lt;cmath&gt;20+a=2Rsin(2z)&lt;/cmath&gt;<br /> &lt;cmath&gt;a=2Rsin(3z)&lt;/cmath&gt;<br /> Dividing the second from the first we get &lt;/math&gt;cos(z)=\frac{20+a}{44}&lt;math&gt;<br /> By the triple angle formula we can manipulate the third equation as follows:<br /> &lt;/math&gt;a=2R\times sin(3z)=\frac{22}{sin(z)} \times (3sin(z)-4sin^3(z)) = 22(3-4sin^2(z))=22(4cos^2(z))\$<br /> Solving it gives the answer.<br /> <br /> == See also ==<br /> {{AIME box|year=2001|n=I|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Mysteryguy6647