Wednesday, May 16, 2018

Shifting matrix

An $n \times n$ matrix is filled with numbers, where there are $k$ number ones and the rest zero. The operation that is allowed on the matrix is to shift a single column down by one (so that each number in that column moves down by one, and the bottom most number goes to the top), or to shift a single row to the left by one.

Determine all $k$ such that, no matter how the initial condition is, through a series of operations, we can make it so that each column and each row has an even sum.

Tuesday, May 15, 2018

For $x,y,z$ positive numbers such that $xyz = 1$, prove that: $$2 \sqrt{2} (x^7+y^7)(x^7+z^7)(y^7+z^7) \geq \sqrt{(x^{16}+7)(y^{16}+7)(z^{16}+7)}$$


$$2(x^7+y^7)(x^7+z^7) = x^{14} + (x^{14} + 2x^7(y^7+z^7) + 2y^7z^7)$$ by AM-GM: $$ \geq x^{14} + 7x^6y^4z^4 = \frac{x^{16}+7}{x^2}$$ By multiplying similar inequalities and taking square root, we get the desired result

Find all m for inequality

Find all real number $m$ such that, for all positive real numbers $x,y,z$ the following is true: $$ \frac{x}{x^2 + myz} + \frac{y}{y^2 + mxz} + \frac{z}{z^2 + mxy} \geq \frac{9}{(m+1)(x+y+z)}$$


First we show that for $m \geq 8$ it's true. By Cauchy: $$\frac{x}{x^2 + myz} + \frac{y}{y^2 + mxz} + \frac{z}{z^2 + mxy} \geq \frac{(x+y+z)^2}{x^3 + y^3 + z^3 +}$$ Then let $A = x^2 + y^2 + z^2,B = xy+yz+zx$. Because $x^3+y^3+z^3 = (x+y+z)(A -B)+3xyz$, $$ = \frac{A+2B}{(x+y+z)(A-B)+3(m+1)xyz} \geq \frac{9}{(m+1)(x+y+z)}$$ The last inequality is equivalent to (because $A \geq B$ we may multiply by the denominators without changing the sign): $$(A+2B)(x+y+z)(m+1) \geq 9(x+y+z)(A-B) + 27(m+1)(x+y+z)$$ $$\iff (x+y+z)[(m-8)A + (2m+11)B] \geq 27(m+1)xyz$$ Indeed by AM-GM: $$x+y+z \geq 3 \sqrt[3]{xyz}$$ $$ A \geq 3 \sqrt[3]{x^2y^2z^2}$$ $$ B \geq 3 \sqrt[3]{x^2y^2z^2}$$ So: $$ (x+y+z)[(m-8)A + (2m+11)B] \geq 3 \sqrt[3]{xyz} [3(m-8) \sqrt[3]{x^2y^2z^2} + 3(2m+11)\sqrt[3]{x^2y^2z^2} = 27(m+1)xyz$$ Now to show necessity, plug in $z = t, x=y=1$, then the left hand side is : $$ \frac{2}{1+mt} + \frac{t}{t^2+m} \geq \frac{9}{(m+1)(2+t)}$$ $$(2(t^2+m)+t(mt+1))(2+t)(m+1) \geq 9(t^2+m)(mt+1)$$ which has to be true for all $t \geq 0$. However, the coefficient of $t^3$ on the LHS is $m(m+1)$ and on the RHS is $9m$. Because this inequality has to be true for all $t$ no matter how big, then the coefficient on the LHS has to be greater than or equal to that of the RHS, otherwise we can choose $t$ large enough to violate that expression. $$m(m+1) \geq 9m$$ which means $m \geq 8$.

Friday, May 11, 2018

Inequality a b c

For $a,b,c \geq 0$ prove that: $$2(a+b+c)^2 + 3(ab+bc+ca) \geq (a+b+c)(\sqrt{a} + \sqrt{b} + \sqrt{c})^2$$


This is equivalent to: $$(a+b+c)^2 + 3(ab+bc+ca) \geq 6(a+b+c)(\sqrt{ab} + \sqrt{bc} + \sqrt{ca})$$ which is the cyclic sum of: $$(a+b+c)^2 + 9ab \geq 6 \sqrt{ab}(a+b+c)$$ which is true by AM-GM.


Find all $\lambda$ such that this holds for all $a,b,c \geq 0$: $$(a+b+c)^2 + \lambda (ab+bc+ca) \geq \frac{\lambda + 3}{9}(a+b+c)(\sqrt{a}+\sqrt{b}+\sqrt{c})^2$$


