https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=JNEW&feedformat=atom AoPS Wiki - User contributions [en] 2021-04-17T22:46:48Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Wooga_Looga_Theorem&diff=136097 Wooga Looga Theorem 2020-10-30T00:46:41Z <p>JNEW: /* Testimonials */</p> <hr /> <div>=Definition=<br /> If there is &lt;math&gt;\triangle ABC&lt;/math&gt; and points &lt;math&gt;X,Y,Z&lt;/math&gt; on the sides &lt;math&gt;BC,CA,AB&lt;/math&gt; such that &lt;math&gt;\frac{XB}{XC}=\frac{YC}{YA}=\frac{ZA}{ZB}=\frac mn&lt;/math&gt;, then the ratio &lt;math&gt;\frac{[XYZ]}{[ABC]}=\frac{m^2-m+n}{(m+n)^2}&lt;/math&gt;<br /> <br /> Created by the Ooga Booga Tribe of the Caveman Society, https://www.youtube.com/channel/UC50E9TuLIMWbOPUX45xZPaQ<br /> <br /> =Application 1=<br /> ==Problem==<br /> The Wooga Looga Theorem states that the solution to this problem by franzliszt:<br /> <br /> In &lt;math&gt;\triangle ABC&lt;/math&gt; points &lt;math&gt;X,Y,Z&lt;/math&gt; are on sides &lt;math&gt;BC,CA,AB&lt;/math&gt; such that &lt;math&gt;\frac{XB}{XC}=\frac{YC}{YA}=\frac{ZA}{ZB}=\frac 71&lt;/math&gt;. Find the ratio of &lt;math&gt;[XYZ]&lt;/math&gt; to &lt;math&gt;[ABC]&lt;/math&gt;.<br /> <br /> ==Solution 1==<br /> is this solution by RedFireTruck:<br /> <br /> WLOG let &lt;math&gt;A=(0, 0)&lt;/math&gt;, &lt;math&gt;B=(1, 0)&lt;/math&gt;, &lt;math&gt;C=(x, y)&lt;/math&gt;. Then &lt;math&gt;[ABC]=\frac12|y|&lt;/math&gt; by Shoelace Theorem and &lt;math&gt;X=(\frac{7x+1}{8}, \frac{7y}{8})&lt;/math&gt;, &lt;math&gt;Y=(\frac{x}{8}, \frac{y}{8})&lt;/math&gt;, &lt;math&gt;Z=(\frac78, 0)&lt;/math&gt;. Then &lt;math&gt;[XYZ]=\frac12|\frac{43y}{64}|&lt;/math&gt; by Shoelace Theorem. Therefore the answer is &lt;math&gt;\boxed{\frac{43}{64}}&lt;/math&gt;.<br /> ==Solution 2==<br /> or this solution by franzliszt:<br /> <br /> We apply Barycentric Coordinates w.r.t. &lt;math&gt;\triangle ABC&lt;/math&gt;. Let &lt;math&gt;A=(1,0,0),B=(0,1,0),C=(0,0,1)&lt;/math&gt;. Then we find that &lt;math&gt;X=(0,\tfrac 18,\tfrac 78),Y=(\tfrac 78,0,\tfrac 18),Z=(\tfrac18,\tfrac78,0)&lt;/math&gt;. In the barycentric coordinate system, the area formula is &lt;math&gt;[XYZ]=\begin{vmatrix}<br /> x_{1} &amp;y_{1} &amp;z_{1} \\<br /> x_{2} &amp;y_{2} &amp;z_{2} \\ <br /> x_{3}&amp; y_{3} &amp; z_{3}<br /> \end{vmatrix}\cdot [ABC]&lt;/math&gt; where &lt;math&gt;\triangle XYZ&lt;/math&gt; is a random triangle and &lt;math&gt;\triangle ABC&lt;/math&gt; is the reference triangle. Using this, we find that &lt;cmath&gt;\frac{[XYZ]}{[ABC]}=\begin{vmatrix}<br /> 0&amp;\tfrac 18&amp;\tfrac 78\\<br /> \tfrac 78&amp;0&amp;\tfrac 18\\<br /> \tfrac18&amp;\tfrac78&amp;0<br /> \end{vmatrix}=\frac{43}{64}.&lt;/cmath&gt; &lt;math&gt;\blacksquare&lt;/math&gt;<br /> ==Solution 3==<br /> or this solution by aaja3427:<br /> <br /> According the the Wooga Looga Theorem, It is &lt;math&gt;\frac{49-7+1}{8^2}&lt;/math&gt;. This is &lt;math&gt;\boxed{\frac{43}{64}}&lt;/math&gt;<br /> <br /> ==Solution 4==<br /> or this solution by ilovepizza2020:<br /> <br /> We use the &lt;math&gt;\mathbf{FUNDEMENTAL~THEOREM~OF~GEOGEBRA}&lt;/math&gt; to instantly get &lt;math&gt;\boxed{\frac{43}{64}}&lt;/math&gt;. (Note: You can only use this method when you are not in a contest as this method is so overpowered that the people behind tests decided to ban it.)<br /> <br /> ==Solution 5==<br /> or this solution by eduD_looC:<br /> <br /> This is a perfect application of the Adhiytaha Anweopifanwpuiefhbavpwiuefnapveuihfnpvwheibfpanuwvfaw Lemma, which results in the answer being &lt;math&gt;\boxed{\frac{43}{64}}&lt;/math&gt;. A very beautiful application, which leaves graders and readers speechless.<br /> <br /> =Application 2=<br /> ==Problem==<br /> The Wooga Looga Theorem states that the solution to this problem by Matholic:<br /> <br /> The figure below shows a triangle ABC whose area is 72cm2. If AD: DB = BE: EC =CF: FA =1: 5, find the area of triangle DEF<br /> <br /> ==Solution==<br /> is this solution by franzliszt:<br /> <br /> We apply Barycentric Coordinates w.r.t. &lt;math&gt;\triangle ABC&lt;/math&gt;. Let &lt;math&gt;A=(1,0,0),B=(0,1,0),C=(0,0,1)&lt;/math&gt;. Then we find that &lt;math&gt;D=(\tfrac 56,\tfrac 16,0),E=(0,\tfrac 56,\tfrac 16),F=(\tfrac16,0,\tfrac56)&lt;/math&gt;. In the barycentric coordinate system, the area formula is &lt;math&gt;[XYZ]=\begin{vmatrix}<br /> x_{1} &amp;y_{1} &amp;z_{1} \\ <br /> x_{2} &amp;y_{2} &amp;z_{2} \\ <br /> x_{3}&amp; y_{3} &amp; z_{3}<br /> \end{vmatrix}\cdot [ABC]&lt;/math&gt; where &lt;math&gt;\triangle XYZ&lt;/math&gt; is a random triangle and &lt;math&gt;\triangle ABC&lt;/math&gt; is the reference triangle. Using this, we find that&lt;cmath&gt;\frac{[DEF]}{}=\begin{vmatrix}<br /> \tfrac 56&amp;\tfrac 16&amp;0\\<br /> 0&amp;\tfrac 56&amp;\tfrac 16\\<br /> \tfrac16&amp;0&amp;\tfrac56<br /> \end{vmatrix}=\frac{7}{12}&lt;/cmath&gt; so &lt;math&gt;[DEF]=42&lt;/math&gt;. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> =Application 3=<br /> ==Problem==<br /> The Wooga Looga Theorem states that the solution to this problem by RedFireTruck:<br /> <br /> Find the ratio &lt;math&gt;\frac{[GHI]}{[ABC]}&lt;/math&gt; if &lt;math&gt;\frac{AD}{DB}=\frac{BE}{EC}=\frac{CF}{FA}=\frac12&lt;/math&gt; and &lt;math&gt;\frac{DG}{GE}=\frac{EH}{HF}=\frac{FI}{ID}=1&lt;/math&gt; in the diagram below.&lt;asy&gt;<br /> draw((0, 0)--(6, 0)--(4, 3)--cycle);<br /> draw((2, 0)--(16/3, 1)--(8/3, 2)--cycle);<br /> draw((11/3, 1/2)--(4, 3/2)--(7/3, 1)--cycle);<br /> label(&quot;$A$&quot;, (0, 0), SW);<br /> label(&quot;$B$&quot;, (6, 0), SE);<br /> label(&quot;$C$&quot;, (4, 3), N);<br /> label(&quot;$D$&quot;, (2, 0), S);<br /> label(&quot;$E$&quot;, (16/3, 1), NE);<br /> label(&quot;$F$&quot;, (8/3, 2), NW);<br /> label(&quot;$G$&quot;, (11/3, 1/2), SE);<br /> label(&quot;$H$&quot;, (4, 3/2), NE);<br /> label(&quot;$I$&quot;, (7/3, 1), W);<br /> &lt;/asy&gt;<br /> ==Solution 1==<br /> is this solution by franzliszt:<br /> <br /> By the Wooga Looga Theorem, &lt;math&gt;\frac{[DEF]}{[ABC]}=\frac{2^2-2+1}{(1+2)^2}=\frac 13&lt;/math&gt;. Notice that &lt;math&gt;\triangle GHI&lt;/math&gt; is the medial triangle of '''Wooga Looga Triangle ''' of &lt;math&gt;\triangle ABC&lt;/math&gt;. So &lt;math&gt;\frac{[GHI]}{[DEF]}=\frac 14&lt;/math&gt; and &lt;math&gt;\frac{[GHI]}{[ABD]}=\frac{[DEF]}{[ABC]}\cdot\frac{[GHI]}{[DEF]}=\frac 13 \cdot \frac 14 = \frac {1}{12}&lt;/math&gt; by Chain Rule ideas.<br /> <br /> ==Solution 2==<br /> or this solution by franzliszt:<br /> <br /> Apply Barycentrics w.r.t. &lt;math&gt;\triangle ABC&lt;/math&gt; so that &lt;math&gt;A=(1,0,0),B=(0,1,0),C=(0,0,1)&lt;/math&gt;. Then &lt;math&gt;D=(\tfrac 23,\tfrac 13,0),E=(0,\tfrac 23,\tfrac 13),F=(\tfrac 13,0,\tfrac 23)&lt;/math&gt;. And &lt;math&gt;G=(\tfrac 13,\tfrac 12,\tfrac 16),H=(\tfrac 16,\tfrac 13,\tfrac 12),I=(\tfrac 12,\tfrac 16,\tfrac 13)&lt;/math&gt;.<br /> <br /> In the barycentric coordinate system, the area formula is &lt;math&gt;[XYZ]=\begin{vmatrix} x_{1} &amp;y_{1} &amp;z_{1} \\ x_{2} &amp;y_{2} &amp;z_{2} \\ x_{3}&amp; y_{3} &amp; z_{3} \end{vmatrix}\cdot [ABC]&lt;/math&gt; where &lt;math&gt;\triangle XYZ&lt;/math&gt; is a random triangle and &lt;math&gt;\triangle ABC&lt;/math&gt; is the reference triangle. Using this, we find that&lt;cmath&gt;\frac{[GHI]}{[ABC]}=\begin{vmatrix} \tfrac 13&amp;\tfrac 12&amp;\tfrac 16\\ \tfrac 16&amp;\tfrac 13&amp;\tfrac 12\\ \tfrac 12&amp;\tfrac 16&amp;\tfrac 13 \end{vmatrix}=\frac{1}{12}.&lt;/cmath&gt;<br /> =Testimonials=<br /> The Wooga Looga Theorem can be used to prove many problems and should be a part of any geometry textbook.<br /> ~ilp2020<br /> <br /> The Wooga Looga Theorem is amazing and can be applied to so many problems and should be taught in every school. - RedFireTruck<br /> <br /> The Wooga Looga Theorem is the best. -aaja3427<br /> <br /> This lemma sucks. Adihaya Jayasharmaramankumarguptareddybavarajugopal's Lemme is way better, as it trivializes every problem -Heavytoothpaste<br /> @above, this is a Theorem which is different than a Lemma thonk -franzi<br /> <br /> This Theorem is literally false. Fix it.</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10A_Problems/Problem_11&diff=83274 2017 AMC 10A Problems/Problem 11 2017-02-09T12:32:36Z <p>JNEW: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> The region consisting of all point in three-dimensional space within 3 units of line segment &lt;math&gt;\overline{AB}&lt;/math&gt; has volume 216&lt;math&gt;\pi&lt;/math&gt;. What is the length &lt;math&gt;\textit{AB}&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A)}\ 6\qquad\textbf{(B)}\ 12\qquad\textbf{(C)}\ 18\qquad\textbf{(D)}\ 20\qquad\textbf{(E)}\ 24&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> In order to solve this problem, we must first visualize what the region contained looks like. We know that, in a three dimensional plane, the region consisting of all points within &lt;math&gt;3&lt;/math&gt; units of a point would be a sphere with radius &lt;math&gt;3&lt;/math&gt;. However, we need to find the region containing all points within 3 units of a segment. It can be seen that our region is a cylinder with two hemispheres on either end. We know the volume of our region, so we set up the following equation (the volume of our cylinder + the volume of our two hemispheres will equal &lt;math&gt;216 \pi&lt;/math&gt;):<br /> <br /> &lt;math&gt;\frac{4 \pi }{3} \cdot 3^3+9 \pi x=216 \pi&lt;/math&gt;, where &lt;math&gt;x&lt;/math&gt; is equal to the length of our line segment.<br /> <br /> Solving, we find that &lt;math&gt;x = \boxed{\textbf{(D)}\ 20}&lt;/math&gt;.<br /> <br /> ==Diagram==<br /> <br /> http://i.imgur.com/cwNt293.png<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2017|ab=A|num-b=10|num-a=12}}<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Answer_Key&diff=81380 2016 AMC 8 Answer Key 2016-11-23T15:11:10Z <p>JNEW: </p> <hr /> <div>#C<br /> #A<br /> #A<br /> #B<br /> #E<br /> #B<br /> #B<br /> #C<br /> #B<br /> #D<br /> #B<br /> #B<br /> #D<br /> #A<br /> #C<br /> #D<br /> #D<br /> #C<br /> #E<br /> #A<br /> #B<br /> #C<br /> #C<br /> #A<br /> #B</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Problems/Problem_25&diff=81375 2016 AMC 8 Problems/Problem 25 2016-11-23T15:04:47Z <p>JNEW: </p> <hr /> <div>25. A semicircle is inscribed in an isosceles triangle with base &lt;math&gt;16&lt;/math&gt; and height &lt;math&gt;15&lt;/math&gt; so that the diameter of the semicircle is contained in the base of the triangle as shown. What is the radius of the semicircle?<br /> <br /> &lt;asy&gt;draw((0,0)--(8,15)--(16,0)--(0,0));<br /> draw(arc((8,0),7.0588,0,180));&lt;/asy&gt;<br /> <br /> &lt;math&gt;\textbf{(A) }4 \sqrt{3}\qquad\textbf{(B) } \dfrac{120}{17}\qquad\textbf{(C) }10\qquad\textbf{(D) }\dfrac{17\sqrt{2}}{2}\qquad \textbf{(E)} \dfrac{17\sqrt{3}}{2}&lt;/math&gt;<br /> <br /> <br /> ==Solution 1==<br /> <br /> {{AMC8 box|year=2016|num-b=24|after=Last Problem}}<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Problems/Problem_25&diff=81374 2016 AMC 8 Problems/Problem 25 2016-11-23T15:04:34Z <p>JNEW: /* Solution 1 */</p> <hr /> <div>25. A semicircle is inscribed in an isosceles triangle with base &lt;math&gt;16&lt;/math&gt; and height &lt;math&gt;15&lt;/math&gt; so that the diameter of the semicircle is contained in the base of the triangle as shown. What is the radius of the semicircle?<br /> <br /> &lt;asy&gt;draw((0,0)--(8,15)--(16,0)--(0,0));<br /> draw(arc((8,0),7.0588,0,180));&lt;/asy&gt;<br /> <br /> &lt;math&gt;\textbf{(A) }4 \sqrt{3}\qquad\textbf{(B) } \dfrac{120}{17}\qquad\textbf{(C) }10\qquad\textbf{(D) }\dfrac{17\sqrt{2}}{2}\qquad \textbf{(E)} \dfrac{17\sqrt{3}}{2}&lt;/math&gt;<br /> <br /> B<br /> <br /> ==Solution 1==<br /> <br /> {{AMC8 box|year=2016|num-b=24|after=Last Problem}}<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Answer_Key&diff=81371 2016 AMC 8 Answer Key 2016-11-23T15:01:53Z <p>JNEW: </p> <hr /> <div>#C<br /> #A<br /> #A<br /> #B<br /> #E<br /> #B<br /> #B<br /> #C<br /> #B<br /> #D<br /> #B<br /> #B<br /> #D<br /> #A<br /> #C<br /> #D<br /> #B<br /> #C<br /> #E<br /> #A<br /> #B<br /> #C<br /> #C<br /> #A<br /> #B</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Problems/Problem_24&diff=81349 2016 AMC 8 Problems/Problem 24 2016-11-23T14:19:09Z <p>JNEW: /* Solution */</p> <hr /> <div>The digits &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, &lt;math&gt;4&lt;/math&gt;, and &lt;math&gt;5&lt;/math&gt; are each used once to write a five-digit number &lt;math&gt;PQRST&lt;/math&gt;. The three-digit number &lt;math&gt;PQR&lt;/math&gt; is divisible by &lt;math&gt;4&lt;/math&gt;, the three-digit number &lt;math&gt;QRS&lt;/math&gt; is divisible by &lt;math&gt;5&lt;/math&gt;, and the three-digit number &lt;math&gt;RST&lt;/math&gt; is divisible by &lt;math&gt;3&lt;/math&gt;. What is &lt;math&gt;P&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) }1\qquad\textbf{(B) }2\qquad\textbf{(C) }3\qquad\textbf{(D) }4\qquad \textbf{(E) }5&lt;/math&gt;<br /> <br /> ==Solution==<br /> <br /> <br /> {{solution}}<br /> {{AMC8 box|year=2016|num-b=23|num-a=25}}<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Problems/Problem_5&diff=81345 2016 AMC 8 Problems/Problem 5 2016-11-23T14:16:09Z <p>JNEW: /* Solution */</p> <hr /> <div>The number &lt;math&gt;N&lt;/math&gt; is a two-digit number.<br /> <br /> • When &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;9&lt;/math&gt;, the remainder is &lt;math&gt;1&lt;/math&gt;.<br /> <br /> • When &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;10&lt;/math&gt;, the remainder is &lt;math&gt;3&lt;/math&gt;.<br /> <br /> What is the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;11&lt;/math&gt;?<br /> <br /> <br /> &lt;math&gt;\textbf{(A) }0\qquad\textbf{(B) }2\qquad\textbf{(C) }4\qquad\textbf{(D) }5\qquad \textbf{(E) }7&lt;/math&gt;<br /> <br /> ==Solution==<br /> From the second bullet, we know that the second digit must be 3. Because there is a remainder of 1 when it is divided by three, the multiple of 9 must end in a 2. We now look for this one: <br /> <br /> &lt;math&gt;9(1)=9\\<br /> 9(2)=18\\<br /> 9(3)=27\\<br /> 9(4)=36\\<br /> 9(5)=45\\<br /> 9(6)=54\\<br /> 9(7)=63\\<br /> 9(8)=72&lt;/math&gt;<br /> <br /> The number &lt;math&gt;72+1=73&lt;/math&gt; satisfies both conditions. We subtract the biggest multiple of 11 less than 73 to get the remainder. Thus, &lt;math&gt;73-11(6)=73-66=\boxed{\text{(E) }7}&lt;/math&gt;.<br /> <br /> {{AMC8 box|year=2016|num-b=4|num-a=6}}<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2007_AMC_12A_Problems/Problem_25&diff=79667 2007 AMC 12A Problems/Problem 25 2016-07-21T16:36:28Z <p>JNEW: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Call a set of integers ''spacy'' if it contains no more than one out of any three consecutive integers. How many [[subset]]s of &lt;math&gt;\{1,2,3,\ldots,12\},&lt;/math&gt; including the [[empty set]], are spacy?<br /> <br /> &lt;cmath&gt;\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129&lt;/cmath&gt;<br /> <br /> __TOC__<br /> <br /> == Solution ==<br /> === Solution 1 ===<br /> Let &lt;math&gt;S_{n}&lt;/math&gt; denote the number of spacy subsets of &lt;math&gt;\{ 1, 2, ... n \}&lt;/math&gt;. We have &lt;math&gt;S_{0} = 1, S_{1} = 2, S_{2} = 3&lt;/math&gt;. <br /> <br /> The spacy subsets of &lt;math&gt;S_{n + 1}&lt;/math&gt; can be divided into two groups:<br /> *&lt;math&gt;A = &lt;/math&gt; those not containing &lt;math&gt;n + 1&lt;/math&gt;. Clearly &lt;math&gt;|A|=S_{n}&lt;/math&gt;. <br /> *&lt;math&gt;B = &lt;/math&gt; those containing &lt;math&gt;n + 1&lt;/math&gt;. We have &lt;math&gt;|B|=S_{n - 2}&lt;/math&gt;, since removing &lt;math&gt;n + 1&lt;/math&gt; from any set in &lt;math&gt;B&lt;/math&gt; produces a spacy set with all elements at most equal to &lt;math&gt;n - 2,&lt;/math&gt; and each such spacy set can be constructed from exactly one spacy set in &lt;math&gt;B&lt;/math&gt;.<br /> Hence,<br /> <br /> &lt;div style=&quot;text-align:center;&quot;&gt;&lt;math&gt;S_{n + 1} = S_{n} + S_{n - 2}&lt;/math&gt;&lt;/div&gt;<br /> <br /> From this [[recursion]], we find that<br /> <br /> {| class=&quot;wikitable&quot; border=&quot;1px solid&quot;<br /> |-<br /> | &lt;math&gt;S(0)&lt;/math&gt; || &lt;math&gt;S(1)&lt;/math&gt; || &lt;math&gt;S(2)&lt;/math&gt; || &lt;math&gt;S(3)&lt;/math&gt; || &lt;math&gt;S(4)&lt;/math&gt; || &lt;math&gt;S(5)&lt;/math&gt; || &lt;math&gt;S(6)&lt;/math&gt; || &lt;math&gt;S(7)&lt;/math&gt; || &lt;math&gt;S(8)&lt;/math&gt; || &lt;math&gt;S(9)&lt;/math&gt; || &lt;math&gt;S(10)&lt;/math&gt; || &lt;math&gt;S(11)&lt;/math&gt; || &lt;math&gt;S(12)&lt;/math&gt; || <br /> |-<br /> | 1 || 2 || 3 || 4 || 6 || 9 || 13 || 19 || 28 || 41 || 60 || 88 || 129<br /> |}<br /> <br /> === Solution 2 ===<br /> Since each of the elements of the subsets must be spaced at least two apart, a divider counting argument can be used.<br /> <br /> From the set &lt;math&gt;\{1,2,3,4,5,6,7,8,9,10,11,12\}&lt;/math&gt; we choose at most four numbers. Let those numbers be represented by balls. Between each of the balls there are at least two dividers. So for example, o | | o | | o | | o | | represents &lt;math&gt;{1,4,7,10}&lt;/math&gt;.<br /> <br /> For subsets of size &lt;math&gt;k&lt;/math&gt; there must be &lt;math&gt;2(k - 1)&lt;/math&gt; dividers between the balls, leaving &lt;math&gt;12 - k - 2(k - 1) = 12 - 3k + 2&lt;/math&gt; dividers to be be placed in &lt;math&gt;k + 1&lt;/math&gt; spots between the balls. The number of way this can be done is &lt;math&gt;\binom{(12 - 3k + 2) + (k + 1) - 1}k = \binom{12 - 2k + 2}k&lt;/math&gt;.<br /> <br /> Therefore, the number of spacy subsets is &lt;math&gt;\binom 64 + \binom 83 + \binom{10}2 + \binom{12}1 + \binom{14}0 = 129&lt;/math&gt;.<br /> === Solution 3 ===<br /> A shifting argument is also possible, and is similiar in spirit to Solution 2. Clearly we can have at most &lt;math&gt;4&lt;/math&gt; elements. Given any arrangment, we subract &lt;math&gt;2i-2&lt;/math&gt; from the &lt;math&gt;i-th&lt;/math&gt; element in our subset, when the elements are arranged in increasing order. This creates a [[bijection]] with the number of size &lt;math&gt;k&lt;/math&gt; subsets of the set of the first &lt;math&gt;14-2k&lt;/math&gt; positive integers. For instance, the arrangment o | | o | | o | | | o | corresponds to the arrangment o o o | o |. Notice that there is no longer any restriction on consectutive numbers. Therefore, we can easily plug in the possible integers 0, 1, 2, 3, 4, 5 for &lt;math&gt;k&lt;/math&gt;: &lt;math&gt;{14 \choose 0} + {12 \choose 1} + {10 \choose 2} + {8 \choose 3} + {6 \choose 4} = \boxed{129}&lt;/math&gt;<br /> <br /> In general, the number of subsets of a set with &lt;math&gt;n&lt;/math&gt; element and with no &lt;math&gt;k&lt;/math&gt; consecutive numbers is &lt;math&gt;\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=0}{{n-(k-1)(i-1) \choose i}}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AMC12 box|year=2007|ab=A|num-b=24|after=Last question}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> JNEW https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_8_Problems/Problem_25&diff=72672 2010 AMC 8 Problems/Problem 25 2015-10-31T18:58:04Z <p>JNEW: Somebody trolled and edited.</p> <hr /> <div>==Problem==<br /> Everyday at school, Jo climbs a flight of &lt;math&gt;6&lt;/math&gt; stairs. Jo can take the stairs &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, or &lt;math&gt;3&lt;/math&gt; at a time. For example, Jo could climb &lt;math&gt;3&lt;/math&gt;, then &lt;math&gt;1&lt;/math&gt;, then &lt;math&gt;2&lt;/math&gt;. In how many ways can Jo climb the stairs?<br /> <br /> &lt;math&gt; \textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24 &lt;/math&gt;<br /> <br /> ==Solution==<br /> We will systematically consider all of the possibilities. A valid climb can be thought of as a sequence of some or all of the numbers &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, and &lt;math&gt;3&lt;/math&gt;, in which the sum of the sequence adds to &lt;math&gt;6&lt;/math&gt;. Since there is only one way to create a sequence which contains all &lt;math&gt;1s&lt;/math&gt;, all &lt;math&gt;2s&lt;/math&gt;, or all &lt;math&gt;3s&lt;/math&gt;, there are three possible sequences which only contain one number. If we attempt to create sequences which contain one &lt;math&gt;2&lt;/math&gt; and the rest &lt;math&gt;1s&lt;/math&gt;, the sequence will contain one &lt;math&gt;2&lt;/math&gt; and four &lt;math&gt;1s&lt;/math&gt;. We can place the &lt;math&gt;2&lt;/math&gt; in either the first, second, third, fourth, or fifth position, giving a total of five possibilities. If we attempt to create sequences which contain one &lt;math&gt;3&lt;/math&gt; and the rest &lt;math&gt;1s&lt;/math&gt;, the sequence will contain one &lt;math&gt;3&lt;/math&gt; and three &lt;math&gt;1s&lt;/math&gt;. We can place the &lt;math&gt;3&lt;/math&gt; in either the first, second, third, or fourth position, giving a total of four possibilities. For sequences which contain exactly two &lt;math&gt;2s&lt;/math&gt; and the rest &lt;math&gt;1s&lt;/math&gt;, the sequence will contain two &lt;math&gt;2s&lt;/math&gt; and two &lt;math&gt;1s&lt;/math&gt;. The two &lt;math&gt;2s&lt;/math&gt; could be next to each other, separated by one &lt;math&gt;1&lt;/math&gt; in between, or separated by two &lt;math&gt;1s&lt;/math&gt; in between. We can place the two &lt;math&gt;2s&lt;/math&gt; next to each other in three ways, separated by one &lt;math&gt;1&lt;/math&gt; in two ways, and separated by two &lt;math&gt;1s&lt;/math&gt; in only one way. This gives us a total of six ways to create a sequence which contains two &lt;math&gt;2s&lt;/math&gt; and two &lt;math&gt;1s&lt;/math&gt;. Note that we cannot have a sequence of only &lt;math&gt;2s&lt;/math&gt; and &lt;math&gt;3s&lt;/math&gt; since the sum will either be &lt;math&gt;5&lt;/math&gt; or greater than &lt;math&gt;6&lt;/math&gt;. We now only need to consider the case where we use all three numbers in the sequence. Since all three numbers add to &lt;math&gt;6&lt;/math&gt;, the number of permutations of the three numbers is &lt;math&gt;3!=6&lt;/math&gt;. Adding up the number of sequences above, we get: &lt;math&gt;3+5+4+6+6=24&lt;/math&gt;. Thus, answer choice &lt;math&gt;\boxed{\textbf{(E)}\ 24}&lt;/math&gt; is correct.<br /> <br /> ==Solution 2==<br /> An inductive approach is quick and easy. The number of ways to climb one stair is &lt;math&gt;1&lt;/math&gt;. There are &lt;math&gt;2&lt;/math&gt; ways to climb two stairs: &lt;math&gt;1&lt;/math&gt;,&lt;math&gt;1&lt;/math&gt; or &lt;math&gt;2&lt;/math&gt;. For 3 stairs, there are four ways: <br /> (&lt;math&gt;1&lt;/math&gt;,&lt;math&gt;1&lt;/math&gt;,&lt;math&gt;1&lt;/math&gt;)<br /> (&lt;math&gt;1&lt;/math&gt;,&lt;math&gt;2&lt;/math&gt;)<br /> (&lt;math&gt;2&lt;/math&gt;,&lt;math&gt;1&lt;/math&gt;)<br /> (&lt;math&gt;3&lt;/math&gt;)<br /> <br /> For four stairs, consider what step they came from to land on the fourth stair. They could have hopped straight from the 1st, done a double from #2, or used a single step from #3. The ways to get to each of these steps are &lt;math&gt;1+2+4=7&lt;/math&gt; ways to get to step 4. The pattern can then be extended:<br /> &lt;math&gt;4&lt;/math&gt; steps: &lt;math&gt;1+2+4=7&lt;/math&gt; ways.<br /> &lt;math&gt;5&lt;/math&gt; steps: &lt;math&gt;2+4+7=13&lt;/math&gt; ways.<br /> &lt;math&gt;6&lt;/math&gt; steps: &lt;math&gt;4+7+13=24&lt;/math&gt; ways.<br /> <br /> Thus, there are &lt;math&gt;\boxed{\textbf{(E) } 24}&lt;/math&gt; ways to get to step 6.<br /> <br /> ==See Also==<br /> {{AMC8 box|year=2010|num-b=24|after=Last Problem}}<br /> {{MAA Notice}}</div> JNEW