AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
, the sides 
and 
are parallel and the angles 
and 
are acute. Show that it is possible to divide the triangle 
into 4 disjoint triangle 
and the triangle 
into 4 disjoint triangles 
such that the triangles 
and 
are congruent for all 
.
is given in the plane, let 
be the set of points which lie strictly inside it. Also let 
be the set of circles in the plane. For a point 
, let 
be the reflection of 
in sides 
respectively. Define a function 
such that 
is the circumcircle of 
. Is 
injective? is called injective if for any 
, 
board, some squares are painted red. Let 
be the number of rows that have an odd number of red squares and let 
be the number of columns that have an odd number of red squares. Find all possible values of 
. For each value found, give a example of how the board can be painted.
sides are marked on the blackboard. Ana and Beto play alternately, Ana begins. Each player, in turn, must do the following:
join two vertices with a segment, without cutting another already marked segment; or delete a vertex that does not belong to any marked segment.
be the set of positive real numbers. Determine all functions 
such that ![\[x \big(f(x) + f(y)\big) \geqslant \big(f(f(x)) + y\big) f(y)\]](http://latex.artofproblemsolving.com/e/7/1/e71b6e0d0b858eb46b81149f1e6be8c41e13d301.png)
for every 
.
friends, 
people are seated around a circular table in a fixed order. Ali places apples for serving directly in front of himself and wants to distribute them among everyone. Since Ali and his friends dislike eating alone and won't start unless everyone receives an apple at the same time, in each step, each person who has at least one apple passes one apple to the first person to their right who doesn't have an apple (in the clockwise direction). such that after some number of steps, the situation reaches a point where each person has exactly one apple.
be a triangle with circumcircle , 
be the foot of altitudes from 
onto the opposite sides respectively and 
the orthocentre. Reflect across the line 
to obtain 
. Suppose there exists points 
such that 
is the incentre of 
. If 
and be the midpoints of 
and 
respectively, then show that 
are collinear.
square is divided into unit squares. Is it possible to fill each unit square with a number 
in such a way that, whenever one places the tile so that it fully covers nine unit squares, the tile will cover nine different numbers?
be a positive integer. There're roads in Mahismati, no three roads are concurrent and no two roads are parallel (so each two of them intersect). Number all possible 
angles formed by intersection points with 
in any order.
if he goes through 
, turns at the intersection point around the angle and then continues to 
(or vice versa). Katappa colors two numbers 
with 
with the same color iff there's a path traced by Baahubali which touches the angles numbered simultaneously.
colors will be used by Katappa to color all the numbers?
: In the picture attached below, total 
colors will be used to color the numbers in each set with same color 
. The numbers 
will be colored with the same color because the red path traced by Baahubali touches the angles 
.
, and be a positive integer. and 
denote the number of solutions to 
, where is allowed to vary on the set of positive integers
such that 
for all , and 
infintiely many often.
. Prove there are infinitely many primes 
such that divides atleast one element of
^2
.
.
, and let 
for all with 
. The lemma we wish to prove can easily be seen to be equivalent to
. We will determine the coefficients of each variable on both sides of the equation.
appears if and only if 
, in which case it comes with a factor if 
. Hence, the coefficient of on the left-hand side is 
. On the right-hand side, appears iff , in which case it comes with a factor if 
. Hence, the coefficient of on the right-hand side is 
, which is equal to the coefficient on the left. 
. By the Cauchy-Schwarz inequality,
and so on.
![\[\left(\sum_{1\le i<j\le n}|x_i-x_j|\right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}|x_i-x_j|^2\right)\]](http://latex.artofproblemsolving.com/4/7/3/473924c0c473b769ead37325b864455c58a4bd88.png)
.
and let 
. The inequality is equivalent to![\[\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)^2\right)\]](http://latex.artofproblemsolving.com/d/0/3/d03deb5369fe223a2ca0a0e2413d2a86ea2be289.png)
for all 
.![\[\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\]](http://latex.artofproblemsolving.com/f/c/2/fc2bbfcb4fb58cf04db910bdb7b00334ff9ac359.png)
![\[\sum_{j-i=l}(a_i+\dots+a_j)=\sum_{j-i=(n-l)}(a_i+\dots+a_j)\]](http://latex.artofproblemsolving.com/1/0/a/10a1559c7aa261915304975d35faa06fafcf0b31.png)
. Indeed, we may consider the 
matrix:![\[ \left( \begin{array}{cccc}
a_1 & a_2 & \dots & a_l \\
a_2 & a_3 & \dots & a_{l+1} \\
\vdots & \vdots & \ddots & \vdots\\
a_{n-l} & a_{n-l+1} & \dots & a_n \end{array} \right)\]](http://latex.artofproblemsolving.com/f/5/b/f5b5dd298011c9bdaca227fa948e80edebb14a7a.png)
![\[\sum_{l=1}^{n-1}\sum_{j-i=l}l^2=\sum_{l=1}^{n-1}(n-l)l^2=\frac{n^4-n^2}{12}\]](http://latex.artofproblemsolving.com/8/f/6/8f60d04846c488159e1d2557a5b7d36410f14ad9.png)
. Thus we have proven that![\[\frac{n^4-n^2}{12}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\]](http://latex.artofproblemsolving.com/6/3/b/63bd75efc6d642ee8b191d4a5fb5dcc1cc580b8b.png)
yields![\[\frac{n^2-1}{3}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\]](http://latex.artofproblemsolving.com/9/6/c/96c4ce1330750155d24ecf051f56bea39ae730fb.png)
as desired.
- that is, when the 
form an arithmetic sequence.
, the inequality is obviously true. Now let's assume that the inequality is true for and we will prove it for 
.
such that 
and we have 
we have: 
where:![\[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(\sum_{i,j=1}^{n+1} (y_{i}-y_{j})^2) - (\sum_{i,j=1}^{n+1} |y_{i}-y_{j}|)^2 \geq 0\]](http://latex.artofproblemsolving.com/4/a/8/4a8f2a61e33874d5f28e327de9d38e3c9d0ced07.png)
Let 
and 
and we have from induction's hypothesis 
.![\[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(2ny_{n+1}^2+\frac{n+1}{n}A_{n})-(2ny_{n+1}+B_{n})^2\]](http://latex.artofproblemsolving.com/2/5/4/254b0b224b1089baebf0ca03b72df8b3b15265b9.png)
reaches a minimal value for 
such that 
and after simplification, we get:![\[P'(y_{n+1})=0 \Leftrightarrow y_{n+1}=\frac{3B_{n}}{2n(n-1)}\]](http://latex.artofproblemsolving.com/7/8/4/784bf32c2d0a4aa7a62536c4604d0573395d834d.png)
Then we have:![\[P(y_{n+1}) \geq P(\frac{3B_{n}}{2n(n-1)})=\frac{n+2}{n-1}(\frac{2}{3}(n^2-1)A_{n}-B_{n}^2) \geq 0\]](http://latex.artofproblemsolving.com/1/2/a/12a77ebb397f141e717cfe006960979d6175d6e0.png)
Equality case: we have 
which is true only if there exists a real number 
such that 
for all 
, and![\[x_{n+1}=y_{n+1}+\frac{\sum_{i=1}^{n} x_{i}}{n}=\frac{3\sum_{i,j=1}^{n}|i-j|r}{2n(n-1)}+\frac{\sum_{i=1}^{n} ir}{n}=\frac{(n+1)r}{2}+\frac{(n+1)r}{2}=(n+1)r\]](http://latex.artofproblemsolving.com/9/7/7/9777aaa6b67a555689e493d1b95917350c53979c.png)
Which completes the proof by induction.
, then we work on the LHS,
Now we work on the RHS,
, so we may set it equal to zero. Then the desired inequality becomes![\[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\frac{n(n^2-1)}{3}\sum_{i=1}^n x_i^2.\]](http://latex.artofproblemsolving.com/c/c/8/cc8c5ff1f27e0b2037d5696c242cb6f8bf4f264a.png)
![\[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\left(\sum_{i=1}^n (2i-n-1)^2\right)\left(\sum_{i=1}^n x_i^2\right),\]](http://latex.artofproblemsolving.com/1/f/f/1ff4ae0f711993764b73ba3a11d8b6363a58fd77.png)
so it suffices to show that![\[\sum_{i=1}^n (2i-n-1)^2=\frac{n(n^2-1)}{3}.\]](http://latex.artofproblemsolving.com/2/c/2/2c23339e395ca3f60ad814e6c4d81227a887cf23.png)
, we have
as desired.
, we have
as desired.![\[x_1:x_2:\cdots:x_n=1-n:3-n:\cdots:n-1,\]](http://latex.artofproblemsolving.com/d/7/2/d723ec9eaf882c59f1e2068e1bca0d5ad8096c2c.png)
so they are in arithmetic progression, as desired.
![\[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le \frac{n^2 - 1}{3} \sum_{1 \le i < j \le n} (x_j - x_i)^2 \]](http://latex.artofproblemsolving.com/3/4/8/348997f373244e85581fc7ad2dc2240c9ca3bf70.png)
Now, we'll prove that![\[ \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} = \frac{n^2}{12} \]](http://latex.artofproblemsolving.com/8/f/9/8f9ff7c49d5e8fcd7970fa5ff350407037ed482b.png)
This can be proved by noticing that
which is what we wanted.![\[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \]](http://latex.artofproblemsolving.com/f/f/2/ff27ecf5a65bc310d9177f354a1179ad238fc291.png)
Now, apply CS at the RHS, we have![\[ 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \ge \left( 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) \right)^2 \]](http://latex.artofproblemsolving.com/a/4/8/a48f0841241e9f6505be42afb3f240ad595c33e4.png)
It suffices to prove that![\[ 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) = \sum_{1 \le i < j \le n} (x_j - x_i) \]](http://latex.artofproblemsolving.com/c/3/1/c316f1930b511ad1e07d645aef94b1bf2e54ca77.png)
But this is true by considering each coefficient of .
is 
and in the LHS, we have the coefficient of is![\[ \frac{2 ( (1 + 2 + \dots + j - 1) - (1 + \dots + (n - j)) )}{n} = \frac{(j - 1)j - (n -j)(n-j+1)}{n} = \frac{2nj - n^2 - n}{n} = 2j - n - 1\]](http://latex.artofproblemsolving.com/a/8/a/a8a7e720afb4c59f8ccec4016ef9edece7645867.png)
and 
equal the LHS and RHS of the inequality respectively. We have 
since 
. Next, let 
and 
. Also, let 
. By Cauchy-Schwarz, 
where the last step can be proven by considering specific values of .
. We have the following lemmas: 
Therefore, 
Therefore, we have 
. Note that 
. Also, let 
. For specific 
, notice that if 
, then 
will result in a negative term. If 
, then 
will result in a positive term, and otherwise nothing. We now see that the coefficient of will be 
as desired. However, 
. This means 
, which proves the inequality. Finally, we see that equality holds when 
is a constant which gives equality in the Cauchy-Schwarz. Since 
, this means 
must be an arithmetic sequence. 
. By Cauchy-Schwarz, ![\[ \left[\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{n(n+1)(n-1)}{12}\cdot\sum_{i=1}^nx_i^2;\]](http://latex.artofproblemsolving.com/1/6/2/16247e0cae88d3183694588c3f857c4a814f9daf.png)
that is, ![\[\left[4\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{2(n^2-1)}3\left[2n\sum_{i=1}^nx_i^2-2\left(\sum_{i=1}^nx_i\right)^2\right],\]](http://latex.artofproblemsolving.com/b/e/5/be59fffcb8422b4425dee0c924dcaaf5c5735e29.png)
which is equivalent to the desired inequality. Equality holds iff 
, \ldots, 
is an arithmetic sequence.
does not affect the problem, we can assume that the sum is 
. We have
Clearly, the equality condition of Cauchy will force the equality case of this inequality to also be an arithmetic sequence. In the case that one of the coefficients in the second line of our work is zero, we can add 
to each of the coefficients to get the same inequality but avoid division by zero.
. The base case 
simplifies to 
, which is clear. For the inductive step, we will assume that the problem is true for 
, and prove that it is also true for 
. Noticing that the problem statement does not change if we shift all variables by a constant, assume that their sum 
to simplify calculations. Let ![\[\rho_1 = \sum_{i, j=1}^k |x_i - x_j| \text{ and } \rho_2 = \sum_{i,j = 1}^k (x_i - x_j)^2.\]](http://latex.artofproblemsolving.com/2/d/5/2d5875dd945d07e39974def90b07248d12745358.png)
By the inductive hypothesis, we may assume that ![\[\frac{2(k^2 - 1)}{3} \cdot \rho_2 \ge \rho_1^2.\]](http://latex.artofproblemsolving.com/5/e/8/5e8d02f3b734d3057df49513039caefbfe127c57.png)
Let 
be ![\[P(x_{k + 1}) = \frac{2[(k + 1)^2 - 1]}{3} \cdot \sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 - \left(\sum_{i,j = 1}^{k + 1}|x_i - x_j|\right)^2.\]](http://latex.artofproblemsolving.com/2/7/d/27dfeec0ee9609d24e8704793494b534f6094474.png)
We wish to show that 
for 
. Using the fact that , we can calculate ![\[\sum_{i,j = 1}^{k + 1} |x_i - x_j| = p_1 + 2 \sum_{i = 1}^{k} (x_{k + 1} - x_i) = p_1 + 2kx_{k + 1}.\]](http://latex.artofproblemsolving.com/a/8/e/a8ead86e445ed8fea13d92336d6d2b819ec055d2.png)
We can also calculate ![\[\sum_{i,j = 1}^{k + 1}(x_i - x_j)^2 = \rho_2 + 2\sum_{i = 1}^k (x_i - x_{k + 1})^2 = p_2 + 2\sum_{i = 1}^k x_i^2 + 2k x_{k + 1}^2.\]](http://latex.artofproblemsolving.com/b/8/8/b88e4bfbdc999a01035eb5c4a1a6fa04a652d49e.png)
In addition, I claim that ![\[2\sum_{i = 1}^k x_i^2 = \frac{\rho_2}{k}.\]](http://latex.artofproblemsolving.com/5/5/7/557914d7e5862a0f5358822772a4b47400716953.png)
This is because 
So, we can further simplify our formula to get ![\[\sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 = \frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2.\]](http://latex.artofproblemsolving.com/6/a/b/6ab4f77fb8cd6cf336617f1bee3b2aeecc0cd7f7.png)
Thus, ![\[P(x_{k + 1}) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2\right) - (\rho_1 + 2k x_{k + 1})^2.\]](http://latex.artofproblemsolving.com/f/3/9/f39ebdf7f3a30200b54b5614239cd9734c3d6d19.png)
Treating this as a quadratic polynomial in terms of 
holding all other terms are constant, is minimized at ![\[x_{k + 1} = \frac{-(-4k\rho_1)}{2\left(\frac{4k^3 + 8k^2}{3} - 4k^2\right)} = \frac{4k\rho_1}{2\left(\frac{4k^3 - 4k^2}{3}\right)} = \frac{3\rho_1}{2k(k - 1)}.\]](http://latex.artofproblemsolving.com/e/4/a/e4aabb261a607c93e580e93a04c05c0f147f10a2.png)
Plugging this in, ![\[P\left(\frac{3\rho_1}{2k(k - 1)}\right) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + \frac{9\rho_1^2}{2k(k - 1)^2}\right) - \left(\rho_1 + \frac{3\rho_1}{k - 1}\right)^2.\]](http://latex.artofproblemsolving.com/2/3/c/23c5a047387dd422083eb4aefbd370fdbe557cbe.png)
This simplifies to 
By the inductive hypothesis, 
, so we get that which completes the inductive step. Equality holds if and only if for all 
, ![\[x_{k + 1} = \frac{3\sum_{i,j = 1}^k |x_i - x_j|}{2k(k - 1)}.\]](http://latex.artofproblemsolving.com/f/9/9/f990543a3686e18dc4cfaaae0ec7a05f34c23d4e.png)
We will prove that this is equivalent to 
being an arithmetic sequence using induction. For 
, the problem statement becomes 
, which is true for all 
and 
. Since any two numbers are in an arithmetic sequence, the base case is clear. For the inductive step, assume that 
, and we will prove that 
as well. This is equivalent to the numbers being in an arithmetic sequence. Since we previously assumed that 
, this means that 
. We can simplify 
In the sum in the numerator, a difference of 
occurs 
times, a difference of 
occurs 
times, and so-on. Thus, 
Thus, , completing the inductive step. Thus, we have proven the inequality and have shown that equality holds if and only if the variables are in an arithmetic sequence.
, where the 
's are non-negative. Then we have ![\begin{align*} \frac 23 (n^2-1) \sum_{i=1}^n \sum_{j=1}^n (x_i-x_j)^2 & = \frac 43 (n^2-1) \sum_{i=2}^n \sum_{j=1}^{i-1} (x_i-x_j)^2 \\ & = \frac 43 (n^2-1) \sum_{i=2}^n \sum_{j=1}^{i-1} (a_{i-1}+a_{i-2}+\dots+a_j)^2 \\ & = \frac 43 (n^2-1) \left [ \sum_{k=1}^{n-1} k(n-k) a_k^2+2\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} i(n-j) a_i a_j \right ].\end{align*}](http://latex.artofproblemsolving.com/2/f/b/2fb87980763440f89afaa28ec9ba0202af7f99c6.png)
And similarly, ![\begin{align*} \left (\sum_{i=1}^n \sum_{j=1}^n |x_i-x_j|\right)^2 & = 4 \left (\sum_{i=2}^n \sum_{j=1}^{i-1} (x_i-x_j)\right)^2 \\ & = 4 \left (\sum_{i=2}^n \sum_{j=1}^{i-1} (a_{i-1}+a_{i-2}+\dots+a_j)\right)^2 \\ & = 4\left [ \sum_{k=1}^{n-1} k^2(n-k)^2 a_k^2+2\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} ij(n-i)(n-j) a_i a_j \right].\end{align*}](http://latex.artofproblemsolving.com/9/8/c/98c5195cb5e820ac2abecc85fcd398b0b0d30a65.png)
![$$F(a_1,a_2,\dots,a_{n-1}):=\sum_{k=1}^{n-1} \left [ k(n-k)(n^2-1)-3k^2(n-k)^2\right ]a_k^2 -\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} \left [ 3ij(n-i)(n-j)-i(n^2-1)(n-j)\right ] 2a_ia_j\geqslant 0 \qquad (1)$$](http://latex.artofproblemsolving.com/1/6/0/1601ccb1544829fdd8ed11f359021e6f6e274efc.png)
The inequality is homogeneous, so we can assume wlog that 
So that the domain of 
becomes ![$[0,1]^{n-1}$](http://latex.artofproblemsolving.com/f/c/1/fc1cd7eeeea5a87664ff3788bf53ee54c07acc59.png)
which is compact. So attains a global minimum.
. If one of the 
's is 
and the rest are , then 
because 
is true when 
. And when all are then obviously 
. Now suppose 
so that we can proceed with Lagrange Multipliers. Taking the gradients of and the constraint function 
we get the equations 
(Take the empty sum to be ). Notice that we have variables 
and linear independent (this is not very hard to see?) equations 
and 
. So if there is a solution, it must be unique. We claim the solution is 
Indeed this solution satisfies and we can show without much effort that 
so it also satisfies . Finally, showing 
is pretty much the same as proving 
, so we'll omit this too. is . This proves 
and so the original inequality as well. Also the equality holds iff 
, as seen above. This implies that the equality case of the original inequality is when 
is arithmetic. This finishes the problem.
the equality doesn't hold?
such that: 
.
such that for any 
:
be real numbers.![\[
\left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2\le\frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2.
\]](http://latex.artofproblemsolving.com/8/1/e/81ef4493de1ab4a1ac30124fe291256917760ca1.png)
is an arithmetic sequence.
and only consider the case when 
.
.
Since equality occurs when 
![$$\sum_{k=1}^{n-1} \left [ k(n-k)(n^2-1)-3k^2(n-k)^2\right ]a_k^2 \geqslant \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} \left [ 3ij(n-i)(n-j)-i(n^2-1)(n-j)\right ] 2a_ia_j \qquad (1)$$](http://latex.artofproblemsolving.com/c/5/e/c5ebb5f9b506b1f69147265c583a3aafb3c4a4ca.png)
For convenience, let us define 
.
when 
(
Now it's not very hard to calculate the sums inside parenthesis; we'll find 
for all 
being arithmetic. So we're done.
and the other