For $0 \leq \lambda \leq 3/2$ we can show it by proving the original problem, and realizing that: $$3(a+b+c)^2 \geq (a+b+c)(\sqrt{a} + \sqrt{b} + \sqrt{c})^2$$ is just AM-RMS.

Wednesday, May 9, 2018

Inequality x y z

If $x,y,z$ are positive numbers such that $x+y+z = 1$ show that: $$ \frac{1}{x+y} + \frac{1}{x+z}+ \frac{1}{y+z} + \frac{9}{2} \geq \frac{3}{1 - (\frac{x-y}{2})^2} + \frac{3}{1 - (\frac{y-z}{2})^2} + \frac{3}{1 - (\frac{x-z}{2})^2}$$

(Hopefully) Correct Solution

WLOG we may assume that $x \geq y \geq z$. And for now we assume that $2y \geq x+z$ (the case where $2y < x+z$ is handled later below).

By AM-HM: $$\frac{1}{y+z} + \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{9}{(y+z)+(y+z)+(x+z)} = \frac{9}{1+y+2z} = \frac{9}{2+z-x}$$ $$\frac{1}{y+z} + \frac{1}{x+z} + \frac{1}{x+z} \geq \frac{9}{1+x+2z} = \frac{9}{2+z-y}$$ Adding the two inequalities: $$ \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{3}{2+z-x} + \frac{3}{2+z-y} $$ (Call this inequality 1).

Incorrect Solution

WLOG we may assume that $x \geq y \geq z$. Suppose $a = x-z, b = x-y$ so $a+b = 2x-y-z = 3x-1$. If $a=b=0$ then $x=y=z=1/3$ and equality happens. Thus at least one of $a,b$ is positive, so $a+b > 0$. Now, by Cauchy: $$(\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2})(\frac{a(y+z)}{a+b} + \frac{2b}{3(a+b)}) \geq (\frac{a}{a+b} + \frac{b}{a+b})^2 = 1$$ So: $$\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3a(y+z) + 2b} = \frac{3}{2+z-x}$$ The last equality is equivalent to: $$ \frac{1(a+b)}{3a(y+z) + 2b} = \frac{1}{2+z-x} $$ $$ \iff (a+b)(2+z-x) = 3a(y+z) + 2b $$ Because $2+z-x \iff 3-2x-y$ and $y+z = 1-x$ $$ \iff (3x-1)(3-2x-y) = 3(x-z)(1-z) + 2(x-y)$$ Upon expanding and rearranging: $$ \iff 0 = 3(x-1)(x+y+z - 1) $$ which is true. On the other hand, using the same definition of $a,b$, we can also show: $$\frac{b}{a+b} . \frac{1}{y+z} + \frac{a}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3b(y+z) + 2a} = \frac{3}{2+y-x}$$ (Using similar identity as above) Adding the two inequalities, we have: $$ \frac{1}{y+z} + \frac{3}{2} \geq \frac{3}{2+z-x} + \frac{3}{2+y-x}$$ And similarly: $$ \frac{1}{x+z} + \frac{3}{2} \geq \frac{3}{2+x-y} + \frac{3}{2+z-y}$$ $$ \frac{1}{x+y} + \frac{3}{2} \geq \frac{3}{2+y-z} + \frac{3}{2+z-x}$$ Now all we need to show is that the sum of LHS is equal to the LHS of the given problem. Indeed it is so because: $$ \frac{3}{2+y-x} + \frac{3}{2+x-y} = \frac{3(2+x-y) + 3(2+y-x)}{2^2 - (x-y)^2} = \frac{12}{4 - (x-y)^2} = \frac{3}{1 - (\frac{x-y}{2})^2}$$ Edit: what is wrong with this proof?

Inequality a,b,c

For $a,b,c$ non-negative real numbers such that $a+b+c=1$, prove that: $$(3a+1)(3b+1)(3c+1) \geq 3 \sqrt{3}(\sqrt{a} + \sqrt{b})(\sqrt{b}+\sqrt{c})(\sqrt{c}+\sqrt{a})$$


With Cauchy we have: $$(3a + 1)(1 + 3b) \geq (\sqrt{3a} + \sqrt{3b})^2 = 3(\sqrt{a} + \sqrt{b})^2$$ Multiplying all of the similar inequalities, we get the desired result. Equality happens if and only if $3a = 1/(3b), 3b = 1/(3c), 3c = 1/(3a)$, which means $a=b=c = 1/3$.

Tuesday, May 8, 2018

Tricolored polygon

Given a regular $(3n+2)$-gon, the vertices are colored with red, blue, or green such that there are $n+1$ green points, $n+1$ blue points, and $n$ red points. Prove that there exists a line going through a blue point and a green point, such that on one side of the line there are $k$ points of each color, and on the other side there are $(n-k)$ of each color (with $k \geq 0$).


