tag:blogger.com,1999:blog-28917254394297643352023-01-25T20:35:03.173-05:00IMO MathMost math olympiad solutions you see aren't intuitive and informative. In this blog, I post intuitive and detailed solutions to math olympiad problems, which helps the reader understand where the solution came from and how to think of it themselves. Because after all, give a man a fish and you feed him for a day; teach a man to fish and you feed him for a lifetime. It will show 10 posts per page. To view more, click "More Posts" at the bottom of the page.IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.comBlogger149125tag:blogger.com,1999:blog-2891725439429764335.post-30094469424036117672022-12-06T08:39:00.003-05:002022-12-07T10:18:52.739-05:002014 IMO SL #C2<p>&nbsp;<b>Problem</b>:&nbsp;We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ .</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p><b>Solution</b>:&nbsp;Consider the product of all the terms. Notice that due to the inequality$$(a+b)^2 \geq 4ab$$, the product&nbsp;scales up by a factor of at least four every time we perform the operation. It follows that after $m2^{m-1}$ steps, the product would be at least $4^{m2^{m-1}}$. By the AM-GM inequality, we have&nbsp;$$\sum_{i=1}^{2^m} a_i \geq 2^m \sqrt[2^m]{2^{m 2^m}} = (2^m)^2 = 4^m,$$ as desired. $\square$</p><p><br /></p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-24558328705311962612022-11-25T20:08:00.004-05:002022-11-25T20:08:50.120-05:002009 IMO SL #C1<p><b>Problem</b>:&nbsp;Consider $2009$ cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. (a) Does the game necessarily end? (b) Does there exist a winning strategy for the starting player?</p><p><br /></p><p><span></span></p><a name='more'></a><br /><p></p><p><b>Solution</b>:</p><p>&nbsp;(a) Consider the row of cards to be a binary number, with a card showing its gold side representing a $1$ and a card showing its black side representing a $0$. We see that since the leftmost card of every move has to be gold, applying a move always decreases our number. Therefore, since we clearly can't go to negative numbers, the game can only have finitely many moves, and therefore does eventually end. $\square$&nbsp;</p><p>(b) Label the bits $1, 2, \cdots, 2009$ from right to left. Now, consider the bits that have a label that is divisible by $50$ (i.e. bits $50, 100, \cdots, 2000$). There are $40$ such bits, and we see that each one needs to be toggled an odd number of times for the game to end. However, the sum of $40$ odd numbers will be even, so the game must end in an even number of moves. This implies that player $2$ must make the last move of the game, so player $1$ does $\textit{not}$ have a winning strategy. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-72058658448642568202022-10-23T10:42:00.003-04:002022-11-16T16:39:48.586-05:001998 USAMO #3<p><b>Problem</b>: Let $a_0,a_1,\cdots ,a_n$ be numbers from the interval $(0,\pi/2)$ such that$\tan (a_0-\frac{\pi}{4})+ \tan (a_1-\frac{\pi}{4})+\cdots +\tan (a_n-\frac{\pi}{4})\geq n-1.&nbsp;$Prove that$\tan a_0\tan a_1 \cdots \tan a_n\geq n^{n+1}.&nbsp;$</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p><b>Solution</b>:&nbsp;Denote $x_i$ as $\tan(a_i - \frac{\pi}{4})$. We now write $\tan a_i$ as $\tan(a_i - 45^{\circ} + 45^{\circ})$. By the $\tan(a+b)$ formula, we know that this is equivalent to $$\frac{x_i + 1}{1 - x_i}.$$ If we let $y_i = \frac{1 - x_i}{2} \in (0,1)$, then it suffices to prove that if $\sum_0^n y_i \le 1$ and $y_i \ge 0$, then $\prod_{i=1}^n \left( \frac{1}{y_i}-1 \right) \ge n^{n+1}.$</p><p>It is easy to show this. Homogenizing the inequality, we must show&nbsp;</p><p>$$\prod_{i=1}^n \left( \frac{y_0+y_1+y_2+\dots+y_n}{y_i}-1 \right) \ge n^{n+1},$$</p><p>and by AM-GM, $$\frac{y_1+y_2+y_3+\dots+y_n}{y_0}\ge n \sqrt[n]{\frac{y_1y_2y_3\dots y_n}{y_1}},$$ from which we can simply cyclically product. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-39838274520088141082022-10-23T10:18:00.003-04:002022-11-17T16:12:03.583-05:002022 USEMO #3<p>Point $P$ lies in the interior of a triangle $ABC$. Lines $AP$, $BP$, and $CP$ meet the opposite sides of triangle $ABC$ at $A$', $B'$, and $C'$ respectively. Let $P_A$ the midpoint of the segment joining the incenters of triangles $BPC'$ and $CPB'$, and define points $P_B$ and $P_C$ analogously. Show that if $AB'+BC'+CA'=AC'+BA'+CB'$then points $P,P_A,P_B,$ and $P_C$ are concyclic.&nbsp;</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p>Let $$X_A$$, $$X_B$$, $$X_C$$ be the projections of $$P_A$$, $$P_B$$, $$P_C$$ onto $$\overline{BB'}$$, $$\overline{CC'}$$, $$\overline{AA'}$$, respectively. Then$PX_A=\tfrac14(BP+PC'-C'B)-\tfrac14(B'P+PC-CB'),$so (with lengths appropriately directed) we have $$PX_A+PX_B+PX_C=0$$. Let $$\alpha=\angle BPP_A$$, and similarly define $$\beta$$ and $$\gamma$$, so $$\alpha+\beta+\gamma=90^\circ$$. Let $$P_A'$$, $$P_B'$$, $$P_C'$$ be the inverses of $$P_A$$, $$P_B$$, $$P_C$$ about $$P$$ with radius 1. Then\begin{align*}&nbsp; &nbsp; &nbsp;\operatorname{Area}(\triangle P_A'P_B'P_C') &amp;=\sum_\mathrm{cyc}\operatorname{Area}(\triangle PP_B'P_C') =\sum_\mathrm{cyc} PP_B'\cdot PP_C'\cdot\sin(\alpha+\beta)\\ &amp;=\sum_\mathrm{cyc}\frac{\cos\alpha}{PX_B}\cdot\frac{\cos\beta}{PX_C}\cdot\cos\gamma =\frac{\cos\alpha\cos\beta\cos\gamma}{PX_A\cdot PX_B\cdot PX_C}\cdot\sum_\mathrm{cyc} PX_A=0. \end{align*}It follows that $$P_A'$$, $$P_B'$$, $$P_C'$$ are collinear, as desired. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-55314246831769946892022-10-20T09:48:00.000-04:002022-10-20T09:48:59.133-04:002019 IMO SL #A5<p><b>Problem</b>: Let $x_1, x_2, \dots, x_n$ be different real numbers. Prove that $\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}=\left\{\begin{array}{ll} 0, &amp; \text { if } n \text { is even; } \\ 1, &amp; \text { if } n \text { is odd. } \end{array}\right.$</p><p><b><br /></b></p><p><b>Solution 1 (induction)</b>:&nbsp;We induct on $n$, and the base case is trivial. Now for any $n &gt; 2,$ define the multivariable rational function$$\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}} = A_n(x_1, \dots x_n)$$and the multivariable polynomial$$B_n(x_1, \dots x_n) = \prod_{i&lt;j}(x_i-x_j)(A_n - (\text{n's remainder mod 2})).$$This polynomial has at most degree $\binom{n}{2} + (n-1).$ But for every $x_i,$ we know $x_i - 1$ and $x_i+1$ divide $B_n$ by the inductive hypothesis, as well as all the terms of the form $x_i-x_j.$ That yields $\binom{n}{2} + 2n$ terms dividing $B_n,$ more than its degree. So $B_n$ is a zero polynomial as desired. $\square$</p><p><br /></p><p><b>Solution 2 (Lagrange Interpolation)</b>: Let $F$ be the value of the expression in the problem. We will work with the polynomial $$P(X) \stackrel {\text {def}}{:=} \prod_{i=1}^n(1-xx_i).$$ Note that $P(x_i) = (1-x_i^2) \textstyle \prod_{j\neq i} (1-x_ix_j)$. We will use Lagrange interpolation on $P(X)$ with the points (aka nodes) $x_1,x_2,\dots,x_n,1,-1$. We get $$P(X) = \sum_{i=1}^n P(x_i)\cdot \frac {(x^2-1)}{(x_i^2-1)} \prod_{j\neq i} \frac {(x-x_j)} {(x_i-x_j)} + \frac {P(1)}{2} (x+1) \prod_{j= 1}^n \frac {(x-x_j)} {(1-x_j)} +(-1)^{\frac {n+1}{2}} \frac {P(-1)}{2} (x-1) \prod_{j= 1}^n \frac {(x-x_j)} {(1+x_j)}.$$ Now, because $P(x)$ has degree $n$, we know that the coefficient of $x^{n+1}$ is $0$. Equating the coefficient of $x^{n+1}$ in the above expression, we obtain $$0= P(x_i)\cdot \frac {(x^2-1)}{(x_i^2-1)} \prod_{j\neq i} \frac 1{(x_i-x_j)}&nbsp; + \frac {P(1)}{2} \prod_{j= 1}^n \frac 1{(1-x_j)} + (-1)^{\frac {n+1}{2}} \frac {P(-1)}{2} \prod_{j= 1}^n \frac 1{(1+x_j)}$$$$\implies 0=-F + \frac 12 + (-1)^{n+1} \frac 12,$$and this completes the proof. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-32411474605270186972022-10-15T11:41:00.004-04:002022-10-15T11:45:03.614-04:002019 ISL #C7<p>&nbsp;There are 60 empty boxes $B_1,\ldots,B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game. In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer $k$ with $1\leq k\leq 59$ and splits the boxes into the two groups $B_1,\ldots,B_k$ and $B_{k+1},\ldots,B_{60}$. (b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group. Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning.</p><p><br /></p><span><a name='more'></a></span><h1 style="text-align: left;"><b>Solution 1:</b></h1><p>The answer is $31+30+\dots+2+1+2+\dots+30 = \boxed{960}$.</p><p><b>Strategy for Alice (sufficiency):</b></p><p>Distribute the pebbles in the order $31,30, \dots 2,1,2, \dots , 30$ from left to right. Suppose Bob chooses an integer $k \ge 31,$ add to $B_1,\ldots,B_k$ if this is the $2n-1$th time Bob has made this choice for an integer $n.$ Otherwise, add to $B_{k+1},\ldots,B_{60}$. We can now assume that each integer has been toggled at most once, and it is easy to verify her strategy works.</p><p><br /></p><p><b>Strategy for Bob (necessity):</b></p><p>Suppose for a positive integer $k$ there are $2k$ boxes with at most $k$ each. We claim Bob can win.</p><p><br /></p><p>First, Bob does a $k, k$ split. Assume WLOG Alice adds to the left.</p><p><br /></p><p>Now do a $k+1, k-1$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+1$th box has one less pebble and the rest of the boxes are unaffected.</p><p><br /></p><p>Otherwise Alice adds to the left again. Now do a $k+2, k-2$ split. If Alice adds to the right, then the net effect after the last two rounds is that the $k+2$th box has one less pebble and the rest of the boxes are unaffected.</p><p><br /></p><p>Otherwise Alice adds to the left again. Now do a $k+3, k-3$ split, a $k+4, k-4$ split, and so on. Bob will continue performing moves in this way, and each time we may assume Alice adds to the left (otherwise she worsens her position). By the time he completes the $2k-1$ split, the rightmost box will be empty.</p><p><br /></p><p>If Bob cannot win, than for any positive integer $k &lt; 60$ there are at least $60-2k+1$ boxes contain more than $k$ (and obviously each box has at least one pebble); so we need at least $60+59+57+ \cdots + 1 = 960$ pebbles.</p><p>We are done. $\square$</p><h1 style="text-align: left;"><b>Solution 2:&nbsp;</b></h1><p>The answer is $\boxed{960}$.</p><p>Generalize to $n$ boxes where $n$ is even. The answer is $(n/2 + 1)^2 - 1$, which is 960 when $n = 60$. Let box $B_i$ have $b_i$ coins.&nbsp;</p><p><b>Claim:</b> If Alice can avoid the game ending, then for all $x,y$ with $1 \leq x,y \leq n$, we must have $b_x + b_y \geq |x-y+2|$.&nbsp;</p><p><b>Proof: </b>We show the contrapositive. WLOG, $x = 1$ and $y = n$, since we won't need the other boxes. Then we want to show that $b_1 + b_n \leq n$ implies Bob can win. We'll have Bob split the boxes at $k = b_1$ each move. We claim that regardless of Alice's choice, $S = b_1(n - b_1) + T$ decreases by one each move, where $T$ is the total number of coins in all the boxes from $B_1$ to $B_n$. To show this, we just compute how $S$ changes for each of Alice's options, and the arithmetic is easily checked. Since $S \geq b_1b_n + T$, $S$ is always positive while the game is being played. But since $S$ decreases by one each move, it cannot always stay positive, so Bob must eventually win. We have proved the claim.</p><p>The claim implies that if Alice can survive, then $i = 1, 2, \ldots, n/2$, $b_i + b_{2n+1-i} \geq 2n+3-2i$. Therefore, $\sum_{i=1}^{n} b_i \geq \sum_{i=1}^{n/2} (2n+3-2i) = (n/2 + 1)^2 - 1.$So Alice needs to place at least $(n/2 + 1)^2 - 1$ coins, as we claimed.&nbsp;</p><p>We now show this many coins are enough. Alice will place $n+1, n, n-1, \ldots, 2$ coins in the first $n$ boxes and $1, 2, 3, \ldots, n$ coins in the last $n$ boxes, which gives the right total. Alice will also mark $m = n+1$ as the pivot, which will change over time, and maintain the invariant that each box $i$ will have at least $|i-m| + 1$ coins. When Alice has to make a move, she will always increase the number of coins in the pivot. Moreover, if Alice added a coin to box 1, she decreases the pivot $m$ by one, and otherwise she increases the pivot $m$ by one. It is easy to check that this will maintain the invariant, which shows that she can keep every box from being emptied. $\square$</p><p><br /></p><h1 style="text-align: left;">Remarks</h1><div>This was a somewhat unique problem. The first solution was standard, but the second solution was very short and sweet.&nbsp;</div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-88011544132134983202022-10-10T10:36:00.002-04:002022-10-10T10:36:26.981-04:002019 IMC #3<p><b>Problem</b>: Let $f:(-1,1)\to \mathbb{R}$ be a twice differentiable function such that $$2f’(x)+xf''(x)\geqslant 1 \quad \text{ for } x\in (-1,1).$$Prove that $$\int_{-1}^{1}xf(x)dx\geqslant \frac{1}{3}.$$</p><p><br /></p><p><b>Solution 1</b>:&nbsp;The LHS of the original inequality looks like the result of an application of the product rule. Indeed, the derivative of $f'g$ is $g'f'+gf''$. We cannot make $g=x$ and $g'=2$, but we can multiply by $x$ to get $g=x^2, g'=2x$. Now to do this we need to be careful about the sign of $x$. So, suppose that $x &gt; 0$. Then $2xf'(x)+x^2f''(x) \ge x$ and hence $(x^2f')' \ge x$ so that $x^2f'(x) \ge \frac{1}{2} x^2$ and hence $f'(x) \ge \frac{1}{2}$. Similarly, we know that $f'(x)\ge \frac{1}{2}$ for $x &lt; 0$, so we have proved this for all $x$ (for $x=0$ by continuity or by just plugging in $x=0$ into the original inequality). The rest is easy. WLOG, assume that $f(0)=0$ since shifting $f$ by a constant changes neither the integral nor the condition on the derivatives (here we make use of $\int_{-1}^1 xdx=0$). Then $f(x) \ge \frac{x}{2}$ for $x\ge 0$ and $f(x)\le \frac{x}{2}$ for $x&lt;0$ so that $xf(x) \ge \frac{x^2}{2}$ for all $x$ and we have $\int_{-1}^1 xf(x) dx \ge \int_{-1}^1 \frac{x^2}{2} dx=\frac{1}{3},$ as desired. $\square$</p><p><br /></p><p><b>Solution 2</b>: Let $g(x)=xf(x)-\frac{x^2}{2}$. Then, we have $g''(x) \ge 0$. So, note that&nbsp;$$\int_{-1}^{1}g(x)dx\geq 2\cdot g\left(\frac{1+(-1)}{2}\right)=0$$</p><p>$$\implies \int_{-1}^{1}xf(x)dx\geqslant \int_{-1}^{1}\frac{x^2}{2}=\frac{1}{3},$$ as desired. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com1tag:blogger.com,1999:blog-2891725439429764335.post-48179208882518341892022-10-01T10:51:00.006-04:002022-10-01T10:51:49.348-04:002012 IMO SL #G6<p>&nbsp;<b>Problem:&nbsp;</b>Let $ABC$ be a triangle with circumcenter $O$ and incenter $I$. The points $D,E$ and $F$ on the sides $BC,CA$ and $AB$ respectively are such that $BD+BF=CA$ and $CD+CE=AB$. The circumcircles of the triangles $BFD$ and $CDE$ intersect at $P \neq D$. Prove that $OP=OI$.</p><p><br /></p><p><b>Solution 1:&nbsp;</b>Let circle with radius $OI$ intersect $BI, CI$ at $S, T \ne I$ respectively. Let $H$ be the foot of $S$ to $AB$ and let $BI$ meet $(ABC)$ at $M \ne A.$ It's known that if any circle passing through $S,B$ intersects $BC,BA$ at $D',F'$ respectively then $BD'+BF' = 2BH.$ But$$BH = BS \cdot \cos \left(\frac{1}{2} \angle ABC \right) = IM \cdot \cos \left(\frac{1}{2} \angle ABC \right) = MA \cdot \cos \left(\frac{1}{2} \angle ABC \right) = \frac{1}{2}AC$$so in fact $BFSD$ cyclic, similarly $CDTE$ cyclic. Then$$\angle TPS = 360^\circ - \angle TPD - \angle SPD = \frac{1}{2} \angle ABC&nbsp; + \frac{1}{2} \angle ACB = \angle TIS$$so $P$ lies on $(TIS)$ centered at $O,$ done. $\square$</p><p><br /></p><p><b>Solution 2:&nbsp;</b>Let $\Gamma$ be the circumcircle of $ABC$, and let $\omega_a = (AEF)$, $\omega_b = (BFD)$, $\omega_c = (CDE)$. We'll show that $\text{Pow}(P, \Gamma) = \text{Pow}(I, \Gamma)$ with barycentric coordinates. Let $BD = p$ and $CD = q$, with $p + q = a$. Then we have $BF = b - p$ and $AF = c - b + p$, while $CE = c - q$ and $AE = b - c + q$. Now because $u$ is the power of $A$ to the circle $[u, v, w]$ we have $\omega_a = [0, c(b - p), b(c - q)]$, and $\omega_b = [c(c - b + p), 0, aq]$ and $\omega_c = [b(b - c + q), ap, 0]$. By Miquel's Theorem $P$ is on all three circles, so $P$ is the intersection of the radical axes of $(\omega_a, \omega_b)$ and $(\omega_a, \omega_c)$. This means it satisfies$-c(c - b + p)x + c(b - p)y + (b(c - q) - aq)z = 0$and its symmetric counterpart$-b(b - c + q)x + (c(b - p) - ap)y + b(c - q)z = 0.$On the other hand, we have $\text{Pow}(P, \Gamma) = \text{Pow}(P, \Gamma) - \text{Pow}(P, \omega_a) = -c(b - p)y - b(c - q)z$if $P$ is homogenized, while$\text{Pow}(I, \Gamma) = -2Rr = -\frac{abc}{2K}\cdot \frac{K}{s} = -\frac{abc}{a + b + c},$so we want to show$\frac{c(b - p)y + b(c - q)z}{x + y + z} = \frac{abc}{a + b + c}.$This rearranges to$-abcx + c(b^2 + bc - p(a + b + c))y + b(c^2 + bc - q(a + b + c))z = 0.$But this equation is $b$ times the first equation plus $c$ times the second, so since $P$ satisfies both of those equations, it must satisfy this one as well. $\square$</p><p><br /></p><p><b>Solution 3:&nbsp;</b>Let $\omega$ be the circle centered at $O$ with radius $OI$. Notice that $AF+AE=BD+DC=BC$, hence the problem is symmetric about $A,B,C$. Let $A_1,A_2$ be the second intersection of $AI$ with $\omega$ and $(AFE)$ respectively. Let $M$ be the projection of $O$ on $AA'$, then $$AA_1=2AM-AI=2R\sin\angle OAI-4R\sin\frac{B}{2}\sin\frac{C}{2}=2R\sin\frac{B-C}{2}-4R\sin\frac{B}{2}\sin\frac{C}{2}=2R\sin\frac{A}{2}$$Meanwhile, by Ptolemy's theorem, $$AA_2=\frac{(AF+AE)\cdot AF}{FE}=BC\cdot\frac{AF}{FE}=\frac{2R\sin A\sin\frac{A}{2}}{\sin A}=2R\sin\frac{A}{2}=AA_1$$Hence $A_1=A_2$, denote this common point by $A'$, define $B'$ and $C'$ symmetrically. We finish the problem by directly applying Miquel's theorem to triangle $BIC$ and points $B',C',D$. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com1tag:blogger.com,1999:blog-2891725439429764335.post-55554125890979863752022-09-26T13:33:00.001-04:002022-10-01T10:48:06.841-04:002021 IMO SL #A1<p><b>Problem:&nbsp;</b>Let $n$ be a positive integer. Given is a subset $A$ of $\{0,1,...,5^n\}$ with $4n+2$ elements. Prove that there exist three elements $a&lt;b&lt;c$ from $A$ such that $c+2a&gt;3b$.</p><p><b><br /></b></p><p><b>Solution:&nbsp;</b></p><p>Suppose for the sake of contradiction that $c+2a\le 3b$ for all $a,b,c\in A$ with $a&lt;b&lt;c$.&nbsp;</p><p>We claim that if the elements of $A$ are $s_1&lt;s_2&lt;\dots&lt;s_{4n+2}$, then $$s_i\ge s_{4n+2}(1-(\tfrac{2}{3})^{i-1})$$ for all $i$. We use induction to prove this -- the base case is trivially true because $s_1\geq 0$. As for the inductive step, consider $s_k.$ Take $(a,b,c)=(s_{k-1},s_k,s_{4n+2})$; by our assumption, we have $$s_{4n+2}+2s_{k-1}\ge 3s_k.$$ Therefore, $$s_k\ge\frac{s_{4n+2}+2s_{k-1}}{3}\ge\frac{s_{4n+2}+2(s_{4n+2}(1-(\tfrac{2}{3})^{k-2}))}{3}=\frac{s_{4n+2}(3-2(\tfrac{2}{3})^{k-2})}{3}=s_{4n+2}(1-(\tfrac{2}{3})^{k-1}),$$ which completes the induction.&nbsp;</p><p><br /></p><p>Now, using our claim, we have $$s_{4n+1}\ge s_{4n+2}(1-(\tfrac{2}{3})^{4n})=s_{4n+2}-(\tfrac{16}{81})^{n}s_{4n+2}&gt;s_{4n+2}-(\tfrac{1}{5})^{n}5^n=s_{4n+2}-1,$$ which is impossible because $s_{4n+1}$ is an integer less than $s_{4n+2}$.&nbsp;</p><p>We are done. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-67188115007438268712022-09-20T17:32:00.006-04:002022-09-26T11:26:50.258-04:002017 USAJMO #3<p>Let $ABC$ be an equilateral triangle, and point $P$ on its circumcircle. Let $PA$ and $BC$ intersect at $D$, $PB$ and $AC$ intersect at $E$, and $PC$ and $AB$ intersect at $F$. Prove that the area of $\triangle DEF$ is twice the area of $\triangle ABC$.</p><p><br /></p><p><b>Solution 1:&nbsp;</b></p><p>Note that $$\angle{DPF}=\angle{FPE}=\angle{EPD}=120^{\circ}.$$ Now, using the sin area formula, we get $$[DEF]=[DPF]+[FPE]+[EPD]=\frac{\sqrt{3}}{4}\left(DP \cdot FP+FP \cdot EP+EP \cdot DP\right).$$We also have that $$[ABC]=BC^2 \cdot \frac{\sqrt{3}}{4}.$$ So, it suffices to prove $$\frac{\sqrt{3}}{4}\left(DP \cdot FP+FP \cdot EP+EP \cdot DP\right)=2 \cdot \frac{BC^2\sqrt{3}}{4} \implies DP \cdot FP+FP \cdot EP+EP \cdot DP=2BC^2.$$By the Law of Cosines on $\triangle{BPC}$, we obtain $$BC^2=b^2+c^2-2 \cdot b \cdot c \cdot \cos{120^{\circ}}=b^2+c^2+bc,$$ and Ptolemy's Theorem on quadrilateral $ABPC$ gives$$AP \cdot BC=BP \cdot AC+CP \cdot AB \implies AP=b+c.$$From some angle chasing, we know that $\triangle{ACD} \sim \triangle{APC}$, and therefore $$\frac{AC}{AP}=\frac{CD}{PC}=\frac{AD}{AC} \implies AC^2=AD \cdot AP=AD(b+c) \implies AD=\frac{b^2+bc+c^2}{b+c}.$$So, we have $$PD=AP-AD=b+c-\left(\frac{b^2+bc+c^2}{b+c}\right)=\frac{bc}{b+c}.$$Now, from angle chasing again, we see that $$\triangle{FBP} \sim \triangle{ACP} \implies \frac{FB}{AC}=\frac{BP}{CP}=\frac{FP}{AP} \implies FP=\frac{BP}{CP} \cdot AP=\frac{b(b+c)}{c},$$ and similarly $EP=\frac{c(b+c)}{b}.$ Thus, we finally have&nbsp;</p><p>$$DP \cdot FP+FP \cdot EP+EP \cdot DP=\frac{bc}{b+c} \cdot \frac{b(b+c)}{c}+\frac{b(b+c)}{c} \cdot\frac{c(b+c)}{b}+\frac{c(b+c)}{b} \cdot \frac{bc}{b+c}$$</p><p>$$=b^2+(b+c)^2+c^2=2b^2+2bc+2c^2=2(b^2+bc+c^2)=2 \cdot BC^2,$$ as desired. $\square$</p><p><br /></p><p><b>Solution 2:&nbsp;</b></p><p>There is a solution with barycentric coordinates, which should be pretty obvious if you know the technique. Regardless, I will upload this solution when I have time.</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-86943183381962042382022-09-11T21:25:00.008-04:002022-10-09T19:09:11.089-04:002000 Putnam A1<p><b>Problem: </b>Let $A$ be a positive real number. What are the possible values of $$\sum_{j=0}^{\infty} x_j^2,$$ given that $x_0,x_1,\dots$ are positive numbers for which $$\sum_{j=0}^{\infty}=A?$$</p><p><br /></p><p><b>Solution:&nbsp;</b>The answer is $\boxed{(0,A^2)}$. \\ There are two things we need to prove: first, that the possible values of $\sum_{j=0}^{\infty} x_j^2$ must lie in the interval $(0,A^2)$, and second, all values in this interval can be achieved. \\ For our first problem, the values are obviously positive. Also, note that $$\sum_{j=0}^{\infty} \frac{x_j}{A}=1,$$ and because $x_j&gt;0$, we must have $$0 &lt;&nbsp; \frac{x_j}A&nbsp; &nbsp;&lt; 1,$$ which implies that $$\left(\frac{x_j}A\right)^2&nbsp; &nbsp;&lt;&nbsp; \frac{x_j}A&nbsp; ,$$$$\implies \sum_{j=0}^{\infty}\left(\frac{x_j}A\right)^2&nbsp; &nbsp;&lt;&nbsp; \sum_{j=0}^{\infty}\left(\frac{x_j}A\right)&nbsp; &nbsp;= 1.$$Multiplying by $A^2$, we get $$\sum_{j=0}^{\infty}x_j^2 &lt; A^2.$$ \\ Now, for the second part, let the sequence of $x_j$'s be a geometric sequence with ratio $r$. Then, we have $$\sum_{j=0}^{\infty}x_j=\frac{x_0}{1-r},$$ so \begin{align*} &amp;\sum_{j=0}^{\infty}x_j^2\\ &amp;=\frac{x_0^2}{1-r^2}\\ &amp;=\left (\frac{1-r}{1+r}\right )\left (\sum_{j=0}^{\infty} x_j \right )^2.\\ &amp;=\left (\frac{1-r}{1+r}\right ) A^2. \end{align*}Now, notice that we can make $\frac{1-r}{1+r}$ take on any value in the range $(0,1)$ by taking the appropriate value of $r$ in $(0,1)$. In particular, $x=\frac{1-r}{1+r}$ implies $r=\frac{1-x}{1+x}$. As $r$ goes from $0$ to $1$, the fraction goes from $1$ to $0$. This proves that that all values in the interval $(0,A^2)$ can be achieved. \\ We have proved both sub-problems, and we are done. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-31773278452349514842022-09-11T21:13:00.004-04:002022-09-11T21:23:09.267-04:00Occasional Putnam problems<p>Starting now, I will occasionally post Putnam problems on this blog. However, the main content will still be IMO Problems.&nbsp;</p><p>These problems will be under the tag #putnam.</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-575050696318446782022-08-29T13:55:00.006-04:002022-08-30T11:03:48.275-04:002006 IMO #G3<p>Let $ABCDE$ be a convex pentagon such that $\angle BAC = \angle CAD = \angle DAE\qquad \text{and}\qquad \angle ABC = \angle ACD = \angle ADE.$The diagonals $BD$ and $CE$ meet at $P$. Prove that the line $AP$ bisects the side $CD$.</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p><b>Solution 1:</b></p><p>Note that $\triangle ABC \sim \triangle ADE \sim \triangle ACD$ from AA, so $\frac{BC}{DC}=\frac{AC}{AD}=\frac{CD}{DE}$ as well as $\angle BCD = \angle CDE$, so $\triangle CBD \sim \triangle DCE$. Let $DB \cap AC = Q, EC \cap AD = R$. Then from Ceva's Theorem, it suffices to show that $\triangle ARQ \sim \triangle ADC$. We also have $\angle CBM = \angle DCE$, so we get $\triangle DRC \sim \triangle CQB$. This means that $\frac{BC}{DC}=\frac{QC}{RD}=\frac{AC}{AD}$, so $\triangle ARQ \sim \triangle ADC$, as desired. $\square$</p><p><br /></p><p><br /></p><p><br /></p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-30692545108981889062022-08-21T17:47:00.001-04:002022-08-21T17:47:21.326-04:00Problem request: 2022 AIME II #13Hi everyone,&nbsp;<div><br /></div><div>I hope you had a great summer!&nbsp;</div><div>I was not posting for about a month or so because not many people were viewing the blog in the summer.&nbsp;</div><div><br /></div><div>I'm going to start to post frequently again, and for now I have a problem request I got a couple days ago.&nbsp;</div><div><br /></div><div><br /></div><div><br /></div><div>There is a polynomial $P(x)$ with integer coefficients such that$P(x)=\frac{(x^{2310}-1)^6}{(x^{105}-1)(x^{70}-1)(x^{42}-1)(x^{30}-1)}$holds for every $0&lt;x&lt;1.$ Find the coefficient of $x^{2022}$ in $P(x)$.</div><div><br /></div><div><br /></div><span><a name='more'></a></span><div><br /></div><div><br /></div><div><br /></div><div>Note that $$\tfrac{x^{mn}-1}{x^n-1}=x^{(m-1)n}+x^{(m-2)n}+\dots+x^n+1.$$ Then</div><div>$$P(x)=(x^{21\cdot105}+x^{20\cdot105}+\dots+x^{105}+1)(x^{32\cdot70}+x^{31\cdot70}+\dots+x^{70}+1)$$&nbsp;</div><div>$$(x^{54\cdot42}+x^{53\cdot42}+\dots+x^{53}+1)(x^{76\cdot30}+x^{75\cdot30}+\dots+x^{30}+1)(x^{2310}-1)^2.$$</div><div><br /></div><div>We want to compute the number of ways to choose a term from each of the $6$ factors above such that the product of all $6$ terms is $x^{2022}$. A term from the first factor is of the form $x^{105a}$, a term from the second factor is of the form $x^{70b}$, a term from the third factor is of the form $x^{42c}$, and a term from the fourth factor is of the form $x^{30d}$.&nbsp; The terms chosen from the last two factors must be $-1$, because $x^{2310}$ causes the degree of the term to already be too high.&nbsp;</div><div><br /></div><div>Now, we need to find the number of nonnegative integer solutions to the equation $$105a+70b+42c+30d=2022 \qquad \qquad \qquad (1)$$</div><div>Now, notice that $22\cdot105$, $33\cdot70$, $55\cdot42$, and $77\cdot30$ are all equal to $2310$. From this, we see that each of $105$, $70$, $42$, and $30$ aren't divisible by a prime that is divisible by the other three numbers. These $4$ primes are $2$, $3$, $5$, and $7$, and taking $(1)$ modulo each of these primes gives us $a=2a'$, $b=3b'$, $c=5c'+1$, and $d=7d'+2$. Substituting these, we obtain $$105(2a')+70(3b')+42(5c'+1)+30(7d'+3)=210a'+210b'+210c'+210d'+132=2022$$</div><div>$$\implies a'+b'+c'+d'=9.$$By Stars and Bars, the number of solutions $(a,b,c,d)$ in nonnegative integers to the above equation is $\tbinom{12}{3}=\boxed{220}$.</div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com1tag:blogger.com,1999:blog-2891725439429764335.post-81750583745036165572022-07-07T16:45:00.002-04:002022-07-07T16:46:18.866-04:002015 IMO SL #A1<p>&nbsp;Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies$a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}$for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p>We shall use induction on $n$. Taking $k=1$ gives $a_1a_2 \ge 1$. Therefore, by AM-GM, we have $a_1+a_2\ge 2$, which establishes the $n=2$ case. Rewrite the given condition as$$\frac{k}{a_{k+1}}\le a_k+\frac{k-1}{a_k}.$$Summing this from $k=1$ to $k=n$, we see$$a_1+a_2+\cdots +a_n\ge \frac{n}{a_{n+1}} \implies a_{n+1}=\frac{n}{a_1+a_2+\cdots+a_n}.$$Hence,$$a_1+a_2+\cdots +a_{n+1}\ge a_1+a_2+\cdots+a_n+\frac{n}{a_1+a_2+\cdots+a_n} \ge n+1,$$where the last step follows from the inductive step $a_1+a_2+\cdots +a_n\ge n$. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-28430683751208996552022-07-05T09:54:00.005-04:002022-07-05T09:54:47.712-04:002019 IMO SL #C1<p>&nbsp;The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and$\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k$for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p>We claim that for any $n \in \mathbb{Z},$ we have $$\{a_1, a_2, \dots a_n\} = \{0,1,\dots ,q\}\cup\{0,1, \dots ,n-q-1\},$$where $q$ is a integer.&nbsp;</p><p>We will proceed with induction.&nbsp;</p><p><br /></p><p>Base Case: If $n=0$, we must have $\{a_0\} = \{0\},$ as needed.&nbsp;</p><p>Inductive Step: Assume we have that $$\{a_1, a_2, \dots, a_{n-1}\} = \{0, 1, \dots, k\} \cup \{0, 1, \dots n-k-2\}$$for some $k$. Then, \begin{align*} 2^n &amp;= \sum_{i}\binom{n}{a_i} \\ &amp;=\left( \binom{n}{0} + \dots + \binom{n}{k} \right) + \left(\binom{n}{0} + \dots + \binom{n}{n-k-2} \right) + \binom{n}{a_n} \\ &amp;= \left(\binom{n}{0} + \dots + \binom{n}{k} \right) + \left( \binom{n}{k+2} + \dots + \binom{n}{n} \right) + \binom{n}{a_n}\\ &amp;= 2^k - \binom{n}{k+1}+\binom{n}{a_n}, \end{align*}where the third line is obtained from ${n \choose r} = {n \choose n-r},$ and the the fourth from the well-known fact that $\sum_{r=0}^{n} {n \choose r} = 2^n.$ Thus, $\binom{n}{k+1}=\binom{n}{a_n},$ and $a_n = k+1,$ or $n-k-1,$ as desired. $\square$</p><p><br /></p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-44879957325488242632022-07-04T11:15:00.003-04:002022-07-04T11:15:29.364-04:00Regarding adsHello,&nbsp;<div><br /></div><div>I have enabled ads on this blog as a fund for my future education. Please cooperate with this and if they annoy you, click the down arrow button next to the ad to hide it.</div><div><br /></div><div>Thank you!</div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com1tag:blogger.com,1999:blog-2891725439429764335.post-17792823056905233062022-07-03T08:14:00.001-04:002022-07-03T08:14:10.763-04:001995 IMO #2<p>&nbsp;Let $a$, $b$, $c$ be positive real numbers such that $abc = 1$. Prove that $\frac {1}{a^{3}\left(b + c\right)} + \frac {1}{b^{3}\left(c + a\right)} + \frac {1}{c^{3}\left(a + b\right)}\geq \frac {3}{2}.$</p><p><br /></p><span><a name='more'></a></span><p><b>Solution 1:&nbsp;</b></p><div style="text-align: left;">We have $$\sum_{\text{cyc}}\frac{1}{a^3(b+c)}=\sum_{\text{cyc}}\frac{(bc)^3}{b+c}=\sum_{\text{cyc}}\frac{(bc)^2}{\frac{b+c}{bc}}=\sum_{\text{cyc}}\frac{(bc)^2}{\frac{1}{b}+\frac{1}{c}}.$$By Titu's Lemma, we obtain that$$\sum_{\text{cyc}}\frac{(bc^2)}{\frac{1}{b}+\frac{1}{c}} \geq \frac{(ab+bc+ca)^2}{2\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)}=\frac{\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)^2}{2\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)} \qquad (\clubsuit).$$However, note that by AM-GM,$$ab+bc+ac \geq 3\sqrt{(abc)^2}=3 \implies \frac{1}{a}+\frac{1}{b}+\frac{1}{c} \geq 3$$$$\implies \frac{\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)^2}{\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)} \geq 3$$$$\implies \frac{\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)^2}{2\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)} \geq \frac{3}{2},$$which, combined with $(\clubsuit),$ gives us the result. $\square$</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Solution 2:&nbsp;</b></div><div style="text-align: left;">By Cauchy-Schwarz, we know that$$\left(\sqrt{\frac{1}{a^3(b+c)}}^2 + \sqrt{\frac{1}{b^3(a+c)}}^2 + \sqrt{\frac{1}{b^3(a+b)}}^2 \right) \left(\sqrt{a(b+c)}^2 + \sqrt{b(a+c)}^2 + \sqrt{c(a+b)}^2\right) \ge \left(\frac{1}{a} + \frac{1}{b} + \frac{1}{c}\right)^2.$$Using the fact that $abc = 1$, we know that $\left(\frac{1}{a} + \frac{1}{b} + \frac{1}{c} \right)^2 = (ab + bc + ca)^2$. So from the Cauchy-Schwarz inequality, we know that$$\left(\sqrt{\frac{1}{a^3(b+c)}}^2 + \sqrt{\frac{1}{b^3(a+c)}}^2 + \sqrt{\frac{1}{b^3(a+b)}}^2 \right) \left(\sqrt{a(b+c)}^2 + \sqrt{b(a+c)}^2 + \sqrt{c(a+b)}^2\right) \ge \frac{(ab+ bc + ac)^2}{2}.$$By AM-GM and the condition that $abc = 1$, we know that $\frac{(ab+ bc + ac)^2}{2} \ge \frac{3}{2}.$ Thus$$\frac{1}{a^3(b+c)} + \frac{1}{b^3(a+c)} + \frac{1}{c^3(a+b)} \ge \frac{3}{2}.$$</div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-83968455293585440342022-06-30T01:52:00.004-04:002022-06-30T01:52:35.328-04:001993 IMO #1<p>&nbsp;Let $n &gt; 1$ be an integer and let $f(x) = x^n + 5 \cdot x^{n-1} + 3.$ Prove that there do not exist polynomials $g(x),h(x),$ each having integer coefficients and degree at least one, such that $f(x) = g(x) \cdot h(x).$</p><p><br /></p><p><br /></p><p><b>Solution 1 (overkill):&nbsp;</b></p><p>Since $5&gt;1+3$, from Perron's Criterion this polynomial is irreducible over the integers as desired.</p><p><br /></p><p><b>Solution 2 (normal solution):</b></p><p>Assume FTSOC that there do exist $g(x), h(x)$ such that $f(x)=g(x)\cdot h(x)$. Observe that there are no integer roots of $f(x)$ from the Rational Root Theorem. Thus, $g(x), h(x)$ cannot be linear, and their degree is greater than or equal to $2$. We have $g(0)h(0)=3$. WLOG $g(0)=1$. Let $r_1, r_2, \dots r_j \in\mathbb{C}$ be the roots of $g(x)$. We have $r_1r_2\dots r_n=\pm 1$. Multiplying the equalities $r_i^{n-1}(r_i+5)=-3$ for all $1\leq i\leq j$, we obtain$\vert g(-5)\vert = \vert (r_1+5)(r_2+5)\dots (r_m+5)\vert = 3^m.$But $g(-5)f(-5)=3$, contradiction.</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-7941109071499300492022-06-14T22:29:00.005-04:002022-06-16T22:09:38.029-04:00Inequality problem I made<p>&nbsp;Prove for all positive reals $a,b,c$,</p><p>$$\sum_{cyc} \frac{a}{\sqrt{3ab+bc}} \ge \frac 32.$$</p><p><br /></p><p>I'll wait for comments and will post the solution in 2 days!</p><p><br /></p><p><br /></p><p>EDIT - Well now that it's been <i>3 days </i>(oops i forgot to post), I'll show my solution now.&nbsp;</p><p><br /></p><p>By Holder,$$\left( \sum_{cyc} \frac{a}{\sqrt{3ab+bc}} \right)^2 \left( \sum_{cyc} a(3ab+bc) \right) \ge (a+b+c)^3$$</p><p>So it suffices to show$$(a+b+c)^3 \ge \frac 94 \sum_{cyc} a(3ab+bc)$$</p><p>Expanding and cancelling terms, we wish to show$$f(a,b,c)=4\sum_{cyc} a^3 + 12\sum_{cyc} b^2a-15\sum_{cyc} a^2b-3abc\ge 0$$</p><p>Claim: $f(a,b,c) \le f(a+d, b+d, c+d)$ if $d&gt;0$</p><p><br /></p><p>Proof:$$f(a+d,b+d,c+d)-f(a,b,c) =d (4\sum_{cyc} 3a^2 + 12\sum_{cyc} (b^2+2ba) - 15\sum_{cyc} (a^2+2ba) - 3(ab+bc+ca))$$</p><p>$$+d^2 (4\sum_{cyc} 3a + 12 \sum_{cyc} (2b+a) - 15\sum_{cyc} (2a+b) - 3(a+b+c)$$</p><p>The $d^2, d^3$ stuff cancel. So $f(a+d,b+d,c+d) - f(a,b,c) = \frac{9d}{2} \sum_{cyc} (a-b)^2 &gt; 0$.</p><p><br /></p><p>Let $a=\min\{a,b,c\}$, then $f(a,a+b,a+c) \ge f(0,b,c)$. Let $x=\frac bc$, then$$f(0,b,c) = c^3 (4x^3-15x^2+12x+4) = c^3 (x-2)^2 (4x+1)\ge 0,$$</p><p>as desired. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com6tag:blogger.com,1999:blog-2891725439429764335.post-2663124668012207092022-06-14T06:19:00.002-04:002022-06-14T06:34:08.323-04:002001 IMO SL #A6<p>Last one. I promise.&nbsp;</p><p><br /></p><p>&nbsp;Prove that for all positive real numbers $a,b,c$,$\frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}} \geq 1.&nbsp;$</p><p><br /></p><span><a name='more'></a></span><p><br /></p><p><b>Solution 1:</b></p><p>Note that this inequality is homogeneous. WLOG, assume $a+b+c=1$.</p><p><br /></p><p>Now, we can proceed by using Jensen's inequality for $f(x)=\frac{1}{\sqrt{x}}$. This gives us:</p><p>$\frac{a}{\sqrt{a^2+8bc}}+\frac{b}{\sqrt{b^2+8ac}}+\frac{c}{\sqrt{c^2+8ab}} \geq \frac{1}{\sqrt{a^3+b^3+c^3+24abc}}$</p><p>Now, we finish off with AM-GM:</p><p>$\displaystyle 1=(a+b+c)^3=a^3+b^3+c^3+6abc+3(a^2b+a^2c+b^2a+b^2c+c^2a+c^2b) \geq a^3+b^3+c^3+24abc$</p><p>And this proves the inequality.</p><p><br /></p><p><b>Solution 2:</b></p><p>By Cauchy-Schwarz, we have</p><p>$(\frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}})^2 (\sum_{cyc}{a(a^2+8bc)}).$</p><p>$\geq(a+b+c)^3$</p><p>And we know that&nbsp;</p><p>$(a+b+c)^3\geq\sum_{cyc}{a(a^2+8bc)},$</p><p>so we obtain</p><p>$(\frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}})^2&nbsp; \geq\frac{(a+b+c)^3}{(\sum{a(a^2+8bc)})}$</p><p>$\geq1,$</p><p>as desired. $\square$</p><p><br /></p><p><b>Solution 3:</b></p><p>From Holder's, $(\sum(\frac{a}{\sqrt{a^2+8bc}}))^2(a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab))\ge (a+b+c)^3$.</p><p><br /></p><p>Now, we have $(\sum(\frac{a}{\sqrt{a^2+8bc}}))^2 \ge \frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}$.</p><p><br /></p><p>We have our desired $\sum \frac{a}{\sqrt{a^2+8bc}}\ge 1\iff \frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}\ge 1$ from above.</p><p><br /></p><p>Therefore, we now have to prove $\frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}\ge 1$. We desire $a^3+b^3+c^3+3a^2b+3ab^2+3a^2c+3ac^2+3b^2c+3bc^2+6abc\ge a^3+b^3+c^3+24abc$.</p><p><br /></p><p></p><p>Therefore, we now want $3a^2b+3ab^2+3a^2+3ac^2+3b^2c+3bc^2\ge 18abc$ which is true by AM-GM, so we are done. $\square$</p><p><br /></p><p><b>Solution 4:&nbsp;</b></p><p>By Holder's,$$\left(\sum_{cyc} \frac{a}{\sqrt{a^2 + 8bc}} \right)^2 \left(\sum_{cyc} a(a^2 + 8bc) \right) \ge (a+b+c)^3$$Since $a,b,c$ are positive, we need to show that$$(a+b+c)^3\geq \sum_{cyc} \frac{a}{\sqrt{a^2 + 8bc}}$$Expanding and simplifying gives us the following:</p><p></p><p>$$a^3+b^3+c^3+3(\sum_{cyc}a^2b)+6abc\geq a^3+b^3+c^3+24abc$$$$\sum_{cyc}a^2b\geq 6ab$$This is true because it is Muirhead's on $(2, 1, 0)\succ(1,1,1)$, and we are done. $\square$</p><p><br /></p><p><b>Solution 5:</b></p><p>Firstly, $a^{2}+8bc=(a^{2}+2bc)+6bc \leq^{AG} (a^{2}+b^{2}+c^{2})+6bc=S+6bc$ (where $S=a^{2}+b^{2}+c^{2}$) and its cyclic variations.</p><p>Next note that $(a,b,c)$ and $\left( \frac{1}{\sqrt{S+6bc}}, \frac{1}{\sqrt{S+6ca}}, \frac{1}{\sqrt{S+6ab}} \right)$ are similarly oriented sequences. Thus</p><p>$$\sum_{cyc} \frac{a}{\sqrt{a^{2}+8bc}} \ge \sum_{cyc} \frac{a}{\sqrt{S+6bc}}$$$$\geq ^{chev} \frac{1}{3}(a+b+c)\left( \frac{1}{\sqrt{S+6bc}}+\frac{1}{\sqrt{S+6ca}}+\frac{1}{\sqrt{S+6ab}} \right)$$$$\geq^{AH} \frac{1}{3}(a+b+c) \left( \frac{9}{\sqrt{S+6bc}+\sqrt{S+6ca}+\sqrt{S+6ab}} \right)$$$$\geq^{QA} (a+b+c) \sqrt{\frac{3}{(S+6bc)+(S+6ca)+(S+6ab)}}$$$$=(a+b+c)\sqrt{\frac{3}{3(a+b+c)^{2}}}=1$$</p><p>Notation: $AG$: AM-GM inequality, $AH$: AM-HM inequality, $chev$: Chebyshev inequality, $QA$: QM-AM inequality aka RMS inequality</p><p><br /></p><span><!--more--></span><p><br /></p><p><b>ALRIGHT THAT'S ENOUGH SOLUTIONS NOW STOP!</b></p><p><br /></p><p><i>At last, I'm somewhat satisfied.&nbsp;&nbsp;</i></p><p><i>I would do another problem but I promised you that this is the last one so... that's it I guess?</i></p><p><i><br /></i></p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-51832220222367101722022-06-14T05:57:00.000-04:002022-06-14T05:57:38.906-04:002014 IMO SL #C2<p>Since the last one was super easy, I have to do another one... right?</p><p><br /></p><p><br /></p><p>&nbsp;We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ .</p><div><br /></div><span><a name='more'></a></span><div><br /></div><div><div>Let $S_n, P_n$ denote the sum, product of the numbers after $n$ moves respectively.</div><div><br /></div><div>Claim: $P_n \ge 2^{2n}$</div><div>Proof: Note that $(a+b)^2 \ge 4ab.$ So we get the recursive relation $P_n \ge 4P_{n-1}.$ This yields the claim. $\square$</div><div><br /></div><div>Thus by AM-GM</div><div>$$S_{m2^{m-1}} \ge 2^m \left( P_{m2^{m-1}} \right) ^{1/2^m} \ge 2^m \left( 2^{m2^{m}} \right) ^{1/2^m} = 4^m$$which is the desired bound. $\blacksquare$.</div></div><div><br /></div><span><!--more--></span><div><br /></div><div><br /></div><div>Alright, at least it wasn't <i>as easy</i>&nbsp;as the last one.&nbsp;</div><div><br /></div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com0tag:blogger.com,1999:blog-2891725439429764335.post-2373467309711341292022-06-14T05:43:00.001-04:002022-06-14T05:43:07.852-04:002019 IMO SL #G1<p>&nbsp;Let $ABC$ be a triangle. Circle $\Gamma$ passes through $A$, meets segments $AB$ and $AC$ again at points $D$ and $E$ respectively, and intersects segment $BC$ at $F$ and $G$ such that $F$ lies between $B$ and $G$. The tangent to circle $BDF$ at $F$ and the tangent to circle $CEG$ at $G$ meet at point $T$. Suppose that points $A$ and $T$ are distinct. Prove that line $AT$ is parallel to $BC$.</p><div><br /></div><div><br /></div><span><a name='more'></a></span><div><br /></div><div><br /></div><div>We have$\measuredangle TGF = \measuredangle TGC = \measuredangle GEC = \measuredangle GEA = \measuredangle GFA$and similarly $\measuredangle TFG = \measuredangle FGA$. Thus $TAGF$ is an isosceles trapezoid, as needed.&nbsp;</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div>This has got to be the easiest IMO Shortlist problem I've ever seen.</div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com1tag:blogger.com,1999:blog-2891725439429764335.post-66554947280006546112022-06-08T20:52:00.005-04:002022-06-08T20:52:51.933-04:002013 IMO #4<p>Let $ABC$ be an acute triangle with orthocenter $H$, and let $W$ be a point on the side $BC$, lying strictly between $B$ and $C$. The points $M$ and $N$ are the feet of the altitudes from $B$ and $C$, respectively. Denote by $\omega_1$ is the circumcircle of $BWN$, and let $X$ be the point on $\omega_1$ such that $WX$ is a diameter of $\omega_1$. Analogously, denote by $\omega_2$ the circumcircle of triangle $CWM$, and let $Y$ be the point such that $WY$ is a diameter of $\omega_2$. Prove that $X,Y$ and $H$ are collinear.</p><div><br /></div><span><a name='more'></a></span><div><br /></div><div><b>Solution 1:</b></div><div><div>Let $\omega_1$ and $\omega_2$ meet again at $P$. Then by the Miquel Point, $P$ is on the circumcircle of $\triangle{AMN}$, which has diameter $H$. Thus, $\measuredangle{APH}=\frac{\pi}{2}$. In particular, $H$ lies on the line through $P$ perpendicular to $AP$. But note that$\measuredangle{XPW}=\frac{\pi}{2}=\measuredangle{YPW}$because $WX$ and $WY$ are diameters of $\omega_1$ and $\omega_2$, respectively, so $X$ and $Y$ lie on the line through $P$ perpendicular to $WP$.</div><div><br /></div><div>We now claim that $A$, $P$, and $W$ are collinear. It suffices to prove that $A$ is on the radical axis of $\omega_1$ and $\omega_2$. But this is true because $A$ is the radical center of $\omega_1$, $\omega_2$, and the circumcircle of cyclic quadrilateral $BNMC$ (because it is $BN\cap CM$). Thus, $A$, $P$, and $W$ are collinear.</div><div><br /></div><div>Now, $H$, $X$, and $Y$ all lie on the line through $P$ perpendicular to $WP$, so $X$, $Y$, and $H$ are collinear, as desired. $\square$</div></div><div><br /></div><div><br /></div><div><br /></div><div><b>Solution 2:&nbsp;</b></div><div><div>Let $P$ be the second intersection of $\omega_1, \omega_2$. Then $P$ is the Miquel point of $\triangle MNW$ w.r.t $\triangle ABC$, so $AMPHN$ is cyclic. Now $BX \parallel AH$, so $X, H, P$ are collinear by Reim's theorem. Similarly, $H,P,Y$ are collinear, and the result follows. $\square$</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><h2 style="text-align: left;">Notice:</h2><div>I will rarely be posting from now till July 4th, because I will be on vacation. However, if you have any questions regarding my previous solutions then you can always contact me (see contact info on sidebar) and I will most likely be able to respond in a day or two. Have a nice summer!</div><div style="font-weight: bold;"><br /></div></div>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com3tag:blogger.com,1999:blog-2891725439429764335.post-30618603595567731452022-06-06T13:23:00.010-04:002022-06-08T20:41:27.301-04:002017 IMO SL #N6<p>&nbsp;Find the smallest positive integer $n$ or show no such $n$ exists, with the following property: there are infinitely many distinct $n$-tuples of positive rational numbers $(a_1, a_2, \ldots, a_n)$ such that both $$a_1+a_2+\dots +a_n \quad \text{and} \quad \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n}$$are integers.</p><p><br /></p><span><a name='more'></a></span><p>The answer is $n=3$.&nbsp;</p><p>We will show that that $n=1,2$ don't work and $n=3$ does.</p><p><br /></p><p>Clearly, $n=1$ does not work, as there are only finitely many such tuples, namely $1$ and $-1$.&nbsp;</p><p>For the $n=2$ case, consider rationals $a_1=\frac{a}{b}, a_2=\frac{c}{d}$ where $\gcd(a,b)=\gcd(c,d)=1$. Note that $$\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}\in\mathbb{Z}$$therefore $b\mid ad+bc\implies b\mid ad\implies b\mid d$. Similarly $d\mid b$ hence $b=d$. Since $\frac{b}{a}+\frac{d}{c}\in\mathbb{Z}$, repeating similar logic gives $a=c$. These two together give $a_1=a_2$, so these two rationals are not distinct, and hence $n=2$ doesn't work.</p><p><br /></p><p>Now to show $n=3$ works, consider $(a_1, a_2, a_3) = \left(\frac1{m+n+1},\frac m{m+n+1},\frac n{m+n+1}\right)$ for positive integers $1&lt;m&lt;n$.&nbsp;The $a_i$ are distinct, and $a_1 + a_2 + a_3 = 1$, so $\frac{m+1}n+\frac{n+1}m$ must be a positive integer for infinitely many pairs $(m,n)$ for $1&lt;m&lt;n$.&nbsp;</p><p>Write this as$m^2 + n^2 + m + n = mnk$for some positive integer $k$. As a quadratic in $m$, this becomes$m^2 + (1 - kn)m + (n^2 + n) = 0$so by Vieta's, given the solution $(m, n)$ with $m &lt; n$, it then follows that$(kn - 1 - n, n) \longleftrightarrow (n, kn - 1 - m)$is also a solution. Note $kn - 1 - m &gt; n$ for all $k &gt; 2$. Therefore, if we are given any initial solution $(m_0, n_0)$ and some fixed $k$, we can compute infinitely many solutions by $(m_{i+1}, n_{i+1}) = (n_i, kn_i - 1 - m_i)$ where $\min(m_i, n_i)$ is increasing. Note that for $k = 3$ there exists an initial solution $(m_0, n_0) = (2, 3)$, so using the method defined above, we can produce as many $(m_i, n_i)$ we want, as desired. $\square$</p>IMOMathhttp://www.blogger.com/profile/13395609085241002693noreply@blogger.com2