https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Aopsvd&feedformat=atom AoPS Wiki - User contributions [en] 2020-12-04T12:21:48Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=1991_AIME_Problems/Problem_11&diff=42901 1991 AIME Problems/Problem 11 2011-11-03T06:40:44Z <p>Aopsvd: /* Solution */</p> <hr /> <div>== Problem ==<br /> Twelve congruent disks are placed on a [[circle]] &lt;math&gt;C^{}_{}&lt;/math&gt; of [[radius]] 1 in such a way that the twelve disks cover &lt;math&gt;C^{}_{}&lt;/math&gt;, no two of the disks overlap, and so that each of the twelve disks is [[tangent (geometry)|tangent]] to its two neighbors. The resulting arrangement of disks is shown in the figure below. The sum of the areas of the twelve disks can be written in the from &lt;math&gt;\pi(a-b\sqrt{c})&lt;/math&gt;, where &lt;math&gt;a,b,c^{}_{}&lt;/math&gt; are positive integers and &lt;math&gt;c^{}_{}&lt;/math&gt; is not divisible by the square of any prime. Find &lt;math&gt;a+b+c^{}_{}&lt;/math&gt;.<br /> <br /> [[Image:AIME_1991_Problem_11.png|300px]]<br /> <br /> == Solution ==<br /> We wish to find the radius of one circle, so that we can find the total area.<br /> <br /> Notice that for them to contain the entire circle, each pair of circles must be tangent on the larger circle. Now consider two adjacent smaller circles. This means that the line connecting the radii is a segment of length &lt;math&gt;2r&lt;/math&gt; that is tangent to the larger circle at the midpoint of the two centers. Thus, we have essentially have a regular dodecagon whose vertices are the centers of the smaller triangles circumscribed about a circle of radius &lt;math&gt;1&lt;/math&gt;.<br /> <br /> We thus know that the [[apothem]] of the [[dodecagon]] is equal to &lt;math&gt;1&lt;/math&gt;. To find the side length, we make a triangle consisting of a vertex, the midpoint of a side, and the center of the dodecagon, which we denote &lt;math&gt;A, M,&lt;/math&gt; and &lt;math&gt;O&lt;/math&gt; respectively. Notice that &lt;math&gt;OM=1&lt;/math&gt;, and that &lt;math&gt;\triangle OMA&lt;/math&gt; is a right triangle with [[hypotenuse]] &lt;math&gt;OA&lt;/math&gt; and &lt;math&gt;m \angle MOA = 15^\circ&lt;/math&gt;. Thus &lt;math&gt;AM = (1) \tan{15^\circ} = 2 - \sqrt {3}&lt;/math&gt;, which is the radius of one of the circles. The area of one circle is thus &lt;math&gt;\pi(2 - \sqrt {3})^{2} = \pi (7 - 4 \sqrt {3})&lt;/math&gt;, so the area of all &lt;math&gt;12&lt;/math&gt; circles is &lt;math&gt;\pi (84 - 48 \sqrt {3})&lt;/math&gt;, giving an answer of &lt;math&gt;84 + 48 + 3 = \boxed{135}&lt;/math&gt;.<br /> &lt;!--Let &lt;math&gt;R_{}^{}&lt;/math&gt; and &lt;math&gt;r_{}^{}&lt;/math&gt; denote the radii of the large and small circles (&lt;math&gt;R_{}^{}&gt;r_{}^{}&lt;/math&gt;), respectively. Suppose that there are &lt;math&gt;n_{}^{}&lt;/math&gt; circles of radius &lt;math&gt;r_{}^{}&lt;/math&gt; centered on the circumference of the circle having radius &lt;math&gt;R_{}^{}&lt;/math&gt;. Let &lt;math&gt;O_{}^{}&lt;/math&gt;, &lt;math&gt;P_{}^{}&lt;/math&gt;, and &lt;math&gt;Q_{}^{}&lt;/math&gt; label the vertices of the triangle with &lt;math&gt;O_{}^{}&lt;/math&gt; being at the center of the large circle, whereas &lt;math&gt;P_{}^{}&lt;/math&gt; and &lt;math&gt;Q_{}^{}&lt;/math&gt; are the tangential points of one of the &lt;math&gt;n_{}^{}&lt;/math&gt; small circles with its two other neighbours, and &lt;math&gt;S_{}^{}&lt;/math&gt; its center. The angle subtended by &lt;math&gt;P_{}^{}OQ&lt;/math&gt; is &lt;math&gt;2\pi/n_{}^{}&lt;/math&gt;. The segments &lt;math&gt;O_{}^{}P&lt;/math&gt; and &lt;math&gt;S_{}^{}P&lt;/math&gt; are [[perpendicular]]. Therefore, triangle &lt;math&gt;P_{}^{}OS&lt;/math&gt; is rectangular and the angle subtended by &lt;math&gt;P_{}^{}OS&lt;/math&gt; equals &lt;math&gt;\pi/n_{}^{}&lt;/math&gt;. Hence, the radius &lt;math&gt;r_{}^{}=R\sin(\pi/n)&lt;/math&gt;. The total area &lt;math&gt;A_{n}^{}&lt;/math&gt; of the &lt;math&gt;n_{}^{}&lt;/math&gt; circles is thus given by <br /> <br /> &lt;cmath&gt;<br /> A_{n}^{}=n\pi r^{2}=n\pi R^{2}\sin^{2}\left(\frac{\pi}{n}\right)=\frac{1}{2}n\pi R^{2}\left[1-\cos\left(\frac{2\pi}{n}\right)\right]\, .<br /> &lt;/cmath&gt;<br /> <br /> In the present problem, &lt;math&gt;n_{}^{}=12&lt;/math&gt; and &lt;math&gt;R_{}^{}=1&lt;/math&gt;. It follows that &lt;math&gt;A_{12}^{}=6\pi\left[1-\cos(\pi/6)\right]=\pi\left(6-3\sqrt{3}\right)\equiv \pi\left(a-b\sqrt{c}\right)&lt;/math&gt;.<br /> <br /> In summary, &lt;math&gt;a_{}^{}+b+c=\boxed{012}&lt;/math&gt;.--&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=1991|num-b=10|num-a=12}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1991_AIME_Problems/Problem_11&diff=42900 1991 AIME Problems/Problem 11 2011-11-03T06:40:11Z <p>Aopsvd: /* Problem */</p> <hr /> <div>== Problem ==<br /> Twelve congruent disks are placed on a [[circle]] &lt;math&gt;C^{}_{}&lt;/math&gt; of [[radius]] 1 in such a way that the twelve disks cover &lt;math&gt;C^{}_{}&lt;/math&gt;, no two of the disks overlap, and so that each of the twelve disks is [[tangent (geometry)|tangent]] to its two neighbors. The resulting arrangement of disks is shown in the figure below. The sum of the areas of the twelve disks can be written in the from &lt;math&gt;\pi(a-b\sqrt{c})&lt;/math&gt;, where &lt;math&gt;a,b,c^{}_{}&lt;/math&gt; are positive integers and &lt;math&gt;c^{}_{}&lt;/math&gt; is not divisible by the square of any prime. Find &lt;math&gt;a+b+c^{}_{}&lt;/math&gt;.<br /> <br /> [[Image:AIME_1991_Problem_11.png|300px]]<br /> <br /> == Solution ==<br /> Note that the above image is not completely accurate with regard to the problem description. <br /> <br /> We wish to find the radius of one circle, so that we can find the total area.<br /> <br /> Notice that for them to contain the entire circle, each pair of circles must be tangent on the larger circle. Now consider two adjacent smaller circles. This means that the line connecting the radii is a segment of length &lt;math&gt;2r&lt;/math&gt; that is tangent to the larger circle at the midpoint of the two centers. Thus, we have essentially have a regular dodecagon whose vertices are the centers of the smaller triangles circumscribed about a circle of radius &lt;math&gt;1&lt;/math&gt;.<br /> <br /> We thus know that the [[apothem]] of the [[dodecagon]] is equal to &lt;math&gt;1&lt;/math&gt;. To find the side length, we make a triangle consisting of a vertex, the midpoint of a side, and the center of the dodecagon, which we denote &lt;math&gt;A, M,&lt;/math&gt; and &lt;math&gt;O&lt;/math&gt; respectively. Notice that &lt;math&gt;OM=1&lt;/math&gt;, and that &lt;math&gt;\triangle OMA&lt;/math&gt; is a right triangle with [[hypotenuse]] &lt;math&gt;OA&lt;/math&gt; and &lt;math&gt;m \angle MOA = 15^\circ&lt;/math&gt;. Thus &lt;math&gt;AM = (1) \tan{15^\circ} = 2 - \sqrt {3}&lt;/math&gt;, which is the radius of one of the circles. The area of one circle is thus &lt;math&gt;\pi(2 - \sqrt {3})^{2} = \pi (7 - 4 \sqrt {3})&lt;/math&gt;, so the area of all &lt;math&gt;12&lt;/math&gt; circles is &lt;math&gt;\pi (84 - 48 \sqrt {3})&lt;/math&gt;, giving an answer of &lt;math&gt;84 + 48 + 3 = \boxed{135}&lt;/math&gt;.<br /> &lt;!--Let &lt;math&gt;R_{}^{}&lt;/math&gt; and &lt;math&gt;r_{}^{}&lt;/math&gt; denote the radii of the large and small circles (&lt;math&gt;R_{}^{}&gt;r_{}^{}&lt;/math&gt;), respectively. Suppose that there are &lt;math&gt;n_{}^{}&lt;/math&gt; circles of radius &lt;math&gt;r_{}^{}&lt;/math&gt; centered on the circumference of the circle having radius &lt;math&gt;R_{}^{}&lt;/math&gt;. Let &lt;math&gt;O_{}^{}&lt;/math&gt;, &lt;math&gt;P_{}^{}&lt;/math&gt;, and &lt;math&gt;Q_{}^{}&lt;/math&gt; label the vertices of the triangle with &lt;math&gt;O_{}^{}&lt;/math&gt; being at the center of the large circle, whereas &lt;math&gt;P_{}^{}&lt;/math&gt; and &lt;math&gt;Q_{}^{}&lt;/math&gt; are the tangential points of one of the &lt;math&gt;n_{}^{}&lt;/math&gt; small circles with its two other neighbours, and &lt;math&gt;S_{}^{}&lt;/math&gt; its center. The angle subtended by &lt;math&gt;P_{}^{}OQ&lt;/math&gt; is &lt;math&gt;2\pi/n_{}^{}&lt;/math&gt;. The segments &lt;math&gt;O_{}^{}P&lt;/math&gt; and &lt;math&gt;S_{}^{}P&lt;/math&gt; are [[perpendicular]]. Therefore, triangle &lt;math&gt;P_{}^{}OS&lt;/math&gt; is rectangular and the angle subtended by &lt;math&gt;P_{}^{}OS&lt;/math&gt; equals &lt;math&gt;\pi/n_{}^{}&lt;/math&gt;. Hence, the radius &lt;math&gt;r_{}^{}=R\sin(\pi/n)&lt;/math&gt;. The total area &lt;math&gt;A_{n}^{}&lt;/math&gt; of the &lt;math&gt;n_{}^{}&lt;/math&gt; circles is thus given by <br /> <br /> &lt;cmath&gt;<br /> A_{n}^{}=n\pi r^{2}=n\pi R^{2}\sin^{2}\left(\frac{\pi}{n}\right)=\frac{1}{2}n\pi R^{2}\left[1-\cos\left(\frac{2\pi}{n}\right)\right]\, .<br /> &lt;/cmath&gt;<br /> <br /> In the present problem, &lt;math&gt;n_{}^{}=12&lt;/math&gt; and &lt;math&gt;R_{}^{}=1&lt;/math&gt;. It follows that &lt;math&gt;A_{12}^{}=6\pi\left[1-\cos(\pi/6)\right]=\pi\left(6-3\sqrt{3}\right)\equiv \pi\left(a-b\sqrt{c}\right)&lt;/math&gt;.<br /> <br /> In summary, &lt;math&gt;a_{}^{}+b+c=\boxed{012}&lt;/math&gt;.--&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=1991|num-b=10|num-a=12}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=File:AIME_1991_Problem_11.png&diff=42899 File:AIME 1991 Problem 11.png 2011-11-03T06:38:08Z <p>Aopsvd: uploaded a new version of &amp;quot;File:AIME 1991 Problem 11.png&amp;quot;: Better diagram</p> <hr /> <div>Better diagram</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=File:AIME_1991_Problem_11.png&diff=42898 File:AIME 1991 Problem 11.png 2011-11-03T06:23:16Z <p>Aopsvd: uploaded a new version of &amp;quot;File:AIME 1991 Problem 11.png&amp;quot;: Better diagram</p> <hr /> <div>Better diagram</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=File:AIME_1991_Problem_11.png&diff=42897 File:AIME 1991 Problem 11.png 2011-11-03T06:19:24Z <p>Aopsvd: Better diagram</p> <hr /> <div>Better diagram</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_14&diff=38472 2010 AIME I Problems/Problem 14 2011-05-11T04:40:43Z <p>Aopsvd: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> For each positive integer n, let &lt;math&gt;f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor&lt;/math&gt;. Find the largest value of n for which &lt;math&gt;f(n) \le 300&lt;/math&gt;.<br /> <br /> '''Note:''' &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> Observe that &lt;math&gt;f&lt;/math&gt; is strictly increasing in &lt;math&gt;n&lt;/math&gt;. We realize that we need &lt;math&gt;100&lt;/math&gt; terms to add up to around &lt;math&gt;300&lt;/math&gt;, so we need some sequence of &lt;math&gt;2&lt;/math&gt;s, &lt;math&gt;3&lt;/math&gt;s, and then &lt;math&gt;4&lt;/math&gt;s.<br /> <br /> It follows that &lt;math&gt;n \approx 100&lt;/math&gt;. Manually checking shows that &lt;math&gt;f(109) = 300&lt;/math&gt; and &lt;math&gt;f(110) &gt; 300&lt;/math&gt;. Thus, our answer is &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> Because we want the value for which &lt;math&gt;f(n)=300&lt;/math&gt;, the average value of the 100 terms of the sequence should be around &lt;math&gt;3&lt;/math&gt;. For the value of &lt;math&gt;\lfloor \log_{10} (kn) \rfloor&lt;/math&gt; to be &lt;math&gt;3&lt;/math&gt;, &lt;math&gt;1000 \le kn &lt; 10000&lt;/math&gt;. We want kn to be around the middle of that range, and for k to be in the middle of 0 and 100, let &lt;math&gt;k=50&lt;/math&gt;, so &lt;math&gt;50n=\frac{10000+1000}{2}=\frac{11000}{2}=5500&lt;/math&gt;, and &lt;math&gt;n = 110&lt;/math&gt;. &lt;math&gt;f(110) = 301&lt;/math&gt;, so we want to lower &lt;math&gt;n&lt;/math&gt;. Testing &lt;math&gt;109&lt;/math&gt; yields &lt;math&gt;300&lt;/math&gt;, so our answer is still &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == Solution 3 ==<br /> <br /> For any &lt;math&gt;n&lt;/math&gt; where the sum is close to &lt;math&gt;300&lt;/math&gt;, all the terms in the sum must be equal to &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;. Let &lt;math&gt;M&lt;/math&gt; be the number of terms less than or equal to &lt;math&gt;3&lt;/math&gt; and &lt;math&gt;N&lt;/math&gt; be the number of terms equal to &lt;math&gt;2&lt;/math&gt; (also counted in &lt;math&gt;M&lt;/math&gt;). With this definition of &lt;math&gt;M&lt;/math&gt; and &lt;math&gt;N&lt;/math&gt; the total will be &lt;math&gt;400 - M - N \le 300&lt;/math&gt;, from which &lt;math&gt;M + N \ge 100&lt;/math&gt;. Now &lt;math&gt;M+1&lt;/math&gt; is the smallest integer &lt;math&gt;k&lt;/math&gt; for which &lt;math&gt;\log_{10}(kn) \ge 4&lt;/math&gt; or &lt;math&gt;kn \ge 10000&lt;/math&gt;, thus &lt;cmath&gt;M = \left\lfloor\frac{9999}{n}\right\rfloor.&lt;/cmath&gt; Similarly, &lt;cmath&gt;N = \left\lfloor\frac{999}{n}\right\rfloor = \left\lfloor\frac{M}{10}\right\rfloor.&lt;/cmath&gt;<br /> <br /> Therefore, &lt;cmath&gt;M + \left\lfloor \frac{M}{10} \right\rfloor \ge 100 \implies M \ge \left\lceil\frac{1000}{11}\right\rceil = 91 \implies n \le \left\lfloor\frac{9999}{91}\right\rfloor = 109.&lt;/cmath&gt; Since we want the largest possible &lt;math&gt;n&lt;/math&gt;, the answer is &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2010|num-b=13|num-a=15|n=I}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_14&diff=38471 2010 AIME I Problems/Problem 14 2011-05-11T04:32:49Z <p>Aopsvd: /* Solution 3 */</p> <hr /> <div>== Problem ==<br /> For each positive integer n, let &lt;math&gt;f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor&lt;/math&gt;. Find the largest value of n for which &lt;math&gt;f(n) \le 300&lt;/math&gt;.<br /> <br /> '''Note:''' &lt;math&gt;\lfloor x \rfloor&lt;/math&gt; is the greatest integer less than or equal to &lt;math&gt;x&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> Observe that &lt;math&gt;f&lt;/math&gt; is strictly increasing in &lt;math&gt;n&lt;/math&gt;. We realize that we need &lt;math&gt;100&lt;/math&gt; terms to add up to around &lt;math&gt;300&lt;/math&gt;, so we need some sequence of &lt;math&gt;2&lt;/math&gt;s, &lt;math&gt;3&lt;/math&gt;s, and then &lt;math&gt;4&lt;/math&gt;s.<br /> <br /> It follows that &lt;math&gt;n \approx 100&lt;/math&gt;. Manually checking shows that &lt;math&gt;f(109) = 300&lt;/math&gt; and &lt;math&gt;f(110) &gt; 300&lt;/math&gt;. Thus, our answer is &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> Because we want the value for which &lt;math&gt;f(n)=300&lt;/math&gt;, the average value of the 100 terms of the sequence should be around &lt;math&gt;3&lt;/math&gt;. For the value of &lt;math&gt;\lfloor \log_{10} (kn) \rfloor&lt;/math&gt; to be &lt;math&gt;3&lt;/math&gt;, &lt;math&gt;1000 \le kn &lt; 10000&lt;/math&gt;. We want kn to be around the middle of that range, and for k to be in the middle of 0 and 100, let &lt;math&gt;k=50&lt;/math&gt;, so &lt;math&gt;50n=\frac{10000+1000}{2}=\frac{11000}{2}=5500&lt;/math&gt;, and &lt;math&gt;n = 110&lt;/math&gt;. &lt;math&gt;f(110) = 301&lt;/math&gt;, so we want to lower &lt;math&gt;n&lt;/math&gt;. Testing &lt;math&gt;109&lt;/math&gt; yields &lt;math&gt;300&lt;/math&gt;, so our answer is still &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == Solution 3 ==<br /> <br /> For any &lt;math&gt;n&lt;/math&gt; where the sum is close to &lt;math&gt;300&lt;/math&gt;, all the terms in the sum must be equal to &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt; or &lt;math&gt;4&lt;/math&gt;. Let &lt;math&gt;M&lt;/math&gt; be the number of terms less than or equal to &lt;math&gt;3&lt;/math&gt; and &lt;math&gt;N&lt;/math&gt; be the number of terms equal to &lt;math&gt;2&lt;/math&gt; (also counted in &lt;math&gt;M&lt;/math&gt;). With this definition of &lt;math&gt;M&lt;/math&gt; and &lt;math&gt;N&lt;/math&gt; the total will be &lt;math&gt;400 - M - N \le 300&lt;/math&gt;, from which &lt;math&gt;M + N \ge 100&lt;/math&gt;. Now &lt;math&gt;M+1&lt;/math&gt; is the smallest integer &lt;math&gt;k&lt;/math&gt; for which &lt;math&gt;\log_{10}(kn) \ge 4&lt;/math&gt; or &lt;math&gt;kn \ge 10000&lt;/math&gt;, thus &lt;cmath&gt;M = \left\lfloor\frac{9999}{n}\right\rfloor.&lt;/cmath&gt; Similarly, &lt;cmath&gt;N = \left\lfloor\frac{999}{n}\right\rfloor = \left\lfloor\frac{M}{10}\right\rfloor.&lt;/cmath&gt;<br /> <br /> Therefore, &lt;cmath&gt;M + \left\lfloor \frac{M}{10} \right\rfloor \ge 100 \implies M \ge 91 \implies n \le \left\lfloor\frac{9999}M\right\rfloor = 109.&lt;/cmath&gt; Since we want the largest possible &lt;math&gt;n&lt;/math&gt;, the answer is &lt;math&gt;\boxed{109}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2010|num-b=13|num-a=15|n=I}}<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_1&diff=38443 1988 IMO Problems/Problem 1 2011-05-10T00:33:07Z <p>Aopsvd: /* Problem */</p> <hr /> <div>==Problem==<br /> Consider 2 concentric circles with radii &lt;math&gt;R&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; (&lt;math&gt;R&gt;r&lt;/math&gt;) with center &lt;math&gt;O&lt;/math&gt;. Fix &lt;math&gt;P&lt;/math&gt; on the small circle and consider the variable chord &lt;math&gt;AP&lt;/math&gt; of the small circle. Points &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; lie on the large circle; &lt;math&gt;B,P,C&lt;/math&gt; are collinear and &lt;math&gt;BC&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;. <br /> <br /> &lt;ol type=&quot;i&quot;&gt;<br /> &lt;li&gt;For which values of &lt;math&gt;\angle OPA&lt;/math&gt; is the sum &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; extremal?&lt;/li&gt;<br /> &lt;li&gt;What are the possible positions of the midpoints &lt;math&gt;U&lt;/math&gt; of &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;V&lt;/math&gt; of &lt;math&gt;AC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; varies?&lt;/li&gt;<br /> &lt;/ol&gt;<br /> <br /> ==Solution==<br /> <br /> &lt;ol type=&quot;i&quot;&gt;<br /> &lt;li&gt;<br /> We claim that the value &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies, and thus achieves its maximum at all value of &lt;math&gt;\angle OPA&lt;/math&gt;. We have from the Pythagorean Theorem that &lt;math&gt;CA^2=AP^2+PC^2&lt;/math&gt; and &lt;math&gt;AB^2=AP^2+PB^2&lt;/math&gt; and so our expression becomes<br /> <br /> &lt;cmath&gt; BC^2+PB^2+PC^2+2AP^2=2BC^2+2AP^2-2PB\cdot PC &lt;/cmath&gt;<br /> <br /> Since &lt;math&gt;PB\cdot PC&lt;/math&gt; is the power of the point &lt;math&gt;P&lt;/math&gt;, it stays constant as &lt;math&gt;A&lt;/math&gt; varies. Thus, we are left to prove that the value &lt;math&gt;BC^2+AP^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies. Let &lt;math&gt;G&lt;/math&gt; be the midpoint of &lt;math&gt;AP&lt;/math&gt; and let &lt;math&gt;H&lt;/math&gt; be the midpoint of &lt;math&gt;BC&lt;/math&gt;. Since &lt;math&gt;OG&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;, we find that &lt;math&gt;PG=r\cos OPA&lt;/math&gt;. Similarly, we find that &lt;math&gt;OH=r\sin OPC=r\cos OPA&lt;/math&gt;. Thus, by the Pythagorean Theorem, we have <br /> <br /> &lt;cmath&gt;<br /> \begin{align*}<br /> BC^2&amp; =4(R^2-r^2\cos^2 OPA) \\<br /> AP^2&amp;=4r^2\cos^2OPA<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Now it is obvious that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant for all values of &lt;math&gt;\angle OPA&lt;/math&gt;. <br /> &lt;/li&gt;<br /> <br /> &lt;li&gt;<br /> <br /> We claim that all points &lt;math&gt;U,V&lt;/math&gt; lie on a circle centered at the midpoint of &lt;math&gt;OP&lt;/math&gt;, &lt;math&gt;M&lt;/math&gt; with radius &lt;math&gt;\frac{R}{2}&lt;/math&gt;. Let &lt;math&gt;T&lt;/math&gt; be the midpoint of &lt;math&gt;UV&lt;/math&gt;. Since &lt;math&gt;H&lt;/math&gt; is the midpoint of &lt;math&gt;BC&lt;/math&gt;, it is clear that the projection of &lt;math&gt;T&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt; is the midpoint of &lt;math&gt;H&lt;/math&gt; and &lt;math&gt;P&lt;/math&gt; (the projection of &lt;math&gt;A&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt;). Thus, we have that &lt;math&gt;MT&lt;/math&gt; is perpendicular to &lt;math&gt;UV&lt;/math&gt; and thus the triangle &lt;math&gt;MUV&lt;/math&gt; is isosceles. We have<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> UT &amp;=\frac{1}{2}UV=\frac{1}{4}BC \mbox{ and } \\<br /> MT &amp;=\frac{1}{2}PG=\frac{1}{4}AP.<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Thus, from the Pythagorean Theorem we have<br /> &lt;cmath&gt; MV^2=MU^2=\frac{1}{16}\left(BC^2+AP^2\right).&lt;/cmath&gt;<br /> Since we have shown already that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant, we have that &lt;math&gt;MV=MU=\frac{R}{2}&lt;/math&gt; and the locus of points &lt;math&gt;U,V&lt;/math&gt; is indeed a circle of radius &lt;math&gt;\frac{R}{2}&lt;/math&gt; with center &lt;math&gt;M&lt;/math&gt;.<br /> &lt;/li&gt;<br /> &lt;/ol&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_1&diff=38442 1988 IMO Problems/Problem 1 2011-05-10T00:27:06Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem==<br /> Consider 2 concentric circles with radii &lt;math&gt;R&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; (&lt;math&gt;R&gt;r&lt;/math&gt;) with center &lt;math&gt;O&lt;/math&gt;. Fix &lt;math&gt;P&lt;/math&gt; on the small circle and consider the variable chord &lt;math&gt;AP&lt;/math&gt; of the small circle. Points &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; lie on the large circle; &lt;math&gt;B,P,C&lt;/math&gt; are collinear and &lt;math&gt;BC&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;. <br /> <br /> i.) For which values of &lt;math&gt;\angle OPA&lt;/math&gt; is the sum &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; extremal? <br /> <br /> ii.) What are the possible positions of the midpoints &lt;math&gt;U&lt;/math&gt; of &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;V&lt;/math&gt; of &lt;math&gt;AC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; varies? <br /> <br /> <br /> ==Solution==<br /> <br /> &lt;ol type=&quot;i&quot;&gt;<br /> &lt;li&gt;<br /> We claim that the value &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies, and thus achieves its maximum at all value of &lt;math&gt;\angle OPA&lt;/math&gt;. We have from the Pythagorean Theorem that &lt;math&gt;CA^2=AP^2+PC^2&lt;/math&gt; and &lt;math&gt;AB^2=AP^2+PB^2&lt;/math&gt; and so our expression becomes<br /> <br /> &lt;cmath&gt; BC^2+PB^2+PC^2+2AP^2=2BC^2+2AP^2-2PB\cdot PC &lt;/cmath&gt;<br /> <br /> Since &lt;math&gt;PB\cdot PC&lt;/math&gt; is the power of the point &lt;math&gt;P&lt;/math&gt;, it stays constant as &lt;math&gt;A&lt;/math&gt; varies. Thus, we are left to prove that the value &lt;math&gt;BC^2+AP^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies. Let &lt;math&gt;G&lt;/math&gt; be the midpoint of &lt;math&gt;AP&lt;/math&gt; and let &lt;math&gt;H&lt;/math&gt; be the midpoint of &lt;math&gt;BC&lt;/math&gt;. Since &lt;math&gt;OG&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;, we find that &lt;math&gt;PG=r\cos OPA&lt;/math&gt;. Similarly, we find that &lt;math&gt;OH=r\sin OPC=r\cos OPA&lt;/math&gt;. Thus, by the Pythagorean Theorem, we have <br /> <br /> &lt;cmath&gt;<br /> \begin{align*}<br /> BC^2&amp; =4(R^2-r^2\cos^2 OPA) \\<br /> AP^2&amp;=4r^2\cos^2OPA<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Now it is obvious that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant for all values of &lt;math&gt;\angle OPA&lt;/math&gt;. <br /> &lt;/li&gt;<br /> <br /> &lt;li&gt;<br /> <br /> We claim that all points &lt;math&gt;U,V&lt;/math&gt; lie on a circle centered at the midpoint of &lt;math&gt;OP&lt;/math&gt;, &lt;math&gt;M&lt;/math&gt; with radius &lt;math&gt;\frac{R}{2}&lt;/math&gt;. Let &lt;math&gt;T&lt;/math&gt; be the midpoint of &lt;math&gt;UV&lt;/math&gt;. Since &lt;math&gt;H&lt;/math&gt; is the midpoint of &lt;math&gt;BC&lt;/math&gt;, it is clear that the projection of &lt;math&gt;T&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt; is the midpoint of &lt;math&gt;H&lt;/math&gt; and &lt;math&gt;P&lt;/math&gt; (the projection of &lt;math&gt;A&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt;). Thus, we have that &lt;math&gt;MT&lt;/math&gt; is perpendicular to &lt;math&gt;UV&lt;/math&gt; and thus the triangle &lt;math&gt;MUV&lt;/math&gt; is isosceles. We have<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> UT &amp;=\frac{1}{2}UV=\frac{1}{4}BC \mbox{ and } \\<br /> MT &amp;=\frac{1}{2}PG=\frac{1}{4}AP.<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Thus, from the Pythagorean Theorem we have<br /> &lt;cmath&gt; MV^2=MU^2=\frac{1}{16}\left(BC^2+AP^2\right).&lt;/cmath&gt;<br /> Since we have shown already that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant, we have that &lt;math&gt;MV=MU=\frac{R}{2}&lt;/math&gt; and the locus of points &lt;math&gt;U,V&lt;/math&gt; is indeed a circle of radius &lt;math&gt;\frac{R}{2}&lt;/math&gt; with center &lt;math&gt;M&lt;/math&gt;.<br /> &lt;/li&gt;<br /> &lt;/ol&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_1&diff=38441 1988 IMO Problems/Problem 1 2011-05-10T00:00:17Z <p>Aopsvd: </p> <hr /> <div>==Problem==<br /> Consider 2 concentric circles with radii &lt;math&gt;R&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt; (&lt;math&gt;R&gt;r&lt;/math&gt;) with center &lt;math&gt;O&lt;/math&gt;. Fix &lt;math&gt;P&lt;/math&gt; on the small circle and consider the variable chord &lt;math&gt;AP&lt;/math&gt; of the small circle. Points &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; lie on the large circle; &lt;math&gt;B,P,C&lt;/math&gt; are collinear and &lt;math&gt;BC&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;. <br /> <br /> i.) For which values of &lt;math&gt;\angle OPA&lt;/math&gt; is the sum &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; extremal? <br /> <br /> ii.) What are the possible positions of the midpoints &lt;math&gt;U&lt;/math&gt; of &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;V&lt;/math&gt; of &lt;math&gt;AC&lt;/math&gt; as &lt;math&gt;A&lt;/math&gt; varies? <br /> <br /> <br /> ==Solution==<br /> <br /> '''i.)'''<br /> <br /> We claim that the value &lt;math&gt;BC^2+CA^2+AB^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies, and thus achieves its maximum at all value of &lt;math&gt;\angle OPA&lt;/math&gt;. We have from the Pythagorean Theorem that &lt;math&gt;CA^2=AP^2+PC^2&lt;/math&gt; and &lt;math&gt;AB^2=AP^2+PB^2&lt;/math&gt; and so our expression becomes<br /> <br /> &lt;math&gt;BC^2+PB^2+PC^2+2AP^2=2BC^2+2AP^2-2PB\cdot PC&lt;/math&gt;<br /> <br /> Since &lt;math&gt;PB\cdot PC&lt;/math&gt; is the power of the point &lt;math&gt;P&lt;/math&gt;, it stays constant as &lt;math&gt;A&lt;/math&gt; varies. Thus, we are left to prove that the value &lt;math&gt;BC^2+AP^2&lt;/math&gt; stays constant as &lt;math&gt;\angle OPA&lt;/math&gt; varies. Let &lt;math&gt;G&lt;/math&gt; be the midpoint of &lt;math&gt;AP&lt;/math&gt; and let &lt;math&gt;H&lt;/math&gt; be the midpoint of &lt;math&gt;BC&lt;/math&gt;. Since &lt;math&gt;OG&lt;/math&gt; is perpendicular to &lt;math&gt;AP&lt;/math&gt;, we find that &lt;math&gt;PG=r\cos OPA&lt;/math&gt;. Similarly, we find that &lt;math&gt;OH=r\sin OPC=r\cos OPA&lt;/math&gt;. Thus, by the Pythagorean Theorem, we have <br /> <br /> &lt;math&gt;BC^2=4(R^2-r^2\cos^2 OPA)&lt;/math&gt;<br /> <br /> &lt;math&gt;AP^2=4r^2\cos^2OPA&lt;/math&gt;<br /> <br /> Now it is obvious that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant for all values of &lt;math&gt;\angle OPA&lt;/math&gt;. <br /> <br /> <br /> '''ii.)'''<br /> <br /> We claim that all points &lt;math&gt;U,V&lt;/math&gt; lie on a circle centered at the midpoint of &lt;math&gt;OP&lt;/math&gt;, &lt;math&gt;M&lt;/math&gt; with radius &lt;math&gt;\frac{R}{2}&lt;/math&gt;. Let &lt;math&gt;T&lt;/math&gt; be the midpoint of &lt;math&gt;UV&lt;/math&gt;. Since &lt;math&gt;H&lt;/math&gt; is the midpoint of &lt;math&gt;BC&lt;/math&gt;, it is clear that the projection of &lt;math&gt;T&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt; is the midpoint of &lt;math&gt;H&lt;/math&gt; and &lt;math&gt;P&lt;/math&gt; (the projection of &lt;math&gt;A&lt;/math&gt; onto &lt;math&gt;BC&lt;/math&gt;). Thus, we have that &lt;math&gt;MT&lt;/math&gt; is perpendicular to &lt;math&gt;UV&lt;/math&gt; and thus the triangle &lt;math&gt;MUV&lt;/math&gt; is iscoceles. We have &lt;math&gt;UT=\frac{1}{2}UV=\frac{1}{4}BC&lt;/math&gt; and &lt;math&gt;MT=\frac{1}{2}PG=\frac{1}{4}AP&lt;/math&gt;. Thus, from the Pythagorean Theorem we have &lt;math&gt;MV^2=MU^2=\frac{1}{16}\left(BC^2+AP^2\right)&lt;/math&gt;. Since we have shown already that &lt;math&gt;BC^2+AP^2=4R^2&lt;/math&gt; is constant, we have that &lt;math&gt;MV=MU=\frac{R}{2}&lt;/math&gt; and the locus of points &lt;math&gt;U,V&lt;/math&gt; is indeed a circle of radius &lt;math&gt;\frac{R}{2}&lt;/math&gt; with center &lt;math&gt;M&lt;/math&gt;.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_4&diff=38348 2011 USAMO Problems/Problem 4 2011-05-06T16:47:27Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem==<br /> Consider the assertion that for each positive integer &lt;math&gt;n \ge 2&lt;/math&gt;, the remainder upon dividing &lt;math&gt;2^{2^n}&lt;/math&gt; by &lt;math&gt;2^n-1&lt;/math&gt; is a power of 4. Either prove the assertion or find (with proof) a counterexample.<br /> <br /> ==Solution==<br /> We will show that &lt;math&gt;n = 25&lt;/math&gt; is a counter-example.<br /> <br /> Since &lt;math&gt;\textstyle 2^n \equiv 1 \pmod{2^n - 1}&lt;/math&gt;, we see that for any integer &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;\textstyle 2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}&lt;/math&gt;. Let &lt;math&gt;0 \le m &lt; n&lt;/math&gt; be the residue of &lt;math&gt;2^n \pmod n&lt;/math&gt;. Note that since &lt;math&gt;\textstyle m &lt; n&lt;/math&gt; and &lt;math&gt;\textstyle n \ge 2&lt;/math&gt;, necessarily &lt;math&gt;\textstyle 2^m &lt; 2^n -1&lt;/math&gt;, and thus the remainder in question is &lt;math&gt;\textstyle 2^m&lt;/math&gt;. We want to show that &lt;math&gt;\textstyle 2^m \pmod {2^n-1}&lt;/math&gt; is an odd power of 2 for some &lt;math&gt;\textstyle n&lt;/math&gt;, and thus not a power of 4.<br /> <br /> Let &lt;math&gt;\textstyle n=p^2&lt;/math&gt; for some odd prime &lt;math&gt;\textstyle p&lt;/math&gt;. Then &lt;math&gt;\textstyle \varphi(p^2) = p^2 - p&lt;/math&gt;. Since 2 is co-prime to &lt;math&gt;\textstyle p^2&lt;/math&gt;, we have<br /> &lt;cmath&gt;{2^{\varphi(p^2)} \equiv 1 \pmod{p^2}}&lt;/cmath&gt;<br /> and thus<br /> &lt;cmath&gt;\textstyle 2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}.&lt;/cmath&gt;<br /> <br /> Therefore, for a counter-example, it suffices that &lt;math&gt;\textstyle 2^p \pmod{p^2}&lt;/math&gt; be odd. Choosing &lt;math&gt;\textstyle p=5&lt;/math&gt;, we have &lt;math&gt;\textstyle 2^5 = 32 \equiv 7 \pmod{25}&lt;/math&gt;. Therefore, &lt;math&gt;\textstyle 2^{25} \equiv 7 \pmod{25}&lt;/math&gt; and thus<br /> &lt;cmath&gt;\textstyle 2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}.&lt;/cmath&gt;<br /> Since &lt;math&gt;\textstyle 2^7&lt;/math&gt; is not a power of 4, we are done.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=3|num-a=5}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38337 2011 USAMO Problems/Problem 6 2011-05-05T19:33:54Z <p>Aopsvd: /* Minimality */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\textstyle \binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\textstyle \binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;\textstyle U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;\textstyle n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;\textstyle A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\textstyle \prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\textstyle \binom{n_\alpha}k}&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38336 2011 USAMO Problems/Problem 6 2011-05-05T19:33:31Z <p>Aopsvd: /* Minimality */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\textstyle \binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\textstyle \binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;\textstyle n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;\textstyle A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\textstyle \prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\textstyle \binom{n_\alpha}k}&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38335 2011 USAMO Problems/Problem 6 2011-05-05T19:32:02Z <p>Aopsvd: /* Existence */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\textstyle \binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\textstyle \binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\textstyle \binom{n_\alpha}k}&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38334 2011 USAMO Problems/Problem 6 2011-05-05T19:31:45Z <p>Aopsvd: /* Existence */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\textstyle \binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\textstyle \binom{n_\alpha}k}&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38333 2011 USAMO Problems/Problem 6 2011-05-05T19:31:15Z <p>Aopsvd: /* Minimality */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\textstyle \binom{n_\alpha}k}&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38332 2011 USAMO Problems/Problem 6 2011-05-05T19:29:24Z <p>Aopsvd: /* Minimality */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, as an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\binom{n_\alpha}k&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k. &lt;/cmath&gt;<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38331 2011 USAMO Problems/Problem 6 2011-05-05T19:28:11Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt; N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S| &lt;/cmath&gt;<br /> reversing the order summation, we get:<br /> &lt;cmath&gt;\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k &lt;/cmath&gt; since an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\binom{n_\alpha}k&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets.<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;\begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}&lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt;\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=38321 2011 USAMO Problems/Problem 6 2011-05-03T22:46:02Z <p>Aopsvd: Created page with '==Problem== Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;…'</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> ==Solution==<br /> <br /> ===Existence===<br /> Note that &lt;math&gt;\binom{11}3 = 165,&lt;/math&gt; and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&amp;mdash;one with each of the 9 remaining sets&amp;mdash;any two sets will have 9 elements in common. Since &lt;math&gt;\binom{10}2 = 45,&lt;/math&gt; each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the &lt;math&gt;A_i&lt;/math&gt; and we are done.<br /> <br /> ===Minimality===<br /> As in the proof of PIE, let &lt;math&gt;I&lt;/math&gt; be a finite set. Let &lt;math&gt;U = \bigcup_{i\in I} A_i&lt;/math&gt;. For &lt;math&gt;i\in I&lt;/math&gt;, let &lt;math&gt;\chi_i&lt;/math&gt; be the &lt;i&gt;characteristic function&lt;/i&gt; of &lt;math&gt;A_i&lt;/math&gt;, that is, for &lt;math&gt;\alpha \in U,&lt;/math&gt;<br /> &lt;cmath&gt;<br /> \chi_i(\alpha) = \begin{cases}<br /> 1 &amp; \alpha \in A_i \\<br /> 0 &amp; \alpha \not\in A_i<br /> \end{cases}<br /> &lt;/cmath&gt;<br /> <br /> For each &lt;math&gt;\alpha \in U&lt;/math&gt; let &lt;math&gt;n_\alpha = \sum_{i \in I} \chi_i(\alpha)&lt;/math&gt;, that is the number of subsets &lt;math&gt;A_i&lt;/math&gt; of which &lt;math&gt;\alpha&lt;/math&gt; is an element.<br /> <br /> If &lt;math&gt;S \subset I&lt;/math&gt;, let &lt;math&gt;A_S = \bigcap_{i \in S}A_i&lt;/math&gt;. Then the characteristic function of &lt;math&gt;A_S&lt;/math&gt; is &lt;math&gt;\prod_{i \in S} \chi_i&lt;/math&gt;.<br /> The number of elements of &lt;math&gt;A_S&lt;/math&gt; is simply the sum of its characteristic function over all the elements of &lt;math&gt;U&lt;/math&gt;:<br /> &lt;cmath&gt; |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). &lt;/cmath&gt;<br /> For &lt;math&gt;0 \le k \le |I|&lt;/math&gt;, consider the sum &lt;math&gt;N_k&lt;/math&gt; of &lt;math&gt;|A_S|&lt;/math&gt; over all &lt;math&gt;S\subset I&lt;/math&gt; with &lt;math&gt;|S|= k&lt;/math&gt;. This is:<br /> &lt;cmath&gt;<br /> N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S|<br /> &lt;/cmath&gt;<br /> reversing the order summation, we get:<br /> &lt;cmath&gt;<br /> \sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k<br /> &lt;/cmath&gt;<br /> since an element &lt;math&gt;\alpha&lt;/math&gt; that appears in &lt;math&gt;n_\alpha&lt;/math&gt; of the &lt;math&gt;A_i&lt;/math&gt;, will appear in exactly &lt;math&gt;\binom{n_\alpha}k&lt;/math&gt; intersections of &lt;math&gt;k&lt;/math&gt; subsets.<br /> <br /> Applying the above with &lt;math&gt;I = \{1, 2, \ldots, 11\},&lt;/math&gt; and &lt;math&gt;k=1&lt;/math&gt;, since each of the 11 &lt;math&gt;A_i&lt;/math&gt; has 45 elements, we get:<br /> &lt;cmath&gt; N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45, &lt;/cmath&gt;<br /> and for &lt;math&gt;k = 2&lt;/math&gt;, since each of the 55 pairs &lt;math&gt;A_i \cap A_j&lt;/math&gt; has 9 elements, we get:<br /> &lt;cmath&gt; N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45. &lt;/cmath&gt;<br /> <br /> Therefore<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> s_1 &amp;= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\<br /> s_2 &amp;= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45.<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Let &lt;math&gt;n = |U|&lt;/math&gt; be the number of elements of &lt;math&gt;U&lt;/math&gt;.<br /> Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have:<br /> &lt;cmath&gt; \frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.&lt;/cmath&gt;<br /> <br /> Thus &lt;math&gt;|U| \ge 165&lt;/math&gt; as required.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_2&diff=38279 2011 USAMO Problems/Problem 2 2011-04-29T15:42:48Z <p>Aopsvd: /* See also */</p> <hr /> <div>==Problem==<br /> An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer &lt;math&gt;m&lt;/math&gt; from each of the integers at two neighboring vertices and adding 2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount &lt;math&gt;m&lt;/math&gt; and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.<br /> <br /> ==Solution==<br /> Let &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4.<br /> For each &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; let &lt;math&gt;n_i&lt;/math&gt; be the integer at vertex &lt;math&gt;i&lt;/math&gt; and let &lt;math&gt;r_i \in \mathbb{Z}_5&lt;/math&gt; be defined as:<br /> &lt;cmath&gt;<br /> r_i<br /> \equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4}<br /> \equiv \sum_{k\in\mathbb{Z}_5}(i-k)n_k \pmod 5.<br /> &lt;/cmath&gt;<br /> Let &lt;math&gt;s = \sum_{i\in\mathbb{Z}_5} n_i&lt;/math&gt;. A move in the game consists of<br /> &lt;cmath&gt;<br /> (n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) \mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})<br /> &lt;/cmath&gt;<br /> for some vertex &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; and integer &lt;math&gt;m&lt;/math&gt;. We immediately see that &lt;math&gt;s&lt;/math&gt; is an invariant of the game. After our move the new value of &lt;math&gt;r_i&lt;/math&gt; is decreased by &lt;math&gt;3m + 2m \equiv 0 \pmod 5&lt;/math&gt; as a result of the change in the &lt;math&gt;3n_{i+2}&lt;/math&gt; and &lt;math&gt;2n_{i+3}&lt;/math&gt; terms. So &lt;math&gt;r_i&lt;/math&gt; does not change after a move at vertex &lt;math&gt;i&lt;/math&gt;.<br /> <br /> For all &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; we have:<br /> &lt;cmath&gt;<br /> r_{i+1} - r_i<br /> \equiv \sum_{k\in\mathbb{Z}_5} ((i+1-k)n_k - (i-k)n_k)<br /> \equiv \sum_{k\in\mathbb{Z}_5} n_k \equiv s \pmod 5.<br /> &lt;/cmath&gt;<br /> <br /> Therefore, the &lt;math&gt;r_i&lt;/math&gt; form an arithmetic progression in &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; with a difference of &lt;math&gt;s&lt;/math&gt;. Since &lt;math&gt;r_k&lt;/math&gt; is unchanged by a move at vertex &lt;math&gt;k&lt;/math&gt;, so are all the remaining &lt;math&gt;r_i&lt;/math&gt; as the differences are constant.<br /> <br /> Provided &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, we see that the mapping &lt;math&gt;i \mapsto r_i&lt;/math&gt; is a bijection &lt;math&gt;\mathbb{Z}_5 \to \mathbb{Z}_5&lt;/math&gt; and exactly one vertex will have &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt;. As &lt;math&gt;r_i&lt;/math&gt; is an invariant, a winning vertex must have &lt;math&gt;r_i \equiv 0&lt;/math&gt;, since in the final state each &lt;math&gt;n_k&lt;/math&gt; with &lt;math&gt;k \ne i&lt;/math&gt; is zero. So, for &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, if a winning vertex exists, it is the unique vertex with &lt;math&gt;r_i \equiv 0&lt;/math&gt;.<br /> <br /> Without loss of generality, it remains to show that if &lt;math&gt;r_0 \equiv 0 \pmod 5&lt;/math&gt;, then 0 must be a winning vertex. To prove this, we perform the following moves:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n_0, n_1, n_2, n_3, n_4) &amp;\mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), &amp; (i, m) &amp;= (3, n_1) \\<br /> &amp;\mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) &amp; (i, m) &amp;= (2, n_4)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> We designate the new state &lt;math&gt;(n'_0, 0, n'_2, n'_3, 0)&lt;/math&gt;. Since &lt;math&gt;r_0 \equiv 0&lt;/math&gt; is an invariant, and &lt;math&gt;n'_1 = n'_4 = 0&lt;/math&gt;, we now have &lt;math&gt;r_0 \equiv n'_3 - n'_2 = 5p&lt;/math&gt;, for some integer &lt;math&gt;p&lt;/math&gt;. Our final set of moves is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n'_0, 0, n'_2, n'_3, 0) &amp;\mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), &amp; (i, m) &amp;= (3, -p)\\<br /> &amp;\mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), &amp; (i, m) &amp;= (4, p) \\<br /> &amp;\mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), &amp; (i, m) &amp;= (2, 2p)\\<br /> &amp;\mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) &amp; (i, m) &amp;= (0, n'_2 + 3p)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Now our chosen vertex 0 is the only vertex with a non-zero value, and since &lt;math&gt;s&lt;/math&gt; is invariant, that value is &lt;math&gt;s&lt;/math&gt; as required. Since a vertex &lt;math&gt;i&lt;/math&gt; with &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt; is winnable, and with &lt;math&gt;s = 2011 \not\equiv 0 \pmod 5&lt;/math&gt; we always have a unique such vertex, we are done.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=1|num-a=3}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_4&diff=38278 2011 USAMO Problems/Problem 4 2011-04-29T15:42:24Z <p>Aopsvd: /* See also */</p> <hr /> <div>==Problem==<br /> Consider the assertion that for each positive integer &lt;math&gt;n \ge 2&lt;/math&gt;, the remainder upon dividing &lt;math&gt;2^{2^n}&lt;/math&gt; by &lt;math&gt;2^n-1&lt;/math&gt; is a power of 4. Either prove the assertion or find (with proof) a counterexample.<br /> <br /> ==Solution==<br /> We will show that &lt;math&gt;n = 25&lt;/math&gt; is a counter-example.<br /> <br /> Since &lt;math&gt;2^n \equiv 1 \pmod{2^n - 1}&lt;/math&gt;, we see that for any integer &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}&lt;/math&gt;. Let &lt;math&gt;0 \le m &lt; n&lt;/math&gt; be the residue of &lt;math&gt;2^n \pmod n&lt;/math&gt;. Note that since &lt;math&gt;m &lt; n&lt;/math&gt; and &lt;math&gt;n \ge 2&lt;/math&gt;, necessarily &lt;math&gt;2^m &lt; 2^n -1&lt;/math&gt;, and thus the remainder in question is &lt;math&gt;2^m&lt;/math&gt;. We want to show that &lt;math&gt;2^m \pmod {2^n-1}&lt;/math&gt; is an odd power of &lt;math&gt;2&lt;/math&gt; for some &lt;math&gt;n&lt;/math&gt;, and thus not a power of &lt;math&gt;4&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;n=p^2&lt;/math&gt; for some odd prime &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;\varphi(p^2) = p^2 - p&lt;/math&gt;. Since &lt;math&gt;2&lt;/math&gt; is co-prime to &lt;math&gt;p^2&lt;/math&gt;, we have &lt;math&gt;2^{\varphi(p^2)} \equiv 1 \pmod{p^2}&lt;/math&gt; and thus &lt;math&gt;2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}&lt;/math&gt;.<br /> <br /> Therefore, for a counter-example, it suffices that &lt;math&gt;2^p \pmod{p^2}&lt;/math&gt; be odd. Choosing &lt;math&gt;p=5&lt;/math&gt;, we have &lt;math&gt;2^5 = 32 \equiv 7 \pmod{25}&lt;/math&gt;. Therefore, &lt;math&gt;2^{25} \equiv 2^7 \pmod{25}&lt;/math&gt; and thus &lt;math&gt;2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}&lt;/math&gt;. Since &lt;math&gt;2^7&lt;/math&gt; is not a power of &lt;math&gt;4&lt;/math&gt;, we are done.<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=3|num-a=5}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_4&diff=38277 2011 USAMO Problems/Problem 4 2011-04-29T15:38:06Z <p>Aopsvd: Added footer</p> <hr /> <div>==Problem==<br /> Consider the assertion that for each positive integer &lt;math&gt;n \ge 2&lt;/math&gt;, the remainder upon dividing &lt;math&gt;2^{2^n}&lt;/math&gt; by &lt;math&gt;2^n-1&lt;/math&gt; is a power of 4. Either prove the assertion or find (with proof) a counterexample.<br /> <br /> ==Solution==<br /> We will show that &lt;math&gt;n = 25&lt;/math&gt; is a counter-example.<br /> <br /> Since &lt;math&gt;2^n \equiv 1 \pmod{2^n - 1}&lt;/math&gt;, we see that for any integer &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}&lt;/math&gt;. Let &lt;math&gt;0 \le m &lt; n&lt;/math&gt; be the residue of &lt;math&gt;2^n \pmod n&lt;/math&gt;. Note that since &lt;math&gt;m &lt; n&lt;/math&gt; and &lt;math&gt;n \ge 2&lt;/math&gt;, necessarily &lt;math&gt;2^m &lt; 2^n -1&lt;/math&gt;, and thus the remainder in question is &lt;math&gt;2^m&lt;/math&gt;. We want to show that &lt;math&gt;2^m \pmod {2^n-1}&lt;/math&gt; is an odd power of &lt;math&gt;2&lt;/math&gt; for some &lt;math&gt;n&lt;/math&gt;, and thus not a power of &lt;math&gt;4&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;n=p^2&lt;/math&gt; for some odd prime &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;\varphi(p^2) = p^2 - p&lt;/math&gt;. Since &lt;math&gt;2&lt;/math&gt; is co-prime to &lt;math&gt;p^2&lt;/math&gt;, we have &lt;math&gt;2^{\varphi(p^2)} \equiv 1 \pmod{p^2}&lt;/math&gt; and thus &lt;math&gt;2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}&lt;/math&gt;.<br /> <br /> Therefore, for a counter-example, it suffices that &lt;math&gt;2^p \pmod{p^2}&lt;/math&gt; be odd. Choosing &lt;math&gt;p=5&lt;/math&gt;, we have &lt;math&gt;2^5 = 32 \equiv 7 \pmod{25}&lt;/math&gt;. Therefore, &lt;math&gt;2^{25} \equiv 2^7 \pmod{25}&lt;/math&gt; and thus &lt;math&gt;2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}&lt;/math&gt;. Since &lt;math&gt;2^7&lt;/math&gt; is not a power of &lt;math&gt;4&lt;/math&gt;, we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2011|num-b=3|num-a=5}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_2&diff=38276 2011 USAMO Problems/Problem 2 2011-04-29T15:37:13Z <p>Aopsvd: Added footer</p> <hr /> <div>==Problem==<br /> An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer &lt;math&gt;m&lt;/math&gt; from each of the integers at two neighboring vertices and adding 2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount &lt;math&gt;m&lt;/math&gt; and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.<br /> <br /> ==Solution==<br /> Let &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4.<br /> For each &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; let &lt;math&gt;n_i&lt;/math&gt; be the integer at vertex &lt;math&gt;i&lt;/math&gt; and let &lt;math&gt;r_i \in \mathbb{Z}_5&lt;/math&gt; be defined as:<br /> &lt;cmath&gt;<br /> r_i<br /> \equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4}<br /> \equiv \sum_{k\in\mathbb{Z}_5}(i-k)n_k \pmod 5.<br /> &lt;/cmath&gt;<br /> Let &lt;math&gt;s = \sum_{i\in\mathbb{Z}_5} n_i&lt;/math&gt;. A move in the game consists of<br /> &lt;cmath&gt;<br /> (n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) \mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})<br /> &lt;/cmath&gt;<br /> for some vertex &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; and integer &lt;math&gt;m&lt;/math&gt;. We immediately see that &lt;math&gt;s&lt;/math&gt; is an invariant of the game. After our move the new value of &lt;math&gt;r_i&lt;/math&gt; is decreased by &lt;math&gt;3m + 2m \equiv 0 \pmod 5&lt;/math&gt; as a result of the change in the &lt;math&gt;3n_{i+2}&lt;/math&gt; and &lt;math&gt;2n_{i+3}&lt;/math&gt; terms. So &lt;math&gt;r_i&lt;/math&gt; does not change after a move at vertex &lt;math&gt;i&lt;/math&gt;.<br /> <br /> For all &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; we have:<br /> &lt;cmath&gt;<br /> r_{i+1} - r_i<br /> \equiv \sum_{k\in\mathbb{Z}_5} ((i+1-k)n_k - (i-k)n_k)<br /> \equiv \sum_{k\in\mathbb{Z}_5} n_k \equiv s \pmod 5.<br /> &lt;/cmath&gt;<br /> <br /> Therefore, the &lt;math&gt;r_i&lt;/math&gt; form an arithmetic progression in &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; with a difference of &lt;math&gt;s&lt;/math&gt;. Since &lt;math&gt;r_k&lt;/math&gt; is unchanged by a move at vertex &lt;math&gt;k&lt;/math&gt;, so are all the remaining &lt;math&gt;r_i&lt;/math&gt; as the differences are constant.<br /> <br /> Provided &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, we see that the mapping &lt;math&gt;i \mapsto r_i&lt;/math&gt; is a bijection &lt;math&gt;\mathbb{Z}_5 \to \mathbb{Z}_5&lt;/math&gt; and exactly one vertex will have &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt;. As &lt;math&gt;r_i&lt;/math&gt; is an invariant, a winning vertex must have &lt;math&gt;r_i \equiv 0&lt;/math&gt;, since in the final state each &lt;math&gt;n_k&lt;/math&gt; with &lt;math&gt;k \ne i&lt;/math&gt; is zero. So, for &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, if a winning vertex exists, it is the unique vertex with &lt;math&gt;r_i \equiv 0&lt;/math&gt;.<br /> <br /> Without loss of generality, it remains to show that if &lt;math&gt;r_0 \equiv 0 \pmod 5&lt;/math&gt;, then 0 must be a winning vertex. To prove this, we perform the following moves:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n_0, n_1, n_2, n_3, n_4) &amp;\mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), &amp; (i, m) &amp;= (3, n_1) \\<br /> &amp;\mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) &amp; (i, m) &amp;= (2, n_4)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> We designate the new state &lt;math&gt;(n'_0, 0, n'_2, n'_3, 0)&lt;/math&gt;. Since &lt;math&gt;r_0 \equiv 0&lt;/math&gt; is an invariant, and &lt;math&gt;n'_1 = n'_4 = 0&lt;/math&gt;, we now have &lt;math&gt;r_0 \equiv n'_3 - n'_2 = 5p&lt;/math&gt;, for some integer &lt;math&gt;p&lt;/math&gt;. Our final set of moves is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n'_0, 0, n'_2, n'_3, 0) &amp;\mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), &amp; (i, m) &amp;= (3, -p)\\<br /> &amp;\mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), &amp; (i, m) &amp;= (4, p) \\<br /> &amp;\mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), &amp; (i, m) &amp;= (2, 2p)\\<br /> &amp;\mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) &amp; (i, m) &amp;= (0, n'_2 + 3p)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Now our chosen vertex 0 is the only vertex with a non-zero value, and since &lt;math&gt;s&lt;/math&gt; is invariant, that value is &lt;math&gt;s&lt;/math&gt; as required. Since a vertex &lt;math&gt;i&lt;/math&gt; with &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt; is winnable, and with &lt;math&gt;s = 2011 \not\equiv 0 \pmod 5&lt;/math&gt; we always have a unique such vertex, we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2011|num-b=1|num-a=3}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_1&diff=38275 2011 USAMO Problems/Problem 1 2011-04-29T15:36:02Z <p>Aopsvd: Added footer</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt; be positive real numbers such that &lt;math&gt;a^2 + b^2 + c^2 + (a + b + c)^2 \le 4&lt;/math&gt;. Prove that<br /> &lt;cmath&gt;\frac{ab + 1}{(a + b)^2} + \frac{bc + 1}{(b + c)^2} + \frac{ca + 1}{(c + a)^2} \ge 3.&lt;/cmath&gt;<br /> <br /> ==Solution==<br /> Since<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (a+b)^2 + (b+c)^2 + (c+a)^2 &amp;= 2(a^2 + b^2 + c^2 + ab + bc + ca) \\<br /> &amp;= a^2 + b^2 + c^2 + (a + b + c)^2,<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> it is natural to consider a change of variables:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> \alpha &amp;= b + c \\<br /> \beta &amp;= c + a \\<br /> \gamma &amp;= a + b<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> with the inverse mapping given by:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> a &amp;= \frac{\beta + \gamma - \alpha}2 \\<br /> b &amp;= \frac{\alpha + \gamma - \beta}2 \\<br /> c &amp;= \frac{\alpha + \beta - \gamma}2<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> With this change of variables, the constraint becomes<br /> &lt;cmath&gt;<br /> \alpha^2 + \beta^2 + \gamma^2 \le 4,<br /> &lt;/cmath&gt;<br /> while the left side of the inequality we need to prove is now<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> &amp; \frac{\gamma^2 - (\alpha - \beta)^2 + 4}{4\gamma^2} +<br /> \frac{\alpha^2 - (\beta - \gamma)^2 + 4}{4\alpha^2} +<br /> \frac{\beta^2 - (\gamma - \alpha)^2 + 4}{4\beta^2} \ge \\ &amp;<br /> \frac{\gamma^2 - (\alpha - \beta)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\gamma^2} +<br /> \frac{\alpha^2 - (\beta - \gamma)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\alpha^2} +<br /> \frac{\beta^2 - (\gamma - \alpha)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\beta^2} = \\ &amp;<br /> \frac{2\gamma^2 + 2\alpha\beta}{4\gamma^2} +<br /> \frac{2\alpha^2 + 2\beta\gamma}{4\alpha^2} +<br /> \frac{2\beta^2 + 2\gamma\alpha}{4\beta^2} = \\ &amp;<br /> \frac32 + \frac{\alpha\beta}{2\gamma^2} +<br /> \frac{\beta\gamma}{2\alpha^2} +<br /> \frac{\gamma\alpha}{2\beta^2}.<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Therefore it remains to prove that<br /> &lt;cmath&gt;<br /> \frac{\alpha\beta}{2\gamma^2} +<br /> \frac{\beta\gamma}{2\alpha^2} +<br /> \frac{\gamma\alpha}{2\beta^2} \ge \frac32.<br /> &lt;/cmath&gt;<br /> <br /> We note that the product of the three (positive) terms is 1/8, therefore by AM-GM their mean is at least 1/2, and thus their sum is at least 3/2 and we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2011|beforetext=|before=First Problem|num-a=2}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_4&diff=38274 2011 USAMO Problems/Problem 4 2011-04-29T15:29:45Z <p>Aopsvd: Since 2^n is 1 mod (2^n-1), reduce the exponent mod n, we can't win with n prime, but n=p^2 will do...</p> <hr /> <div>==Problem==<br /> Consider the assertion that for each positive integer &lt;math&gt;n \ge 2&lt;/math&gt;, the remainder upon dividing &lt;math&gt;2^{2^n}&lt;/math&gt; by &lt;math&gt;2^n-1&lt;/math&gt; is a power of 4. Either prove the assertion or find (with proof) a counterexample.<br /> <br /> ==Solution==<br /> We will show that &lt;math&gt;n = 25&lt;/math&gt; is a counter-example.<br /> <br /> Since &lt;math&gt;2^n \equiv 1 \pmod{2^n - 1}&lt;/math&gt;, we see that for any integer &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}&lt;/math&gt;. Let &lt;math&gt;0 \le m &lt; n&lt;/math&gt; be the residue of &lt;math&gt;2^n \pmod n&lt;/math&gt;. Note that since &lt;math&gt;m &lt; n&lt;/math&gt; and &lt;math&gt;n \ge 2&lt;/math&gt;, necessarily &lt;math&gt;2^m &lt; 2^n -1&lt;/math&gt;, and thus the remainder in question is &lt;math&gt;2^m&lt;/math&gt;. We want to show that &lt;math&gt;2^m \pmod {2^n-1}&lt;/math&gt; is an odd power of &lt;math&gt;2&lt;/math&gt; for some &lt;math&gt;n&lt;/math&gt;, and thus not a power of &lt;math&gt;4&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;n=p^2&lt;/math&gt; for some odd prime &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;\varphi(p^2) = p^2 - p&lt;/math&gt;. Since &lt;math&gt;2&lt;/math&gt; is co-prime to &lt;math&gt;p^2&lt;/math&gt;, we have &lt;math&gt;2^{\varphi(p^2)} \equiv 1 \pmod{p^2}&lt;/math&gt; and thus &lt;math&gt;2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}&lt;/math&gt;.<br /> <br /> Therefore, for a counter-example, it suffices that &lt;math&gt;2^p \pmod{p^2}&lt;/math&gt; be odd. Choosing &lt;math&gt;p=5&lt;/math&gt;, we have &lt;math&gt;2^5 = 32 \equiv 7 \pmod{25}&lt;/math&gt;. Therefore, &lt;math&gt;2^{25} \equiv 2^7 \pmod{25}&lt;/math&gt; and thus &lt;math&gt;2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}&lt;/math&gt;. Since &lt;math&gt;2^7&lt;/math&gt; is not a power of &lt;math&gt;4&lt;/math&gt;, we are done.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_2&diff=38273 2011 USAMO Problems/Problem 2 2011-04-29T15:22:00Z <p>Aopsvd: Zeroing adjacent vertices and looking at how the opposites become winnable solves the problem</p> <hr /> <div>==Problem==<br /> An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer &lt;math&gt;m&lt;/math&gt; from each of the integers at two neighboring vertices and adding 2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount &lt;math&gt;m&lt;/math&gt; and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.<br /> <br /> ==Solution==<br /> Let &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4.<br /> For each &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; let &lt;math&gt;n_i&lt;/math&gt; be the integer at vertex &lt;math&gt;i&lt;/math&gt; and let &lt;math&gt;r_i \in \mathbb{Z}_5&lt;/math&gt; be defined as:<br /> &lt;cmath&gt;<br /> r_i<br /> \equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4}<br /> \equiv \sum_{k\in\mathbb{Z}_5}(i-k)n_k \pmod 5.<br /> &lt;/cmath&gt;<br /> Let &lt;math&gt;s = \sum_{i\in\mathbb{Z}_5} n_i&lt;/math&gt;. A move in the game consists of<br /> &lt;cmath&gt;<br /> (n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) \mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})<br /> &lt;/cmath&gt;<br /> for some vertex &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; and integer &lt;math&gt;m&lt;/math&gt;. We immediately see that &lt;math&gt;s&lt;/math&gt; is an invariant of the game. After our move the new value of &lt;math&gt;r_i&lt;/math&gt; is decreased by &lt;math&gt;3m + 2m \equiv 0 \pmod 5&lt;/math&gt; as a result of the change in the &lt;math&gt;3n_{i+2}&lt;/math&gt; and &lt;math&gt;2n_{i+3}&lt;/math&gt; terms. So &lt;math&gt;r_i&lt;/math&gt; does not change after a move at vertex &lt;math&gt;i&lt;/math&gt;.<br /> <br /> For all &lt;math&gt;i \in \mathbb{Z}_5&lt;/math&gt; we have:<br /> &lt;cmath&gt;<br /> r_{i+1} - r_i<br /> \equiv \sum_{k\in\mathbb{Z}_5} ((i+1-k)n_k - (i-k)n_k)<br /> \equiv \sum_{k\in\mathbb{Z}_5} n_k \equiv s \pmod 5.<br /> &lt;/cmath&gt;<br /> <br /> Therefore, the &lt;math&gt;r_i&lt;/math&gt; form an arithmetic progression in &lt;math&gt;\mathbb{Z}_5&lt;/math&gt; with a difference of &lt;math&gt;s&lt;/math&gt;. Since &lt;math&gt;r_k&lt;/math&gt; is unchanged by a move at vertex &lt;math&gt;k&lt;/math&gt;, so are all the remaining &lt;math&gt;r_i&lt;/math&gt; as the differences are constant.<br /> <br /> Provided &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, we see that the mapping &lt;math&gt;i \mapsto r_i&lt;/math&gt; is a bijection &lt;math&gt;\mathbb{Z}_5 \to \mathbb{Z}_5&lt;/math&gt; and exactly one vertex will have &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt;. As &lt;math&gt;r_i&lt;/math&gt; is an invariant, a winning vertex must have &lt;math&gt;r_i \equiv 0&lt;/math&gt;, since in the final state each &lt;math&gt;n_k&lt;/math&gt; with &lt;math&gt;k \ne i&lt;/math&gt; is zero. So, for &lt;math&gt;s \not\equiv 0 \pmod 5&lt;/math&gt;, if a winning vertex exists, it is the unique vertex with &lt;math&gt;r_i \equiv 0&lt;/math&gt;.<br /> <br /> Without loss of generality, it remains to show that if &lt;math&gt;r_0 \equiv 0 \pmod 5&lt;/math&gt;, then 0 must be a winning vertex. To prove this, we perform the following moves:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n_0, n_1, n_2, n_3, n_4) &amp;\mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), &amp; (i, m) &amp;= (3, n_1) \\<br /> &amp;\mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) &amp; (i, m) &amp;= (2, n_4)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> We designate the new state &lt;math&gt;(n'_0, 0, n'_2, n'_3, 0)&lt;/math&gt;. Since &lt;math&gt;r_0 \equiv 0&lt;/math&gt; is an invariant, and &lt;math&gt;n'_1 = n'_4 = 0&lt;/math&gt;, we now have &lt;math&gt;r_0 \equiv n'_3 - n'_2 = 5p&lt;/math&gt;, for some integer &lt;math&gt;p&lt;/math&gt;. Our final set of moves is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (n'_0, 0, n'_2, n'_3, 0) &amp;\mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), &amp; (i, m) &amp;= (3, -p)\\<br /> &amp;\mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), &amp; (i, m) &amp;= (4, p) \\<br /> &amp;\mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), &amp; (i, m) &amp;= (2, 2p)\\<br /> &amp;\mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) &amp; (i, m) &amp;= (0, n'_2 + 3p)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> Now our chosen vertex 0 is the only vertex with a non-zero value, and since &lt;math&gt;s&lt;/math&gt; is invariant, that value is &lt;math&gt;s&lt;/math&gt; as required. Since a vertex &lt;math&gt;i&lt;/math&gt; with &lt;math&gt;r_i \equiv 0 \pmod 5&lt;/math&gt; is winnable, and with &lt;math&gt;s = 2011 \not\equiv 0 \pmod 5&lt;/math&gt; we always have a unique such vertex, we are done.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems&diff=38272 2011 USAMO Problems 2011-04-29T15:11:50Z <p>Aopsvd: Corrected typo.</p> <hr /> <div>=Day 1=<br /> ==Problem 1==<br /> Let &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt; be positive real numbers such that &lt;math&gt;a^2 + b^2 + c^2 + (a + b + c)^2 \le 4&lt;/math&gt;. Prove that<br /> &lt;cmath&gt;\frac{ab + 1}{(a + b)^2} + \frac{bc + 1}{(b + c)^2} + \frac{ca + 1}{(c + a)^2} \ge 3.&lt;/cmath&gt;<br /> <br /> [[2011 USAMO Problems/Problem 1|Solution]]<br /> <br /> ==Problem 2==<br /> An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer &lt;math&gt;m&lt;/math&gt; from each of the integers at two neighboring vertices and adding &lt;math&gt;2m&lt;/math&gt; to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount &lt;math&gt;m&lt;/math&gt; and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.<br /> <br /> [[2011 USAMO Problems/Problem 2|Solution]]<br /> <br /> ==Problem 3==<br /> In hexagon &lt;math&gt;ABCDEF&lt;/math&gt;, which is nonconvex but not self-intersecting, no pair of opposite sides are parallel. The internal angles satisfy &lt;math&gt;\angle A = 3 \angle D&lt;/math&gt;, &lt;math&gt;\angle C = 3 \angle F&lt;/math&gt;, and &lt;math&gt;\angle E = 3 \angle B&lt;/math&gt;. Furthermore, &lt;math&gt;AB = DE&lt;/math&gt;, &lt;math&gt;BC = EF&lt;/math&gt;, and &lt;math&gt;CD = FA&lt;/math&gt;. Prove that diagonals &lt;math&gt;\overline{AD}&lt;/math&gt;, &lt;math&gt;\overline{BE}&lt;/math&gt;, and &lt;math&gt;\overline{CF}&lt;/math&gt; are concurrent.<br /> <br /> [[2011 USAMO Problems/Problem 3|Solution]]<br /> <br /> =Day 2=<br /> ==Problem 4==<br /> Consider the assertion that for each positive integer &lt;math&gt;n \ge 2&lt;/math&gt;, the remainder upon dividing &lt;math&gt;2^{2^n}&lt;/math&gt; by &lt;math&gt;2^n - 1&lt;/math&gt; is a power of 4. Either prove the assertion or find (with proof) a counterexample.<br /> <br /> [[2011 USAMO Problems/Problem 4|Solution]]<br /> <br /> ==Problem 5==<br /> Let &lt;math&gt;P&lt;/math&gt; be a given point inside quadrilateral &lt;math&gt;ABCD&lt;/math&gt;. Points &lt;math&gt;Q_1&lt;/math&gt; and &lt;math&gt;Q_2&lt;/math&gt; are located within &lt;math&gt;ABCD&lt;/math&gt; such that &lt;math&gt;\angle Q_1 BC = \angle ABP&lt;/math&gt;, &lt;math&gt;\angle Q_1 CB = \angle DCP&lt;/math&gt;, &lt;math&gt;\angle Q_2 AD = \angle BAP&lt;/math&gt;, &lt;math&gt;\angle Q_2 DA = \angle CDP&lt;/math&gt;. Prove that &lt;math&gt;\overline{Q_1 Q_2} \parallel \overline{AB}&lt;/math&gt; if and only if &lt;math&gt;\overline{Q_1 Q_2} \parallel \overline{CD}&lt;/math&gt;.<br /> <br /> [[2011 USAMO Problems/Problem 5|Solution]]<br /> <br /> ==Problem 6==<br /> Let &lt;math&gt;A&lt;/math&gt; be a set with &lt;math&gt;|A| = 225&lt;/math&gt;, meaning that &lt;math&gt;A&lt;/math&gt; has 225 elements. Suppose further that there are eleven subsets &lt;math&gt;A_1&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;A_{11}&lt;/math&gt; of &lt;math&gt;A&lt;/math&gt; such that &lt;math&gt;|A_i | = 45&lt;/math&gt; for &lt;math&gt;1 \le i \le 11&lt;/math&gt; and &lt;math&gt;|A_i \cap A_j| = 9&lt;/math&gt; for &lt;math&gt;1 \le i &lt; j \le 11&lt;/math&gt;. Prove that &lt;math&gt;|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165&lt;/math&gt;, and give an example for which equality holds.<br /> <br /> [[2011 USAMO Problems/Problem 6|Solution]]<br /> <br /> = See also =<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year= 2011|before=[[2010 USAMO]]|after=[[2012 USAMO]]}}</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_2&diff=38271 2011 USAMO Problems/Problem 2 2011-04-29T15:09:38Z <p>Aopsvd: Created page with '==Problem== An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an intege…'</p> <hr /> <div>==Problem==<br /> An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer &lt;math&gt;m&lt;/math&gt; from each of the integers at two neighboring vertices and adding &lt;math&gt;2m&lt;/math&gt; to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount &lt;math&gt;m&lt;/math&gt; and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_1&diff=38270 2011 USAMO Problems/Problem 1 2011-04-29T15:06:29Z <p>Aopsvd: Solution by change of variables and AM-GM</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, &lt;math&gt;c&lt;/math&gt; be positive real numbers such that &lt;math&gt;a^2 + b^2 + c^2 + (a + b + c)^2 \le 4&lt;/math&gt;. Prove that<br /> &lt;cmath&gt;\frac{ab + 1}{(a + b)^2} + \frac{bc + 1}{(b + c)^2} + \frac{ca + 1}{(c + a)^2} \ge 3.&lt;/cmath&gt;<br /> <br /> ==Solution==<br /> Since<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> (a+b)^2 + (b+c)^2 + (c+a)^2 &amp;= 2(a^2 + b^2 + c^2 + ab + bc + ca) \\<br /> &amp;= a^2 + b^2 + c^2 + (a + b + c)^2,<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> it is natural to consider a change of variables:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> \alpha &amp;= b + c \\<br /> \beta &amp;= c + a \\<br /> \gamma &amp;= a + b<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> with the inverse mapping given by:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> a &amp;= \frac{\beta + \gamma - \alpha}2 \\<br /> b &amp;= \frac{\alpha + \gamma - \beta}2 \\<br /> c &amp;= \frac{\alpha + \beta - \gamma}2<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> With this change of variables, the constraint becomes<br /> &lt;cmath&gt;<br /> \alpha^2 + \beta^2 + \gamma^2 \le 4,<br /> &lt;/cmath&gt;<br /> while the left side of the inequality we need to prove is now<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> &amp; \frac{\gamma^2 - (\alpha - \beta)^2 + 4}{4\gamma^2} +<br /> \frac{\alpha^2 - (\beta - \gamma)^2 + 4}{4\alpha^2} +<br /> \frac{\beta^2 - (\gamma - \alpha)^2 + 4}{4\beta^2} \ge \\ &amp;<br /> \frac{\gamma^2 - (\alpha - \beta)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\gamma^2} +<br /> \frac{\alpha^2 - (\beta - \gamma)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\alpha^2} +<br /> \frac{\beta^2 - (\gamma - \alpha)^2 + \alpha^2 + \beta^2 + \gamma^2}{4\beta^2} = \\ &amp;<br /> \frac{2\gamma^2 + 2\alpha\beta}{4\gamma^2} +<br /> \frac{2\alpha^2 + 2\beta\gamma}{4\alpha^2} +<br /> \frac{2\beta^2 + 2\gamma\alpha}{4\beta^2} = \\ &amp;<br /> \frac32 + \frac{\alpha\beta}{2\gamma^2} +<br /> \frac{\beta\gamma}{2\alpha^2} +<br /> \frac{\gamma\alpha}{2\beta^2}.<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> <br /> Therefore it remains to prove that<br /> &lt;cmath&gt;<br /> \frac{\alpha\beta}{2\gamma^2} +<br /> \frac{\beta\gamma}{2\alpha^2} +<br /> \frac{\gamma\alpha}{2\beta^2} \ge \frac32.<br /> &lt;/cmath&gt;<br /> <br /> We note that the product of the three (positive) terms is 1/8, therefore by AM-GM their mean is at least 1/2, and thus their sum is at least 3/2 and we are done.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_2&diff=38040 2011 AIME II Problems/Problem 2 2011-04-03T05:05:16Z <p>Aopsvd: </p> <hr /> <div>== Problem 2 ==<br /> On square ABCD, point E lies on side AD and point F lies on side BC, so that BE=EF=FD=30. Find the area of the square ABCD.<br /> <br /> == Solution ==<br /> Drawing the square and examining the given lengths,<br /> &lt;asy&gt;<br /> size(2inch, 2inch);<br /> currentpen = fontsize(8pt);<br /> pair A = (0, 0); dot(A); label(&quot;$A$&quot;, A, plain.SW);<br /> pair B = (3, 0); dot(B); label(&quot;$B$&quot;, B, plain.SE);<br /> pair C = (3, 3); dot(C); label(&quot;$C$&quot;, C, plain.NE);<br /> pair D = (0, 3); dot(D); label(&quot;$D$&quot;, D, plain.NW);<br /> pair E = (0, 1); dot(E); label(&quot;$E$&quot;, E, plain.W);<br /> pair F = (3, 2); dot(F); label(&quot;$F$&quot;, F, plain.E);<br /> label(&quot;$\frac x3$&quot;, E--A);<br /> label(&quot;$\frac x3$&quot;, F--C);<br /> label(&quot;$x$&quot;, A--B);<br /> label(&quot;$x$&quot;, C--D);<br /> label(&quot;$\frac {2x}3$&quot;, B--F);<br /> label(&quot;$\frac {2x}3$&quot;, D--E);<br /> label(&quot;$30$&quot;, B--E);<br /> label(&quot;$30$&quot;, F--E);<br /> label(&quot;$30$&quot;, F--D);<br /> draw(B--C--D--F--E--B--A--D);<br /> &lt;/asy&gt;<br /> you find that the three segments cut the square into three equal horizontal sections. Therefore, (&lt;math&gt;x&lt;/math&gt; being the side length), &lt;math&gt;\sqrt{x^2+(x/3)^2}=30&lt;/math&gt;, or &lt;math&gt;x^2+(x/3)^2=900&lt;/math&gt;. Solving for &lt;math&gt;x&lt;/math&gt;, we get &lt;math&gt;x=9\sqrt{10}&lt;/math&gt;, and &lt;math&gt;x^2=810.&lt;/math&gt;<br /> <br /> Area of the square is &lt;math&gt;\fbox{810.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38035 2011 AIME II Problems/Problem 9 2011-04-02T19:42:26Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem 9==<br /> Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Note that neither the constraint nor the expression we need to maximize involves products &lt;math&gt;x_i x_j&lt;/math&gt; with &lt;math&gt;i - j \equiv 3 \pmod 6&lt;/math&gt;. Factoring out say &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_4&lt;/math&gt; we see that the constraint is &lt;math&gt;x_1(x_3x_5) + x_4(x_2x_6) \ge {\scriptstyle\frac1{540}}&lt;/math&gt;, while the expression we want to maximize is &lt;math&gt;x_1(x_2x_3 + x_5x_6 + x_6x_2) + x_4(x_2x_3 + x_5x_6 + x_3x_5)&lt;/math&gt;. Adding the left side of the constraint to the expression we get: &lt;math&gt;(x_1 + x_4)(x_2x_3 + x_5x_6 + x_6x_2 + x_3x_5) = (x_1 + x_4)(x_2 + x_5)(x_3 + x_6)&lt;/math&gt;. This new expression is the product of three non-negative terms whose sum is equal to 1. By AM-GM this product is at most &lt;math&gt;\scriptstyle\frac1{27}&lt;/math&gt;. Since we have added at least &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; the desired maximum is at most &lt;math&gt;\scriptstyle\frac1{27} - \frac1{540} = \frac{19}{540}&lt;/math&gt;. It is easy to see that this upper bound can in fact be achieved by ensuring that the constraint expression is equal to &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; with &lt;math&gt;x_1 + x_4 = x_2 + x_5 = x_3 + x_6 = \scriptstyle\frac13&lt;/math&gt;&amp;mdash;for example, by choosing &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_2&lt;/math&gt; small enough&amp;mdash;so our answer is &lt;math&gt;540 + 19 = \fbox{559}.&lt;/math&gt;<br /> <br /> An example is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> x_3 &amp;= x_6 = \frac16 \\<br /> x_1 &amp;= x_2 = \frac{5 - \sqrt{20}}{30} \\<br /> x_5 &amp;= x_4 = \frac{5 + \sqrt{20}}{30}<br /> \end{align*}<br /> &lt;/cmath&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_12&diff=38027 2011 AIME II Problems/Problem 12 2011-04-02T06:00:31Z <p>Aopsvd: </p> <hr /> <div>== Problem 12 ==<br /> Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m + n&lt;/math&gt;.<br /> <br /> == Solution ==<br /> <br /> Use complementary probability and PIE.<br /> <br /> If we consider the delegates from each country to be indistinguishable and number the chairs, we have &lt;cmath&gt;\frac{9!}{(3!)^3}&lt;/cmath&gt; total ways to seat the candidates. This comes to: &lt;cmath&gt;\frac{9\cdot8\cdot7\cdot6\cdot5\cdot4}{6\cdot6} = 6\cdot8\cdot7\cdot5 = 30\cdot56.&lt;/cmath&gt;<br /> <br /> Of these there are &lt;cmath&gt; 3 \times 9 \times \frac{6!}{(3!)^2} &lt;/cmath&gt; ways to have the candidates of at least some one country sit together. This comes to &lt;cmath&gt;\frac{27\cdot6\cdot5\cdot4}6 = 27\cdot 20.&lt;/cmath&gt;<br /> <br /> Among these there are &lt;cmath&gt; 3 \times 9 \times 4 &lt;/cmath&gt; ways for candidates from two countries to each sit together. This comes to &lt;cmath&gt; 27\cdot 4. &lt;/cmath&gt;<br /> <br /> Finally, there are &lt;cmath&gt; 9 \times 2 = 18.&lt;/cmath&gt; ways for the candidates from all the countries to sit in three blocks (9 clockwise arrangements, and 9 counter-clockwise arrangements).<br /> <br /> So, by PIE, the total count of unwanted arrangements is &lt;cmath&gt;27\cdot 20 - 27\cdot 4 + 18 = 16\cdot27 + 18 = 18\cdot25. &lt;/cmath&gt;<br /> <br /> So the fraction &lt;cmath&gt; \frac mn = \frac{30\cdot 56 - 18\cdot 25}{30\cdot 56} = \frac{56 - 15}{56} = \frac{41}{56}.&lt;/cmath&gt; Thus &lt;math&gt;m + n = 56 + 41 = \fbox{97.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_3&diff=38022 2011 AIME II Problems/Problem 3 2011-04-02T05:30:30Z <p>Aopsvd: </p> <hr /> <div>== Problem 3 ==<br /> The degree measures of the angles in a convex 18-sided polygon form an increasing arithmetic sequence with integer values. Find the degree measure of the smallest angle.<br /> <br /> == Solution ==<br /> The average angle in an 18-gon is &lt;math&gt;160^\circ&lt;/math&gt;. In an arithmetic sequence the average is the same as the median, so the middle two terms of the sequence average to &lt;math&gt;160^\circ&lt;/math&gt;. Thus for some positive (the sequence is increasing and thus non-constant) integer &lt;math&gt;d&lt;/math&gt;, the middle two terms are &lt;math&gt;(160-d)^\circ&lt;/math&gt; and &lt;math&gt;(160+d)^\circ&lt;/math&gt;. Since the step is &lt;math&gt;2d&lt;/math&gt; the last term of the sequence is &lt;math&gt;(160 + 17d)^\circ&lt;/math&gt;, which must be less than &lt;math&gt;180^\circ&lt;/math&gt;, since the polygon is convex. This gives &lt;math&gt;17d &lt; 20&lt;/math&gt;, so the only suitable positive integer &lt;math&gt;d&lt;/math&gt; is 1. The first term is then &lt;math&gt;(160-17)^\circ = \fbox{143^\circ.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_1&diff=38017 2011 AIME II Problems/Problem 1 2011-04-02T05:20:31Z <p>Aopsvd: </p> <hr /> <div>== Problem 1 ==<br /> Gary purchased a large beverage, but only drank ''m''/''n'' of it, where ''m'' and ''n'' are relatively prime positive integers. If he had purchased half as much and drunk twice as much, he would have wasted only 2/9 as much beverage. Find ''m''+''n''.<br /> <br /> == Solution ==<br /> Let &lt;math&gt;x&lt;/math&gt; be the fraction consumed, then &lt;math&gt;(1-x)&lt;/math&gt; is the fraction wasted. We have &lt;math&gt;1/2 - 2x = 2/9(1-x)&lt;/math&gt;, or &lt;math&gt;9 - 36x = 4 - 4x&lt;/math&gt;, or &lt;math&gt;32x = 5&lt;/math&gt; or &lt;math&gt;x = 5/32&lt;/math&gt;. Therefore, &lt;math&gt;m + n = 5 + 32 = \fbox{37.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_6&diff=38011 2011 AIME II Problems/Problem 6 2011-04-02T05:08:42Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem 6==<br /> <br /> Define an ordered quadruple &lt;math&gt;(a, b, c, d)&lt;/math&gt; as interesting if &lt;math&gt;1 \le a&lt;b&lt;c&lt;d \le 10&lt;/math&gt;, and &lt;math&gt;a+d&gt;b+c&lt;/math&gt;. How many ordered quadruples are there?<br /> <br /> ==Solution==<br /> Rearranging the inequality we get &lt;math&gt;d-c &gt; b-a&lt;/math&gt;. Let &lt;math&gt;e = 11&lt;/math&gt;, then &lt;math&gt;(a, b-a, c-b, d-c, e-d)&lt;/math&gt; is a partition of 11 into 5 positive integers or equivalently:<br /> &lt;math&gt;(a-1, b-a-1, c-b-1, d-c-1, e-d-1)&lt;/math&gt; is a partition of 6 into 5 non-negative integer parts. Via a standard balls and urns argument, the number of ways to partition 6 into 5 non-negative parts is &lt;math&gt;\binom{6+4}4 = \binom{10}4 = 210&lt;/math&gt;. The interesting quadruples correspond to partitions where the second number is less than the fourth. By symmetry there as many partitions where the fourth is less than the second. So, if &lt;math&gt;N&lt;/math&gt; is the number of partitions where the second element is equal to the fourth, our answer is &lt;math&gt;(210-N)/2&lt;/math&gt;.<br /> <br /> We find &lt;math&gt;N&lt;/math&gt; as a sum of 4 cases:<br /> * two parts equal to zero, &lt;math&gt;\binom82 = 28&lt;/math&gt; ways,<br /> * two parts equal to one, &lt;math&gt;\binom62 = 15&lt;/math&gt; ways,<br /> * two parts equal to two, &lt;math&gt;\binom42 = 6&lt;/math&gt; ways,<br /> * two parts equal to three, &lt;math&gt;\binom22 = 1&lt;/math&gt; way.<br /> Therefore, &lt;math&gt;N = 28 + 15 + 6 + 1 = 50&lt;/math&gt; and our answer is &lt;math&gt;(210 - 50)/2 = \fbox{80.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_6&diff=38009 2011 AIME II Problems/Problem 6 2011-04-02T05:05:25Z <p>Aopsvd: </p> <hr /> <div>==Problem 6==<br /> <br /> Define an ordered quadruple &lt;math&gt;(a, b, c, d)&lt;/math&gt; as interesting if &lt;math&gt;1 \le a&lt;b&lt;c&lt;d \le 10&lt;/math&gt;, and &lt;math&gt;a+d&gt;b+c&lt;/math&gt;. How many ordered quadruples are there?<br /> <br /> ==Solution==<br /> Rearranging the inequality we get &lt;math&gt;d-c &gt; b-a&lt;/math&gt;. Let &lt;math&gt;e = 11&lt;/math&gt;, then &lt;math&gt;(a, b-a, c-b, d-c, e-d)&lt;/math&gt; is a partition of 11 into 5 positive integers or equivalently:<br /> &lt;math&gt;(a-1, b-a-1, c-b-1, d-c-1, e-d-1)&lt;/math&gt; is a partition of 6 into 5 non-negative integers. The number of ways to partition 6 into 5 non-negative parts is (bals and urns) &lt;math&gt;\binom{6+4}4 = \binom{10}4 = 210&lt;/math&gt;. The interesting quadruples correspond to partitions where the second number is less than the fourth. By symmetry there as many partitions where the fourth is less than the second. So, if &lt;math&gt;N&lt;/math&gt; is the number of partitions where the second element is equal to the fourth, our answer is &lt;math&gt;(210-N)/2&lt;/math&gt;.<br /> <br /> We find &lt;math&gt;N&lt;/math&gt; as a sum of 4 cases:<br /> * two parts equal to zero, &lt;math&gt;\binom82 = 28&lt;/math&gt; ways,<br /> * two parts equal to one, &lt;math&gt;\binom62 = 15&lt;/math&gt; ways,<br /> * two parts equal to two, &lt;math&gt;\binom42 = 6&lt;/math&gt; ways,<br /> * two parts equal to three, &lt;math&gt;\binom22 = 1&lt;/math&gt; way.<br /> Therefore, &lt;math&gt;N = 28 + 15 + 6 + 1 = 50&lt;/math&gt; and our answer is &lt;math&gt;(210 - 50)/2 = \fbox{80.}&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38008 2011 AIME II Problems/Problem 9 2011-04-02T04:41:56Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem 9==<br /> Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Note that neither the constraint nor the expression we need to maximize involves products &lt;math&gt;x_i x_j&lt;/math&gt; with &lt;math&gt;i - j \equiv 3 \pmod 6&lt;/math&gt;. Factoring out say &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_4&lt;/math&gt; we see that the constraint is &lt;math&gt;x_1(x_3x_5) + x_4(x_2x_6) \ge {\scriptstyle\frac1{540}}&lt;/math&gt;, while the expression we want to maximize is &lt;math&gt;x_1(x_2x_3 + x_5x_6 + x_6x_2) + x_4(x_2x_3 + x_5x_6 + x_3x_5)&lt;/math&gt;. Adding the left side of the constraint to the expression we get: &lt;math&gt;(x_1 + x_4)(x_2x_3 + x_5x_6 + x_6x_2 + x_3x_5) = (x_1 + x_4)(x_2 + x_5)(x_3 + x_6)&lt;/math&gt;. This new expression is the product of three non-negative terms whose sum is equal to 1. By AM-GM this product is at most &lt;math&gt;\scriptstyle\frac1{27}&lt;/math&gt;. Since we have added at least &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; the desired maximum is at most &lt;math&gt;\scriptstyle\frac1{27} - \frac1{540} = \frac{19}{540}&lt;/math&gt;. It is easy to see that this upper bound can in fact be achieved by ensuring that constraint expression is equal to &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; with &lt;math&gt;x_1 + x_4 = x_2 + x_5 = x_3 + x_6 = \scriptstyle\frac13&lt;/math&gt;&amp;mdash;for example, by choosing &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_2&lt;/math&gt; small enough&amp;mdash;so our answer is &lt;math&gt;540 + 19 = \fbox{559}.&lt;/math&gt;<br /> <br /> An example is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> x_3 &amp;= x_6 = \frac16 \\<br /> x_1 &amp;= x_2 = \frac{5 - \sqrt{20}}{30} \\<br /> x_5 &amp;= x_4 = \frac{5 + \sqrt{20}}{30}<br /> \end{align*}<br /> &lt;/cmath&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38007 2011 AIME II Problems/Problem 9 2011-04-02T04:38:35Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem 9==<br /> Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Note that neither the constraint nor the expression we need to maximize involves products &lt;math&gt;x_i x_j&lt;/math&gt; with &lt;math&gt;i - j \equiv 3 \pmod 6&lt;/math&gt;. Factoring out say &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_4&lt;/math&gt; we see that the constraint is &lt;math&gt;x_1(x_3x_5) + x_4(x_2x_6) \ge {\scriptstyle\frac1{540}}&lt;/math&gt;, while the expression we want to maximize is &lt;math&gt;x_1(x_2x_3 + x_5x_6 + x_6x_2) + x_4(x_2x_3 + x_5x_6 + x_3x_5)&lt;/math&gt;. Adding the left side of the constraint to the expression we get: &lt;math&gt;(x_1 + x_4)(x_2x_3 + x_5x_6 + x_6x_2 + x_3x_5) = (x_1 + x_4)(x_2 + x_5)(x_3 + x_6)&lt;/math&gt;. This new expression is the product of three non-negative terms whose sum is equal to 1. By AM-GM this product is at most &lt;math&gt;\scriptstyle\frac1{27}&lt;/math&gt;. Since we have added at least &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; the desired maximum is at most &lt;math&gt;\scriptstyle\frac1{27} - \frac1{540} = \frac{19}{540}&lt;/math&gt;. It is easy to see that this upper bound can in fact be achieved by ensuring that constraint expression is equal to &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; with &lt;math&gt;x_1 + x_4 = x_2 + x_5 = x_3 + x_6 = \scriptstyle\frac13&lt;/math&gt;&amp;mdash;for example, by choosing &lt;math&gt;x_1&lt;/math&gt; and &lt;math&gt;x_2&lt;/math&gt; small enough&amp;mdash;so our answer is &lt;math&gt;540 + 19 = \fbox{559}.&lt;/math&gt;<br /> <br /> An example is:<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> x_3 &amp;= x_6 = \frac16 \\<br /> x_1 &amp;= x_2 = \frac{15 - \sqrt{220}}{30} \\<br /> x_5 &amp;= x_4 = \frac{15 + \sqrt{220}}{30}<br /> \end{align*}<br /> &lt;/cmath&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38006 2011 AIME II Problems/Problem 9 2011-04-02T03:42:33Z <p>Aopsvd: </p> <hr /> <div>==Problem 9==<br /> Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> ==Solution==<br /> Note that none of the expressions involve products &lt;math&gt;x_i x_j&lt;/math&gt; with &lt;math&gt;i - j \equiv 3 \pmod 6&lt;/math&gt;. The constraint is &lt;math&gt;x_1(x_3x_5) + x_4(x_2x_6) \ge {\scriptstyle\frac1{540}}&lt;/math&gt;, while the expression we want to maximize is &lt;math&gt;x_1(x_2x_3 + x_5x_6 + x_6x_2) + x_4(x_2x_3 + x_5x_6 + x_3x_5)&lt;/math&gt;. Adding the left side of the constraint to the expression we get: &lt;math&gt;(x_1 + x_4)(x_2x_3 + x_5x_6 + x_6x_2 + x_3x_5) = (x_1 + x_4)(x_2 + x_5)(x_3 + x_6)&lt;/math&gt;. This new expression is the product of three non-negative terms whose sum is equal to 1. By AM-GM this product is at most &lt;math&gt;\scriptstyle\frac1{27}&lt;/math&gt;. Since we have added at least &lt;math&gt;\scriptstyle\frac1{540}&lt;/math&gt; the desired maximum is at most &lt;math&gt;\scriptstyle\frac1{27} - \frac1{540} = \frac{19}{540}&lt;/math&gt;. It is easy to see that the maximum can in fact be achieved, so our answer is &lt;math&gt;540 + 19 = \fbox{559}.&lt;/math&gt;</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38003 2011 AIME II Problems/Problem 9 2011-04-01T21:47:15Z <p>Aopsvd: </p> <hr /> <div>Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems&diff=38002 2011 AIME II Problems 2011-04-01T21:46:45Z <p>Aopsvd: /* Problem 9 */</p> <hr /> <div>{{AIME Problems|year=2011|n=II}}<br /> <br /> == Problem 1 ==<br /> Gary purchased a large bevarage, but only drank ''m''/''n'' of it, where ''m'' and ''n'' are relatively prime positive integers. If he had purchased half as much and drank twice as much, he would have wasted only 2/9 as much bevarage. Find ''m''+''n''.<br /> <br /> [[2011 AIME II Problems/Problem 1|Solution]]<br /> <br /> == Problem 2 ==<br /> On square ABCD, point E lies on side AD and point F lies on side BC, so that BE=EF=FD=30. Find the area of the square ABCD.<br /> <br /> [[2011 AIME II Problems/Problem 2|Solution]]<br /> <br /> == Problem 3 ==<br /> The degree measures of the angles in a convex 18-sided polygon form an increasing arithmetic sequence with integer values. Find the degree measure of the smallest angle.<br /> <br /> [[2011 AIME II Problems/Problem 3|Solution]]<br /> <br /> == Problem 4 ==<br /> In triangle ABC, AB=(20/11)AC. The angle bisector of angle A intersects BC at point D, and point M is the midpoint of AD. Let P be the point of intersection of AC and the line BM. The ratio of CP to PA can be expresses in the form m/n, where m and n are relatively prime positive integers. Find m+n. <br /> <br /> [[2011 AIME II Problems/Problem 4|Solution]]<br /> <br /> == Problem 5 ==<br /> The sum of the first 2011 terms of a geometric sequence is 200. The sum of the first 4022 terms is 380. Find the sum of the first 6033 terms. <br /> <br /> [[2011 AIME II Problems/Problem 5|Solution]]<br /> <br /> == Problem 6 ==<br /> Define an ordered quadruple (a, b, c, d) as interesting if &lt;math&gt;1 \le a&lt;b&lt;c&lt;d \le 10&lt;/math&gt;, and a+d&gt;b+c. How many interesting ordered quadruples are there?<br /> <br /> [[2011 AIME II Problems/Problem 6|Solution]]<br /> <br /> == Problem 7 ==<br /> Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let &lt;math&gt;m&lt;/math&gt; be the maximum number of red marbles for which such an arrangement is possible, and let &lt;math&gt;N&lt;/math&gt; be the number of ways he can arrange the &lt;math&gt;m+5&lt;/math&gt; marbles to satisfy the requirement. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by &lt;math&gt;1000&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 7|Solution]]<br /> <br /> == Problem 8 ==<br /> Let &lt;math&gt;z_1&lt;/math&gt;, &lt;math&gt;z_2&lt;/math&gt;, &lt;math&gt;z_3&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;z_{12}&lt;/math&gt; be the 12 zeroes of the polynomial &lt;math&gt;z^{12} - 2^{36}&lt;/math&gt;. For each &lt;math&gt;j&lt;/math&gt;, let &lt;math&gt;w_j&lt;/math&gt; be one of &lt;math&gt;z_j&lt;/math&gt; or &lt;math&gt;iz_j&lt;/math&gt;. Then the maximum possible value of the real part of &lt;math&gt;\sum_{j = 1}^{12} w_j&lt;/math&gt; can be written as &lt;math&gt;m + \sqrt{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are positive integers. Find &lt;math&gt;m + n&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 8|Solution]]<br /> <br /> == Problem 9 ==<br /> Let &lt;math&gt;x_1&lt;/math&gt;, &lt;math&gt;x_2&lt;/math&gt;, &lt;math&gt;\dots&lt;/math&gt;, &lt;math&gt;x_6&lt;/math&gt; be nonnegative real numbers such that &lt;math&gt;x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 1&lt;/math&gt;, and &lt;math&gt;x_1x_3x_5 + x_2x_4x_6 \ge {\scriptstyle\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of &lt;math&gt;x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_6 + x_5x_6x_1 + x_6x_1x_2&lt;/math&gt;. Find &lt;math&gt;p + q&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 9|Solution]]<br /> <br /> == Problem 10 ==<br /> A circle with center &lt;math&gt;O&lt;/math&gt; has radius 25. Chord &lt;math&gt;\overline{AB}&lt;/math&gt; of length 30 and chord &lt;math&gt;\overline{CD}&lt;/math&gt; of length 14 intersect at point &lt;math&gt;P&lt;/math&gt;. The distance between the midpoints of the two chords is 12. The quantity &lt;math&gt;OP^2&lt;/math&gt; can be represented as &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find the remainder when &lt;math&gt;m + n&lt;/math&gt; is divided by 1000.<br /> <br /> [[2011 AIME II Problems/Problem 10|Solution]]<br /> <br /> == Problem 11 ==<br /> Let &lt;math&gt;M_n&lt;/math&gt; be the &lt;math&gt;n \times n&lt;/math&gt; matrix with entries as follows: for &lt;math&gt;1 \le i \le n&lt;/math&gt;, &lt;math&gt;m_{i,i} = 10&lt;/math&gt;; for &lt;math&gt;1 \le i \le n - 1&lt;/math&gt;, &lt;math&gt;m_{i+1,i} = m_{i,i+1} = 3&lt;/math&gt;; all other entries in &lt;math&gt;M_n&lt;/math&gt; are zero. Let &lt;math&gt;D_n&lt;/math&gt; be the determinant of matrix &lt;math&gt;M_n&lt;/math&gt;. Then &lt;math&gt;\sum_{n=1}^{\infty} \frac{1}{8D_n+1}&lt;/math&gt; can be represented as &lt;math&gt;\frac{p}{q}&lt;/math&gt;, where &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;p + q&lt;/math&gt;.<br /> Note: The determinant of the &lt;math&gt;1 \times 1&lt;/math&gt; matrix &lt;math&gt;[a]&lt;/math&gt; is &lt;math&gt;a&lt;/math&gt;, and the determinant of the &lt;math&gt;2 \times 2&lt;/math&gt; matrix &lt;math&gt;\left[ {\begin{array}{cc}<br /> a &amp; b \\<br /> c &amp; d \\<br /> \end{array} } \right] = ad - bc&lt;/math&gt;; for &lt;math&gt;n \ge 2&lt;/math&gt;, the determinant of an &lt;math&gt;n \times n&lt;/math&gt; matrix with first row or first column &lt;math&gt;a_1&lt;/math&gt; &lt;math&gt;a_2&lt;/math&gt; &lt;math&gt;a_3&lt;/math&gt; &lt;math&gt;\dots&lt;/math&gt; &lt;math&gt;a_n&lt;/math&gt; is equal to &lt;math&gt;a_1C_1 - a_2C_2 + a_3C_3 - \dots + (-1)^{n+1}a_nC_n&lt;/math&gt;, where &lt;math&gt;C_i&lt;/math&gt; is the determinant of the &lt;math&gt;(n - 1) \times (n - 1)&lt;/math&gt; matrix formed by eliminating the row and column containing &lt;math&gt;a_i&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 11|Solution]]<br /> <br /> == Problem 12 ==<br /> Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be &lt;math&gt;\frac{m}{n}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m + n&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 12|Solution]]<br /> <br /> == Problem 13 ==<br /> Point &lt;math&gt;P&lt;/math&gt; lies on the diagonal &lt;math&gt;AC&lt;/math&gt; of square &lt;math&gt;ABCD&lt;/math&gt; with &lt;math&gt;AP \gt CP&lt;/math&gt;. Let &lt;math&gt;O_1&lt;/math&gt; and &lt;math&gt;O_2&lt;/math&gt; be the circumcenters of triangles &lt;math&gt;ABP&lt;/math&gt; and &lt;math&gt;CDP&lt;/math&gt;, respectively. Given that &lt;math&gt;AB = 12&lt;/math&gt; and &lt;math&gt;\angle O_1PO_2 = 120\textdegree&lt;/math&gt;, then &lt;math&gt;AP = \sqrt{a} + \sqrt{b}&lt;/math&gt;, where &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are positive integers. Find &lt;math&gt;a + b&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 13|Solution]]<br /> <br /> == Problem 14 ==<br /> There are &lt;math&gt;N&lt;/math&gt; permutations &lt;math&gt;(a_1, a_2, \dots, a_{30})&lt;/math&gt; of &lt;math&gt;1, 2, \dots, 30&lt;/math&gt; such that for &lt;math&gt;m \in \{2,3,5\}&lt;/math&gt;, &lt;math&gt;m&lt;/math&gt; divides &lt;math&gt;a_{n+m} - a_n&lt;/math&gt; for all integers &lt;math&gt;n&lt;/math&gt; with &lt;math&gt;1 \le n &lt; n+m \le 30&lt;/math&gt;. Find the remainder when &lt;math&gt;N&lt;/math&gt; is divided by 1000.<br /> <br /> [[2011 AIME II Problems/Problem 14|Solution]]<br /> <br /> == Problem 15 ==<br /> Let &lt;math&gt;P(x) = x^2 - 3x - 9&lt;/math&gt;. A real number &lt;math&gt;x&lt;/math&gt; is chosen at random from the interval &lt;math&gt;5 \le x \le 15&lt;/math&gt;. The probability that &lt;math&gt;\lfloor\sqrt{P(x)}\rfloor = \sqrt{P(\lfloor x \rfloor)}&lt;/math&gt; is equal to &lt;math&gt;\frac{\sqrt{a} + \sqrt{b} + \sqrt{c} - d}{e}&lt;/math&gt; , where &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;, and &lt;math&gt;e&lt;/math&gt; are positive integers, and none of &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, or &lt;math&gt;c&lt;/math&gt; is divisible by the square of a prime. Find &lt;math&gt;a + b + c + d + e&lt;/math&gt;.<br /> <br /> [[2011 AIME II Problems/Problem 15|Solution]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_9&diff=38001 2011 AIME II Problems/Problem 9 2011-04-01T21:45:13Z <p>Aopsvd: </p> <hr /> <div>Let &lt;math&gt;x_1, x_2, ... , x_6&lt;/math&gt; be non-negative real numbers such that &lt;math&gt;x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1&lt;/math&gt;, and &lt;math&gt;x_1 x_3 x_5 +x_2 x_4 x_6 \ge \scriptstyle{\frac{1}{540}}&lt;/math&gt;. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be positive relatively prime integers such that &lt;math&gt;\frac{p}{q}&lt;/math&gt; is the maximum possible value of<br /> &lt;math&gt;x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2&lt;/math&gt;. Find &lt;math&gt;p+q&lt;/math&gt;.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1983_AIME_Problems/Problem_11&diff=37788 1983 AIME Problems/Problem 11 2011-03-26T21:03:35Z <p>Aopsvd: /* Solution 1 */</p> <hr /> <div>== Problem ==<br /> The solid shown has a [[square]] base of side length &lt;math&gt;s&lt;/math&gt;. The upper edge is [[parallel]] to the base and has length &lt;math&gt;2s&lt;/math&gt;. All other edges have length &lt;math&gt;s&lt;/math&gt;. Given that &lt;math&gt;s=6\sqrt{2}&lt;/math&gt;, what is the volume of the solid?<br /> &lt;center&gt;&lt;asy&gt;<br /> size(180);<br /> import three; pathpen = black+linewidth(0.65); pointpen = black;<br /> currentprojection = perspective(30,-20,10);<br /> real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> draw(A--B--C--D--A--E--D);<br /> draw(B--F--C);<br /> draw(E--F);<br /> label(&quot;A&quot;,A);<br /> label(&quot;B&quot;,B);<br /> label(&quot;C&quot;,C);<br /> label(&quot;D&quot;,D);<br /> label(&quot;E&quot;,E,N);<br /> label(&quot;F&quot;,F,N);<br /> &lt;/asy&gt;&lt;/center&gt; &lt;!-- Asymptote replacement for Image:1983Number11.JPG by bpms --&gt;<br /> <br /> == Solution 1 ==<br /> First, we find the height of the figure by drawing a [[perpendicular]] from the midpoint of &lt;math&gt;AD&lt;/math&gt; to &lt;math&gt;EF&lt;/math&gt;. The [[hypotenuse]] of the triangle is the [[median]] of [[equilateral triangle]] &lt;math&gt;ADE&lt;/math&gt; one of the legs is &lt;math&gt;3\sqrt{2}&lt;/math&gt;. We apply the [[Pythagorean Theorem]] to find that the height is equal to &lt;math&gt;6&lt;/math&gt;.<br /> &lt;center&gt;&lt;asy&gt;<br /> size(180);<br /> import three; pathpen = black+linewidth(0.65); pointpen = black; pen d = linewidth(0.65); pen l = linewidth(0.5);<br /> currentprojection = perspective(30,-20,10);<br /> real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> triple Aa=(E.x,0,0),Ba=(F.x,0,0),Ca=(F.x,s,0),Da=(E.x,s,0);<br /> draw(A--B--C--D--A--E--D);<br /> draw(B--F--C);<br /> draw(E--F); <br /> draw(B--Ba--Ca--C,dashed+d);<br /> draw(A--Aa--Da--D,dashed+d);<br /> draw(E--(E.x,E.y,0),dashed+l);<br /> draw(F--(F.x,F.y,0),dashed+l);<br /> draw(Aa--E--Da,dashed+d);<br /> draw(Ba--F--Ca,dashed+d);<br /> label(&quot;A&quot;,A);<br /> label(&quot;B&quot;,B);<br /> label(&quot;C&quot;,C);<br /> label(&quot;D&quot;,D);<br /> label(&quot;E&quot;,E,N);<br /> label(&quot;F&quot;,F,N);<br /> label(&quot;$12\sqrt{2}$&quot;,(E+F)/2,N);<br /> label(&quot;$6\sqrt{2}$&quot;,(A+B)/2);<br /> label(&quot;6&quot;,(3*s/2,s/2,3),ENE);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> Next, we complete the figure into a triangular prism, and find the area, which is &lt;math&gt;\frac{6\sqrt{2}\cdot 12\sqrt{2}\cdot 6}{2}=432&lt;/math&gt;.<br /> <br /> Now, we subtract off the two extra [[pyramid]]s that we included, whose combined area is &lt;math&gt;2\cdot \left( \frac{6\sqrt{2}\cdot 3\sqrt{2} \cdot 6}{3} \right)=144&lt;/math&gt;.<br /> <br /> Thus, our answer is &lt;math&gt;432-144=\boxed{288}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> Extend &lt;math&gt;EA&lt;/math&gt; and &lt;math&gt;FB&lt;/math&gt; to meet at &lt;math&gt;G&lt;/math&gt;, and &lt;math&gt;ED&lt;/math&gt; and &lt;math&gt;FC&lt;/math&gt; to meet at &lt;math&gt;H&lt;/math&gt;. now, we have a regular tetrahedron &lt;math&gt;EFGH&lt;/math&gt;, which has twice the volume of our original solid. This tetrahedron has side length &lt;math&gt;2s = 12\sqrt{2}&lt;/math&gt;. Using the formula for the volume of a regular tetrahedron, which is &lt;math&gt;V = \frac{\sqrt{2}S^3}{12}&lt;/math&gt;, where S is the side length of the tetrahedron, the volume of our original solid is:<br /> <br /> &lt;math&gt;V = \frac{1}{2} \cdot \frac{\sqrt{2} \cdot (12\sqrt{2})^3}{12} = \boxed{288}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=1983|num-b=10|num-a=12}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1983_AIME_Problems/Problem_11&diff=37787 1983 AIME Problems/Problem 11 2011-03-26T20:59:49Z <p>Aopsvd: /* Problem */</p> <hr /> <div>== Problem ==<br /> The solid shown has a [[square]] base of side length &lt;math&gt;s&lt;/math&gt;. The upper edge is [[parallel]] to the base and has length &lt;math&gt;2s&lt;/math&gt;. All other edges have length &lt;math&gt;s&lt;/math&gt;. Given that &lt;math&gt;s=6\sqrt{2}&lt;/math&gt;, what is the volume of the solid?<br /> &lt;center&gt;&lt;asy&gt;<br /> size(180);<br /> import three; pathpen = black+linewidth(0.65); pointpen = black;<br /> currentprojection = perspective(30,-20,10);<br /> real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> draw(A--B--C--D--A--E--D);<br /> draw(B--F--C);<br /> draw(E--F);<br /> label(&quot;A&quot;,A);<br /> label(&quot;B&quot;,B);<br /> label(&quot;C&quot;,C);<br /> label(&quot;D&quot;,D);<br /> label(&quot;E&quot;,E,N);<br /> label(&quot;F&quot;,F,N);<br /> &lt;/asy&gt;&lt;/center&gt; &lt;!-- Asymptote replacement for Image:1983Number11.JPG by bpms --&gt;<br /> <br /> == Solution 1 ==<br /> First, we find the height of the figure by drawing a [[perpendicular]] from the midpoint of &lt;math&gt;AD&lt;/math&gt; to &lt;math&gt;EF&lt;/math&gt;. The [[hypotenuse]] of the triangle is the [[median]] of [[equilateral triangle]] &lt;math&gt;ADE&lt;/math&gt; one of the legs is &lt;math&gt;3\sqrt{2}&lt;/math&gt;. We apply the [[Pythagorean Theorem]] to find that the height is equal to &lt;math&gt;6&lt;/math&gt;.<br /> &lt;center&gt;&lt;asy&gt;<br /> size(180);<br /> import three; pathpen = black+linewidth(0.65); pointpen = black; pen d = linewidth(0.65); pen l = linewidth(0.5);<br /> currentprojection = perspective(30,-20,10);<br /> real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> triple Aa=(E.x,0,0),Ba=(F.x,0,0),Ca=(F.x,s,0),Da=(E.x,s,0);<br /> D(A--B--C--D--A--E--D); D(B--F--C); D(E--F); <br /> D(B--Ba--Ca--C,dashed+d);D(A--Aa--Da--D,dashed+d);D(E--(E.x,E.y,0),dashed+l);D(F--(F.x,F.y,0),dashed+l);<br /> D(Aa--E--Da,dashed+d); D(Ba--F--Ca,dashed+d);<br /> MP(&quot;A&quot;,A);MP(&quot;B&quot;,B);MP(&quot;C&quot;,C);MP(&quot;D&quot;,D);MP(&quot;E&quot;,E,N);MP(&quot;F&quot;,F,N);MP(&quot;12\sqrt{2}&quot;,(E+F)/2,N);MP(&quot;6\sqrt{2}&quot;,(A+B)/2);MP(&quot;6&quot;,(3*s/2,s/2,3),ENE);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> Next, we complete the figure into a triangular prism, and find the area, which is &lt;math&gt;\frac{6\sqrt{2}\cdot 12\sqrt{2}\cdot 6}{2}=432&lt;/math&gt;.<br /> <br /> Now, we subtract off the two extra [[pyramid]]s that we included, whose combined area is &lt;math&gt;2\cdot \left( \frac{6\sqrt{2}\cdot 3\sqrt{2} \cdot 6}{3} \right)=144&lt;/math&gt;.<br /> <br /> Thus, our answer is &lt;math&gt;432-144=\boxed{288}&lt;/math&gt;.<br /> <br /> == Solution 2 ==<br /> Extend &lt;math&gt;EA&lt;/math&gt; and &lt;math&gt;FB&lt;/math&gt; to meet at &lt;math&gt;G&lt;/math&gt;, and &lt;math&gt;ED&lt;/math&gt; and &lt;math&gt;FC&lt;/math&gt; to meet at &lt;math&gt;H&lt;/math&gt;. now, we have a regular tetrahedron &lt;math&gt;EFGH&lt;/math&gt;, which has twice the volume of our original solid. This tetrahedron has side length &lt;math&gt;2s = 12\sqrt{2}&lt;/math&gt;. Using the formula for the volume of a regular tetrahedron, which is &lt;math&gt;V = \frac{\sqrt{2}S^3}{12}&lt;/math&gt;, where S is the side length of the tetrahedron, the volume of our original solid is:<br /> <br /> &lt;math&gt;V = \frac{1}{2} \cdot \frac{\sqrt{2} \cdot (12\sqrt{2})^3}{12} = \boxed{288}&lt;/math&gt;<br /> <br /> == See also ==<br /> {{AIME box|year=1983|num-b=10|num-a=12}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=1983_AIME_Problems&diff=37781 1983 AIME Problems 2011-03-26T20:44:53Z <p>Aopsvd: Asy now compiles and gives sensible output</p> <hr /> <div>{{AIME Problems|year=1983}}<br /> <br /> == Problem 1 ==<br /> Let &lt;math&gt;x&lt;/math&gt;,&lt;math&gt;y&lt;/math&gt;, and &lt;math&gt;z&lt;/math&gt; all exceed &lt;math&gt;1&lt;/math&gt;, and let &lt;math&gt;w&lt;/math&gt; be a positive number such that &lt;math&gt;\log_xw=24&lt;/math&gt;, &lt;math&gt;\log_y w = 40&lt;/math&gt;, and &lt;math&gt;\log_{xyz}w=12&lt;/math&gt;. Find &lt;math&gt;\log_zw&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 1|Solution]]<br /> <br /> == Problem 2 ==<br /> Let &lt;math&gt;f(x)=|x-p|+|x-15|+|x-p-15|&lt;/math&gt;, where &lt;math&gt;p \leq x \leq 15&lt;/math&gt;. Determine the minimum value taken by &lt;math&gt;f(x)&lt;/math&gt; by &lt;math&gt;x&lt;/math&gt; in the interval &lt;math&gt;0 &lt; x \leq 15&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 2|Solution]]<br /> <br /> == Problem 3 ==<br /> What is the product of the real roots of the equation &lt;math&gt;x^2 + 18x + 30 = 2 \sqrt{x^2 + 18x + 45}&lt;/math&gt;?<br /> <br /> [[1983 AIME Problems/Problem 3|Solution]]<br /> <br /> == Problem 4 ==<br /> A machine shop cutting tool is in the shape of a notched circle, as shown. The radius of the circle is &lt;math&gt;\sqrt{50}&lt;/math&gt; cm, the length of &lt;math&gt;AB&lt;/math&gt; is 6 cm, and that of &lt;math&gt;BC&lt;/math&gt; is 2 cm. The angle &lt;math&gt;ABC&lt;/math&gt; is a right angle. Find the square of the distance (in centimeters) from &lt;math&gt;B&lt;/math&gt; to the center of the circle.<br /> <br /> &lt;asy&gt;<br /> size(150); defaultpen(linewidth(0.65)+fontsize(11));<br /> real r=10;<br /> pair O=(0,0),A=r*dir(45),B=(A.x,A.y-r),C;<br /> path P=circle(O,r);<br /> C=intersectionpoint(B--(B.x+r,B.y),P);<br /> draw(P);<br /> draw(C--B--O--A--B);<br /> dot(O); dot(A); dot(B); dot(C);<br /> label(&quot;$O$&quot;,O,SW);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,S);<br /> label(&quot;$C$&quot;,C,SE);<br /> &lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 4|Solution]]<br /> <br /> == Problem 5 ==<br /> Suppose that the sum of the squares of two complex numbers &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; is &lt;math&gt;7&lt;/math&gt; and the sum of the cubes is &lt;math&gt;10&lt;/math&gt;. What is the largest real value that &lt;math&gt;x + y&lt;/math&gt; can have?<br /> <br /> [[1983 AIME Problems/Problem 5|Solution]]<br /> <br /> == Problem 6 ==<br /> Let &lt;math&gt;a_n&lt;/math&gt; equal &lt;math&gt;6^{n}+8^{n}&lt;/math&gt;. Determine the remainder upon dividing &lt;math&gt;a_ {83}&lt;/math&gt; by &lt;math&gt;49&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 6|Solution]]<br /> <br /> == Problem 7 ==<br /> Twenty five of King Arthur's knights are seated at their customary round table. Three of them are chosen - all choices being equally likely - and are sent off to slay a troublesome dragon. Let &lt;math&gt;P&lt;/math&gt; be the probability that at least two of the three had been sitting next to each other. If &lt;math&gt;P&lt;/math&gt; is written as a fraction in lowest terms, what is the sum of the numerator and the denominator?<br /> <br /> [[1983 AIME Problems/Problem 7|Solution]]<br /> <br /> == Problem 8 ==<br /> What is the largest 2-digit prime factor of the integer &lt;math&gt;{200\choose 100}&lt;/math&gt;?<br /> <br /> [[1983 AIME Problems/Problem 8|Solution]]<br /> <br /> == Problem 9 ==<br /> Find the minimum value of &lt;math&gt;\frac{9x^2\sin^2 x + 4}{x\sin x}&lt;/math&gt; for &lt;math&gt;0 &lt; x &lt; \pi&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 9|Solution]]<br /> <br /> == Problem 10 ==<br /> The numbers &lt;math&gt;1447&lt;/math&gt;, &lt;math&gt;1005&lt;/math&gt;, and &lt;math&gt;1231&lt;/math&gt; have something in common. Each is a four-digit number beginning with &lt;math&gt;1&lt;/math&gt; that has exactly two identical digits. How many such numbers are there?<br /> <br /> [[1983 AIME Problems/Problem 10|Solution]]<br /> <br /> == Problem 11 ==<br /> The solid shown has a square base of side length &lt;math&gt;s&lt;/math&gt;. The upper edge is parallel to the base and has length &lt;math&gt;2s&lt;/math&gt;. All edges have length &lt;math&gt;s&lt;/math&gt;. Given that &lt;math&gt;s=6\sqrt{2}&lt;/math&gt;, what is the volume of the solid?<br /> <br /> &lt;asy&gt;<br /> import three;<br /> size(170);<br /> pathpen = black+linewidth(0.65);<br /> pointpen = black;<br /> currentprojection = perspective(30,-20,10);<br /> real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> draw(A--B--C--D--A--E--D);<br /> draw(B--F--C); <br /> draw(E--F);<br /> label(&quot;A&quot;,A);<br /> label(&quot;B&quot;,B);<br /> label(&quot;C&quot;,C);<br /> label(&quot;D&quot;,D);<br /> label(&quot;E&quot;,E,N);<br /> label(&quot;F&quot;,F,N);<br /> &lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 11|Solution]]<br /> <br /> == Problem 12 ==<br /> The length of diameter &lt;math&gt;AB&lt;/math&gt; is a two digit integer. Reversing the digits gives the length of a perpendicular chord &lt;math&gt;CD&lt;/math&gt;. The distance from their intersection point &lt;math&gt;H&lt;/math&gt; to the center &lt;math&gt;O&lt;/math&gt; is a positive rational number. Determine the length of &lt;math&gt;AB&lt;/math&gt;.<br /> <br /> &lt;asy&gt;pointpen=black; pathpen=black+linewidth(0.65);<br /> pair O=(0,0),A=(-65/2,0),B=(65/2,0);<br /> pair H=(-((65/2)^2-28^2)^.5,0),C=(H.x,28),D=(H.x,-28);<br /> D(CP(O,A));D(MP(&quot;A&quot;,A,W)--MP(&quot;B&quot;,B,E));D(MP(&quot;C&quot;,C,N)--MP(&quot;D&quot;,D));<br /> dot(MP(&quot;H&quot;,H,SE));dot(MP(&quot;O&quot;,O,SE));&lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 12|Solution]]<br /> <br /> == Problem 13 ==<br /> For &lt;math&gt;\{1, 2, 3, \ldots, n\}&lt;/math&gt; and each of its non-empty subsets, an alternating sum is defined as follows. Arrange the number in the subset in decreasing order and then, beginning with the largest, alternately add and subtract succesive numbers. For example, the alternating sum for &lt;math&gt;\{1, 2, 3, 6,9\}&lt;/math&gt; is &lt;math&gt;9-6+3-2+1=6&lt;/math&gt; and for &lt;math&gt;\{5\}&lt;/math&gt; it is simply &lt;math&gt;5&lt;/math&gt;. Find the sum of all such alternating sums for &lt;math&gt;n=7&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 13|Solution]]<br /> <br /> == Problem 14 ==<br /> In the adjoining figure, two circles with radii &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;8&lt;/math&gt; are drawn with their centers &lt;math&gt;12&lt;/math&gt; units apart. At &lt;math&gt;P&lt;/math&gt;, one of the points of intersection, a line is drawn in such a way that the chords &lt;math&gt;QP&lt;/math&gt; and &lt;math&gt;PR&lt;/math&gt; have equal length. (&lt;math&gt;P&lt;/math&gt; is the midpoint of &lt;math&gt;QR&lt;/math&gt;) Find the square of the length of &lt;math&gt;QP&lt;/math&gt;. <br /> <br /> [[Image:1983_AIME-14.png]]<br /> <br /> [[1983 AIME Problems/Problem 14|Solution]]<br /> <br /> == Problem 15 ==<br /> The adjoining figure shows two intersecting chords in a circle, with &lt;math&gt;B&lt;/math&gt; on minor arc &lt;math&gt;AD&lt;/math&gt;. Suppose that the radius of the circle is &lt;math&gt;5&lt;/math&gt;, that &lt;math&gt;BC=6&lt;/math&gt;, and that &lt;math&gt;AD&lt;/math&gt; is bisected by &lt;math&gt;BC&lt;/math&gt;. Suppose further that &lt;math&gt;AD&lt;/math&gt; is the only chord starting at &lt;math&gt;A&lt;/math&gt; which is bisected by &lt;math&gt;BC&lt;/math&gt;. It follows that the sine of the minor arc &lt;math&gt;AB&lt;/math&gt; is a rational number. If this fraction is expressed as a fraction &lt;math&gt;\frac{m}{n}&lt;/math&gt; in lowest terms, what is the product &lt;math&gt;mn&lt;/math&gt;?<br /> <br /> [[Image:1983_AIME-15.png]]<br /> <br /> [[1983 AIME Problems/Problem 15|Solution]]<br /> <br /> == See also ==<br /> * [[1983 AIME]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[AIME Problems and Solutions]]<br /> * [[Mathematics competition resources]]<br /> <br /> [[Category:AIME Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=USAJMO_Problems_and_Solutions&diff=34503 USAJMO Problems and Solutions 2010-05-14T19:18:09Z <p>Aopsvd: </p> <hr /> <div>[[USAMO|USAJMO]] problems and solutions by test:<br /> *[[2010 USAJMO]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_II_Problems/Problem_15&diff=34502 2005 AIME II Problems/Problem 15 2010-05-14T05:18:39Z <p>Aopsvd: /* Problem */</p> <hr /> <div>== Problem ==<br /> Let &lt;math&gt; w_1 &lt;/math&gt; and &lt;math&gt; w_2 &lt;/math&gt; denote the [[circle]]s &lt;math&gt; x^2+y^2+10x-24y-87=0 &lt;/math&gt; and &lt;math&gt; x^2 +y^2-10x-24y+153=0, &lt;/math&gt; respectively. Let &lt;math&gt; m &lt;/math&gt; be the smallest positive value of &lt;math&gt; a &lt;/math&gt; for which the line &lt;math&gt; y=ax &lt;/math&gt; contains the center of a circle that is externally [[tangent (geometry)|tangent]] to &lt;math&gt; w_2 &lt;/math&gt; and internally tangent to &lt;math&gt; w_1. &lt;/math&gt; Given that &lt;math&gt; m^2=\frac pq, &lt;/math&gt; where &lt;math&gt; p &lt;/math&gt; and &lt;math&gt; q &lt;/math&gt; are relatively prime integers, find &lt;math&gt; p+q. &lt;/math&gt;<br /> <br /> == Solution ==<br /> Rewrite the given equations as &lt;math&gt;(x+5)^2 + (y-12)^2 = 256&lt;/math&gt; and &lt;math&gt;(x-5)^2 + (y-12)^2 = 16&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;w_3&lt;/math&gt; have center &lt;math&gt;(x,y)&lt;/math&gt; and radius &lt;math&gt;r&lt;/math&gt;. Now, if two circles with radii &lt;math&gt;r_1&lt;/math&gt; and &lt;math&gt;r_2&lt;/math&gt; are externally tangent, then the distance between their centers is &lt;math&gt;r_1 + r_2&lt;/math&gt;, and if they are internally tangent, it is &lt;math&gt;|r_1 - r_2|&lt;/math&gt;. So we have<br /> <br /> &lt;cmath&gt;\begin{align*}<br /> r + 4 &amp;= \sqrt{(x-5)^2 + (y-12)^2} \\<br /> 16 - r &amp;= \sqrt{(x+5)^2 + (y-12)^2} \end{align*} &lt;/cmath&gt;<br /> <br /> Solving for &lt;math&gt;r&lt;/math&gt; in both equations and setting them equal, then simplifying, yields<br /> <br /> &lt;cmath&gt;\begin{align*}<br /> 20 - \sqrt{(x+5)^2 + (y-12)^2} &amp;= \sqrt{(x-5)^2 + (y-12)^2} \\<br /> 20+x &amp;= 2\sqrt{(x+5)^2 + (y-12)^2}<br /> \end{align*} &lt;/cmath&gt;<br /> <br /> Squaring again and canceling yields &lt;math&gt;1 = \frac{x^2}{100} + \frac{(y-12)^2}{75}.&lt;/math&gt;<br /> <br /> So the locus of points that can be the center of the circle with the desired properties is an [[ellipse]].<br /> <br /> &lt;center&gt;&lt;asy&gt;<br /> size(220); pointpen = black; pen d = linewidth(0.7); pathpen = d; <br /> pair A = (-5, 12), B = (5, 12), C = (0, 0);<br /> D(CR(A,16));D(CR(B,4));D(shift((0,12)) * yscale(3^.5 / 2) * CR(C,10), linetype(&quot;2 2&quot;) + d + red);<br /> D((0,30)--(0,-10),Arrows(4));D((15,0)--(-25,0),Arrows(4));D((0,0)--MP(&quot;y=ax&quot;,(14,14 * (69/100)^.5),E),EndArrow(4));<br /> <br /> void bluecirc (real x) {<br /> pair P = (x, (3 * (25 - x^2 / 4))^.5 + 12); dot(P, blue);<br /> D(CR(P, ((P.x - 5)^2 + (P.y - 12)^2)^.5 - 4) , blue + d + linetype(&quot;4 4&quot;));<br /> }<br /> <br /> bluecirc(-9.2); bluecirc(-4); bluecirc(3);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> Since the center lies on the line &lt;math&gt;y = ax&lt;/math&gt;, we substitute for &lt;math&gt;y&lt;/math&gt; and expand: <br /> &lt;cmath&gt;1 = \frac{x^2}{100} + \frac{(ax-12)^2}{75} \Longrightarrow (3+4a^2)x^2 - 96ax + 276 = 0.&lt;/cmath&gt;<br /> <br /> We want the value of &lt;math&gt;a&lt;/math&gt; that makes the line &lt;math&gt;y=ax&lt;/math&gt; tangent to the ellipse, which will mean that for that choice of &lt;math&gt;a&lt;/math&gt; there is only one solution to the most recent equation. But a quadratic has one solution [[iff]] its discriminant is &lt;math&gt;0&lt;/math&gt;, so &lt;math&gt;(-96a)^2 - 4(3+4a^2)(276) = 0&lt;/math&gt;.<br /> <br /> Solving yields &lt;math&gt;a^2 = \frac{69}{100}&lt;/math&gt;, so the answer is &lt;math&gt;\boxed{169}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2005|n=II|num-b=14|after=Last Question}}<br /> <br /> [[Category:Intermediate Geometry Problems]]</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_4&diff=34500 2010 USAMO Problems/Problem 4 2010-05-12T23:48:46Z <p>Aopsvd: TeX cleanup</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with &lt;math&gt;\angle A = 90^{\circ}&lt;/math&gt;. Points &lt;math&gt;D&lt;/math&gt;<br /> and &lt;math&gt;E&lt;/math&gt; lie on sides &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;AB&lt;/math&gt;, respectively, such that &lt;math&gt;\angle<br /> ABD = \angle DBC&lt;/math&gt; and &lt;math&gt;\angle ACE = \angle ECB&lt;/math&gt;. Segments &lt;math&gt;BD&lt;/math&gt; and<br /> &lt;math&gt;CE&lt;/math&gt; meet at &lt;math&gt;I&lt;/math&gt;. Determine whether or not it is possible for<br /> segments &lt;math&gt;AB, AC, BI, ID, CI, IE&lt;/math&gt; to all have integer lengths.<br /> <br /> ==Solution==<br /> We know that angle &lt;math&gt;BIC = 135^{\circ}&lt;/math&gt;, as the other two angles in triangle &lt;math&gt;BIC&lt;/math&gt; add to &lt;math&gt;45^{\circ}&lt;/math&gt;. Assume that only &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; are integers. Using the [[Law of Cosines]] on triangle BIC,<br /> &lt;center&gt;<br /> &lt;asy&gt;<br /> import olympiad;<br /> <br /> // Scale<br /> unitsize(1inch);<br /> <br /> // Shape<br /> real h = 1.75;<br /> real w = 2.5;<br /> <br /> // Points<br /> void ldot(pair p, string l, pair dir=p) { dot(p); label(l, p, unit(dir)); }<br /> pair A = origin; ldot(A, &quot;$A$&quot;, plain.SW);<br /> pair B = w * plain.E; ldot(B, &quot;$B$&quot;, plain.SE);<br /> pair C = h * plain.N; ldot(C, &quot;$C$&quot;, plain.NW);<br /> pair D = extension(B, bisectorpoint(C, B, A), A, C); ldot(D, &quot;$D$&quot;, D-B);<br /> pair E = extension(C, bisectorpoint(A, C, B), A, B); ldot(E, &quot;$E$&quot;, E-C);<br /> pair I = extension(B, D, C, E); ldot(I, &quot;$I$&quot;, A-I);<br /> <br /> // Segments<br /> draw(A--B); draw(B--C); draw(C--A);<br /> draw(C--E); draw(B--D);<br /> <br /> // Angles<br /> import markers;<br /> draw(rightanglemark(B, A, C, 4));<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, I, B, E);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, C, B, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, I, C, B);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, D, C, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{3\pi}{4}}$&quot;), radius=10, B, I, C);<br /> &lt;/asy&gt;<br /> &lt;/center&gt;<br /> <br /> &lt;math&gt;BC^2 = BI^2 + CI^2 - 2BI\cdot CI \cdot \cos 135^{\circ}&lt;/math&gt;. Observing that &lt;math&gt;BC^2 = AB^2 + AC^2&lt;/math&gt; and that &lt;math&gt;\cos 135^{\circ} = -\frac{\sqrt{2}}{2},&lt;/math&gt; we have<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> AB^2 + AC^2 - BI^2 - CI^2 = BI\cdot CI\cdot \sqrt{2}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and therefore,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \sqrt{2} = \frac{AB^2 + AC^2 - BI^2 - CI^2}{BI\cdot CI}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> <br /> Since the right side of the equation is a rational number, the left side (i.e. &lt;math&gt;\sqrt{2}&lt;/math&gt;) must also be rational. Obviously since &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, this claim is false and we have a contradiction. Therefore, it is impossible for &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.<br /> <br /> ==Solution 2==<br /> The result can be also proved without direct appeal to trigonometry,<br /> via just the angle bisector theorem and the structure of Pythagorean<br /> triples. (This is a lot more work).<br /> <br /> A triangle in which all the required lengths are integers exists if and<br /> only if there exists a triangle in which &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths of the segments &lt;math&gt;BI, ID, CI, IE&lt;/math&gt; are all rational<br /> (we divide all the lengths by the &lt;math&gt;\gcd(AB, AC)&lt;/math&gt; or<br /> conversely multiply all the lengths by the least common multiple<br /> of the denominators of the rational lengths).<br /> <br /> Suppose there exists a triangle in which the lengths &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths &lt;math&gt;IB, ID, CI, IE&lt;/math&gt; are all rational.<br /> <br /> Since &lt;math&gt;CE&lt;/math&gt; is the bisector of &lt;math&gt;\angle ACB&lt;/math&gt;, by the angle bisector<br /> theorem, the ratio &lt;math&gt;IB : ID = CB : CD&lt;/math&gt;, and since &lt;math&gt;BD&lt;/math&gt; is the<br /> bisector of &lt;math&gt;\angle ABC&lt;/math&gt;, &lt;math&gt;CB : CD = (AB + BC) : AC&lt;/math&gt;. Therefore,<br /> &lt;math&gt;IB : ID = (AB + BC) : AC&lt;/math&gt;. Now &lt;math&gt;IB : ID&lt;/math&gt; is by assumption rational,<br /> so &lt;math&gt;(AB + BC) : AC&lt;/math&gt; is rational, but &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are assumed integers<br /> so &lt;math&gt;BC : AC&lt;/math&gt; must also be rational. Since &lt;math&gt;BC&lt;/math&gt; is the hypotenuse of<br /> a right-triangle, its length is the square root of an integer,<br /> and thus either an integer or irrational, so &lt;math&gt;BC&lt;/math&gt; must be an integer.<br /> <br /> With &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; relatively-prime, we conclude that the side<br /> lengths of &lt;math&gt;\triangle ABC&lt;/math&gt; must be a Pythagorean triple: &lt;math&gt;(2pq, p^2<br /> - q^2, p^2 + q^2)&lt;/math&gt;, with &lt;math&gt;p &gt; q&lt;/math&gt; relatively-prime positive integers<br /> and &lt;math&gt;p+q&lt;/math&gt; odd.<br /> <br /> Without loss of generality, &lt;math&gt;AC = 2pq, AB = p^2 - q^2, BC = p^2+q^2&lt;/math&gt;.<br /> By the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AE &amp;= \dfrac{AB \cdot AC}{AC + CB} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + 2pq}<br /> = \dfrac{2pq(p-q)}{p+q}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> <br /> Since &lt;math&gt;\triangle CAE&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> CE^2 &amp;= AC^2 + AE^2<br /> = 4p^2q^2 + \left(\dfrac{2pq(p-q)}{p+q}\right)^2<br /> = 4p^2q^2\left[1 + \left(\dfrac{p-q}{p+q}\right)^2\right] \\<br /> &amp;= \frac{4p^2q^2}{(p+q)^2}\left[(p+q)^2 + (p-q)^2\right]<br /> = \frac{4p^2q^2}{(p+q)^2}(2p^2 + 2q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;CE&lt;/math&gt; is rational if and only if &lt;math&gt;2p^2 + 2q^2&lt;/math&gt; is a perfect square.<br /> <br /> Also by the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AD &amp;= \dfrac{AB \cdot AC}{AB + BC} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + p^2 - q^2} <br /> = \dfrac{q(p^2-q^2)}{p}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and therefore, since &lt;math&gt;\triangle DAB&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> BD^2 &amp;= AB^2 + AD^2<br /> = (p^2-q^2)^2 + \left(\dfrac{q(p^2-q^2)}{p}\right)^2 \\<br /> &amp;= (p^2-q^2)^2\left[1 + \frac{q^2}{p^2}\right]<br /> = \frac{(p^2-q^2)^2}{p^2}(p^2 + q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;BD&lt;/math&gt; is rational if and only if &lt;math&gt;p^2 + q^2&lt;/math&gt; is a perfect square.<br /> <br /> Combining the conditions on &lt;math&gt;CE&lt;/math&gt; and &lt;math&gt;BD&lt;/math&gt;, we see that<br /> &lt;math&gt;2p^2+2q^2&lt;/math&gt; and &lt;math&gt;p^2+q^2&lt;/math&gt; must both be perfect squares. If it were so,<br /> their ratio, which is &lt;math&gt;2&lt;/math&gt;, would be the square of a rational number,<br /> but &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, and so the assumed triangle cannot exist.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_4&diff=34499 2010 USAMO Problems/Problem 4 2010-05-12T23:42:17Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with &lt;math&gt;\angle A = 90^{\circ}&lt;/math&gt;. Points &lt;math&gt;D&lt;/math&gt;<br /> and &lt;math&gt;E&lt;/math&gt; lie on sides &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;AB&lt;/math&gt;, respectively, such that &lt;math&gt;\angle<br /> ABD = \angle DBC&lt;/math&gt; and &lt;math&gt;\angle ACE = \angle ECB&lt;/math&gt;. Segments &lt;math&gt;BD&lt;/math&gt; and<br /> &lt;math&gt;CE&lt;/math&gt; meet at &lt;math&gt;I&lt;/math&gt;. Determine whether or not it is possible for<br /> segments &lt;math&gt;AB, AC, BI, ID, CI, IE&lt;/math&gt; to all have integer lengths.<br /> <br /> ==Solution==<br /> We know that angle &lt;math&gt;BIC = 135^{\circ}&lt;/math&gt;, as the other two angles in triangle &lt;math&gt;BIC&lt;/math&gt; add to &lt;math&gt;45^{\circ}&lt;/math&gt;. Assume that only &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; are integers. Using the [[Law of Cosines]] on triangle BIC,<br /> &lt;center&gt;<br /> &lt;asy&gt;<br /> import olympiad;<br /> <br /> // Scale<br /> unitsize(1inch);<br /> <br /> // Shape<br /> real h = 1.75;<br /> real w = 2.5;<br /> <br /> // Points<br /> void ldot(pair p, string l, pair dir=p) { dot(p); label(l, p, unit(dir)); }<br /> pair A = origin; ldot(A, &quot;$A$&quot;, plain.SW);<br /> pair B = w * plain.E; ldot(B, &quot;$B$&quot;, plain.SE);<br /> pair C = h * plain.N; ldot(C, &quot;$C$&quot;, plain.NW);<br /> pair D = extension(B, bisectorpoint(C, B, A), A, C); ldot(D, &quot;$D$&quot;, D-B);<br /> pair E = extension(C, bisectorpoint(A, C, B), A, B); ldot(E, &quot;$E$&quot;, E-C);<br /> pair I = extension(B, D, C, E); ldot(I, &quot;$I$&quot;, A-I);<br /> <br /> // Segments<br /> draw(A--B); draw(B--C); draw(C--A);<br /> draw(C--E); draw(B--D);<br /> <br /> // Angles<br /> import markers;<br /> draw(rightanglemark(B, A, C, 4));<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, I, B, E);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, C, B, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, I, C, B);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, D, C, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{3\pi}{4}}$&quot;), radius=10, B, I, C);<br /> &lt;/asy&gt;<br /> &lt;/center&gt;<br /> <br /> &lt;math&gt;BC^2 = BI^2 + CI^2 - 2BI*CI*\cos 135^{\circ}&lt;/math&gt;. Observing that &lt;math&gt;BC^2 = AB^2 + AC^2&lt;/math&gt; and that &lt;math&gt;\cos 135^{\circ} = -\frac{\sqrt{2}}{2}&lt;/math&gt;, we have<br /> <br /> &lt;math&gt;AB^2 + AC^2 - BI^2 - CI^2 = BI*CI*\sqrt{2}&lt;/math&gt;<br /> <br /> &lt;math&gt;\sqrt{2} = \frac{AB^2 + AC^2 - BI^2 - CI^2}{BI*CI}&lt;/math&gt;<br /> <br /> Since the right side of the equation is a rational number, the left side (i.e. &lt;math&gt;\sqrt{2}&lt;/math&gt;) must also be rational. Obviously since &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, this claim is false and we have a contradiction. Therefore, it is impossible for &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.<br /> <br /> ==Solution 2==<br /> The result can be also proved without direct appeal to trigonometry,<br /> via just the angle bisector theorem and the structure of Pythagorean<br /> triples. (This is a lot more work).<br /> <br /> A triangle in which all the required lengths are integers exists if and<br /> only if there exists a triangle in which &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths of the segments &lt;math&gt;BI, ID, CI, IE&lt;/math&gt; are all rational<br /> (we divide all the lengths by the &lt;math&gt;\gcd(AB, AC)&lt;/math&gt; or<br /> conversely multiply all the lengths by the least common multiple<br /> of the denominators of the rational lengths).<br /> <br /> Suppose there exists a triangle in which the lengths &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths &lt;math&gt;IB, ID, CI, IE&lt;/math&gt; are all rational.<br /> <br /> Since &lt;math&gt;CE&lt;/math&gt; is the bisector of &lt;math&gt;\angle ACB&lt;/math&gt;, by the angle bisector<br /> theorem, the ratio &lt;math&gt;IB : ID = CB : CD&lt;/math&gt;, and since &lt;math&gt;BD&lt;/math&gt; is the<br /> bisector of &lt;math&gt;\angle ABC&lt;/math&gt;, &lt;math&gt;CB : CD = (AB + BC) : AC&lt;/math&gt;. Therefore,<br /> &lt;math&gt;IB : ID = (AB + BC) : AC&lt;/math&gt;. Now &lt;math&gt;IB : ID&lt;/math&gt; is by assumption rational,<br /> so &lt;math&gt;(AB + BC) : AC&lt;/math&gt; is rational, but &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are assumed integers<br /> so &lt;math&gt;BC : AC&lt;/math&gt; must also be rational. Since &lt;math&gt;BC&lt;/math&gt; is the hypotenuse of<br /> a right-triangle, its length is the square root of an integer,<br /> and thus either an integer or irrational, so &lt;math&gt;BC&lt;/math&gt; must be an integer.<br /> <br /> With &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; relatively-prime, we conclude that the side<br /> lengths of &lt;math&gt;\triangle ABC&lt;/math&gt; must be a Pythagorean triple: &lt;math&gt;(2pq, p^2<br /> - q^2, p^2 + q^2)&lt;/math&gt;, with &lt;math&gt;p &gt; q&lt;/math&gt; relatively-prime positive integers<br /> and &lt;math&gt;p+q&lt;/math&gt; odd.<br /> <br /> Without loss of generality, &lt;math&gt;AC = 2pq, AB = p^2 - q^2, BC = p^2+q^2&lt;/math&gt;.<br /> By the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AE &amp;= \dfrac{AB \cdot AC}{AC + CB} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + 2pq}<br /> = \dfrac{2pq(p-q)}{p+q}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> <br /> Since &lt;math&gt;\triangle CAE&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> CE^2 &amp;= AC^2 + AE^2<br /> = 4p^2q^2 + \left(\dfrac{2pq(p-q)}{p+q}\right)^2<br /> = 4p^2q^2\left[1 + \left(\dfrac{p-q}{p+q}\right)^2\right] \\<br /> &amp;= \frac{4p^2q^2}{(p+q)^2}\left[(p+q)^2 + (p-q)^2\right]<br /> = \frac{4p^2q^2}{(p+q)^2}(2p^2 + 2q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;CE&lt;/math&gt; is rational if and only if &lt;math&gt;2p^2 + 2q^2&lt;/math&gt; is a perfect square.<br /> <br /> Also by the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AD &amp;= \dfrac{AB \cdot AC}{AB + BC} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + p^2 - q^2} <br /> = \dfrac{q(p^2-q^2)}{p}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and therefore, since &lt;math&gt;\triangle DAB&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> BD^2 &amp;= AB^2 + AD^2<br /> = (p^2-q^2)^2 + \left(\dfrac{q(p^2-q^2)}{p}\right)^2 \\<br /> &amp;= (p^2-q^2)^2\left[1 + \frac{q^2}{p^2}\right]<br /> = \frac{(p^2-q^2)^2}{p^2}(p^2 + q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;BD&lt;/math&gt; is rational if and only if &lt;math&gt;p^2 + q^2&lt;/math&gt; is a perfect square.<br /> <br /> Combining the conditions on &lt;math&gt;CE&lt;/math&gt; and &lt;math&gt;BD&lt;/math&gt;, we see that<br /> &lt;math&gt;2p^2+2q^2&lt;/math&gt; and &lt;math&gt;p^2+q^2&lt;/math&gt; must both be perfect squares. If it were so,<br /> their ratio, which is &lt;math&gt;2&lt;/math&gt;, would be the square of a rational number,<br /> but &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, and so the assumed triangle cannot exist.</div> Aopsvd https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_4&diff=34498 2010 USAMO Problems/Problem 4 2010-05-12T23:37:30Z <p>Aopsvd: /* Solution */</p> <hr /> <div>==Problem==<br /> Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with &lt;math&gt;\angle A = 90^{\circ}&lt;/math&gt;. Points &lt;math&gt;D&lt;/math&gt;<br /> and &lt;math&gt;E&lt;/math&gt; lie on sides &lt;math&gt;AC&lt;/math&gt; and &lt;math&gt;AB&lt;/math&gt;, respectively, such that &lt;math&gt;\angle<br /> ABD = \angle DBC&lt;/math&gt; and &lt;math&gt;\angle ACE = \angle ECB&lt;/math&gt;. Segments &lt;math&gt;BD&lt;/math&gt; and<br /> &lt;math&gt;CE&lt;/math&gt; meet at &lt;math&gt;I&lt;/math&gt;. Determine whether or not it is possible for<br /> segments &lt;math&gt;AB, AC, BI, ID, CI, IE&lt;/math&gt; to all have integer lengths.<br /> <br /> ==Solution==<br /> We know that angle &lt;math&gt;BIC = 135^{\circ}&lt;/math&gt;, as the other two angles in triangle &lt;math&gt;BIC&lt;/math&gt; add to &lt;math&gt;45^{\circ}&lt;/math&gt;. Assume that only &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; are integers. Using the [[Law of Cosines]] on triangle BIC,<br /> &lt;center&gt;<br /> &lt;asy&gt;<br /> import olympiad;<br /> <br /> // Scale<br /> unitsize(1inch);<br /> <br /> // Shape<br /> real h = 1.75;<br /> real w = 2.5;<br /> <br /> // Points<br /> void ldot(pair p, string l, pair dir=p) { dot(p); label(l, p, unit(dir)); }<br /> pair A = origin; ldot(A, &quot;$A$&quot;, plain.SW);<br /> pair B = w * plain.E; ldot(B, &quot;$B$&quot;, plain.SE);<br /> pair C = h * plain.N; ldot(C, &quot;$C$&quot;, plain.NW);<br /> pair D = extension(B, bisectorpoint(C, B, A), A, C); ldot(D, &quot;$D$&quot;, D-B);<br /> pair E = extension(C, bisectorpoint(A, C, B), A, B); ldot(E, &quot;$E$&quot;, E-C);<br /> pair I = extension(B, D, C, E); ldot(I, &quot;$I$&quot;, A-I);<br /> <br /> // Segments<br /> draw(A--B); draw(B--C); draw(C--A);<br /> draw(C--E); draw(B--D);<br /> <br /> // Angles<br /> import markers;<br /> draw(rightanglemark(B, A, C, 4));<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, I, B, E);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\theta}{2}}$&quot;), radius=40, C, B, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, I, C, B);<br /> markangle(Label(&quot;$\scriptstyle{\frac{\pi}{4} - \frac{\theta}{2}}$&quot;), radius=40, D, C, I);<br /> markangle(Label(&quot;$\scriptstyle{\frac{3\pi}{4}}$&quot;), radius=10, B, I, C);<br /> &lt;/asy&gt;<br /> &lt;/center&gt;<br /> <br /> &lt;math&gt;BC^2 = BI^2 + CI^2 - 2BI*CI*cos 135^{\circ}&lt;/math&gt;. Observing that &lt;math&gt;BC^2 = AB^2 + AC^2&lt;/math&gt; and that &lt;math&gt;cos 135^{\circ} = -\frac{\sqrt{2}}{2}&lt;/math&gt;, we have<br /> <br /> &lt;math&gt;AB^2 + AC^2 - BI^2 - CI^2 = BI*CI*\sqrt{2}&lt;/math&gt;<br /> <br /> &lt;math&gt;\sqrt{2} = \frac{AB^2 + AC^2 - BI^2 - CI^2}{BI*CI}&lt;/math&gt;<br /> <br /> Since the right side of the equation is a rational number, the left side (i.e. &lt;math&gt;\sqrt{2}&lt;/math&gt;) must also be rational. Obviously since &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, this claim is false and we have a contradiction. Therefore, it is impossible for &lt;math&gt;AB, BC, BI&lt;/math&gt;, and &lt;math&gt;CI&lt;/math&gt; to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.<br /> <br /> ==Solution 2==<br /> The result can be also proved without direct appeal to trigonometry,<br /> via just the angle bisector theorem and the structure of Pythagorean<br /> triples. (This is a lot more work).<br /> <br /> A triangle in which all the required lengths are integers exists if and<br /> only if there exists a triangle in which &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths of the segments &lt;math&gt;BI, ID, CI, IE&lt;/math&gt; are all rational<br /> (we divide all the lengths by the &lt;math&gt;\gcd(AB, AC)&lt;/math&gt; or<br /> conversely multiply all the lengths by the least common multiple<br /> of the denominators of the rational lengths).<br /> <br /> Suppose there exists a triangle in which the lengths &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are<br /> relatively-prime integers and the lengths &lt;math&gt;IB, ID, CI, IE&lt;/math&gt; are all rational.<br /> <br /> Since &lt;math&gt;CE&lt;/math&gt; is the bisector of &lt;math&gt;\angle ACB&lt;/math&gt;, by the angle bisector<br /> theorem, the ratio &lt;math&gt;IB : ID = CB : CD&lt;/math&gt;, and since &lt;math&gt;BD&lt;/math&gt; is the<br /> bisector of &lt;math&gt;\angle ABC&lt;/math&gt;, &lt;math&gt;CB : CD = (AB + BC) : AC&lt;/math&gt;. Therefore,<br /> &lt;math&gt;IB : ID = (AB + BC) : AC&lt;/math&gt;. Now &lt;math&gt;IB : ID&lt;/math&gt; is by assumption rational,<br /> so &lt;math&gt;(AB + BC) : AC&lt;/math&gt; is rational, but &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; are assumed integers<br /> so &lt;math&gt;BC : AC&lt;/math&gt; must also be rational. Since &lt;math&gt;BC&lt;/math&gt; is the hypotenuse of<br /> a right-triangle, its length is the square root of an integer,<br /> and thus either an integer or irrational, so &lt;math&gt;BC&lt;/math&gt; must be an integer.<br /> <br /> With &lt;math&gt;AB&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt; relatively-prime, we conclude that the side<br /> lengths of &lt;math&gt;\triangle ABC&lt;/math&gt; must be a Pythagorean triple: &lt;math&gt;(2pq, p^2<br /> - q^2, p^2 + q^2)&lt;/math&gt;, with &lt;math&gt;p &gt; q&lt;/math&gt; relatively-prime positive integers<br /> and &lt;math&gt;p+q&lt;/math&gt; odd.<br /> <br /> Without loss of generality, &lt;math&gt;AC = 2pq, AB = p^2 - q^2, BC = p^2+q^2&lt;/math&gt;.<br /> By the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AE &amp;= \dfrac{AB \cdot AC}{AC + CB} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + 2pq}<br /> = \dfrac{2pq(p-q)}{p+q}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> <br /> Since &lt;math&gt;\triangle CAE&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> CE^2 &amp;= AC^2 + AE^2<br /> = 4p^2q^2 + \left(\dfrac{2pq(p-q)}{p+q}\right)^2<br /> = 4p^2q^2\left[1 + \left(\dfrac{p-q}{p+q}\right)^2\right] \\<br /> &amp;= \frac{4p^2q^2}{(p+q)^2}\left[(p+q)^2 + (p-q)^2\right]<br /> = \frac{4p^2q^2}{(p+q)^2}(2p^2 + 2q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;CE&lt;/math&gt; is rational if and only if &lt;math&gt;2p^2 + 2q^2&lt;/math&gt; is a perfect square.<br /> <br /> Also by the angle bisector theorem,<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> AD &amp;= \dfrac{AB \cdot AC}{AB + BC} = \dfrac{2pq(p^2-q^2)}{p^2 + q^2 + p^2 - q^2} <br /> = \dfrac{q(p^2-q^2)}{p}<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and therefore, since &lt;math&gt;\triangle DAB&lt;/math&gt; is a right-triangle, we have:<br /> &lt;center&gt;<br /> &lt;cmath&gt;<br /> \begin{align*}<br /> BD^2 &amp;= AB^2 + AD^2<br /> = (p^2-q^2)^2 + \left(\dfrac{q(p^2-q^2)}{p}\right)^2 \\<br /> &amp;= (p^2-q^2)^2\left[1 + \frac{q^2}{p^2}\right]<br /> = \frac{(p^2-q^2)^2}{p^2}(p^2 + q^2)<br /> \end{align*}<br /> &lt;/cmath&gt;<br /> &lt;/center&gt;<br /> and so &lt;math&gt;BD&lt;/math&gt; is rational if and only if &lt;math&gt;p^2 + q^2&lt;/math&gt; is a perfect square.<br /> <br /> Combining the conditions on &lt;math&gt;CE&lt;/math&gt; and &lt;math&gt;BD&lt;/math&gt;, we see that<br /> &lt;math&gt;2p^2+2q^2&lt;/math&gt; and &lt;math&gt;p^2+q^2&lt;/math&gt; must both be perfect squares. If it were so,<br /> their ratio, which is &lt;math&gt;2&lt;/math&gt;, would be the square of a rational number,<br /> but &lt;math&gt;\sqrt{2}&lt;/math&gt; is irrational, and so the assumed triangle cannot exist.</div> Aopsvd