So here's a rough draft of what I might post, and notice that it would probably be less of just problems, but explanations first, then practice problems for the interested reader. These will be like excursions into IMO standard problems for the novice. So please give your comments on how this can be improved :)

Invariants

The Principle

Note: I assume the reader has familiarised himself with Introduction to Invariance Principle

Invariants are particularly useful in analysis of games, transformations and questions of the like. Basically, the main motivation behind applying the invariance principle is to find something that does not change, when something is repeated, whence the important usage of this in algorithms. Quoting Problem-Solving Strategies, here is a non-exhausted list to keep in mind when applying invariance.

• Can a given state be reached?

• Find all reachable end states.

• Is there convergence to an end state?

• Find all periods, if possible.

Also, if you are ambitious and want to use this in olympiad combinatorics problems, here's a few common invariants that we will encounter along the way:

1. Parity

2. Colouring (as in the more commonly known checkerboard colouring and others)

3. Sum of squares/products or things of the like

Now, also to introduce another method in invariance, we will start with our first example:

Example 0 : $23$ friends wants to play hockey. However, to ensure that the game is fair play, they choose a referee and the rest of the team splits into $2$ teams of $11$ people each. However, because they are a bit eccentric, they want to do this splitting such that the total weight of each team is the same. Suppose now for simplicity sake that they all have integer weights, and we know that this division is always possible regardless of who is the referee. Show that they all have the same weight.

Solution: Wow, that is a really really long question and to help us understand the context and meaning, we rewrite this in mathematical equations. Let $w_1, w_2, \ldots, w_{23}$ be the weights of the $23$ people. Also, let $S = w_1 + w_2 + \ldots + w_{23}$, the motivation behind this definition is that choosing a referee is the same as removing a person with weight $w_i$ and split the rest into $2$ teams of weight $k$ each. Now, we can write everything in this compact form: $S - w_i = 2k (*)$. Remember what we said about parity? Clearly since the RHS is even, $w_i$ and $S$ needs to have the same parity. And since $w_i$ was completely arbitrary, they are all odd or even.

