https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Mvp+harry&feedformat=atom AoPS Wiki - User contributions [en] 2021-06-21T16:25:51Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_25&diff=115794 2018 AMC 10B Problems/Problem 25 2020-01-29T01:49:05Z <p>Mvp harry: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; denote the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;. How many real numbers &lt;math&gt;x&lt;/math&gt; satisfy the equation &lt;math&gt;x^2 + 10,000\lfloor x \rfloor = 10,000x&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) } 197 \qquad \textbf{(B) } 198 \qquad \textbf{(C) } 199 \qquad \textbf{(D) } 200 \qquad \textbf{(E) } 201&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> This rewrites itself to &lt;math&gt;x^2=10,000\{x\}&lt;/math&gt;.<br /> <br /> Graphing &lt;math&gt;y=10,000\{x\}&lt;/math&gt; and &lt;math&gt;y=x^2&lt;/math&gt; we see that the former is a set of line segments with slope &lt;math&gt;10,000&lt;/math&gt; from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;1&lt;/math&gt; with a hole at &lt;math&gt;x=1&lt;/math&gt;, then &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; with a hole at &lt;math&gt;x=2&lt;/math&gt; etc.<br /> <br /> Here is a graph of &lt;math&gt;y=x^2&lt;/math&gt; and &lt;math&gt;y=16\{x\}&lt;/math&gt; for visualization.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> size(400);<br /> xaxis(&quot;$x$&quot;,Ticks(Label(fontsize(8pt)),new real[]{-5,-4,-3, -2, -1,0,1 2,3, 4,5}));<br /> yaxis(&quot;$y$&quot;,Ticks(Label(fontsize(8pt)),new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}));<br /> real y(real x) {return x^2;}<br /> draw(circle((-4,16), 0.1));<br /> draw(circle((-3,16), 0.1));<br /> draw(circle((-2,16), 0.1));<br /> draw(circle((-1,16), 0.1));<br /> draw(circle((0,16), 0.1));<br /> draw(circle((1,16), 0.1));<br /> draw(circle((2,16), 0.1));<br /> draw(circle((3,16), 0.1));<br /> draw(circle((4,16), 0.1));<br /> draw((-5,0)--(-4,16), black);<br /> draw((-4,0)--(-3,16), black);<br /> draw((-3,0)--(-2,16), black);<br /> draw((-2,0)--(-1,16), black);<br /> draw((-1,0)--(-0,16), black);<br /> draw((0,0)--(1,16), black);<br /> draw((1,0)--(2,16), black);<br /> draw((2,0)--(3,16), black);<br /> draw((3,0)--(4,16), black);<br /> draw(graph(y,-4.2,4.2),green);<br /> &lt;/asy&gt;<br /> <br /> Now notice that when &lt;math&gt;x=\pm 100&lt;/math&gt; then graph has a hole at &lt;math&gt;(\pm 100,10,000)&lt;/math&gt; which the equation &lt;math&gt;y=x^2&lt;/math&gt; passes through and then continues upwards. Thus our set of possible solutions is bounded by &lt;math&gt;(-100,100)&lt;/math&gt;. We can see that &lt;math&gt;y=x^2&lt;/math&gt; intersects each of the lines once and there are &lt;math&gt;99-(-99)+1=199&lt;/math&gt; lines for an answer of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt;.<br /> <br /> Note: From the graph, we can clearly see there are &lt;math&gt;4&lt;/math&gt; solutions on the negative side of the &lt;math&gt;x&lt;/math&gt;-axis and only &lt;math&gt;2&lt;/math&gt; on the positive side of the &lt;math&gt;x&lt;/math&gt;-axis. So the solution really should be from &lt;math&gt;-100&lt;/math&gt; to &lt;math&gt;98&lt;/math&gt;, which still counts to &lt;math&gt;199&lt;/math&gt;. A couple of the alternative solutions also seem to have the same flaw.<br /> <br /> ==Solution 2==<br /> <br /> Same as the first solution, &lt;math&gt;x^2=10,000\{x\} &lt;/math&gt;.<br /> <br /> <br /> We can write &lt;math&gt;x&lt;/math&gt; as &lt;math&gt;\lfloor x \rfloor+\{x\}&lt;/math&gt;. Expanding everything, we get a quadratic in &lt;math&gt;\{x\}&lt;/math&gt; in terms of &lt;math&gt;\lfloor x \rfloor&lt;/math&gt;:<br /> &lt;cmath&gt; \{x\}^2+ (2\lfloor x \rfloor -10,000)\{x\} + \lfloor x \rfloor ^2 = 0&lt;/cmath&gt;<br /> <br /> <br /> We use the quadratic formula to solve for &lt;math&gt;\{x\}&lt;/math&gt; :<br /> &lt;cmath&gt; \{x\} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ ( 2\lfloor x \rfloor - 10,000 )^2 - 4\lfloor x \rfloor^2 }}{2} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ 4\lfloor x \rfloor^2 -20,000 \lfloor x \rfloor + 10,000^2- 4\lfloor x \rfloor^2 }}{2} &lt;/cmath&gt;<br /> <br /> <br /> Since &lt;math&gt; 0 \leq \{x\} &lt; 1 &lt;/math&gt;, we get an inequality which we can then solve. After simplifying a lot, we get that &lt;math&gt;\lfloor x \rfloor^2 + 2\lfloor x \rfloor - 9999 &lt; 0&lt;/math&gt;.<br /> <br /> <br /> Solving over the integers, &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 3==<br /> <br /> Let &lt;math&gt;x = a+k&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the integer part of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;.<br /> We can then rewrite the problem below:<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000(a+k)&lt;/math&gt;<br /> <br /> From here, we get<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000a + 10000k&lt;/math&gt;<br /> <br /> Solving for &lt;math&gt;a+k = x&lt;/math&gt;<br /> <br /> &lt;math&gt;(a+k)^2 = 10000k&lt;/math&gt;<br /> <br /> &lt;math&gt;x = a+k = \pm100\sqrt{k}&lt;/math&gt;<br /> <br /> Because &lt;math&gt;0 \leq k &lt; 1&lt;/math&gt;, we know that &lt;math&gt;a+k&lt;/math&gt; cannot be less than or equal to &lt;math&gt;-100&lt;/math&gt; nor greater than or equal to &lt;math&gt;100&lt;/math&gt;. Therefore:<br /> <br /> &lt;math&gt;-99 \leq x \leq 99&lt;/math&gt;<br /> <br /> There are &lt;math&gt;199&lt;/math&gt; elements in this range, so the answer is &lt;math&gt;\boxed{\textbf{(C)} \text{ 199}}&lt;/math&gt;.<br /> <br /> Note (not by author): this solution seems to be invalid at first, because one can not determine whether &lt;math&gt;x&lt;/math&gt; is an integer or not. However, it actually works because although &lt;math&gt;x&lt;/math&gt; itself might not be an integer, it is very close to one, so there are 199 potential &lt;math&gt;x&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> <br /> Notice the given equation is equivilent to &lt;math&gt;(\lfloor x \rfloor+\{x\})^2=10,000\{x\} &lt;/math&gt;<br /> <br /> Now we now that &lt;math&gt;\{x\} &lt; 1&lt;/math&gt; so plugging in &lt;math&gt;1&lt;/math&gt; for &lt;math&gt;\{x\}&lt;/math&gt; we can find the upper and lower bounds for the values.<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1)^2 = 10,000(1)&lt;/math&gt;<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1) = \pm 100&lt;/math&gt;<br /> <br /> &lt;math&gt;\lfloor x \rfloor = 99, -101&lt;/math&gt;<br /> <br /> And just like &lt;math&gt;\textbf{Solution 2}&lt;/math&gt;, we see that &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 5==<br /> <br /> First, we can let &lt;math&gt;\{x\} = b, \lfloor x \rfloor = a&lt;/math&gt;. We know that &lt;math&gt;a + b = x&lt;/math&gt; by definition. We can rearrange the equation to obtain <br /> <br /> &lt;math&gt;x^2 = 10^4(x - a)&lt;/math&gt;. <br /> <br /> By taking square root on both sides, we obtain &lt;math&gt;x = \pm 100 \sqrt{b}&lt;/math&gt; (because &lt;math&gt;x - a = b&lt;/math&gt;). We know since &lt;math&gt;b&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;, it must be that &lt;math&gt;0 \leq b &lt; 1&lt;/math&gt;. Thus, &lt;math&gt;x&lt;/math&gt; may take any value in the interval &lt;math&gt;-100 &lt; x &lt; 100&lt;/math&gt;. Hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values for &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; in that range and we are done. <br /> <br /> ~awesome1st<br /> <br /> ==Solution 6==<br /> <br /> Firstly, we can rearrange to get &lt;math&gt;\lfloor x \rfloor = x-x^2/10,000&lt;/math&gt;<br /> <br /> Rearranging, we get &lt;math&gt;x^2/10,000 &lt; 1&lt;/math&gt;<br /> <br /> Noticing that &lt;math&gt;10,000 = 100^2&lt;/math&gt;, we know that x can only be within the boundaries of &lt;math&gt;-100&lt;x&lt;100&lt;/math&gt; and hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values.<br /> <br /> ==Solution 7==<br /> <br /> Firstly, if &lt;math&gt;x&lt;/math&gt; is an integer, then &lt;math&gt;10,000\lfloor x \rfloor=10,000x&lt;/math&gt;, so &lt;math&gt;x&lt;/math&gt; must be &lt;math&gt;0&lt;/math&gt;.<br /> <br /> If &lt;math&gt;0&lt;x&lt;1&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;0&lt;x^2&lt;1&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =0&lt;/math&gt;<br /> <br /> &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;<br /> <br /> Therefore, &lt;math&gt;0&lt;x^2+10,000\lfloor x \rfloor &lt;1&lt;/math&gt;, which overlaps with &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;. This means that there is at least one real solution between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Since &lt;math&gt;x^2+10,000\lfloor x \rfloor &lt;/math&gt; increases exponentially and &lt;math&gt;10,000x&lt;/math&gt; increases linearly, there is only one solution for this case. <br /> <br /> Similarly, if &lt;math&gt;1&lt;x&lt;2&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;1&lt;x^2&lt;4&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =1&lt;/math&gt;<br /> <br /> &lt;math&gt;&lt;10,000&lt;10,000x&lt;20,000&lt;/math&gt;<br /> <br /> By following similar logic, we can find that there is one solution between &lt;math&gt;1&lt;/math&gt; ad &lt;math&gt;2&lt;/math&gt;. <br /> <br /> We can also follow the same process to find that there are negative solutions for &lt;math&gt;x&lt;/math&gt; as well.<br /> <br /> There are not an infinite amount of solutions, so at one point there will be no solutions when &lt;math&gt;n&lt;x&lt;n+1&lt;/math&gt; for some positive integer &lt;math&gt;n&lt;/math&gt;. Looking at the answer solutions, they are near &lt;math&gt;200&lt;/math&gt;, so it seems logical that the upper and lower limits are around &lt;math&gt;100&lt;/math&gt; and &lt;math&gt;-100&lt;/math&gt;. Testing this out, we can see that there is a solution for &lt;math&gt;99&lt;x&lt;100&lt;/math&gt;, but not for &lt;math&gt;100&lt;x&lt;101&lt;/math&gt;. Similarly, there is a solution for &lt;math&gt;-100&lt;x&lt;-99&lt;/math&gt;, but not for &lt;math&gt;-101&lt;x&lt;-100&lt;/math&gt;. This means that there are &lt;math&gt;99&lt;/math&gt; positive solutions, &lt;math&gt;99&lt;/math&gt; negative solutions, and &lt;math&gt;0&lt;/math&gt; for a total of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions.<br /> <br /> ~Owen1204<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=vHKPbaXwJUE<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2018|ab=B|num-b=24|after=Last Problem}}<br /> {{AMC12 box|year=2018|ab=B|num-b=23|num-a=25}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_25&diff=115791 2018 AMC 10B Problems/Problem 25 2020-01-29T01:45:42Z <p>Mvp harry: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; denote the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;. How many real numbers &lt;math&gt;x&lt;/math&gt; satisfy the equation &lt;math&gt;x^2 + 10,000\lfloor x \rfloor = 10,000x&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) } 197 \qquad \textbf{(B) } 198 \qquad \textbf{(C) } 199 \qquad \textbf{(D) } 200 \qquad \textbf{(E) } 201&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> This rewrites itself to &lt;math&gt;x^2=10,000\{x\}&lt;/math&gt;.<br /> <br /> Graphing &lt;math&gt;y=10,000\{x\}&lt;/math&gt; and &lt;math&gt;y=x^2&lt;/math&gt; we see that the former is a set of line segments with slope &lt;math&gt;10,000&lt;/math&gt; from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;1&lt;/math&gt; with a hole at &lt;math&gt;x=1&lt;/math&gt;, then &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; with a hole at &lt;math&gt;x=2&lt;/math&gt; etc.<br /> <br /> Here is a graph of &lt;math&gt;y=x^2&lt;/math&gt; and &lt;math&gt;y=16\{x\}&lt;/math&gt; for visualization.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> size(400);<br /> xaxis(&quot;$x$&quot;,Ticks(Label(fontsize(8pt)),new real[]{-5,-4,-3, -2, -1,0,1 2,3, 4,5}));<br /> yaxis(&quot;$y$&quot;,Ticks(Label(fontsize(8pt)),new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}));<br /> real y(real x) {return x^2;}<br /> draw(circle((-4,16), 0.1));<br /> draw(circle((-3,16), 0.1));<br /> draw(circle((-2,16), 0.1));<br /> draw(circle((-1,16), 0.1));<br /> draw(circle((0,16), 0.1));<br /> draw(circle((1,16), 0.1));<br /> draw(circle((2,16), 0.1));<br /> draw(circle((3,16), 0.1));<br /> draw(circle((4,16), 0.1));<br /> draw((-5,0)--(-4,16), black);<br /> draw((-4,0)--(-3,16), black);<br /> draw((-3,0)--(-2,16), black);<br /> draw((-2,0)--(-1,16), black);<br /> draw((-1,0)--(-0,16), black);<br /> draw((0,0)--(1,16), black);<br /> draw((1,0)--(2,16), black);<br /> draw((2,0)--(3,16), black);<br /> draw((3,0)--(4,16), black);<br /> draw(graph(y,-4.2,4.2),green);<br /> &lt;/asy&gt;<br /> <br /> Now notice that when &lt;math&gt;x=\pm 100&lt;/math&gt; then graph has a hole at &lt;math&gt;(\pm 100,10,000)&lt;/math&gt; which the equation &lt;math&gt;y=x^2&lt;/math&gt; passes through and then continues upwards. Thus our set of possible solutions is bounded by &lt;math&gt;(-100,100)&lt;/math&gt;. We can see that &lt;math&gt;y=x^2&lt;/math&gt; intersects each of the lines once and there are &lt;math&gt;99-(-99)+1=199&lt;/math&gt; lines for an answer of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt;.<br /> <br /> Note: From the graph, we can clearly see there are &lt;math&gt;4&lt;/math&gt; solutions on the negative side of the &lt;math&gt;x&lt;/math&gt;-axis and only &lt;math&gt;2&lt;/math&gt; on the positive side of the &lt;math&gt;x&lt;/math&gt;-axis. So the solution really should be from &lt;math&gt;-100&lt;/math&gt; to &lt;math&gt;98&lt;/math&gt;, which still counts to &lt;math&gt;199&lt;/math&gt;. A couple of the alternative solutions also seem to have the same flaw.<br /> <br /> ==Solution 2==<br /> <br /> Same as the first solution, &lt;math&gt;x^2=10,000\{x\} &lt;/math&gt;.<br /> <br /> <br /> We can write &lt;math&gt;x&lt;/math&gt; as &lt;math&gt;\lfloor x \rfloor+\{x\}&lt;/math&gt;. Expanding everything, we get a quadratic in &lt;math&gt;\{x\}&lt;/math&gt; in terms of &lt;math&gt;\lfloor x \rfloor&lt;/math&gt;:<br /> &lt;cmath&gt; \{x\}^2+ (2\lfloor x \rfloor -10,000)\{x\} + \lfloor x \rfloor ^2 = 0&lt;/cmath&gt;<br /> <br /> <br /> We use the quadratic formula to solve for &lt;math&gt;\{x\}&lt;/math&gt; :<br /> &lt;cmath&gt; \{x\} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ ( 2\lfloor x \rfloor - 10,000 )^2 - 4\lfloor x \rfloor^2 }}{2} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ 4\lfloor x \rfloor^2 -20,000 \lfloor x \rfloor + 10,000^2- 4\lfloor x \rfloor^2 }}{2} &lt;/cmath&gt;<br /> <br /> <br /> Since &lt;math&gt; 0 \leq \{x\} &lt; 1 &lt;/math&gt;, we get an inequality which we can then solve. After simplifying a lot, we get that &lt;math&gt;\lfloor x \rfloor^2 + 2\lfloor x \rfloor - 9999 &lt; 0&lt;/math&gt;.<br /> <br /> <br /> Solving over the integers, &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 3==<br /> <br /> Let &lt;math&gt;x = a+k&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the integer part of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;.<br /> We can then rewrite the problem below:<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000(a+k)&lt;/math&gt;<br /> <br /> From here, we get<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000a + 10000k&lt;/math&gt;<br /> <br /> Solving for &lt;math&gt;a+k = x&lt;/math&gt;<br /> <br /> &lt;math&gt;(a+k)^2 = 10000k&lt;/math&gt;<br /> <br /> &lt;math&gt;x = a+k = \pm100\sqrt{k}&lt;/math&gt;<br /> <br /> Because &lt;math&gt;0 \leq k &lt; 1&lt;/math&gt;, we know that &lt;math&gt;a+k&lt;/math&gt; cannot be less than or equal to &lt;math&gt;-100&lt;/math&gt; nor greater than or equal to &lt;math&gt;100&lt;/math&gt;. Therefore:<br /> <br /> &lt;math&gt;-99 \leq x \leq 99&lt;/math&gt;<br /> <br /> There are &lt;math&gt;199&lt;/math&gt; elements in this range, so the answer is &lt;math&gt;\boxed{\textbf{(C)} \text{ 199}}&lt;/math&gt;.<br /> <br /> Note (not by author): this solution is invalid, because one can not determine whether &lt;math&gt;x&lt;/math&gt; is an integer or not.<br /> <br /> ==Solution 4==<br /> <br /> Notice the given equation is equivilent to &lt;math&gt;(\lfloor x \rfloor+\{x\})^2=10,000\{x\} &lt;/math&gt;<br /> <br /> Now we now that &lt;math&gt;\{x\} &lt; 1&lt;/math&gt; so plugging in &lt;math&gt;1&lt;/math&gt; for &lt;math&gt;\{x\}&lt;/math&gt; we can find the upper and lower bounds for the values.<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1)^2 = 10,000(1)&lt;/math&gt;<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1) = \pm 100&lt;/math&gt;<br /> <br /> &lt;math&gt;\lfloor x \rfloor = 99, -101&lt;/math&gt;<br /> <br /> And just like &lt;math&gt;\textbf{Solution 2}&lt;/math&gt;, we see that &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 5==<br /> <br /> First, we can let &lt;math&gt;\{x\} = b, \lfloor x \rfloor = a&lt;/math&gt;. We know that &lt;math&gt;a + b = x&lt;/math&gt; by definition. We can rearrange the equation to obtain <br /> <br /> &lt;math&gt;x^2 = 10^4(x - a)&lt;/math&gt;. <br /> <br /> By taking square root on both sides, we obtain &lt;math&gt;x = \pm 100 \sqrt{b}&lt;/math&gt; (because &lt;math&gt;x - a = b&lt;/math&gt;). We know since &lt;math&gt;b&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;, it must be that &lt;math&gt;0 \leq b &lt; 1&lt;/math&gt;. Thus, &lt;math&gt;x&lt;/math&gt; may take any value in the interval &lt;math&gt;-100 &lt; x &lt; 100&lt;/math&gt;. Hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values for &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; in that range and we are done. <br /> <br /> ~awesome1st<br /> <br /> ==Solution 6==<br /> <br /> Firstly, we can rearrange to get &lt;math&gt;\lfloor x \rfloor = x-x^2/10,000&lt;/math&gt;<br /> <br /> Rearranging, we get &lt;math&gt;x^2/10,000 &lt; 1&lt;/math&gt;<br /> <br /> Noticing that &lt;math&gt;10,000 = 100^2&lt;/math&gt;, we know that x can only be within the boundaries of &lt;math&gt;-100&lt;x&lt;100&lt;/math&gt; and hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values.<br /> <br /> ==Solution 7==<br /> <br /> Firstly, if &lt;math&gt;x&lt;/math&gt; is an integer, then &lt;math&gt;10,000\lfloor x \rfloor=10,000x&lt;/math&gt;, so &lt;math&gt;x&lt;/math&gt; must be &lt;math&gt;0&lt;/math&gt;.<br /> <br /> If &lt;math&gt;0&lt;x&lt;1&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;0&lt;x^2&lt;1&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =0&lt;/math&gt;<br /> <br /> &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;<br /> <br /> Therefore, &lt;math&gt;0&lt;x^2+10,000\lfloor x \rfloor &lt;1&lt;/math&gt;, which overlaps with &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;. This means that there is at least one real solution between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Since &lt;math&gt;x^2+10,000\lfloor x \rfloor &lt;/math&gt; increases exponentially and &lt;math&gt;10,000x&lt;/math&gt; increases linearly, there is only one solution for this case. <br /> <br /> Similarly, if &lt;math&gt;1&lt;x&lt;2&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;1&lt;x^2&lt;4&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =1&lt;/math&gt;<br /> <br /> &lt;math&gt;&lt;10,000&lt;10,000x&lt;20,000&lt;/math&gt;<br /> <br /> By following similar logic, we can find that there is one solution between &lt;math&gt;1&lt;/math&gt; ad &lt;math&gt;2&lt;/math&gt;. <br /> <br /> We can also follow the same process to find that there are negative solutions for &lt;math&gt;x&lt;/math&gt; as well.<br /> <br /> There are not an infinite amount of solutions, so at one point there will be no solutions when &lt;math&gt;n&lt;x&lt;n+1&lt;/math&gt; for some positive integer &lt;math&gt;n&lt;/math&gt;. Looking at the answer solutions, they are near &lt;math&gt;200&lt;/math&gt;, so it seems logical that the upper and lower limits are around &lt;math&gt;100&lt;/math&gt; and &lt;math&gt;-100&lt;/math&gt;. Testing this out, we can see that there is a solution for &lt;math&gt;99&lt;x&lt;100&lt;/math&gt;, but not for &lt;math&gt;100&lt;x&lt;101&lt;/math&gt;. Similarly, there is a solution for &lt;math&gt;-100&lt;x&lt;-99&lt;/math&gt;, but not for &lt;math&gt;-101&lt;x&lt;-100&lt;/math&gt;. This means that there are &lt;math&gt;99&lt;/math&gt; positive solutions, &lt;math&gt;99&lt;/math&gt; negative solutions, and &lt;math&gt;0&lt;/math&gt; for a total of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions.<br /> <br /> ~Owen1204<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=vHKPbaXwJUE<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2018|ab=B|num-b=24|after=Last Problem}}<br /> {{AMC12 box|year=2018|ab=B|num-b=23|num-a=25}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_25&diff=115790 2018 AMC 10B Problems/Problem 25 2020-01-29T01:45:24Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; denote the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;. How many real numbers &lt;math&gt;x&lt;/math&gt; satisfy the equation &lt;math&gt;x^2 + 10,000\lfloor x \rfloor = 10,000x&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) } 197 \qquad \textbf{(B) } 198 \qquad \textbf{(C) } 199 \qquad \textbf{(D) } 200 \qquad \textbf{(E) } 201&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> This rewrites itself to &lt;math&gt;x^2=10,000\{x\}&lt;/math&gt;.<br /> <br /> Graphing &lt;math&gt;y=10,000\{x\}&lt;/math&gt; and &lt;math&gt;y=x^2&lt;/math&gt; we see that the former is a set of line segments with slope &lt;math&gt;10,000&lt;/math&gt; from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;1&lt;/math&gt; with a hole at &lt;math&gt;x=1&lt;/math&gt;, then &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; with a hole at &lt;math&gt;x=2&lt;/math&gt; etc.<br /> <br /> Here is a graph of &lt;math&gt;y=x^2&lt;/math&gt; and &lt;math&gt;y=16\{x\}&lt;/math&gt; for visualization.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> size(400);<br /> xaxis(&quot;$x$&quot;,Ticks(Label(fontsize(8pt)),new real[]{-5,-4,-3, -2, -1,0,1 2,3, 4,5}));<br /> yaxis(&quot;$y$&quot;,Ticks(Label(fontsize(8pt)),new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}));<br /> real y(real x) {return x^2;}<br /> draw(circle((-4,16), 0.1));<br /> draw(circle((-3,16), 0.1));<br /> draw(circle((-2,16), 0.1));<br /> draw(circle((-1,16), 0.1));<br /> draw(circle((0,16), 0.1));<br /> draw(circle((1,16), 0.1));<br /> draw(circle((2,16), 0.1));<br /> draw(circle((3,16), 0.1));<br /> draw(circle((4,16), 0.1));<br /> draw((-5,0)--(-4,16), black);<br /> draw((-4,0)--(-3,16), black);<br /> draw((-3,0)--(-2,16), black);<br /> draw((-2,0)--(-1,16), black);<br /> draw((-1,0)--(-0,16), black);<br /> draw((0,0)--(1,16), black);<br /> draw((1,0)--(2,16), black);<br /> draw((2,0)--(3,16), black);<br /> draw((3,0)--(4,16), black);<br /> draw(graph(y,-4.2,4.2),green);<br /> &lt;/asy&gt;<br /> <br /> Now notice that when &lt;math&gt;x=\pm 100&lt;/math&gt; then graph has a hole at &lt;math&gt;(\pm 100,10,000)&lt;/math&gt; which the equation &lt;math&gt;y=x^2&lt;/math&gt; passes through and then continues upwards. Thus our set of possible solutions is bounded by &lt;math&gt;(-100,100)&lt;/math&gt;. We can see that &lt;math&gt;y=x^2&lt;/math&gt; intersects each of the lines once and there are &lt;math&gt;99-(-99)+1=199&lt;/math&gt; lines for an answer of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt;.<br /> <br /> Note: From the graph, we can clearly see there are &lt;math&gt;4&lt;/math&gt; solutions on the negative side of the &lt;math&gt;x&lt;/math&gt;-axis and only &lt;math&gt;2&lt;/math&gt; on the positive side of the &lt;math&gt;x&lt;/math&gt;-axis. So the solution really should be from &lt;math&gt;-100&lt;/math&gt; to &lt;math&gt;98&lt;/math&gt;, which still counts to &lt;math&gt;199&lt;/math&gt;. A couple of the alternative solutions also seem to have the same flaw.<br /> <br /> ==Solution 2==<br /> <br /> Same as the first solution, &lt;math&gt;x^2=10,000\{x\} &lt;/math&gt;.<br /> <br /> <br /> We can write &lt;math&gt;x&lt;/math&gt; as &lt;math&gt;\lfloor x \rfloor+\{x\}&lt;/math&gt;. Expanding everything, we get a quadratic in &lt;math&gt;\{x\}&lt;/math&gt; in terms of &lt;math&gt;\lfloor x \rfloor&lt;/math&gt;:<br /> &lt;cmath&gt; \{x\}^2+ (2\lfloor x \rfloor -10,000)\{x\} + \lfloor x \rfloor ^2 = 0&lt;/cmath&gt;<br /> <br /> <br /> We use the quadratic formula to solve for &lt;math&gt;\{x\}&lt;/math&gt; :<br /> &lt;cmath&gt; \{x\} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ ( 2\lfloor x \rfloor - 10,000 )^2 - 4\lfloor x \rfloor^2 }}{2} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ 4\lfloor x \rfloor^2 -20,000 \lfloor x \rfloor + 10,000^2- 4\lfloor x \rfloor^2 }}{2} &lt;/cmath&gt;<br /> <br /> <br /> Since &lt;math&gt; 0 \leq \{x\} &lt; 1 &lt;/math&gt;, we get an inequality which we can then solve. After simplifying a lot, we get that &lt;math&gt;\lfloor x \rfloor^2 + 2\lfloor x \rfloor - 9999 &lt; 0&lt;/math&gt;.<br /> <br /> <br /> Solving over the integers, &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 3==<br /> <br /> Let &lt;math&gt;x = a+k&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the integer part of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;.<br /> We can then rewrite the problem below:<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000(a+k)&lt;/math&gt;<br /> <br /> From here, we get<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000a + 10000k&lt;/math&gt;<br /> <br /> Solving for &lt;math&gt;a+k = x&lt;/math&gt;<br /> <br /> &lt;math&gt;(a+k)^2 = 10000k&lt;/math&gt;<br /> <br /> &lt;math&gt;x = a+k = \pm100\sqrt{k}&lt;/math&gt;<br /> <br /> Because &lt;math&gt;0 \leq k &lt; 1&lt;/math&gt;, we know that &lt;math&gt;a+k&lt;/math&gt; cannot be less than or equal to &lt;math&gt;-100&lt;/math&gt; nor greater than or equal to &lt;math&gt;100&lt;/math&gt;. Therefore:<br /> <br /> &lt;math&gt;-99 \leq x \leq 99&lt;/math&gt;<br /> <br /> There are &lt;math&gt;199&lt;/math&gt; elements in this range, so the answer is &lt;math&gt;\boxed{\textbf{(C)} \text{ 199}}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> <br /> Notice the given equation is equivilent to &lt;math&gt;(\lfloor x \rfloor+\{x\})^2=10,000\{x\} &lt;/math&gt;<br /> <br /> Now we now that &lt;math&gt;\{x\} &lt; 1&lt;/math&gt; so plugging in &lt;math&gt;1&lt;/math&gt; for &lt;math&gt;\{x\}&lt;/math&gt; we can find the upper and lower bounds for the values.<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1)^2 = 10,000(1)&lt;/math&gt;<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1) = \pm 100&lt;/math&gt;<br /> <br /> &lt;math&gt;\lfloor x \rfloor = 99, -101&lt;/math&gt;<br /> <br /> And just like &lt;math&gt;\textbf{Solution 2}&lt;/math&gt;, we see that &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 5==<br /> <br /> First, we can let &lt;math&gt;\{x\} = b, \lfloor x \rfloor = a&lt;/math&gt;. We know that &lt;math&gt;a + b = x&lt;/math&gt; by definition. We can rearrange the equation to obtain <br /> <br /> &lt;math&gt;x^2 = 10^4(x - a)&lt;/math&gt;. <br /> <br /> By taking square root on both sides, we obtain &lt;math&gt;x = \pm 100 \sqrt{b}&lt;/math&gt; (because &lt;math&gt;x - a = b&lt;/math&gt;). We know since &lt;math&gt;b&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;, it must be that &lt;math&gt;0 \leq b &lt; 1&lt;/math&gt;. Thus, &lt;math&gt;x&lt;/math&gt; may take any value in the interval &lt;math&gt;-100 &lt; x &lt; 100&lt;/math&gt;. Hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values for &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; in that range and we are done. <br /> <br /> ~awesome1st<br /> <br /> ==Solution 6==<br /> <br /> Firstly, we can rearrange to get &lt;math&gt;\lfloor x \rfloor = x-x^2/10,000&lt;/math&gt;<br /> <br /> Rearranging, we get &lt;math&gt;x^2/10,000 &lt; 1&lt;/math&gt;<br /> <br /> Noticing that &lt;math&gt;10,000 = 100^2&lt;/math&gt;, we know that x can only be within the boundaries of &lt;math&gt;-100&lt;x&lt;100&lt;/math&gt; and hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values.<br /> <br /> ==Solution 7==<br /> <br /> Firstly, if &lt;math&gt;x&lt;/math&gt; is an integer, then &lt;math&gt;10,000\lfloor x \rfloor=10,000x&lt;/math&gt;, so &lt;math&gt;x&lt;/math&gt; must be &lt;math&gt;0&lt;/math&gt;.<br /> <br /> If &lt;math&gt;0&lt;x&lt;1&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;0&lt;x^2&lt;1&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =0&lt;/math&gt;<br /> <br /> &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;<br /> <br /> Therefore, &lt;math&gt;0&lt;x^2+10,000\lfloor x \rfloor &lt;1&lt;/math&gt;, which overlaps with &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;. This means that there is at least one real solution between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Since &lt;math&gt;x^2+10,000\lfloor x \rfloor &lt;/math&gt; increases exponentially and &lt;math&gt;10,000x&lt;/math&gt; increases linearly, there is only one solution for this case. <br /> <br /> Similarly, if &lt;math&gt;1&lt;x&lt;2&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;1&lt;x^2&lt;4&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =1&lt;/math&gt;<br /> <br /> &lt;math&gt;&lt;10,000&lt;10,000x&lt;20,000&lt;/math&gt;<br /> <br /> By following similar logic, we can find that there is one solution between &lt;math&gt;1&lt;/math&gt; ad &lt;math&gt;2&lt;/math&gt;. <br /> <br /> We can also follow the same process to find that there are negative solutions for &lt;math&gt;x&lt;/math&gt; as well.<br /> <br /> There are not an infinite amount of solutions, so at one point there will be no solutions when &lt;math&gt;n&lt;x&lt;n+1&lt;/math&gt; for some positive integer &lt;math&gt;n&lt;/math&gt;. Looking at the answer solutions, they are near &lt;math&gt;200&lt;/math&gt;, so it seems logical that the upper and lower limits are around &lt;math&gt;100&lt;/math&gt; and &lt;math&gt;-100&lt;/math&gt;. Testing this out, we can see that there is a solution for &lt;math&gt;99&lt;x&lt;100&lt;/math&gt;, but not for &lt;math&gt;100&lt;x&lt;101&lt;/math&gt;. Similarly, there is a solution for &lt;math&gt;-100&lt;x&lt;-99&lt;/math&gt;, but not for &lt;math&gt;-101&lt;x&lt;-100&lt;/math&gt;. This means that there are &lt;math&gt;99&lt;/math&gt; positive solutions, &lt;math&gt;99&lt;/math&gt; negative solutions, and &lt;math&gt;0&lt;/math&gt; for a total of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions.<br /> <br /> ~Owen1204<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=vHKPbaXwJUE<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2018|ab=B|num-b=24|after=Last Problem}}<br /> {{AMC12 box|year=2018|ab=B|num-b=23|num-a=25}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_25&diff=115789 2018 AMC 10B Problems/Problem 25 2020-01-29T01:44:49Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; denote the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;. How many real numbers &lt;math&gt;x&lt;/math&gt; satisfy the equation &lt;math&gt;x^2 + 10,000\lfloor x \rfloor = 10,000x&lt;/math&gt;?<br /> <br /> &lt;math&gt;\textbf{(A) } 197 \qquad \textbf{(B) } 198 \qquad \textbf{(C) } 199 \qquad \textbf{(D) } 200 \qquad \textbf{(E) } 201&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> This rewrites itself to &lt;math&gt;x^2=10,000\{x\}&lt;/math&gt;.<br /> <br /> Graphing &lt;math&gt;y=10,000\{x\}&lt;/math&gt; and &lt;math&gt;y=x^2&lt;/math&gt; we see that the former is a set of line segments with slope &lt;math&gt;10,000&lt;/math&gt; from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;1&lt;/math&gt; with a hole at &lt;math&gt;x=1&lt;/math&gt;, then &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;2&lt;/math&gt; with a hole at &lt;math&gt;x=2&lt;/math&gt; etc.<br /> <br /> Here is a graph of &lt;math&gt;y=x^2&lt;/math&gt; and &lt;math&gt;y=16\{x\}&lt;/math&gt; for visualization.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> size(400);<br /> xaxis(&quot;$x$&quot;,Ticks(Label(fontsize(8pt)),new real[]{-5,-4,-3, -2, -1,0,1 2,3, 4,5}));<br /> yaxis(&quot;$y$&quot;,Ticks(Label(fontsize(8pt)),new real[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}));<br /> real y(real x) {return x^2;}<br /> draw(circle((-4,16), 0.1));<br /> draw(circle((-3,16), 0.1));<br /> draw(circle((-2,16), 0.1));<br /> draw(circle((-1,16), 0.1));<br /> draw(circle((0,16), 0.1));<br /> draw(circle((1,16), 0.1));<br /> draw(circle((2,16), 0.1));<br /> draw(circle((3,16), 0.1));<br /> draw(circle((4,16), 0.1));<br /> draw((-5,0)--(-4,16), black);<br /> draw((-4,0)--(-3,16), black);<br /> draw((-3,0)--(-2,16), black);<br /> draw((-2,0)--(-1,16), black);<br /> draw((-1,0)--(-0,16), black);<br /> draw((0,0)--(1,16), black);<br /> draw((1,0)--(2,16), black);<br /> draw((2,0)--(3,16), black);<br /> draw((3,0)--(4,16), black);<br /> draw(graph(y,-4.2,4.2),green);<br /> &lt;/asy&gt;<br /> <br /> Now notice that when &lt;math&gt;x=\pm 100&lt;/math&gt; then graph has a hole at &lt;math&gt;(\pm 100,10,000)&lt;/math&gt; which the equation &lt;math&gt;y=x^2&lt;/math&gt; passes through and then continues upwards. Thus our set of possible solutions is bounded by &lt;math&gt;(-100,100)&lt;/math&gt;. We can see that &lt;math&gt;y=x^2&lt;/math&gt; intersects each of the lines once and there are &lt;math&gt;99-(-99)+1=199&lt;/math&gt; lines for an answer of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt;.<br /> <br /> Note: From the graph, we can clearly see there are &lt;math&gt;4&lt;/math&gt; solutions on the negative side of the &lt;math&gt;x&lt;/math&gt;-axis and only &lt;math&gt;2&lt;/math&gt; on the positive side of the &lt;math&gt;x&lt;/math&gt;-axis. So the solution really should be from &lt;math&gt;-100&lt;/math&gt; to &lt;math&gt;98&lt;/math&gt;, which still counts to &lt;math&gt;199&lt;/math&gt;. A couple of the alternative solutions also seem to have the same flaw.<br /> <br /> ==Solution 2==<br /> <br /> Same as the first solution, &lt;math&gt;x^2=10,000\{x\} &lt;/math&gt;.<br /> <br /> <br /> We can write &lt;math&gt;x&lt;/math&gt; as &lt;math&gt;\lfloor x \rfloor+\{x\}&lt;/math&gt;. Expanding everything, we get a quadratic in &lt;math&gt;\{x\}&lt;/math&gt; in terms of &lt;math&gt;\lfloor x \rfloor&lt;/math&gt;:<br /> &lt;cmath&gt; \{x\}^2+ (2\lfloor x \rfloor -10,000)\{x\} + \lfloor x \rfloor ^2 = 0&lt;/cmath&gt;<br /> <br /> <br /> We use the quadratic formula to solve for &lt;math&gt;\{x\}&lt;/math&gt; :<br /> &lt;cmath&gt; \{x\} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ ( 2\lfloor x \rfloor - 10,000 )^2 - 4\lfloor x \rfloor^2 }}{2} = \frac {-2\lfloor x \rfloor + 10,000 \pm \sqrt{ 4\lfloor x \rfloor^2 -20,000 \lfloor x \rfloor + 10,000^2- 4\lfloor x \rfloor^2 }}{2} &lt;/cmath&gt;<br /> <br /> <br /> Since &lt;math&gt; 0 \leq \{x\} &lt; 1 &lt;/math&gt;, we get an inequality which we can then solve. After simplifying a lot, we get that &lt;math&gt;\lfloor x \rfloor^2 + 2\lfloor x \rfloor - 9999 &lt; 0&lt;/math&gt;.<br /> <br /> <br /> Solving over the integers, &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> <br /> Note (not by author): this solution is invalid, because one can not determine whether &lt;math&gt;x&lt;/math&gt; is an integer or not.<br /> <br /> ==Solution 3==<br /> <br /> Let &lt;math&gt;x = a+k&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the integer part of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;.<br /> We can then rewrite the problem below:<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000(a+k)&lt;/math&gt;<br /> <br /> From here, we get<br /> <br /> &lt;math&gt;(a+k)^2 + 10000a = 10000a + 10000k&lt;/math&gt;<br /> <br /> Solving for &lt;math&gt;a+k = x&lt;/math&gt;<br /> <br /> &lt;math&gt;(a+k)^2 = 10000k&lt;/math&gt;<br /> <br /> &lt;math&gt;x = a+k = \pm100\sqrt{k}&lt;/math&gt;<br /> <br /> Because &lt;math&gt;0 \leq k &lt; 1&lt;/math&gt;, we know that &lt;math&gt;a+k&lt;/math&gt; cannot be less than or equal to &lt;math&gt;-100&lt;/math&gt; nor greater than or equal to &lt;math&gt;100&lt;/math&gt;. Therefore:<br /> <br /> &lt;math&gt;-99 \leq x \leq 99&lt;/math&gt;<br /> <br /> There are &lt;math&gt;199&lt;/math&gt; elements in this range, so the answer is &lt;math&gt;\boxed{\textbf{(C)} \text{ 199}}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> <br /> Notice the given equation is equivilent to &lt;math&gt;(\lfloor x \rfloor+\{x\})^2=10,000\{x\} &lt;/math&gt;<br /> <br /> Now we now that &lt;math&gt;\{x\} &lt; 1&lt;/math&gt; so plugging in &lt;math&gt;1&lt;/math&gt; for &lt;math&gt;\{x\}&lt;/math&gt; we can find the upper and lower bounds for the values.<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1)^2 = 10,000(1)&lt;/math&gt;<br /> <br /> &lt;math&gt;(\lfloor x \rfloor +1) = \pm 100&lt;/math&gt;<br /> <br /> &lt;math&gt;\lfloor x \rfloor = 99, -101&lt;/math&gt;<br /> <br /> And just like &lt;math&gt;\textbf{Solution 2}&lt;/math&gt;, we see that &lt;math&gt;-101 &lt; \lfloor x \rfloor &lt; 99 &lt;/math&gt;, and since &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is an integer, there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions. Each value of &lt;math&gt; \lfloor x \rfloor&lt;/math&gt; should correspond to one value of &lt;math&gt;x&lt;/math&gt;, so we are done.<br /> <br /> ==Solution 5==<br /> <br /> First, we can let &lt;math&gt;\{x\} = b, \lfloor x \rfloor = a&lt;/math&gt;. We know that &lt;math&gt;a + b = x&lt;/math&gt; by definition. We can rearrange the equation to obtain <br /> <br /> &lt;math&gt;x^2 = 10^4(x - a)&lt;/math&gt;. <br /> <br /> By taking square root on both sides, we obtain &lt;math&gt;x = \pm 100 \sqrt{b}&lt;/math&gt; (because &lt;math&gt;x - a = b&lt;/math&gt;). We know since &lt;math&gt;b&lt;/math&gt; is the fractional part of &lt;math&gt;x&lt;/math&gt;, it must be that &lt;math&gt;0 \leq b &lt; 1&lt;/math&gt;. Thus, &lt;math&gt;x&lt;/math&gt; may take any value in the interval &lt;math&gt;-100 &lt; x &lt; 100&lt;/math&gt;. Hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values for &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; in that range and we are done. <br /> <br /> ~awesome1st<br /> <br /> ==Solution 6==<br /> <br /> Firstly, we can rearrange to get &lt;math&gt;\lfloor x \rfloor = x-x^2/10,000&lt;/math&gt;<br /> <br /> Rearranging, we get &lt;math&gt;x^2/10,000 &lt; 1&lt;/math&gt;<br /> <br /> Noticing that &lt;math&gt;10,000 = 100^2&lt;/math&gt;, we know that x can only be within the boundaries of &lt;math&gt;-100&lt;x&lt;100&lt;/math&gt; and hence, we know that there are &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; potential values.<br /> <br /> ==Solution 7==<br /> <br /> Firstly, if &lt;math&gt;x&lt;/math&gt; is an integer, then &lt;math&gt;10,000\lfloor x \rfloor=10,000x&lt;/math&gt;, so &lt;math&gt;x&lt;/math&gt; must be &lt;math&gt;0&lt;/math&gt;.<br /> <br /> If &lt;math&gt;0&lt;x&lt;1&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;0&lt;x^2&lt;1&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =0&lt;/math&gt;<br /> <br /> &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;<br /> <br /> Therefore, &lt;math&gt;0&lt;x^2+10,000\lfloor x \rfloor &lt;1&lt;/math&gt;, which overlaps with &lt;math&gt;0&lt;10,000x&lt;10,000&lt;/math&gt;. This means that there is at least one real solution between &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Since &lt;math&gt;x^2+10,000\lfloor x \rfloor &lt;/math&gt; increases exponentially and &lt;math&gt;10,000x&lt;/math&gt; increases linearly, there is only one solution for this case. <br /> <br /> Similarly, if &lt;math&gt;1&lt;x&lt;2&lt;/math&gt;, then we know the following:<br /> <br /> &lt;math&gt;1&lt;x^2&lt;4&lt;/math&gt;<br /> <br /> &lt;math&gt;10,000\lfloor x \rfloor =1&lt;/math&gt;<br /> <br /> &lt;math&gt;&lt;10,000&lt;10,000x&lt;20,000&lt;/math&gt;<br /> <br /> By following similar logic, we can find that there is one solution between &lt;math&gt;1&lt;/math&gt; ad &lt;math&gt;2&lt;/math&gt;. <br /> <br /> We can also follow the same process to find that there are negative solutions for &lt;math&gt;x&lt;/math&gt; as well.<br /> <br /> There are not an infinite amount of solutions, so at one point there will be no solutions when &lt;math&gt;n&lt;x&lt;n+1&lt;/math&gt; for some positive integer &lt;math&gt;n&lt;/math&gt;. Looking at the answer solutions, they are near &lt;math&gt;200&lt;/math&gt;, so it seems logical that the upper and lower limits are around &lt;math&gt;100&lt;/math&gt; and &lt;math&gt;-100&lt;/math&gt;. Testing this out, we can see that there is a solution for &lt;math&gt;99&lt;x&lt;100&lt;/math&gt;, but not for &lt;math&gt;100&lt;x&lt;101&lt;/math&gt;. Similarly, there is a solution for &lt;math&gt;-100&lt;x&lt;-99&lt;/math&gt;, but not for &lt;math&gt;-101&lt;x&lt;-100&lt;/math&gt;. This means that there are &lt;math&gt;99&lt;/math&gt; positive solutions, &lt;math&gt;99&lt;/math&gt; negative solutions, and &lt;math&gt;0&lt;/math&gt; for a total of &lt;math&gt;\boxed{\text{(C)}~199}&lt;/math&gt; solutions.<br /> <br /> ~Owen1204<br /> <br /> ==Video Solution==<br /> https://www.youtube.com/watch?v=vHKPbaXwJUE<br /> <br /> ==See Also==<br /> <br /> {{AMC10 box|year=2018|ab=B|num-b=24|after=Last Problem}}<br /> {{AMC12 box|year=2018|ab=B|num-b=23|num-a=25}}<br /> {{MAA Notice}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_13&diff=114062 2007 AIME II Problems/Problem 13 2020-01-02T19:03:42Z <p>Mvp harry: /* Note */</p> <hr /> <div>== Problem ==<br /> A [[triangle|triangular]] [[array]] of [[square]]s has one square in the first row, two in the second, and in general, &lt;math&gt;k&lt;/math&gt; squares in the &lt;math&gt;k&lt;/math&gt;th row for &lt;math&gt;1 \leq k \leq 11.&lt;/math&gt; With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a &lt;math&gt;0&lt;/math&gt; or a &lt;math&gt;1&lt;/math&gt; is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of &lt;math&gt;0&lt;/math&gt;'s and &lt;math&gt;1&lt;/math&gt;'s in the bottom row is the number in the top square a [[multiple]] of &lt;math&gt;3&lt;/math&gt;?<br /> <br /> &lt;asy&gt;<br /> for (int i=0; i&lt;12; ++i){<br /> for (int j=0; j&lt;i; ++j){<br /> //dot((-j+i/2,-i));<br /> draw((-j+i/2,-i)--(-j+i/2+1,-i)--(-j+i/2+1,-i+1)--(-j+i/2,-i+1)--cycle);<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> == Solution ==<br /> Label each of the bottom squares as &lt;math&gt;x_0, x_1 \ldots x_9, x_{10}&lt;/math&gt;. <br /> <br /> Through [[induction]], we can find that the top square is equal to &lt;math&gt;{10\choose0}x_0 + {10\choose1}x_1 + {10\choose2}x_2 + \ldots {10\choose10}x_{10}&lt;/math&gt;. (This also makes sense based on a combinatorial argument: the number of ways a number can &quot;travel&quot; to the top position going only up is equal to the number of times it will be counted in the final sum.)<br /> <br /> Examine the equation &lt;math&gt;\mod 3&lt;/math&gt;. All of the coefficients from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; will be multiples of &lt;math&gt;3&lt;/math&gt; (since the numerator will have a &lt;math&gt;9&lt;/math&gt;). Thus, the expression boils down to &lt;math&gt;x_0 + 10x_1 + 10x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Reduce to find that &lt;math&gt;x_0 + x_1 + x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Out of &lt;math&gt;x_0,\ x_1,\ x_9,\ x_{10}&lt;/math&gt;, either all are equal to &lt;math&gt;0&lt;/math&gt;, or three of them are equal to &lt;math&gt;1&lt;/math&gt;. This gives &lt;math&gt;{4\choose0} + {4\choose3} = 1 + 4 = 5&lt;/math&gt; possible combinations of numbers that work. <br /> <br /> The seven terms from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; can assume either &lt;math&gt;0&lt;/math&gt; or &lt;math&gt;1&lt;/math&gt;, giving us &lt;math&gt;2^7&lt;/math&gt; possibilities. The answer is therefore &lt;math&gt;5 \cdot 2^7 = \boxed{640}&lt;/math&gt;.<br /> <br /> == Note ==<br /> The specific induction process: we want to prove that if the bottom row is &lt;math&gt;x_0, x_1 \cdots x_{n}&lt;/math&gt;, the top square is &lt;math&gt;{n\choose0}x_0 + {n\choose1}x_1 + {n\choose2}x_2 + \ldots {n\choose{n}}x_{n}&lt;/math&gt;.<br /> <br /> Base Case: when n = 1, this is obviously true.<br /> <br /> Induction Step: Assume that the statement is true for n, and we wish to prove it for &lt;math&gt;n + 1&lt;/math&gt;. Therefore, we add another row below the &lt;math&gt;n + 1&lt;/math&gt; row, and name the squares as &lt;math&gt;a_0, a_1, \cdots a_{n+1}&lt;/math&gt;. We obtain that &lt;math&gt;x_0 = a_0 + a_1, x_1 = a_1 + a_2, \cdots x_{n} = a_{n} + a_{n+1}&lt;/math&gt;, and using the assumption, yield the top square equals &lt;math&gt;{n\choose0}(a_0 + a_1) + {n\choose1}(a_1 + a_2) + \ldots {n\choose{n}}(a_{n} + a_{n+1})&lt;/math&gt;. While it's easy to prove that &lt;math&gt;{n\choose{k}} + {n\choose{k+1}} = {n+1\choose{k+1}}&lt;/math&gt; (just expand it), we find that the two equations are identical. <br /> <br /> Note contributed by MVP_Harry, friend me if you want ~<br /> <br /> == See also ==<br /> {{AIME box|year=2007|n=II|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_13&diff=114057 2007 AIME II Problems/Problem 13 2020-01-02T19:02:22Z <p>Mvp harry: /* Note */</p> <hr /> <div>== Problem ==<br /> A [[triangle|triangular]] [[array]] of [[square]]s has one square in the first row, two in the second, and in general, &lt;math&gt;k&lt;/math&gt; squares in the &lt;math&gt;k&lt;/math&gt;th row for &lt;math&gt;1 \leq k \leq 11.&lt;/math&gt; With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a &lt;math&gt;0&lt;/math&gt; or a &lt;math&gt;1&lt;/math&gt; is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of &lt;math&gt;0&lt;/math&gt;'s and &lt;math&gt;1&lt;/math&gt;'s in the bottom row is the number in the top square a [[multiple]] of &lt;math&gt;3&lt;/math&gt;?<br /> <br /> &lt;asy&gt;<br /> for (int i=0; i&lt;12; ++i){<br /> for (int j=0; j&lt;i; ++j){<br /> //dot((-j+i/2,-i));<br /> draw((-j+i/2,-i)--(-j+i/2+1,-i)--(-j+i/2+1,-i+1)--(-j+i/2,-i+1)--cycle);<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> == Solution ==<br /> Label each of the bottom squares as &lt;math&gt;x_0, x_1 \ldots x_9, x_{10}&lt;/math&gt;. <br /> <br /> Through [[induction]], we can find that the top square is equal to &lt;math&gt;{10\choose0}x_0 + {10\choose1}x_1 + {10\choose2}x_2 + \ldots {10\choose10}x_{10}&lt;/math&gt;. (This also makes sense based on a combinatorial argument: the number of ways a number can &quot;travel&quot; to the top position going only up is equal to the number of times it will be counted in the final sum.)<br /> <br /> Examine the equation &lt;math&gt;\mod 3&lt;/math&gt;. All of the coefficients from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; will be multiples of &lt;math&gt;3&lt;/math&gt; (since the numerator will have a &lt;math&gt;9&lt;/math&gt;). Thus, the expression boils down to &lt;math&gt;x_0 + 10x_1 + 10x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Reduce to find that &lt;math&gt;x_0 + x_1 + x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Out of &lt;math&gt;x_0,\ x_1,\ x_9,\ x_{10}&lt;/math&gt;, either all are equal to &lt;math&gt;0&lt;/math&gt;, or three of them are equal to &lt;math&gt;1&lt;/math&gt;. This gives &lt;math&gt;{4\choose0} + {4\choose3} = 1 + 4 = 5&lt;/math&gt; possible combinations of numbers that work. <br /> <br /> The seven terms from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; can assume either &lt;math&gt;0&lt;/math&gt; or &lt;math&gt;1&lt;/math&gt;, giving us &lt;math&gt;2^7&lt;/math&gt; possibilities. The answer is therefore &lt;math&gt;5 \cdot 2^7 = \boxed{640}&lt;/math&gt;.<br /> <br /> == Note ==<br /> The specific induction process: we want to prove that if the bottom row is &lt;math&gt;x_0, x_1 \cdots x_{n}&lt;/math&gt;, the top square is &lt;math&gt;{n\choose0}x_0 + {n\choose1}x_1 + {n\choose2}x_2 + \ldots {n\choose{n}}x_{n}&lt;/math&gt;.<br /> <br /> Base Case: when n = 1, this is obviously true.<br /> <br /> Induction Step: Assume that the statement is true for n, and we wish to prove it for &lt;math&gt;n + 1&lt;/math&gt;. Therefore, we add another row below the &lt;math&gt;n + 1&lt;/math&gt; row, and name the squares as &lt;math&gt;a_0, a_1, \cdots a_{n+1}&lt;/math&gt;. We obtain that &lt;math&gt;x_0 = a_0 + a_1, x_1 = a_1 + a_2, \cdots x_{n} = a_{n} + a_{n+1}&lt;/math&gt;, and using the assumption, yield the top square equals &lt;math&gt;{n\choose0}(a_0 + a_1) + {n\choose1}(a_1 + a_2) + \ldots {n\choose{n}}(a_{n} + a_{n+1})&lt;/math&gt;. While it's easy to prove that &lt;math&gt;{n\choose{k}} + {n\choose{k+1}} = {n+1\choose{k+1}&lt;/math&gt; (just expand it), we find that the two equations are identical. <br /> <br /> Note contributed by MVP_Harry, friend me if you want ~<br /> <br /> == See also ==<br /> {{AIME box|year=2007|n=II|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_13&diff=114056 2007 AIME II Problems/Problem 13 2020-01-02T19:00:35Z <p>Mvp harry: /* Note */</p> <hr /> <div>== Problem ==<br /> A [[triangle|triangular]] [[array]] of [[square]]s has one square in the first row, two in the second, and in general, &lt;math&gt;k&lt;/math&gt; squares in the &lt;math&gt;k&lt;/math&gt;th row for &lt;math&gt;1 \leq k \leq 11.&lt;/math&gt; With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a &lt;math&gt;0&lt;/math&gt; or a &lt;math&gt;1&lt;/math&gt; is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of &lt;math&gt;0&lt;/math&gt;'s and &lt;math&gt;1&lt;/math&gt;'s in the bottom row is the number in the top square a [[multiple]] of &lt;math&gt;3&lt;/math&gt;?<br /> <br /> &lt;asy&gt;<br /> for (int i=0; i&lt;12; ++i){<br /> for (int j=0; j&lt;i; ++j){<br /> //dot((-j+i/2,-i));<br /> draw((-j+i/2,-i)--(-j+i/2+1,-i)--(-j+i/2+1,-i+1)--(-j+i/2,-i+1)--cycle);<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> == Solution ==<br /> Label each of the bottom squares as &lt;math&gt;x_0, x_1 \ldots x_9, x_{10}&lt;/math&gt;. <br /> <br /> Through [[induction]], we can find that the top square is equal to &lt;math&gt;{10\choose0}x_0 + {10\choose1}x_1 + {10\choose2}x_2 + \ldots {10\choose10}x_{10}&lt;/math&gt;. (This also makes sense based on a combinatorial argument: the number of ways a number can &quot;travel&quot; to the top position going only up is equal to the number of times it will be counted in the final sum.)<br /> <br /> Examine the equation &lt;math&gt;\mod 3&lt;/math&gt;. All of the coefficients from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; will be multiples of &lt;math&gt;3&lt;/math&gt; (since the numerator will have a &lt;math&gt;9&lt;/math&gt;). Thus, the expression boils down to &lt;math&gt;x_0 + 10x_1 + 10x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Reduce to find that &lt;math&gt;x_0 + x_1 + x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Out of &lt;math&gt;x_0,\ x_1,\ x_9,\ x_{10}&lt;/math&gt;, either all are equal to &lt;math&gt;0&lt;/math&gt;, or three of them are equal to &lt;math&gt;1&lt;/math&gt;. This gives &lt;math&gt;{4\choose0} + {4\choose3} = 1 + 4 = 5&lt;/math&gt; possible combinations of numbers that work. <br /> <br /> The seven terms from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; can assume either &lt;math&gt;0&lt;/math&gt; or &lt;math&gt;1&lt;/math&gt;, giving us &lt;math&gt;2^7&lt;/math&gt; possibilities. The answer is therefore &lt;math&gt;5 \cdot 2^7 = \boxed{640}&lt;/math&gt;.<br /> <br /> == Note ==<br /> The specific induction process: we want to prove that if the bottom row is &lt;math&gt;x_0, x_1 \cdots x_{n}&lt;/math&gt;, the top square is &lt;math&gt;{n\choose0}x_0 + {n\choose1}x_1 + {n\choose2}x_2 + \ldots {n\choose{n}}x_{n}&lt;/math&gt;.<br /> <br /> Base Case: when n = 1, this is obviously true.<br /> <br /> Induction Step: Assume that the statement is true for n, and we wish to prove it for &lt;math&gt;n + 1&lt;/math&gt;. Therefore, we add another row below the &lt;math&gt;n + 1&lt;/math&gt; row, and name the squares as &lt;math&gt;a_0, a_1, \cdots a_{n+1}&lt;/math&gt;. We obtain that &lt;math&gt;x_0 = a_0 + a_1, x_1 = a_1 + a_2, \cdots x_{n} = a_{n} + a_{n+1}&lt;/math&gt;, and using the assumption, yield the top square equals &lt;math&gt;{n\choose0}(a_0 + a_1) + {n\choose1}(a_1 + a_2) + \ldots {n\choose{n}}(a_{n} + a_{n+1})&lt;/math&gt;. While it's easy to prove that &lt;math&gt;{n\choose {k}} + {n\choose {k+1}} = {n+1\choose {k+1}&lt;/math&gt; (just expand it), we find that the two equations are identical. <br /> <br /> Note contributed by MVP_Harry, friend me if you want ~<br /> <br /> == See also ==<br /> {{AIME box|year=2007|n=II|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_13&diff=114055 2007 AIME II Problems/Problem 13 2020-01-02T18:58:50Z <p>Mvp harry: /* Solution */</p> <hr /> <div>== Problem ==<br /> A [[triangle|triangular]] [[array]] of [[square]]s has one square in the first row, two in the second, and in general, &lt;math&gt;k&lt;/math&gt; squares in the &lt;math&gt;k&lt;/math&gt;th row for &lt;math&gt;1 \leq k \leq 11.&lt;/math&gt; With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a &lt;math&gt;0&lt;/math&gt; or a &lt;math&gt;1&lt;/math&gt; is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of &lt;math&gt;0&lt;/math&gt;'s and &lt;math&gt;1&lt;/math&gt;'s in the bottom row is the number in the top square a [[multiple]] of &lt;math&gt;3&lt;/math&gt;?<br /> <br /> &lt;asy&gt;<br /> for (int i=0; i&lt;12; ++i){<br /> for (int j=0; j&lt;i; ++j){<br /> //dot((-j+i/2,-i));<br /> draw((-j+i/2,-i)--(-j+i/2+1,-i)--(-j+i/2+1,-i+1)--(-j+i/2,-i+1)--cycle);<br /> }<br /> }<br /> &lt;/asy&gt;<br /> <br /> == Solution ==<br /> Label each of the bottom squares as &lt;math&gt;x_0, x_1 \ldots x_9, x_{10}&lt;/math&gt;. <br /> <br /> Through [[induction]], we can find that the top square is equal to &lt;math&gt;{10\choose0}x_0 + {10\choose1}x_1 + {10\choose2}x_2 + \ldots {10\choose10}x_{10}&lt;/math&gt;. (This also makes sense based on a combinatorial argument: the number of ways a number can &quot;travel&quot; to the top position going only up is equal to the number of times it will be counted in the final sum.)<br /> <br /> Examine the equation &lt;math&gt;\mod 3&lt;/math&gt;. All of the coefficients from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; will be multiples of &lt;math&gt;3&lt;/math&gt; (since the numerator will have a &lt;math&gt;9&lt;/math&gt;). Thus, the expression boils down to &lt;math&gt;x_0 + 10x_1 + 10x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Reduce to find that &lt;math&gt;x_0 + x_1 + x_9 + x_{10} \equiv 0 \mod 3&lt;/math&gt;. Out of &lt;math&gt;x_0,\ x_1,\ x_9,\ x_{10}&lt;/math&gt;, either all are equal to &lt;math&gt;0&lt;/math&gt;, or three of them are equal to &lt;math&gt;1&lt;/math&gt;. This gives &lt;math&gt;{4\choose0} + {4\choose3} = 1 + 4 = 5&lt;/math&gt; possible combinations of numbers that work. <br /> <br /> The seven terms from &lt;math&gt;x_2 \ldots x_8&lt;/math&gt; can assume either &lt;math&gt;0&lt;/math&gt; or &lt;math&gt;1&lt;/math&gt;, giving us &lt;math&gt;2^7&lt;/math&gt; possibilities. The answer is therefore &lt;math&gt;5 \cdot 2^7 = \boxed{640}&lt;/math&gt;.<br /> <br /> == Note ==<br /> The specific induction process: we want to prove that if the bottom row is &lt;math&gt;x_0, x_1 \cdots x_{n}&lt;/math&gt;, the top square is &lt;math&gt;{n\choose0}x_0 + {n\choose1}x_1 + {n\choose2}x_2 + \ldots {n\choose{n}}x_{n}&lt;/math&gt;.<br /> Base Case: when n = 1, this is obviously true.<br /> Induction Step: Assume that the statement is true for n, and we wish to prove it for &lt;math&gt;n + 1&lt;/math&gt;. Therefore, we add another row below the &lt;math&gt;n + 1&lt;/math&gt; row, and name the squares as &lt;math&gt;a_0, a_1, \cdots a_{n+1}&lt;/math&gt;. We obtain that &lt;math&gt;x_0 = a_0 + a_1, x_1 = a_1 + a_2, \cdots x_{n} = a_{n} + a_{n+1}&lt;/math&gt;, and using the assumption, yield the top square equals &lt;math&gt;{n\choose0}(a_0 + a_1) + {n\choose1}(a_1 + a_2) + \ldots {n\choose{n}}(a{n} + a{n+1})&lt;/math&gt;. While it's easy to prove that &lt;math&gt;{n\choose {k}} + {n\choose {k+1}} = {n+1\choose {k+1}&lt;/math&gt; (just expand it), we find that the two equations are identical. <br /> Note contributed by MVP_Harry, friend me if you want ~<br /> <br /> == See also ==<br /> {{AIME box|year=2007|n=II|num-b=12|num-a=14}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]<br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_26&diff=114030 2008 iTest Problems/Problem 26 2020-01-02T17:09:09Z <p>Mvp harry: /* Solution */</p> <hr /> <div>==Problem==<br /> <br /> Done working on his sand castle design, Joshua sits down and starts rolling a &lt;math&gt;12&lt;/math&gt;-sided die he found when cleaning the storage shed. He rolls and rolls and rolls, and after &lt;math&gt;17&lt;/math&gt; rolls he finally rolls a &lt;math&gt;1&lt;/math&gt;. Just &lt;math&gt;3&lt;/math&gt; rolls later he rolls the first 2 &lt;math&gt;\textit{ after}&lt;/math&gt; that first roll of &lt;math&gt;1&lt;/math&gt;. &lt;math&gt;11&lt;/math&gt; rolls later, Joshua rolls the first &lt;math&gt;3\textit{ after}&lt;/math&gt; the first &lt;math&gt; 2&lt;/math&gt; that he rolled &lt;math&gt;\textit{after}&lt;/math&gt; the first &lt;math&gt;1&lt;/math&gt; that he rolled. His first &lt;math&gt;31&lt;/math&gt; rolls make the sequence &lt;math&gt;4,3,11,3,11,8,5,2,12,9,5,7,11,3,6,10,\textbf{1},8,3,\textbf{2},10,4,2,8,1,9,7,12,11,4,\textbf{3}&lt;/math&gt;.<br /> Joshua wonders how many times he should expect to roll the &lt;math&gt;12&lt;/math&gt;-sided die so that he can remove all but &lt;math&gt;12&lt;/math&gt; of the numbers from the entire sequence of rolls and (without changing the order of the sequence), be left with the sequence &lt;math&gt;1,2,3,4,5,6,7,8,9,10,11,12&lt;/math&gt;. What is the expected value of the number of times Joshua must roll the die before he has such a sequence? (Assume Joshua starts from the beginning - do &lt;math&gt;\textit{not}&lt;/math&gt; assume he starts by rolling the specific sequence of &lt;math&gt;31&lt;/math&gt; rolls above.) <br /> <br /> <br /> ==Solution==<br /> <br /> &lt;math&gt;\boxed{144}&lt;/math&gt;<br /> <br /> The expected number of rolls required to get any particular face of the die is 12 rolls. <br /> The proof goes as follows: the probability of rolling n on roll 1 is &lt;math&gt;(\frac{1}{12})&lt;/math&gt;.<br /> The probability of rolling n on roll 2 (but not roll 1) is &lt;math&gt;(\frac{11}{12})\cdot (\frac{1}{12})&lt;/math&gt;.<br /> The probability of rolling n on roll 3 (but not rolls 1 or 2) is &lt;math&gt;(\frac{11}{12})^2 \cdot (\frac{1}{12})&lt;/math&gt;.<br /> In general, rolling your first n on roll k is &lt;math&gt;(\frac{11}{12})^{(k-1)} \cdot (\frac{1}{12})&lt;/math&gt;.<br /> The expected total number of rolls needed to get your first n is &lt;math&gt;1\cdot \frac{1}{12}+2\cdot (\frac{11}{12})(\frac{1}{12})+3\cdot (\frac{11}{12})^{2}(\frac{1}{12})+4\cdot (\frac{11}{12})^3(\frac{1}{12})+\cdots =<br /> \sum_{k=1}^{\infty}{k\cdot (\frac{11}{12})^{(k-1)}(\frac{1}{12})}&lt;/math&gt;.<br /> <br /> The formula for a geometric series is &lt;math&gt;\sum_{n=0}^{\infty}{x^n}=\frac{1}{1-x}&lt;/math&gt;. Taking derivatives of both sides gives <br /> &lt;math&gt;\sum_{n=1}^{\infty}{n\cdot x^{n-1}}=\frac{1}{(1-x)^2}&lt;/math&gt;<br /> So the expected number of rolls required to get face n is &lt;math&gt;\frac{\frac{1}{12}}{(1-\frac{11}{12})^2}=12&lt;/math&gt;. <br /> <br /> Rolling a sequence to get a first n can be thought of as an independent trial and getting the full sequence of {1,2,3,4,5,6,7,8,9,10,11,12} can be <br /> thought of as running 12 independent trials: trial 1 to get your first 1, then trial 2 to roll your first 2 (after the first 1), then trial 3 to roll the first 3 (after the first 2 after the first 1) etc...<br /> All of these 12 trials can be concatenated together to get the final required sequence.<br /> <br /> Thus the total expected roll count is &lt;math&gt;12\cdot 12 = 144&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{2008 iTest box|num-b=25|num-a=27}}<br /> <br /> [[Category: Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113891 2005 Indonesia MO Problems/Problem 8 2019-12-31T20:06:07Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;\frac{90}{3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. Since &lt;math&gt;\frac{90}{29} &gt; 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113890 2005 Indonesia MO Problems/Problem 8 2019-12-31T19:55:31Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;\frac{90}{3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. <br /> <br /> Since &lt;math&gt;\frac{90}{29} &gt; 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113889 2005 Indonesia MO Problems/Problem 8 2019-12-31T19:55:17Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;\frac{90}{3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. <br /> <br /> Since &lt;math&gt;\frac{90}{29} \&gt; 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113888 2005 Indonesia MO Problems/Problem 8 2019-12-31T19:54:47Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;\frac{90}{3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. <br /> <br /> Since &lt;math&gt;\frac{90}{29} \geq 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113887 2005 Indonesia MO Problems/Problem 8 2019-12-31T19:54:12Z <p>Mvp harry: /* Solution 2 */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;frac{90}{3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. <br /> <br /> Since &lt;math&gt;frac {90}{29} \geq 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&diff=113886 2005 Indonesia MO Problems/Problem 8 2019-12-31T19:53:17Z <p>Mvp harry: /* Solution (credit to Diarmuid) */</p> <hr /> <div>==Problem==<br /> <br /> There are &lt;math&gt;90&lt;/math&gt; contestants in a mathematics competition. Each contestant gets acquainted with at least &lt;math&gt;60&lt;/math&gt; other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.<br /> <br /> ==Solution (credit to Diarmuid)==<br /> <br /> In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.<br /> <br /> &lt;br&gt;<br /> Note that each person can meet up to &lt;math&gt;89&lt;/math&gt; other contestants. Thus, there are &lt;math&gt;89 - 60 + 1 = 30&lt;/math&gt; numbers that can be the number of contestants one meets.<br /> <br /> &lt;br&gt;<br /> For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most &lt;math&gt;90&lt;/math&gt; contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.<br /> <br /> &lt;br&gt;<br /> The total number of meets in this scenario is &lt;math&gt;\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}&lt;/math&gt;, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.<br /> <br /> <br /> ==Solution 2==<br /> <br /> For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be &lt;math&gt;29 - 0 + 1 = 30&lt;/math&gt; numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because &lt;math&gt;frac{90} {3}&lt;/math&gt; is exactly equal to 3.<br /> <br /> However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. <br /> <br /> Since &lt;math&gt;frac {90} {29} \geq 3&lt;/math&gt;, there must be four contestants that make the same number of new friends, just as Amin claims.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2005|num-b=7|after=Last Problem}}<br /> <br /> [[Category:Intermediate Combinatorics Problems]]</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2011_USAJMO_Problems/Problem_5&diff=105513 2011 USAJMO Problems/Problem 5 2019-04-27T11:40:33Z <p>Mvp harry: /* Solution 4 */</p> <hr /> <div>== Problem ==<br /> <br /> Points &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, &lt;math&gt;E&lt;/math&gt; lie on a circle &lt;math&gt;\omega&lt;/math&gt; and point &lt;math&gt;P&lt;/math&gt; lies outside the circle. The given points are such that (i) lines &lt;math&gt;PB&lt;/math&gt; and &lt;math&gt;PD&lt;/math&gt; are tangent to &lt;math&gt;\omega&lt;/math&gt;, (ii) &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt; are collinear, and (iii) &lt;math&gt;\overline{DE} \parallel \overline{AC}&lt;/math&gt;. Prove that &lt;math&gt;\overline{BE}&lt;/math&gt; bisects &lt;math&gt;\overline{AC}&lt;/math&gt;.<br /> <br /> == Solution 4 ==<br /> Connet segment PO, and name the interaction of PO and the circle as point M. <br /> <br /> Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.<br /> <br /> ∠ BOA = 1/2 arc AB + 1/2 arc CE<br /> <br /> Since AC // DE, arc AD = arc CE, <br /> <br /> thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM<br /> <br /> Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)<br /> <br /> BE bisects AC, proof completed!<br /> <br /> ~ MVP Harry<br /> <br /> ==Solution 1==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;X&lt;/math&gt; be the intersection of &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;BE&lt;/math&gt;. Let &lt;math&gt;\angle OPA&lt;/math&gt; be &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;\angle OPD&lt;/math&gt; be &lt;math&gt;y&lt;/math&gt;.<br /> <br /> &lt;math&gt; \angle OPB = \angle OPD = y &lt;/math&gt;, &lt;math&gt; \angle BED = \frac{\angle DOB}{2} = 90-y &lt;/math&gt;, <br /> &lt;math&gt; \angle ODE = \angle PDE - 90 = 90-x-y &lt;/math&gt; <br /> &lt;math&gt; \angle OBE = \angle PBE - 90 = x = \angle OPA &lt;/math&gt;<br /> <br /> Thus &lt;math&gt;PBXO&lt;/math&gt; is a cyclic quadrilateral and &lt;math&gt;\angle OXP = \angle OBP = 90&lt;/math&gt; and so &lt;math&gt;X&lt;/math&gt; is the midpoint of chord &lt;math&gt;AC&lt;/math&gt;.<br /> <br /> ~pandadude<br /> <br /> ==Solution 2==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;M&lt;/math&gt; be the midpoint of &lt;math&gt;AC&lt;/math&gt;. Let &lt;math&gt;\theta&lt;/math&gt; denote the circle with diameter &lt;math&gt;OP&lt;/math&gt;. Since &lt;math&gt;\angle OBP = \angle OMP = \angle ODP = 90^\circ&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; all lie on &lt;math&gt;\theta&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> <br /> unitsize(2 cm);<br /> <br /> pair A, B, C, D, E, M, O, P;<br /> path circ;<br /> <br /> O = (0,0);<br /> circ = Circle(O,1);<br /> B = dir(100);<br /> D = dir(240);<br /> P = extension(B, B + rotate(90)*(B), D, D + rotate(90)*(D));<br /> C = dir(-40);<br /> A = intersectionpoint((P--(P + 0.9*(C - P))),circ);<br /> E = intersectionpoint((D + 0.1*(C - A))--(D + C - A),circ);<br /> M = (A + C)/2;<br /> <br /> draw(circ);<br /> draw(P--B);<br /> draw(P--D);<br /> draw(P--C);<br /> draw(B--E);<br /> draw(D--E);<br /> draw(O--B);<br /> draw(O--D);<br /> draw(O--M);<br /> draw(O--P);<br /> draw(Circle((O + P)/2, abs(O - P)/2),dashed);<br /> draw(D--M);<br /> <br /> dot(&quot;$A$&quot;, A, NE);<br /> dot(&quot;$B$&quot;, B, NE);<br /> dot(&quot;$C$&quot;, C, SE);<br /> dot(&quot;$D$&quot;, D, S);<br /> dot(&quot;$E$&quot;, E, S);<br /> dot(&quot;$M$&quot;, M, NE);<br /> dot(&quot;$O$&quot;, O, dir(0));<br /> dot(&quot;$P$&quot;, P, W);<br /> label(&quot;$\theta$&quot;, (O + P)/2 + abs(O - P)/2*dir(120), NW);<br /> &lt;/asy&gt;<br /> <br /> Since quadrilateral &lt;math&gt;BOMP&lt;/math&gt; is cyclic, &lt;math&gt;\angle BMP = \angle BOP&lt;/math&gt;. Triangles &lt;math&gt;BOP&lt;/math&gt; and &lt;math&gt;DOP&lt;/math&gt; are congruent, so &lt;math&gt;\angle BOP = \angle BOD/2 = \angle BED&lt;/math&gt;, so &lt;math&gt;\angle BMP = \angle BED&lt;/math&gt;. Because &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;DE&lt;/math&gt; are parallel, &lt;math&gt;M&lt;/math&gt; lies on &lt;math&gt;BE&lt;/math&gt; (using Euclid's Parallel Postulate).<br /> <br /> ==Solution 3==<br /> Note that by Lemma 9.9 of EGMO, &lt;math&gt;(A,C;B,D)&lt;/math&gt; is a harmonic bundle. We project through &lt;math&gt;E&lt;/math&gt; onto &lt;math&gt;\overline{AC}&lt;/math&gt;,<br /> &lt;cmath&gt;-1=(A,C;B,D)\stackrel{E}{=}(A,C;M,P_{\infty})&lt;/cmath&gt;<br /> Where &lt;math&gt;P_{\infty}&lt;/math&gt; is the point at infinity for parallel lines &lt;math&gt;\overline{DE}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt;. Thus, we get &lt;math&gt;\frac{MA}{MC}=-1&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; is the midpoint of &lt;math&gt;AC&lt;/math&gt;. ~novus677<br /> <br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2011_USAJMO_Problems/Problem_5&diff=105512 2011 USAJMO Problems/Problem 5 2019-04-27T11:39:57Z <p>Mvp harry: /* Solutions */</p> <hr /> <div>== Problem ==<br /> <br /> Points &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, &lt;math&gt;E&lt;/math&gt; lie on a circle &lt;math&gt;\omega&lt;/math&gt; and point &lt;math&gt;P&lt;/math&gt; lies outside the circle. The given points are such that (i) lines &lt;math&gt;PB&lt;/math&gt; and &lt;math&gt;PD&lt;/math&gt; are tangent to &lt;math&gt;\omega&lt;/math&gt;, (ii) &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt; are collinear, and (iii) &lt;math&gt;\overline{DE} \parallel \overline{AC}&lt;/math&gt;. Prove that &lt;math&gt;\overline{BE}&lt;/math&gt; bisects &lt;math&gt;\overline{AC}&lt;/math&gt;.<br /> <br /> == Solution 4 ==<br /> Connet segment PO, and name the interaction of PO and the circle as point M. <br /> Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.<br /> ∠ BOA = 1/2 arc AB + 1/2 arc CE<br /> Since AC // DE, arc AD = arc CE, <br /> thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM<br /> Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)<br /> BE bisects AC, proof completed!<br /> ~ MVP Harry<br /> <br /> ==Solution 1==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;X&lt;/math&gt; be the intersection of &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;BE&lt;/math&gt;. Let &lt;math&gt;\angle OPA&lt;/math&gt; be &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;\angle OPD&lt;/math&gt; be &lt;math&gt;y&lt;/math&gt;.<br /> <br /> &lt;math&gt; \angle OPB = \angle OPD = y &lt;/math&gt;, &lt;math&gt; \angle BED = \frac{\angle DOB}{2} = 90-y &lt;/math&gt;, <br /> &lt;math&gt; \angle ODE = \angle PDE - 90 = 90-x-y &lt;/math&gt; <br /> &lt;math&gt; \angle OBE = \angle PBE - 90 = x = \angle OPA &lt;/math&gt;<br /> <br /> Thus &lt;math&gt;PBXO&lt;/math&gt; is a cyclic quadrilateral and &lt;math&gt;\angle OXP = \angle OBP = 90&lt;/math&gt; and so &lt;math&gt;X&lt;/math&gt; is the midpoint of chord &lt;math&gt;AC&lt;/math&gt;.<br /> <br /> ~pandadude<br /> <br /> ==Solution 2==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;M&lt;/math&gt; be the midpoint of &lt;math&gt;AC&lt;/math&gt;. Let &lt;math&gt;\theta&lt;/math&gt; denote the circle with diameter &lt;math&gt;OP&lt;/math&gt;. Since &lt;math&gt;\angle OBP = \angle OMP = \angle ODP = 90^\circ&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; all lie on &lt;math&gt;\theta&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> <br /> unitsize(2 cm);<br /> <br /> pair A, B, C, D, E, M, O, P;<br /> path circ;<br /> <br /> O = (0,0);<br /> circ = Circle(O,1);<br /> B = dir(100);<br /> D = dir(240);<br /> P = extension(B, B + rotate(90)*(B), D, D + rotate(90)*(D));<br /> C = dir(-40);<br /> A = intersectionpoint((P--(P + 0.9*(C - P))),circ);<br /> E = intersectionpoint((D + 0.1*(C - A))--(D + C - A),circ);<br /> M = (A + C)/2;<br /> <br /> draw(circ);<br /> draw(P--B);<br /> draw(P--D);<br /> draw(P--C);<br /> draw(B--E);<br /> draw(D--E);<br /> draw(O--B);<br /> draw(O--D);<br /> draw(O--M);<br /> draw(O--P);<br /> draw(Circle((O + P)/2, abs(O - P)/2),dashed);<br /> draw(D--M);<br /> <br /> dot(&quot;$A$&quot;, A, NE);<br /> dot(&quot;$B$&quot;, B, NE);<br /> dot(&quot;$C$&quot;, C, SE);<br /> dot(&quot;$D$&quot;, D, S);<br /> dot(&quot;$E$&quot;, E, S);<br /> dot(&quot;$M$&quot;, M, NE);<br /> dot(&quot;$O$&quot;, O, dir(0));<br /> dot(&quot;$P$&quot;, P, W);<br /> label(&quot;$\theta$&quot;, (O + P)/2 + abs(O - P)/2*dir(120), NW);<br /> &lt;/asy&gt;<br /> <br /> Since quadrilateral &lt;math&gt;BOMP&lt;/math&gt; is cyclic, &lt;math&gt;\angle BMP = \angle BOP&lt;/math&gt;. Triangles &lt;math&gt;BOP&lt;/math&gt; and &lt;math&gt;DOP&lt;/math&gt; are congruent, so &lt;math&gt;\angle BOP = \angle BOD/2 = \angle BED&lt;/math&gt;, so &lt;math&gt;\angle BMP = \angle BED&lt;/math&gt;. Because &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;DE&lt;/math&gt; are parallel, &lt;math&gt;M&lt;/math&gt; lies on &lt;math&gt;BE&lt;/math&gt; (using Euclid's Parallel Postulate).<br /> <br /> ==Solution 3==<br /> Note that by Lemma 9.9 of EGMO, &lt;math&gt;(A,C;B,D)&lt;/math&gt; is a harmonic bundle. We project through &lt;math&gt;E&lt;/math&gt; onto &lt;math&gt;\overline{AC}&lt;/math&gt;,<br /> &lt;cmath&gt;-1=(A,C;B,D)\stackrel{E}{=}(A,C;M,P_{\infty})&lt;/cmath&gt;<br /> Where &lt;math&gt;P_{\infty}&lt;/math&gt; is the point at infinity for parallel lines &lt;math&gt;\overline{DE}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt;. Thus, we get &lt;math&gt;\frac{MA}{MC}=-1&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; is the midpoint of &lt;math&gt;AC&lt;/math&gt;. ~novus677<br /> <br /> {{MAA Notice}}</div> Mvp harry https://artofproblemsolving.com/wiki/index.php?title=2011_USAJMO_Problems/Problem_5&diff=105511 2011 USAJMO Problems/Problem 5 2019-04-27T11:37:25Z <p>Mvp harry: /* Solutions */</p> <hr /> <div>== Problem ==<br /> <br /> Points &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, &lt;math&gt;E&lt;/math&gt; lie on a circle &lt;math&gt;\omega&lt;/math&gt; and point &lt;math&gt;P&lt;/math&gt; lies outside the circle. The given points are such that (i) lines &lt;math&gt;PB&lt;/math&gt; and &lt;math&gt;PD&lt;/math&gt; are tangent to &lt;math&gt;\omega&lt;/math&gt;, (ii) &lt;math&gt;P&lt;/math&gt;, &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;C&lt;/math&gt; are collinear, and (iii) &lt;math&gt;\overline{DE} \parallel \overline{AC}&lt;/math&gt;. Prove that &lt;math&gt;\overline{BE}&lt;/math&gt; bisects &lt;math&gt;\overline{AC}&lt;/math&gt;.<br /> <br /> == Solutions ==<br /> Connet segment PO, and name the interaction of PO and the circle as point M. <br /> Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.<br /> ∠ BOA = 1/2 arc AB + 1/2 arc CE<br /> Since AC // DE, arc AD = arc CE, <br /> thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM<br /> Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)<br /> BE bisects AC, proof completed!<br /> <br /> ==Solution 1==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;X&lt;/math&gt; be the intersection of &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;BE&lt;/math&gt;. Let &lt;math&gt;\angle OPA&lt;/math&gt; be &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;\angle OPD&lt;/math&gt; be &lt;math&gt;y&lt;/math&gt;.<br /> <br /> &lt;math&gt; \angle OPB = \angle OPD = y &lt;/math&gt;, &lt;math&gt; \angle BED = \frac{\angle DOB}{2} = 90-y &lt;/math&gt;, <br /> &lt;math&gt; \angle ODE = \angle PDE - 90 = 90-x-y &lt;/math&gt; <br /> &lt;math&gt; \angle OBE = \angle PBE - 90 = x = \angle OPA &lt;/math&gt;<br /> <br /> Thus &lt;math&gt;PBXO&lt;/math&gt; is a cyclic quadrilateral and &lt;math&gt;\angle OXP = \angle OBP = 90&lt;/math&gt; and so &lt;math&gt;X&lt;/math&gt; is the midpoint of chord &lt;math&gt;AC&lt;/math&gt;.<br /> <br /> ~pandadude<br /> <br /> ==Solution 2==<br /> <br /> Let &lt;math&gt;O&lt;/math&gt; be the center of the circle, and let &lt;math&gt;M&lt;/math&gt; be the midpoint of &lt;math&gt;AC&lt;/math&gt;. Let &lt;math&gt;\theta&lt;/math&gt; denote the circle with diameter &lt;math&gt;OP&lt;/math&gt;. Since &lt;math&gt;\angle OBP = \angle OMP = \angle ODP = 90^\circ&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, &lt;math&gt;D&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; all lie on &lt;math&gt;\theta&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> import graph;<br /> <br /> unitsize(2 cm);<br /> <br /> pair A, B, C, D, E, M, O, P;<br /> path circ;<br /> <br /> O = (0,0);<br /> circ = Circle(O,1);<br /> B = dir(100);<br /> D = dir(240);<br /> P = extension(B, B + rotate(90)*(B), D, D + rotate(90)*(D));<br /> C = dir(-40);<br /> A = intersectionpoint((P--(P + 0.9*(C - P))),circ);<br /> E = intersectionpoint((D + 0.1*(C - A))--(D + C - A),circ);<br /> M = (A + C)/2;<br /> <br /> draw(circ);<br /> draw(P--B);<br /> draw(P--D);<br /> draw(P--C);<br /> draw(B--E);<br /> draw(D--E);<br /> draw(O--B);<br /> draw(O--D);<br /> draw(O--M);<br /> draw(O--P);<br /> draw(Circle((O + P)/2, abs(O - P)/2),dashed);<br /> draw(D--M);<br /> <br /> dot(&quot;$A$&quot;, A, NE);<br /> dot(&quot;$B$&quot;, B, NE);<br /> dot(&quot;$C$&quot;, C, SE);<br /> dot(&quot;$D$&quot;, D, S);<br /> dot(&quot;$E$&quot;, E, S);<br /> dot(&quot;$M$&quot;, M, NE);<br /> dot(&quot;$O$&quot;, O, dir(0));<br /> dot(&quot;$P$&quot;, P, W);<br /> label(&quot;$\theta$&quot;, (O + P)/2 + abs(O - P)/2*dir(120), NW);<br /> &lt;/asy&gt;<br /> <br /> Since quadrilateral &lt;math&gt;BOMP&lt;/math&gt; is cyclic, &lt;math&gt;\angle BMP = \angle BOP&lt;/math&gt;. Triangles &lt;math&gt;BOP&lt;/math&gt; and &lt;math&gt;DOP&lt;/math&gt; are congruent, so &lt;math&gt;\angle BOP = \angle BOD/2 = \angle BED&lt;/math&gt;, so &lt;math&gt;\angle BMP = \angle BED&lt;/math&gt;. Because &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;DE&lt;/math&gt; are parallel, &lt;math&gt;M&lt;/math&gt; lies on &lt;math&gt;BE&lt;/math&gt; (using Euclid's Parallel Postulate).<br /> <br /> ==Solution 3==<br /> Note that by Lemma 9.9 of EGMO, &lt;math&gt;(A,C;B,D)&lt;/math&gt; is a harmonic bundle. We project through &lt;math&gt;E&lt;/math&gt; onto &lt;math&gt;\overline{AC}&lt;/math&gt;,<br /> &lt;cmath&gt;-1=(A,C;B,D)\stackrel{E}{=}(A,C;M,P_{\infty})&lt;/cmath&gt;<br /> Where &lt;math&gt;P_{\infty}&lt;/math&gt; is the point at infinity for parallel lines &lt;math&gt;\overline{DE}&lt;/math&gt; and &lt;math&gt;\overline{AC}&lt;/math&gt;. Thus, we get &lt;math&gt;\frac{MA}{MC}=-1&lt;/math&gt;, and &lt;math&gt;M&lt;/math&gt; is the midpoint of &lt;math&gt;AC&lt;/math&gt;. ~novus677<br /> <br /> {{MAA Notice}}</div> Mvp harry