https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Leonardo+von+einzbern&feedformat=atom AoPS Wiki - User contributions [en] 2021-10-19T03:41:24Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=78424 2016 USAMO Problems/Problem 2 2016-05-05T12:30:05Z <p>Leonardo von einzbern: /* Solution 2 (Controversial) */</p> <hr /> <div>==Problem==<br /> Prove that for any positive integer &lt;math&gt;k,&lt;/math&gt;<br /> &lt;cmath&gt;\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}&lt;/cmath&gt;<br /> is an integer.<br /> ==Solution 1==<br /> Define &lt;math&gt;v_p(N)&lt;/math&gt; for all rational numbers &lt;math&gt;N&lt;/math&gt; and primes &lt;math&gt;p&lt;/math&gt;, where if &lt;math&gt;N=\frac{x}{y}&lt;/math&gt;, then &lt;math&gt;v_p(N)=v_p(x)-v_p(y)&lt;/math&gt;, and &lt;math&gt;v_p(x)&lt;/math&gt; is the greatest power of &lt;math&gt;p&lt;/math&gt; that divides &lt;math&gt;x&lt;/math&gt; for integer &lt;math&gt;x&lt;/math&gt;. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it &lt;math&gt;N&lt;/math&gt;.<br /> <br /> &lt;math&gt;v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor&lt;/math&gt;, by Legendre. Clearly, &lt;math&gt;\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}&lt;/math&gt;, and &lt;math&gt;\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)&lt;/math&gt;, where &lt;math&gt;r(i,m)&lt;/math&gt; is the remainder function(we take out groups of &lt;math&gt;m&lt;/math&gt; which are just permutations of numbers &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;m&lt;/math&gt; until there are less than &lt;math&gt;m&lt;/math&gt; left, then we have &lt;math&gt;m&lt;/math&gt; distinct values, which the minimum sum is attained at &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;k-1&lt;/math&gt;). Thus, &lt;math&gt;v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}_{+}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0&lt;/math&gt;, as the term in each summand is a sum of floors also and is clearly an integer.<br /> <br /> ==Solution 2 (Controversial)==<br /> Consider an &lt;math&gt;k\times k&lt;/math&gt; grid, which is to be filled with the integers &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;k^2&lt;/math&gt; such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux.<br /> <br /> The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this &lt;math&gt;N&lt;/math&gt; for convenience) is:<br /> &lt;cmath&gt;N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.&lt;/cmath&gt;<br /> Now, we do some simple rearrangement:<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\prod_{i=1}^{k}\frac{1}{i+j-1}&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\frac{\left(j-1\right)!}{\left(j+k-1\right)!}.&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.&lt;/cmath&gt;<br /> This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux, it must be an integer, so we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2016|num-b=1|num-a=3}}</div> Leonardo von einzbern https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=78423 2016 USAMO Problems/Problem 2 2016-05-05T12:29:14Z <p>Leonardo von einzbern: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> Prove that for any positive integer &lt;math&gt;k,&lt;/math&gt;<br /> &lt;cmath&gt;\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}&lt;/cmath&gt;<br /> is an integer.<br /> ==Solution 1==<br /> Define &lt;math&gt;v_p(N)&lt;/math&gt; for all rational numbers &lt;math&gt;N&lt;/math&gt; and primes &lt;math&gt;p&lt;/math&gt;, where if &lt;math&gt;N=\frac{x}{y}&lt;/math&gt;, then &lt;math&gt;v_p(N)=v_p(x)-v_p(y)&lt;/math&gt;, and &lt;math&gt;v_p(x)&lt;/math&gt; is the greatest power of &lt;math&gt;p&lt;/math&gt; that divides &lt;math&gt;x&lt;/math&gt; for integer &lt;math&gt;x&lt;/math&gt;. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it &lt;math&gt;N&lt;/math&gt;.<br /> <br /> &lt;math&gt;v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor&lt;/math&gt;, by Legendre. Clearly, &lt;math&gt;\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}&lt;/math&gt;, and &lt;math&gt;\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)&lt;/math&gt;, where &lt;math&gt;r(i,m)&lt;/math&gt; is the remainder function(we take out groups of &lt;math&gt;m&lt;/math&gt; which are just permutations of numbers &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;m&lt;/math&gt; until there are less than &lt;math&gt;m&lt;/math&gt; left, then we have &lt;math&gt;m&lt;/math&gt; distinct values, which the minimum sum is attained at &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;k-1&lt;/math&gt;). Thus, &lt;math&gt;v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}_{+}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0&lt;/math&gt;, as the term in each summand is a sum of floors also and is clearly an integer.<br /> <br /> ==Solution 2 (Controversial)==<br /> Consider an &lt;math&gt;k\times k&lt;/math&gt; grid, which is to be filled with the integers &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;k^2&lt;/math&gt; such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux.<br /> <br /> The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this &lt;math&gt;N&lt;/math&gt; for convenience) is:<br /> &lt;cmath&gt;N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.&lt;/cmath&gt;<br /> Now, we do some simple rearrangement:<br /> &lt;cmath&gt;N = \left(k^2\right)\cdot\prod_{j=1}^{k}\prod_{i=1}^{k}\frac{1}{i+j-1}&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\frac{\left(j-1\right)!}{\left(j+k-1\right)!}.&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.&lt;/cmath&gt;<br /> This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux, it must be an integer, so we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2016|num-b=1|num-a=3}}</div> Leonardo von einzbern https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&diff=78422 2016 USAMO Problems/Problem 2 2016-05-05T11:50:09Z <p>Leonardo von einzbern: /* Solution 1 */</p> <hr /> <div>==Problem==<br /> Prove that for any positive integer &lt;math&gt;k,&lt;/math&gt;<br /> &lt;cmath&gt;\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}&lt;/cmath&gt;<br /> is an integer.<br /> ==Solution 1==<br /> Define &lt;math&gt;v_p(N)&lt;/math&gt; for all rational numbers &lt;math&gt;N&lt;/math&gt; and primes &lt;math&gt;p&lt;/math&gt;, where if &lt;math&gt;N=\frac{x}{y}&lt;/math&gt;, then &lt;math&gt;v_p(N)=v_p(x)-v_p(y)&lt;/math&gt;, and &lt;math&gt;v_p(x)&lt;/math&gt; is the greatest power of &lt;math&gt;p&lt;/math&gt; that divides &lt;math&gt;x&lt;/math&gt; for integer &lt;math&gt;x&lt;/math&gt;. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it &lt;math&gt;N&lt;/math&gt;.<br /> <br /> &lt;math&gt;v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor&lt;/math&gt;, by Legendre. Clearly, &lt;math&gt;\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}&lt;/math&gt;, and &lt;math&gt;\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)&lt;/math&gt;, where &lt;math&gt;r(i,m)&lt;/math&gt; is the remainder function(we take out groups of &lt;math&gt;m&lt;/math&gt; which are just permutations of numbers &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;m&lt;/math&gt; until there are less than &lt;math&gt;m&lt;/math&gt; left, then we have &lt;math&gt;m&lt;/math&gt; distinct values, which the minimum sum is attained at &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;k-1&lt;/math&gt;). Thus, &lt;math&gt;v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0&lt;/math&gt;, as the term in each summand is a sum of floors also and is clearly an integer.<br /> <br /> ==Solution 2 (Controversial)==<br /> Consider an &lt;math&gt;k\times k&lt;/math&gt; grid, which is to be filled with the integers &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;k^2&lt;/math&gt; such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux.<br /> <br /> The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this &lt;math&gt;N&lt;/math&gt; for convenience) is:<br /> &lt;cmath&gt;N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.&lt;/cmath&gt;<br /> Now, we do some simple rearrangement:<br /> &lt;cmath&gt;N = \left(k^2\right)\cdot\prod_{j=1}^{k}\prod_{i=1}^{k}\frac{1}{i+j-1}&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\frac{\left(j-1\right)!}{\left(j+k-1\right)!}.&lt;/cmath&gt;<br /> &lt;cmath&gt;N = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.&lt;/cmath&gt;<br /> This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct &lt;math&gt;k\times k&lt;/math&gt; standard Young tableaux, it must be an integer, so we are done.<br /> <br /> ==See also==<br /> {{USAMO newbox|year=2016|num-b=1|num-a=3}}</div> Leonardo von einzbern https://artofproblemsolving.com/wiki/index.php?title=2008_USAMO_Problems/Problem_4&diff=73706 2008 USAMO Problems/Problem 4 2015-12-14T08:34:42Z <p>Leonardo von einzbern: There are not three solutions but only one!</p> <hr /> <div>== Problem ==<br /> (''Gregory Galparin'') Let &lt;math&gt;\mathcal{P}&lt;/math&gt; be a [[convex polygon]] with &lt;math&gt;n&lt;/math&gt; sides, &lt;math&gt;n\ge3&lt;/math&gt;. Any set of &lt;math&gt;n - 3&lt;/math&gt; diagonals of &lt;math&gt;\mathcal{P}&lt;/math&gt; that do not intersect in the interior of the polygon determine a ''triangulation'' of &lt;math&gt;\mathcal{P}&lt;/math&gt; into &lt;math&gt;n - 2&lt;/math&gt; triangles. If &lt;math&gt;\mathcal{P}&lt;/math&gt; is regular and there is a triangulation of &lt;math&gt;\mathcal{P}&lt;/math&gt; consisting of only isosceles triangles, find all the possible values of &lt;math&gt;n&lt;/math&gt;.<br /> <br /> == Solutions ==<br /> <br /> We label the vertices of &lt;math&gt;\mathcal{P}&lt;/math&gt; as &lt;math&gt;P_0, P_1, P_2, \ldots, P_n&lt;/math&gt;. Consider a diagonal &lt;math&gt;d = \overline{P_a\,P_{a+k}},\,k \le n/2&lt;/math&gt; in the triangulation. We show that &lt;math&gt;k&lt;/math&gt; must have the form &lt;math&gt;2^{m}&lt;/math&gt; for some nonnegative integer &lt;math&gt;m&lt;/math&gt;.<br /> <br /> This diagonal [[partition]]s &lt;math&gt;\mathcal{P}&lt;/math&gt; into two regions &lt;math&gt;\mathcal{Q},\, \mathcal{R}&lt;/math&gt;, and is the side of an isosceles triangle in both regions. [[Without loss of generality]] suppose the area of &lt;math&gt;Q&lt;/math&gt; is less than the area of &lt;math&gt;R&lt;/math&gt; (so the [[circumcenter|center]] of &lt;math&gt;P&lt;/math&gt; does not lie in the interior of &lt;math&gt;Q&lt;/math&gt;); it follows that the lengths of the edges and diagonals in &lt;math&gt;Q&lt;/math&gt; are all smaller than &lt;math&gt;d&lt;/math&gt;. Thus &lt;math&gt;d&lt;/math&gt; must the be the base of the isosceles triangle in &lt;math&gt;Q&lt;/math&gt;, from which it follows that the isosceles triangle is &lt;math&gt;\triangle P_aP_{a+k/2}\,P_{a+k}&lt;/math&gt;, and so &lt;math&gt;2|k&lt;/math&gt;. Repeating this process on the legs of isosceles triangle (&lt;math&gt;\overline{P_aP_{a+k/2}},\,\overline{P_{a+k}P_{a+k/2}}&lt;/math&gt;), it follows that &lt;math&gt;k = 2^m&lt;/math&gt; for some positive integer &lt;math&gt;m&lt;/math&gt; (if we allow [[degenerate|degeneracy]], then we can also let &lt;math&gt;m=0&lt;/math&gt;). <br /> <br /> &lt;center&gt;&lt;table&gt;&lt;tr&gt;&lt;td&gt;&lt;asy&gt;<br /> defaultpen(linewidth(0.7)+fontsize(10));<br /> int n = 17; real r = 1; real rad = pi/2;<br /> <br /> pair pt(real k=0) {<br /> return (r*expi(rad-2*pi*k/n));<br /> }<br /> <br /> for(int i=0; i&lt;n; ++i){<br /> dot(pt(i));<br /> draw(pt(i)--pt(i+1));<br /> }<br /> <br /> draw(pt()--pt(8));<br /> draw(pt()--pt(4)--pt(8),linewidth(0.7)+linetype(&quot;4 4&quot;));<br /> draw(pt()--pt(2)--pt(4),linewidth(0.7)+linetype(&quot;4 4&quot;));<br /> label(&quot;$$d$$&quot;,(pt()+pt(8))/2,WNW);<br /> label(&quot;$$\mathcal{Q}$$&quot;,(pt()+pt(6))/2,SE);<br /> label(&quot;$$\mathcal{R}$$&quot;,(pt()+pt(10))/2,W);<br /> <br /> label(&quot;$$P_0$$&quot;,pt(),N);<br /> label(&quot;$$P_1$$&quot;,pt(1),NNE);<br /> label(&quot;$$P_8$$&quot;,pt(8),S);<br /> label(&quot;$$P_{16}$$&quot;,pt(-1),NNW);<br /> label(&quot;$$\cdots$$&quot;,pt(2),NE);<br /> &lt;/asy&gt;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;/td&gt;&lt;td&gt;&lt;asy&gt;<br /> defaultpen(linewidth(0.7)+fontsize(10));<br /> int n = 20; real r = 1; real rad = pi/2;<br /> <br /> pair pt(real k=0) {<br /> return (r*expi(rad-2*pi*k/n));<br /> }<br /> <br /> for(int i=0; i&lt;n; ++i){<br /> dot(pt(i));<br /> draw(pt(i)--pt(i+1));<br /> }<br /> <br /> draw(pt()--pt(8)--pt(16)--cycle);<br /> label(&quot;$$O$$&quot;,(0,0),W); dot((0,0));<br /> <br /> draw(pt()--pt(4)--pt(8)--pt(6)--pt(4)--pt(2)--pt()--pt(18)--pt(16)--pt(12)--pt(8)--pt(10)--pt(12)--pt(14)--pt(16),linewidth(0.3)+linetype(&quot;4 4&quot;));<br /> <br /> label(&quot;$$P_0$$&quot;,pt(),N);<br /> label(&quot;$$P_1$$&quot;,pt(1),NNE);<br /> label(&quot;$$P_{19}$$&quot;,pt(-1),NNW);<br /> label(&quot;$$P_{8}$$&quot;,pt(8),SE);<br /> label(&quot;$$P_{16}$$&quot;,pt(16),W);<br /> label(&quot;$$\cdots$$&quot;,pt(2),NE);<br /> <br /> &lt;/asy&gt;&lt;/td&gt;&lt;/tr&gt;&lt;tr&gt;&lt;td&gt;&lt;span style=&quot;font-size:85%&quot;&gt;An example for &lt;math&gt;n=17&lt;/math&gt;,&lt;br /&gt;&lt;math&gt;k=8&lt;/math&gt;&lt;/span&gt;&lt;/td&gt;&lt;td&gt;&lt;span style=&quot;font-size:85%&quot;&gt;An isosceles triangle containing&lt;br /&gt; the center for &lt;br /&gt; &lt;math&gt;n=20&lt;/math&gt;, &lt;math&gt;(x,y,z) = (0,8,16)&lt;/math&gt;&lt;/span&gt;&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;&lt;/center&gt;<br /> <br /> Now take the isosceles triangle &lt;math&gt;P_xP_yP_z,\,0 \le x &lt; y &lt; z &lt; n&lt;/math&gt; in the triangulation that contains the center of &lt;math&gt;\mathcal{P}&lt;/math&gt; in its interior; if a diagonal passes through the center, select either of the isosceles triangles with that diagonal as an edge. Without loss of generality, suppose &lt;math&gt;P_xP_y = P_yP_z&lt;/math&gt;. From our previous result, it follows that there are &lt;math&gt;2^a&lt;/math&gt; edges of &lt;math&gt;P&lt;/math&gt; on the minor arcs of &lt;math&gt;P_xP_y,\, P_yP_z&lt;/math&gt; and &lt;math&gt;2^b&lt;/math&gt; edges of &lt;math&gt;P&lt;/math&gt; on the minor arc of &lt;math&gt;P_zP_x&lt;/math&gt;, for positive integers &lt;math&gt;a,\,b&lt;/math&gt;. Therefore, we can write<br /> &lt;cmath&gt;n = 2 \cdot 2^a + 2^b = 2^{a+1} + 2^{b},&lt;/cmath&gt; so &lt;math&gt;n&lt;/math&gt; must be the sum of two powers of &lt;math&gt;2&lt;/math&gt;. <br /> <br /> <br /> We now claim that this condition is sufficient. Suppose without loss of generality that &lt;math&gt;a+1 \ge b&lt;/math&gt;; then we rewrite this as <br /> &lt;cmath&gt;n = 2^{b}(2^{a-b+1}+1).&lt;/cmath&gt;<br /> *''Lemma 1'': All regular polygons with &lt;math&gt;n = 2^k + 1&lt;/math&gt; or &lt;math&gt;n=4&lt;/math&gt; have triangulations that meet the conditions.<br /> <br /> By [[induction]], it follows that we can cover all the desired &lt;math&gt;n&lt;/math&gt;.<br /> <br /> For &lt;math&gt;n = 3,4&lt;/math&gt;, this is trivial. For &lt;math&gt;k&gt;1&lt;/math&gt;, we construct the diagonals of equal length &lt;math&gt;\overline{P_0P_{2^{k-1}}}&lt;/math&gt; and &lt;math&gt;\overline{P_{2^{k-1}+1}P_0}&lt;/math&gt;. This partitions &lt;math&gt;\mathcal{P}&lt;/math&gt; into &lt;math&gt;3&lt;/math&gt; regions: an isosceles &lt;math&gt;\triangle P_0P_{2^{k-1}}P_{2^{k-1}+1}&lt;/math&gt;, and two other regions. For these two regions, we can recursively construct the isosceles triangles defined above in the second paragraph. It follows that we have constructed &lt;math&gt;2(2^{k-1}-1) + (1) = 2^k-1 = n-2&lt;/math&gt; isosceles triangles with non-intersecting diagonals, as desired. <br /> <br /> &lt;center&gt;&lt;asy&gt;<br /> defaultpen(linewidth(0.7)+fontsize(10));<br /> int n = 17; real r = 1; real rad = pi/2;<br /> <br /> pair pt(real k=0) {<br /> return (r*expi(rad-2*pi*k/n));<br /> }<br /> <br /> for(int i=0; i&lt;n; ++i){<br /> dot(pt(i));<br /> draw(pt(i)--pt(i+1));<br /> }<br /> <br /> /* could rewrite recursively, if someone wants to do .. */<br /> draw(pt(8)--pt()--pt(9));<br /> draw(pt()--pt(4)--pt(8));<br /> draw(pt()--pt(2)--pt(4));<br /> draw(pt()--pt(1)--pt(2));<br /> draw(pt(2)--pt(3)--pt(4));<br /> draw(pt(4)--pt(6)--pt(8));<br /> draw(pt(4)--pt(5)--pt(6));<br /> draw(pt(6)--pt(7)--pt(8));<br /> draw(pt(9)--pt(13)--pt(17));<br /> draw(pt(9)--pt(11)--pt(13));<br /> draw(pt(9)--pt(10)--pt(11));<br /> draw(pt(11)--pt(12)--pt(13));<br /> draw(pt(13)--pt(15)--pt(17));<br /> draw(pt(13)--pt(14)--pt(15));<br /> draw(pt(15)--pt(16)--pt(17));<br /> <br /> label(&quot;$$P_0$$&quot;,pt(),N);<br /> label(&quot;$$P_1$$&quot;,pt(1),NNE);<br /> label(&quot;$$P_{16}$$&quot;,pt(-1),NNW);<br /> label(&quot;$$\cdots$$&quot;,pt(2),NE);<br /> &lt;/asy&gt;&lt;br /&gt;&lt;span style=&quot;font-size:85%&quot;&gt;An example for &lt;math&gt;n=17 = 2^{4}+1&lt;/math&gt;&lt;/span&gt;&lt;/center&gt;<br /> <br /> *''Lemma 2'': If a regular polygon with &lt;math&gt;n&lt;/math&gt; sides has a working triangulation, then the regular polygon with &lt;math&gt;2n&lt;/math&gt; sides also has a triangulation that meets the conditions.<br /> We construct the diagonals &lt;math&gt;\overline{P_0P_2},\ \overline{P_2P_4},\ \ldots \overline{P_{2n-2}P_0}&lt;/math&gt;. This partitions &lt;math&gt;\mathcal{P}&lt;/math&gt; into &lt;math&gt;n&lt;/math&gt; isosceles triangles of the form &lt;math&gt;\triangle P_{2k}P_{2k+1}P_{2k+2}&lt;/math&gt;, as well as a central regular polygon with &lt;math&gt;n&lt;/math&gt; sides. However, we know that there exists a triangulation for the &lt;math&gt;n&lt;/math&gt;-sided polygon that yields &lt;math&gt;n-2&lt;/math&gt; isosceles triangles. Thus, we have created &lt;math&gt;(n) + (n-2) = 2n-2&lt;/math&gt; isosceles triangles with non-intersecting diagonals, as desired. <br /> <br /> &lt;center&gt;&lt;asy&gt;<br /> defaultpen(linewidth(0.7)+fontsize(10));<br /> int n = 10; real r = 1; real rad = pi/2;<br /> <br /> pair pt(real k=0) {<br /> return (r*expi(rad-2*pi*k/n));<br /> }<br /> <br /> for(int i=0; i&lt;n; ++i){<br /> dot(pt(i));<br /> draw(pt(i)--pt(i+1));<br /> }<br /> <br /> draw(pt()--pt(2)--pt(4)--pt(6)--pt(8)--cycle);<br /> draw(pt()--pt(4)--pt(6)--cycle,linewidth(0.5)+linetype(&quot;4 4&quot;));<br /> <br /> label(&quot;$$P_0$$&quot;,pt(),N);<br /> label(&quot;$$P_1$$&quot;,pt(1),NNE);<br /> label(&quot;$$P_{2}$$&quot;,pt(2),NE);<br /> label(&quot;$$P_{3}$$&quot;,pt(3),E);<br /> label(&quot;$$P_{4}$$&quot;,pt(4),SE);<br /> label(&quot;$$P_{5}$$&quot;,pt(5),S);<br /> label(&quot;$$P_{6}$$&quot;,pt(6),SW);<br /> label(&quot;$$P_{7}$$&quot;,pt(7),W);<br /> label(&quot;$$P_{8}$$&quot;,pt(8),NW);<br /> label(&quot;$$P_{9}$$&quot;,pt(9),NNW);<br /> <br /> &lt;/asy&gt;&lt;br /&gt;&lt;span style=&quot;font-size:85%&quot;&gt;An example for &lt;math&gt;n=10,\, n/2 = 5&lt;/math&gt;&lt;/span&gt;&lt;/center&gt;<br /> <br /> In summary, the answer is all &lt;math&gt;n&lt;/math&gt; that can be written in the form &lt;math&gt;2^{a+1} + 2^{b},\, a,b \ge 0&lt;/math&gt;. Alternatively, this condition can be expressed as either &lt;math&gt;n=2^{k},\, k \ge 2&lt;/math&gt; (this is the case when &lt;math&gt;a+1 = b&lt;/math&gt;) or &lt;math&gt;n&lt;/math&gt; is the sum of two distinct powers of &lt;math&gt;2&lt;/math&gt;, where &lt;math&gt;1= 2^0&lt;/math&gt; is considered a power of &lt;math&gt;2&lt;/math&gt;. <br /> <br /> <br /> <br /> {{alternate solutions}}<br /> <br /> == See also ==<br /> * &lt;url&gt;viewtopic.php?t=202905 Discussion on AoPS/MathLinks&lt;/url&gt;<br /> <br /> {{USAMO newbox|year=2008|num-b=3|num-a=5}}<br /> <br /> [[Category:Olympiad Combinatorics Problems]]<br /> {{MAA Notice}}</div> Leonardo von einzbern https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&diff=73626 2011 USAMO Problems/Problem 6 2015-12-12T15:46:11Z <p>Leonardo von einzbern: /* 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 /> {{MAA Notice}}<br /> <br /> ==See also==<br /> *[[USAMO Problems and Solutions]]<br /> <br /> {{USAMO newbox|year=2011|num-b=5|aftertext=|after=Last Problem}}</div> Leonardo von einzbern