显示标签为“Olympiad”的博文。显示所有博文
显示标签为“Olympiad”的博文。显示所有博文

2020年7月30日星期四

Variation argument is everywhere

Today I am asked a high school level question: given $1 \geq p_1 \geq p_2 \cdots p_n \geq 0$ and find a subset of these number such that to maximize the quantity
$$F(S) = \sum_{i=1}^{|S|}\frac{p_{\alpha_i}}{1 - p_{\alpha_i}} \left( \prod_{j=1}^{|S|}(1-p_{\alpha_j})\right).$$
If one would like to use the search naively, the complexity will be of course large as $n!$. I want to say a simple variational argument is although simple but useful. But supposing adding one more element, deleting one element, or replacing one element, one can see quickly the description for this optimal subset is $\tau$ that
$$S := \{p_i\}_{1 \leq i \leq \tau}, \tau := \min \left\{n \in \mathbb{N}: \sum_{i=1}^\tau \frac{p_i}{1-p_i} \geq 1\right\}.$$
Thus the complexity is reduced to $O(n)$. So let us always think about the variational argument.

2017年3月19日星期日

An Olympiad inequality Iran96

One day, Xiaoke asks me an Olympiad inequality, which recalls me of a lot of beautiful memories.

For any $a,b,c \in \mathbb{R}$, try to prove$$(ab + bc + ca)(\frac{1}{(a+b)^2} + \frac{1}{(b+c)^2} + \frac{1}{(c+a)^2}) \geq \frac{9}{4}$$

This is a very hard inequality named "Iran96". In the WeChat post, it is said that this one is so hard that many students who participates in competitions cannot solve  it. I believe that it is a little exaggerated. Even for a Olympiad question, this is not the most difficult one.

Let us do some transform.

$$LHS = 4\sum [a^5b + b^5 a + 2a^4 b^2 + 2 a^2 b^4 + 5  a^4 bc + 3 b^3 c^3 + 13 a^3  b^2 c + 13  a^3 b c^2 + 8  a^2b^2c^2]$$
$$RHS = 90a^2b^2c^2 + 9\sum[a^4b^2 + a^2b^4 + 2a^3b^3 + 6a^3b^2c + a^2b^3c + 2 a^4bc]$$

We do some simplification and finally we have to prove this inequality$$\sum[4 a^5b + 4ab^5 + 2a^4bc + 2a^2b^2c^2] \geq \sum[a^4b^2 + a^2b^4 + 6b^3c^3 + 2a^3b^2c + 2a^3bc^2]$$

It reduces to three inequalities$$\begin{eqnarray*}3\sum(a^5b + ab^5) &\geq& 3\sum a^3b^3\\\sum(a^5b + ab^5) &\geq& \sum(a^4b^2 + a^2 b^4)\\2abc(\sum a^3 + 3abc) &\geq& 2abc\sum(a^2b + ab^2)\end{eqnarray*}$$

The last one is a very famous inequality called inequality of Schur.