First we claim that there is a way to pair each blue point with a green point such that the segments formed by each pair is non-intersecting. Proof:

Delete all the red points for now, so we are left with polygon with $(n+1)$ blue and green points each. Take any adjacent pair of a blue point and a green point, pair them, and then delete them. Now we are left with $n$ blue and green points each. Recursively apply this procedure until we are done. It's easy to see that the resulting segments are non-intersecting.

Now that we have $n+1$ such segments, label the points $(b_1, \dots, b_{n+1}, g_1, \dots, g_{n+1})$ where $b_i$ is a blue point that is paired with $g_i$. Let $S_i$ denote the segment formed by $b_ih_i$. Pick an arbitrary red point $R$. We define the following terminology: each segment divides the polygon into two. The "good" side of the segment is the side that contains $R$.

Since no two segments can intersect, then for two different segments $S_i,S_j$, one is fully on the good side of the other. If $S_i$ is fully contained in the good side of $S_j$ then we say that $S_j$ "covers" $S_i$. Note that for any two segments, if $S_i$ covers $S_j$ then $S_j$ does not cover $S_i$, and one necessarily covers the other.

Note the following properties. If $S_a$ covers $S_b$ and $S_b$ covers $S_c$ then $S_a$ covers $S_c$. Conversely, if $S_a$ and $S_b$ both cover $S_c$ then either $S_a$ covers $S_b$ or $S_b$ covers $S_a$. So we may define the relationship called "immediate covering." We say $S_a$ immediately covers $S_b$ if $S_a$ covers $S_b$ and there's no other $S_c$ such that $S_a$ covers $S_c$ and $S_c$ covers $S_b$.

Consider the graph with $n+1$ vertices $1,2,\dots,n+1$ and the edges where $i \to j$ if $S_i$ immediately covers $S_j$. Each segment can only be immediately covered by at most one other segment, so this graph is a tree. It cannot be a forest because for each root of each tree, one necessarily covers the other so there can only be one true root. Define the "height" of each node to be the distance between node $i$ to it's farthest leaf. So every leaf has height zero. If $i$ is a leaf and $S_j$ immediately covers $S_i$ (and only $S_i$), then $j$ has height 1, and so on. If a node has several children of differing heights, then the height of the node is 1 plus the maximum of its children's height.

Now also for each $i$, define $A_i$ to be the number of red points that are located on the good side of $S_i$. Define $B_i$ to be the number of descendants of $i$ in the above-mentioned graph. So, our aim is to show that there exists an $i$ such that $A_i = B_i$, because this would mean that on the good side of $S_i$, there are precisely $A_i$ red points, and $B_i$ segments, each of which contains $B_i$ blue points and $B_i$ green points. Now suppose, in our configuration, there is no $i$ such that $A_i = B_i$.

Our claim now is that for each $i$, $A_i > B_i$. We prove this by induction on the height of the nodes.

We start by looking at the leaves. If there's any leaf $i$ with $A_i = 0$ then there is a contradiction, because $B_i = 0$. So for each leaf $i$, $A_i \geq 1 > 0 = B_i$.

Now suppose that $A_i > B_i$ (which means $A_i \geq B_i + 1$) for each node of height $0, 1, \dots, k$, then let $S_a$ be a node of height $k+1$, and let its children be $S_{b_1}, \dots, S_{b_m}$. Its children has height at most $k$, so for each $i$, $A_{b_i} \geq B_{b_i}$ holds. Now, each red point on the good side of $S_{b_i}$ is also on the good side of $S_a$, therefore $$A_a \geq A_{b_1} + \dots + A_{b_m} \geq (B_{b_1} + 1) + \dots + (B_{b_m}+1) = m + \sum B_{b_i} = B_a$$ The first inequality is due to the fact that each red point in $A_{b_i}$ must be contained in $A_a$ as well (although there may be more red points in $A_a$. The second inequality is from induction hypothesis. The third inequality is by construction of the graph and definition of $B_a$, because the number of descendants of $S_a$ can be counted by summing the number of descendant of children, plus each of the children themselves.

So we established that $A_a \geq B_a$, but because we assumed that there is not $A_i = B_i$, then $A_a > B_a$. Thus, by induction on the height of each node, we can claim that $A_i > B_i$ for each $i$ in the whole graph.

Now consider the root node $r$. We concluded that $A_r > B_r$. But $A_r$ is the number of red points on the good side of $S_r$, which is at most $n$. $B_r$ is the number of descendants of $S_r$, which is $n$. Contradiction.

Thus there must be an $i$ such that $A_i = B_i$ and that is our desired segment.