Being odd or even only gives us one clue on how to proceed, which is whether $2$ divides it or not. Because we want to work with simplified things, consider what happens if we divide those that are even by $2$. For instance, if all $w_i$ are even, if we let $q_i = \frac{w_i}{2}$, does this simplify the problem to some extent? Well, clearly by definition all $q_i$ are integers, and writing a equation, $\frac{S}{2} - q_i = 2\frac{k}{2}$ which is unmistakably $(*)$ so $q_i$ is a new list of weights that also satisfy the conditions. Analogously, we can conclude for $w_i$ being odd (don't forget this case!), we can let $q_i = w_i - 1$.

Here's the important bit. If the $w_i$ at the beginning were not all $0$, then the sum of the weights $q_i$ is strictly smaller. We can always repeat this step (this is sort of an algorithm-like approach - another method that works like induction; you use it if you do not have any idea how to proceed) and reduce the sum of the weights so eventually we will reach a list of only zeroes. Now we backtrack to see what this implies. So since we are able to do this, we conclude the numbers in the original list were all equal, as desired. □

So here, instead of finding something that is not changing, we in fact created something to make $S$ always decreasing. The main idea here is that there is no infinite sequence of non-negative integers that is strictly decreasing. This technique is more commonly known as infinite descent. We will encounter a much more difficult application of this later.

Applications

In these examples, we will go into detail the motivation and thought process behind each key step. The last few questions are taken from the IMO, so expect that it will be much more convoluted and difficult to approach than the rest.

[blah blah - I will write later when I finish my breakfast]

EDIT: So we proceed. The first example is of a game. We will see how to apply the invariance principle.

Example 1: On a chessboard A and B play by turns to place black and white knights, respectively. Either player loses when he places a knight on a square attacked by a knight of the other colour or there are no free squares to place the knight on. If A starts, who has a winning strategy?

Solution: For those chess noobs like me, remark that a knight can only attack the $8$ squares shown in the figure below:

tagtext

Intuitively, if each player can place a knight such that the squares that can be attacked by both knights do not overlap, then since a chessboard has an even number of cells, Player B can win, by in what people call, mirroring the first player.

Clearly a knight on a black square can only attack a knight on a white square and vice versa. So the colours of the squares that the knight attacks is invariant. Recall that a chessboard is a $8\times 8$, so if we "fold" the board along the middle, the $2$ "flaps" would be of opposing colour. For instance, let $a_{i,j}$ be the colour of the cell in the $ith$ row and $jth$ column of the chessboard. Then we have that $a_{4,2} = a_{4,7}$.

The above observation is key for us to see that the strategy for B is to do the same thing as A but symmetric to the center of the board. Basically, notice that if A can place a knight without being attacked by B's knights, the B can always place a "symmetric" knight without being attacked by A's knight due to the colour argument. Now given the way that knights attack, A can never place a knight that attacks the square where B played. Thus A loses in the end. □

To further train the skills of the reader in solving game-like problems (because we would soon be moving to colouring and other invariance, and I would select the IMO problems for demonstration), we will attempt one more example, this problem was in my training notes, and according to our trainer, was from Bulgaria 2001.

Example 2 Alice and Bob play by turns to write ones and zeroes in a list, from left to right. The game ends when each has written 2001 numbers. When the game ends the sequence of $0 ,1$ is interpreted in base $2$. Alice wins if that number can be written as a sum of two perfect squares and if otherwise, Bob wins. Who has a winning strategy?

Solution: We want a invariant that somehow involves squares. Well, preliminarily, just plain squares would remind me of $\pmod 4$. So ultimately one should think of Fermat's Christmas Theorem. Let's see how this property translates to a winning strategy.

Now suppose the number is $1100 \ldots 0$ where there is an even number of $0$, what can you observe? (Hint: consider $\pmod 4$) Yup, exactly! Since $4m$ can be written as a sum of $2$ squares iff $m$ can, we can perfectly well ignore the zeroes at the end. And notice that $11$ in base $2$ cannot be written as a sum of $2$ squares, so B wins! Generalising this argument, at any moment A writes a $1$, B just copies $A's$ move. In this way, if we ignore the zeores, the final number would end in $11$ which is congruent to $3 \pmod 4$ which by Fermat's Christmas Theorem, cannot be written as a sum of $2$ squares, so B wins.

So remember that $A$ is smart. She wants to avoid the above case where she loses. So she says: "Aha! I only write $0s$, in that way, I will win!" Well, sad life A, because you don't. Because if A only writes "0s", using the same argument above we can in fact make B write $1998$ times $0$ and then $3$ times $1$, which after interpreting in binary is $21$ so B wins again. □

[Will continue after urgent meeting]

EDIT again Let us now apply infinite descent to a much more difficult problem.

Example 3: (IMO 1986) We assign an integer to each vertex of a regular pentagon, so that the sum of all of them is positive. We are allowed to perform a transformation if three consecutive vertices have assigned numbers $x,y, z$ respectively and $y < 0$, if so, then we can change the numbers $(x,y,z)$ to $(x+y, -y, z+y)$. This process can be continued as long as one of the numbers is negative. Does this process always come to an end?

Solution: Don't freak out that this is from IMO.

tagtext

We label the pentagon with $a,b,c,d,e$ as shown.

So we need to find a certain invariance. In fact the only "basic" thing we have is the sum of all numbers. Also notice that $(x+y) + (-y) + (z+y) = (x+y+z)$ so the sum remains constant. This does not tell us whether the process ends. We need something that decreases. Now from the sum, it is certainly quite motivated to consider the average. So if every number is very close to the average then none would be negative and the process would end. So we want to search for something that will increase as the numbers are different to the average. Naturally, we might think of $|x-y|$ but the absolute value can be quite unpredictable at times, so we consider the "nicer" alternative squares $(x-y)^2$.

So referring back to the notation at the beginning, consider a function $f(a,b,c,d,e) = (a-c)^2 + (c-e)^2 + (e-b)^2 + (b-d)^2 + (d-a)^2$. Clearly $f(a,b,c,d,e) ≥ 0$. Suppose WLOG that $c < 0$ and we do the transformation in the problem. Then:

$f(a,b+c, -c, d+c, e) = (a+c)^2 + (-c-e)^2 + (e-b-c)^2+ (b-d)^2 + (d+c-a)^2$

$= [(a-c)^2 +4ac] + [(c-e)^2 + 4ce] + [(e-b)^2 - 2ec + 2bc + c^2] + (b-d)^2 + [(d-a)^2 - ac + 2cd + c^2]$

$= f(a,b,c,d,e) + 2c(a+b+c+d+e)$

Since $c<0$ and we assumed that $a+b+c+d+e > 0$, we have that $2c(a+b+c+d+e) < 0$ so $f(a,b,c,d,e)$ decreases at each step. By infinite descent we are done. □

One last example that uses colouring.

Example 4: (IMO 2004) Define a hook to be a figure made up of 6 unit squares as shown in the diagram

tagtext

or any of the tiles by applying rotations and reflections to the diagram. Determine all $m\times n$ rectangles that can covered be hooks such that:

• the rectangle is covered with hooks and no overlaps

• no part of the hook covers an area outside the rectangle.

Solution: We hate hooks because they are in a way disjoint. We like tiles that are nice $2 \times 3$ rectangles or things of the sort. So it is pretty motivated to consider pairs of hooks due to the hole, as marked out (with a black dot) in the following diagram:

tagtext

So necessarily if tile $X$ cover tile $Y's$ "hole", then necessarily tile $Y$ also cover the "hole" of tile $X$. We have the following $2$ pairs:

tagtext

We have our first breakthrough for this problem: $12 \mid mn$. Consider a $2 \times 6$ board. Clearly we cannot tile it with the pairs of tiles. However, we can obviously tile a $4 \times 6$ board. We might now conjecture that we must have (WLOG) that $4 \mid m$.

Let us consider the case where they are both even but $4 \nmid m,n$. So we want to find a colouring that makes use of the divisibility by $4$ condition. Well, the most direct way of incorporating it this is to add a $1$ to each cell of the board that belongs to a column or row divisible by $4$. Basically what we want to do next can then be simplified to proving that each of the pairs of hook only cover an odd number of $1$. (Do you see why this is sufficient?). Anyways, here's the board with the labelling:

tagtext

So each pair of hook clearly can only cover an odd number of $1$ by doing a simple case-bashing (I leave the reader to convince himself). So there must be an even number of tile $\rightarrow$ $4 \mid m$ (WLOG).

Now, let us summarise what we have:

• $12 \mid mn$

• $4 \mid m$

• $m,n \neq 1,2,5$ (do you see why?)

(i) So if $3 \mid n$ then we can clearly tile the whole board using the $3 \times 4$ rectangles formed from the pair of hooks.

(ii) If $12 \mid m$ and by point $3$, $m \geq 6$ then by a simple induction we can show that $m$ can be represented in the form $3a + 4b$. The motivation behind this step is that we want to be able to split up the board into smaller sections of case (i) above, because intuitively the $3 \times 4$ rectangles is more predictable than the second kind of pairing. Then all we do is that we split up the board into $a$ strips of $3 \times m$ and $b$ strips of $4 \times m$ which both can be tiled. □

Example 5: (IMO shortlist 1998) A solitaire game is played on an $m \times n$ regular board, using $mn$ markers that are white on one side and black on the other. Initially, each square of the board contains a marker with its white side up, except for one corner square, which contains a marker with its black side up. In each move, one may take away one marker with its black side up but must then turn over all markers that are in squares having an edge in common with the square of the removed marker. Determine all pairs $(m,n)$ of positive integers such that all markers can be removed from the board.

Solution: This is a particularly annoying problem. It is extremely long and difficult to understand. As such, let us employ the technique of trying small cases to perhaps find a pattern.

1. $m,n = 1$. This is boring. Just remove the "corner square" marker.

2. WLOG $m=2, n =1$. This is boring too. Remove any "corner square" marker. The other will be black. Remove both.

3. $m = 2, n=2$. Just do the operations and you will find that you end up with a sole white marker that cannot be removed.

4. $m = 2, n =3$. Just remove the first row one by one and leave the following scenario, it is clear that all markers can be removed.

5. $m = 2, n = 4$. Playing around shows that this case is impossible.

Diagram 1

These observations motivate us to conjecture that if either $m,n$ is odd then we can remove all markers (using the $4$th case as a hint). WLOG, let us write $m = 2k+1$. For easy reference, we assign the markers a position $(i,j)$ as the $i$th row and $j$th column. So now, again, WLOG, $(1,1)$ is that with the black side up. We remove $(1,1)$ and in sequential from top to bottom, remove all $(k,1)$ for $2≤ k ≤ m$. We have something as in the following diagram:

tagtext

So in our mathematical language, each marker $(k,2)$ now has its black side up (sounds like backside up). Anyways, the next thing is to sequentially (which means in the order of $q = 1, \ldots , \frac{m-1}{2}$ ) remove the markers $(2q+1,2)$. The cute thing here is that each with $(2q,2)$ is actually flipped twice, which means it turn from $\text{black} \rightarrow \text{white} \rightarrow \text{black}$, which is nice. So we have the following diagram:

tagtext

Now by removing the markers $(2q,2)$ sequentially, we end up with the following diagram. It is clear now that by using this procedure we can remove all markers given that $m$ is odd (so that the final row would be black).

tagtext

To show that if $(m,n)$ are both even then we cannot remove all the markers, we need to find an invariance. Here are $2$ approaches, as we will see, the first approach stems from the fact that empty squares without markers are useless, so the idea of removing empty squares. The second one is more well-known, as assigning weights of $-1,1$ allows one to consider sums and products (as in this case).

Consider the perimeter of the board. We consider removing a black marker as removing the edges that the cell it is in shares with the perimeter of the board. This is a bit ambiguous and requires the formal definition of perimeter. With that in mind, we will refer to removing a black marker as removing the cell it is in. Consider removing a cell that shares $k$ edges with the perimeter of the board, then $k$ is lost and $4 -k$ is gained for the perimeter. The presence of $4$ suggests taking $\pmod 4$ which is a considerably good strategy. So, we have a net gain of $4 - 2k$ for the perimeter, which is $2k \pmod 4$.

We want to eliminate the variable $k$, so let's give it a physical meaning first. Well, except for the first black marker and its cell, $k$ is actually $\text{\# of adjacent markers removed} + \text{\# of edges shared with the perimeter of the board}$. Notice that the former is always odd, since if we consider the cycle $\text{white} \rightarrow \text{black} \rightarrow \ldots \rightarrow \text{Black}$, we would always need an odd number of manipulations/arrows, as desired. This implies that the total sum is odd, and we see that no matter whether $k \equiv 1,3 \pmod 4$, $2k \equiv 2 \pmod 4$.

However, this means the perimeter changes $(n-2)(m-2)+3$ times from $2(m+n)$ which is the original perimeter. By assumption $2(m+n) \equiv 0 \pmod 4$, which means that the final perimeter is $2 \pmod 4$. It is clear that a contradiction arises since we need it to be $0 \pmod 4$. □

Example 6: (IMO shortlist 2005) There are $n$ markers, each with one side white and the other side black, aligned in a row with their white sides up. At each step, if possible, we choose a marker with the white side up (but not one of the outermost markers), remove i, and reverse the two neighbouring markers. Prove that one can reach a configuration with only two markers left if and only if $3 \nmid n-1$.

Solution: Just playing around with small examples can lead to one trivial observation: the parity of the number of black markers remains unchanged during the game. Hence if only two markers are left, they must have the same colour.

As with what was written in Example $5$, we can see that we can assign "weights". Well, here the best thing to encode would be the number of black markers. Remember that $(-1)^n$ for some $n$ provides lots of information by encoding the parity(when we consider sums), let us define assign to a white marker with $n$ black markers to its left the value $(-1)^n$. We only assign values to the white markers. Denote $\mathbb{S}$ as the sum of all numbers assigned to the white markers.

Consider an arbitrary white marker with both of its neighbours initially white and with $k$ black markers to its left. We perform an operation on that marker and see how it affects $(-1)^n$. Clearly, if we turn both of its neighbouring markers black and remove it, then $\mathbb{S}$ decreases by $-(-1)^k + (-1)^{k-1} + (-1)^{k-1} = 3 (-1)^{k-1}$. Therefore, we have just shown that $\mathbb{S} \pmod 3$ is invariant.

If the game ends with two black markers then $\mathbb{S} \equiv 0 \pmod 3$ and if it ends with two white markers then $\mathbb{S} \equiv 2 \pmod 3$. $\rightarrow 3 \nmid n-1$.

To show that if we start with $n ≥ 5$ markers and $n \equiv 0,2 \pmod 3$ satisfies the conditions. By removing the $3$ leftmost white markers (that do not violate the conditions), we obtain a row of $n-3$ markers. By working backwards, we can reach $2$ or $3$ white markers. We are done with the former and for the latter we can reach $2$ black markers. □

Practice Problems

1. Five identical empty buckets of $2$-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round, the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighbouring buckets, empties them to the river and puts them back. Then the next round begins. The Stepmother goal's is to make one of these buckets overflow. Cinderella's goal is to prevent this. Can the wicked Stepmother enforce a bucket overflow?

2. Let $S$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P$ \in $\mathcal S$ The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

3. At the vertices of a regular hexagon are written six nonnegative integers whose sum is $2003^{2003}$. Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number $0$ appears at all six vertices.

4. (Optional) (a) Find a monovariant for Example $3$ using absolute values.

(b) Solve Example $5$ by assigning the weights as suggested as a second approach.

Hints:

1. Well, since we cannot spam this directly, consider working backwards. Clearly, Cinderella needs to ensure that the buckets have $a_1,\ldots,a_5\le 1$ or else the bucket would overflow on Stepmother's turn. Suppose then that the stepmother adds $w_1,\ldots,w_5$ to the buckets, where $w_1+\cdots+w_5=1$. So if we think about it further, we can see that if there are $2$ nonadjacent buckets (we are trying to make the stepmother win now), the stepmother wins if we have $a_i + w_i > 1$ and $a_{i+2} + w_{i+2} > 1$. Cinderella needs to prevent the stepmother from setting $(w_i,w_{i+2})=(1+\epsilon-a_i,1+\epsilon-a_{i+2})$, so all she does is to ensure that $2+2\epsilon-a_i-a_{i+2}>1=w_1+\cdots+w_5$ for all $\epsilon>0 \rightarrow a_i+a_{i+2}\le 1$. Now it is just your job to prove that these invariants hold at every step.

2. There isn't a really detailed hint for this question. Remark first that: If we start with a point on the convex hull of $\mathcal{S}$ and a line $\ell$ that is “tangent” to the convex hull then we will only iterate over the points from the convex hull. The key motivation behind the solution is the fact that in rotations there are some really important angles such as $\pi, \frac{\pi}{2}$. Also think, if we draw a line $\ell$, then the plane is split into two sections and there is one point only on $\ell$, how do we know that we can iterate? Maybe we can see what happens if we swap the two sections? Do you see the invariance?

3. Clearly we need to construct a monovariant. Think: Is $2003^{2003}$ purposely there to put you off? Try some small cases. It becomes apparent that we need an alternating odd even structure. Prove that this is possible. Try casework if everything else fails. We need a monovariance that looks something like: $max\{ a,b,c \} - g(a,b,c)$ Here we define $g(a,b,c) = \text{\# of} \space a,b,c \space \text{that are equal to} \space \max \{ a,b,c \}$. The alternating structure suggests strongly to use $3 max\{ a,b,c \} - g(a,b,c)$. Use induction to prove that this invariance holds a every step.

4. (a) Consider including pairwise sums then testing and etc.

(b) Refer to Example $6$.

Sources: IMO problems and my SIMO senior training notes.

Well, recently at my SIMO training we did combi, so I read up a bit more and tried some imo problems. So I can probably write a while or then about combi.

EDIT: In fact, what are we gonna focus on? Olympiad or general math? Or both?

EDIT again: Yup I went to read, so can I write more primarily on Olympiad? :D

Anqi,

This the Titu Lemma part you wanted :

Titu's lemma

The Inequality

Let $x_1, x_2, ..., x_n$ be real numbers and $y_1, y_2, ..., y_n$ be positive real numbers.

Then, the following inequality holds,

$\frac{x_1^2}{y_1} + \frac{x_2^2}{y_2} + ... + \frac{x_n^2}{y_n} \ge \frac{(x_1 + x_2 + ... + x_n)^2}{y_1 + y_2 + ... + y_n}$

Why is this true? Actually, this inequality follows from the Cauchy-Schwarz Inequality.

$(\frac{x_1^2}{y_1} + \frac{x_2^2}{y_2} + ... + \frac{x_n^2}{y_n})(y_1 + y_2 + ... + y_n) \ge (x_1 + x_2 + ... + x_n)^2$

Examples

$1.$ Prove Nesbitt Inequality :

$\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{b + a} \ge \frac{3}{2}$

Solution :

We can't see any squares terms on the numerators, so wishful thinking motivates us to create them.

How can we create the square terms? Squaring the whole left hand side is very messy, and a much simpler way is to multiply the numerators and denominators of the fractions by $a, b, c$ respectively.

Now, the way to proceed is clear, as now by Titu's Lemma we get

$\frac{a^2}{ab + ac} + \frac{b^2}{ab + bc} + \frac{c^2}{bc + ac}$

$\ge \frac{(a + b + c)^2}{2(ab + bc + ca)}$

Now, we just have to prove that $2(a + b + c)^2 \ge 6(ab + bc + ca)$, which can be rewritten as

$(a + b + c)^2 \ge 3(ab + bc + ca)$, which can be rewritten as $a^2 + b^2 + c^2 \ge ab + bc + ca$,

The last inequality follows from $\frac{1}{2}[(a - b)^2 + (b - c)^2 + (a - c)^2] \ge 0$.

$2.$ (TOT 1998) Prove that for any positive real numbers $a, b, c$,

$\frac{a^3}{a^2 + ab + b^2} + \frac{b^3}{b^2 + bc + c^2} + \frac{c^3}{a^2 + ac + c^2} \ge \frac{a + b + c}{3}$

Solution :

Again, we want to make the numerators on the left hand side be squares.

So, we again multiply the numerators and denominators of the fractions by $a, b, c$ respectively.

By Titu's Lemma,

$\frac{a^4}{a(a^2 + ab + b^2)} + \frac{b^3}{b(b^2 + bc + c^2)} + \frac{c^3}{c(a^2 + ac + c^2)}$

$\ge \frac{(a^2 + b^2 + c^2)^2}{a(a^2 + ab + b^2) + b(b^2 + bc + c^2) + c(a^2 + ac + c^2)}$

But the denominator is equivalent to $(a + b + c)(a^2 + b^2 + c^2)$.

Thus, we the inequality becomes

$\frac{a^4}{a(a^2 + ab + b^2)} + \frac{b^3}{b(b^2 + bc + c^2)} + \frac{c^3}{c(a^2 + ac + c^2)} \ge \frac{a^2 + b^2 + c^2}{a + b + c}$

Finally, we have to prove that $\frac{a^2 + b^2 + c^2}{a + b + c} \ge \frac{a + b + c}{3}$, which is true. (The proof is similar to the last problem.))

$3.$ (IMO 1995) Let $a, b, c$ be positive real numbers such that $abc = 1$. Prove that

$\frac{1}{a^3(b + c)} + \frac{1}{b^3(a + c)} + \frac{1}{c^3(b + a)} \ge \frac{3}{2}$.

Solution : Direct application of Titu's Lemma is unfortunately doomed to failure. We divide the numerator and denominator by $a^2, b^2$ and $c^2$ respectively.

Now, we have by Titu's Lemma,

$\frac{1}{a^3(b + c)} + \frac{1}{b^3(a + c)} + \frac{1}{c^3(b + a)} = \frac{\frac{1}{a^2}}{a(b + c)} + \frac{\frac{1}{b^2}}{b(a + c)} + \frac{\frac{1}{c^2}}{c(b + a)}$

$\ge \frac{(\frac{1}{a} + \frac{1}{b} + \frac{1}{c})^2}{2(ab + bc + ca)} = \frac{(ab + bc + ca)^2}{2(ab + bc + ca)}$

$\ge \frac{ab + bc + ca}{2} \ge \frac{3\sqrt[3]{(abc)^2}}{2} = \frac{3}{2}$

where the last inequality holds by AM-GM.

This proves the inequality.

Problems

$1.$ Prove that for all positive real numbers $x, y, z$

$\frac{2}{x + y}+\frac{2}{y + z}+\frac{2}{z + x} \ge \frac{9}{x + y + z}$

$2.$ Prove that for all positive real numbers $a, b, c, d$

$\frac{a}{b + 2c + 3d} + \frac{b}{c + 2d + 3a} + \frac{c}{d + 2a + 3b} + \frac{d}{a + 2b + 3c} \ge \frac{2}{3}$

$3.$ Problem link

$4.$ (IMO 2005)

Prove that for all positive real numbers $x, y, z$ such that $xyz \ge 1$, then

$\frac{x^2 + y^2 + z^2}{x^5 + y^2 + z^2} + \frac{x^2 + y^2 + z^2}{y^5 + x^2 + z^2} + \frac{x^2 + y^2 + z^2}{z^5 + y^2 + x^2} \le 3$

I'll give it a try:

Question: We know that $\displaystyle \sum_{i=1}^n i = \frac {1}{2} n (n + 1)$, $\displaystyle \sum_{i=1}^n i^2 = \frac {1}{6} n (n + 1)(2n+1)$, $\displaystyle \sum_{i=1}^n i^3 = \frac {1}{4} n^2 (n + 1)^2$. We can find $\displaystyle \sum_{i=1}^n i^k$, for $k=4,5, \ldots$. But we need to know the previous sums of power. That is, for example, if we want to find the closed form of $\displaystyle \sum_{i=1}^n i^7$, we must first know $\displaystyle \sum_{i=1}^n i^j$ for $j=1,2,3,4,5,6$. Is there an alternative way to determine a sum of certain power without knowing their preceding sums?

Question 2: If the divisors of natural number $n$ are $a_1, a_2, a_3, \ldots , a_j$ arranged in ascending order, then why is it (usually) the median of these numbers is close to $\sqrt{n}$?

Question 3: It's been proven that for any configurations for a Rubik's Cube, the least number of moves to solve it is 20. Let $G_n$ denote the most number of moves for any configuration for a $n \times n \times n$ cube (so $G_3=20$). How do we evaluate $G_2, G_4, G_5, G_6, \ldots$?

Question 4: Mathematicians are always interested in the finding the largest prime number, the current record is a Mersenne Prime. But it appears that there are only few primes $p$ such that $M_p = 2^p - 1$ is also a prime. Don't you think there's a better way of finding prime numbers? Like applying Mill's constant, because it is GUARANTEED a prime number?

Question 5: There's plenty of ways to prove that a harmonic series diverge. Do you have your own proof that's not listed here?

Question 6: We denote $SOD(n)$ as the sum of digits of positive integer $n$. Is there a formula to determine $\displaystyle \sum_{i=1}^n SOD(i) \space$? What if the integer is written in other base representation (i.e: binary, hexadecimal)?

Posts will happen from an individuals account, with the tag of "Torque Group". This way, others will be able to identify who the originator is, and also find similar interesting material through the tags.

As such, you do not need to choose 1 area to focus on. In fact, having a variety of posts would be preferable, so that you get a broad coverage. I anticipate that different people will focus on specific topics that interest them, and there isn't a requirement for cohesion as a group.

It would be good to think about how you want to structure the timing of the posts. Having 1-2 posts a day would be great, but would of course depend on your availability as a group. I would also expect that other members would be interested in contributing similar posts, though at a lower frequency.

I came across this interesting problem :

There are $30$ people in a party. Each of them has exactly one favorite chess variant and exactly one favorite classical inequality. Each person lists this information in a survey. Among the survey responses, there are exactly $20$ different favorite chess variant and exactly $10$ different favorite inequalities. Let $n$ be the number of people M such that the number of people who listed M's favorite inequality is greater than the number of people who listed M's favorite chess variant. Prove that $n \ge 11$.