Let $ABCDEF$ be a convex hexagon such that $AB$ is parallel to $DE$, $BD$ is parallel to $EF$, and $CD$ is parallel to $FA$.  Let $R_{A}$, $R_{C}$, $R_{E}$ denote the circumradii of triangles $FAB$, $BCD$, $DEF$, respectively, and let $P$ denote the perimeter of the hexagon.  Prove that
$R_{A}+R_{C}+R_{E} \ge \frac{P}{2}$

Solution:
Let $s_{1}=\left| AB \right|,\;s_{2}=\left| BC \right|,\;s_{3}=\left| CD \right|,\;s_{4}=\left| DE \right|,\;s_{5}=\left| EF \right|,\;s_{6}=\left| FA \right|$
Let $d_{1}=\left| FB \right|,\;d_{2}=\left| BD \right|,\;d_{1}=\left| DF \right|$
Let $\alpha_{1}=\angle FAB,\;\alpha_{2}=\angle ABC,\;\alpha_{3}=\angle BCD,\;\alpha_{4}=\angle CDE,\;\alpha_{5}=\angle DEF,\;\alpha_{6}=\angle EFA\;$
From the parallel lines on the hexagon we get:
$\alpha_{1}=\alpha_{4},\;\alpha_{2}=\alpha_{5},\;\alpha_{3}=\alpha_{6}$  [Equations 1]
So now we look at $\Delta FAB$.  We construct a perpendicular from $A$ to $FE$ and a perpendicular from $A$ to $BC$.
We find out the length of these two perpendiculars and add them to get the distance between parallel lines $FE$ and $BC$ and because of the triangle inequality the distance $\left| FB \right|$ is greater or equal to tha the distance between parallel lines $FE$ and $BC$:
This provides the following inequality:
$d_{1} \ge s_{6}sin(\alpha{6})+s_{1}sin(\alpha{2})$
Using the [Equations 1] we simplify to:
$d_{1} \ge s_{6}sin(\alpha{3})+s_{1}sin(\alpha{2})$ [Equation 2]
We now construct a perpendicular from $D$ to $FE$ and a perpendicular from $D$ to $BC$. Then we find out the length of these two perpendiculars and add them to get the distance between parallel lines $FE$ and $BC$ and get:
$d_{1} \ge s_{3}sin(\alpha{3})+s_{4}sin(\alpha{5})$
Using the [Equations 1] we simplify to:
$d_{1} \ge s_{3}sin(\alpha{3})+s_{4}sin(\alpha{2})$ [Equation 3]
We now add [Equation 2] and [Equation 3] to get:
$2d_{1} \ge (s_{3}+s_{6})sin(\alpha_{3})+(s_{1}+s_{4})sin(\alpha_{2})$ [Equation 4]
We now use the Extended law of sines on $\Delta FAB$ with $R_{A}$ to get:
$\frac{d_{1}}{sin(\alpha_{1})}=2R_{A}$
$d_{1}=2R_{A}sin(\alpha_{1})$ [Equation 5]
Substitute [Equation 5] into [Equation 4]:
$4R_{A}sin(\alpha_{1}) \ge (s_{3}+s_{6})sin(\alpha_{3})+(s_{1}+s_{4})sin(\alpha_{2})$
$4R_{A} \ge (s_{3}+s_{6})\frac{sin(\alpha_{3})}{sin(\alpha_{1})}+(s_{1}+s_{4})\frac{sin(\alpha_{2})}{sin(\alpha_{1})}$ [Equation 6]
To find the equivalent inequality for $4R_{C}$ and $4R_{E}$ we just need shift the indexes by two.  That is to add $2$ to each of the indexes of $s_{i}$ and $\alpha_{i}$ and adjust the indexes so that for $s$ the indexes are 1 through 6, and for $\alpha$ the indexes are 1 through 3.
$4R_{C} \ge (s_{2}+s_{5})\frac{sin(\alpha_{2})}{sin(\alpha_{3})}+(s_{3}+s_{6})\frac{sin(\alpha_{1})}{sin(\alpha_{3})}$ [Equation 7]
$4R_{E} \ge (s_{1}+s_{4})\frac{sin(\alpha_{1})}{sin(\alpha_{2})}+(s_{2}+s_{5})\frac{sin(\alpha_{3})}{sin(\alpha_{2})}$ [Equation 8]
Adding [Equation 6], [Equation 7], and [Equation 8] we get:
$4\left( R_{A}+R_{C}+R_{E} \right) \ge (s_{1}+s_{4})\left( \frac{sin(\alpha_{2})}{sin(\alpha_{1})}+ \frac{sin(\alpha_{1})}{sin(\alpha_{2})}\right)+(s_{2}+s_{5})\left( \frac{sin(\alpha_{2})}{sin(\alpha_{3})}+ \frac{sin(\alpha_{3})}{sin(\alpha_{2})}\right)+(s_{3}+s_{6})\left( \frac{sin(\alpha_{3})}{sin(\alpha_{1})}+ \frac{sin(\alpha_{1})}{sin(\alpha_{3})}\right)$
From AM-GM inequality we get:
$x+\frac{1}{x} \ge 2\;$ Therefore, $\left( \frac{sin(\alpha_{a})}{sin(\alpha_{b})}+ \frac{sin(\alpha_{b})}{sin(\alpha_{a})}\right) \ge 2\;$ for any index $a$ and $b$
Therefore,
$4\left( R_{A}+R_{C}+R_{E} \right) \ge 2(s_{1}+s_{4})+2(s_{2}+s_{5})+2(s_{3}+s_{6})$
$4\left( R_{A}+R_{C}+R_{E} \right) \ge 2\sum_{i=1}^{6}s_{i}$
$R_{A}+R_{C}+R_{E} \ge \frac{1}{2}\sum_{i=1}^{6}s_{i}$
Since $P=\sum_{i=1}^{6}s_{i}$, then $R_{A}+R_{C}+R_{E} \ge \frac{P}{2}$
~ Tomas Diaz.  orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Find all pairs $(a,b)$ of integers $a,b \ge 1$ that satisfy the equation
$a^{b^{2}}=b^{a}$

Solution:
Case 1: $(1 \le a \le b)$
$(a^{b})^{b}=b^{a}$
Looking at this expression since $b \ge a$ then $a^{b} \le b$.
Here we look at subcase $a>1$ which gives $a^{b}>b$ for all $(1 < a \le b)$.  This contradicts condition $a^{b} \le b$, and thus $a$ can't be more than one giving the solution of $a=1$ with $b \ge 1$.  So we substitute the value of $a=1$ into the original equation to get $1^{b^2}=b^{1}$ which solves to $b=1$ and our first pair $(a,b)=(1,1)$
Case 2: $(1 \le b < a)$
$a^{b^2}=b^{a}$
since $a>b$, then $b^{2}<a$ and we multiply both sides of the equation by $b^{-2b^{2}}$ to get:
$b^{-2b^{2}}a^{b^2}=b^{-2b^{2}}b^{a}$
$(ab^{-2})^{b^{2}}=b^{a-2b^{2}}$
Since $b^{2}<a$, then $(ab^{-2})^{b^{2}}>1$ and $b^{a-2b^{2}}>0$. This gives $a-2b^{2}>1$
This implies that $a>2b^{2}$ for $b>1$
Let $a=kb^{2}$ with $k \in \mathbb{Z} ^{+}$. Since $a>2b^{2}$, then $k \ge 3$
$(kb^{2}b^{-2})^{b^{2}}=b^{kb^{2}-2b^{2}}$
$k^{b^{2}}=b^{(k-2)b^{2}}$
$k=b^{k-2}$, which gives $b \ge 2$
subcase $k=3$:
$3=b^{3-2}=b$ and $a=kb^{2}=(3)(3)^{2}=27$. which provides 2nd pair $(a,b)=(27,3)$
subcase $k=4$:
$4=b^{4-2}=b^{2}$, thus $b=2$ and $a=kb^{2}=(4)(2)^{2}=16$. which provides 3rd pair $(a,b)=(16,2)$
subcase $k \ge 5$:
$k=b^{k-2}$, thus $b=k^{1/(k-2)}$ which decreases with $k$ and $b \to 1$ as $k \to \infty$ .  From subcase $k=4$, we know that $b=2$, thus for subcase $k \ge 5$, $1<b<2$.  Therefore this subcase has no solution because it contradicts the condition for Case 2 of $b \ge 2$.
Final solution for all pairs is $(a,b)=(1,1); (27,3); (16,2)$
~ Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let I be the incenter of triangle ABC. Let the incircle of ABC touch the sides
BC, CA, and AB at K, L, and M , respectively. The line through B parallel
to M K meets the lines LM and LK at R and S, respectively. Prove that angle
RIS is acute.

Solution: This problem needs a solution. If you have a solution for it, please help us out by adding it.


Two circles $G_{1}$ and $G_{2}$ are contained inside the circle $G$, and are tangent to $G$ at the distinct points $M$ and $N$, respectively.  $G_{1}$ passes through the center of $G_{2}$.  The line passing through the two points of intersection of $G_{1}$ and $G_{2}$ meets $G$ at $A$ and $B$.  The lines $MA$ and $MB$ meet $G_{1}$ at $C$ and $D$, respectively.
Prove that $CD$ is tangent to $G_{2}$.


$ABC$ is a triangle. $X$ lies on $BC$ and $AX$ bisects angle $A$. $Y$ lies on $CA$ and $BY$ bisects angle $B$. Angle $A$ is $60^{\circ}$. $AB + BX = AY + YB$. Find all possible values for angle $B$.

Let $D$ be on extension of $AB$ and $BD=BX$. Let $E$ be on $YC$ and $YE=YB$, then
Since $A=60$, $\triangle{ADE}$ is equilateral. Let $\angle{ABY}=x$, then,
We claim that $X$ must be on $BE$, i.e., $C=E$. If $X$ is not on $BE$, then $\angle{EBX}=\angle{YBX}-\angle{YBE}=\angle{YEX}-\angle{YEB}=\angle{BEX}$, which leads to $BX=EX=DX$, and $\triangle{BDX}$ is equilateral, which is not possible.
With that, we have, in $\triangle{ABE}$, $60+2x+x=180$, $x=40$, and $\angle{ABE}=80$.
Solution by $Mathdummy$.

Refer to the image in Solution 1 just rename Point X as P and Point Y as Q And no need of construction
\begin{align*}
\text{Set: } & \angle ABQ = \angle QBC = x, \quad \angle QCB = 120^\circ - 2x. \\
\text{Observe: } & \angle AQB = 120^\circ - x, \quad \angle APB = 150^\circ - 2x. \\
\text{Using the Law of Sines, we get: } & \\
& AQ = AB \cdot \frac{\sin x^\circ}{\sin(120^\circ - x)}, \\
& BP = AB \cdot \frac{\sin 30^\circ}{\sin(150^\circ - 2x)}, \\
& QB = AB \cdot \frac{\sin 60^\circ}{\sin(120^\circ - x)}. \\
\text{So, the relation } AB + BP &= AQ + AB \text{ is the same as saying} \\
& 1 + \frac{\sin 30^\circ}{\sin(150^\circ - 2x)} = \frac{\sin x + \sin 60^\circ}{\sin(120^\circ - x)}. \\
\text{We have } & \sin x + \sin 60^\circ = 2 \sin\left(\frac{1}{2}(x + 60^\circ)\right) \cos\left(\frac{1}{2}(x - 60^\circ)\right). \\
\text{Also, } & \sin(120^\circ - x) = \sin(x + 60^\circ) \quad \text{and} \\
& \sin(x + 60^\circ) = 2 \sin\left(\frac{1}{2}(x + 60^\circ)\right) \cos\left(\frac{1}{2}(x + 60^\circ)\right). \\
\text{So, } & \frac{\sin x + \sin 60^\circ}{\sin(120^\circ - x)} = \frac{\cos\left(\frac{1}{2}x - 30^\circ\right)}{\cos\left(\frac{1}{2}x + 30^\circ\right)}. \\
\text{Let } & \frac{1}{2}x = t. \\
\text{Then } & \frac{\cos(t - 30^\circ)}{\cos(t + 30^\circ)} - 1 = \frac{\cos(t - 30^\circ) - \cos(t + 30^\circ)}{\cos(t + 30^\circ)} = \frac{2 \sin(30^\circ) \sin(t)}{\cos(t + 30^\circ)}. \\
\text{Hence, the problem is just} & \frac{\sin(30^\circ)}{\sin(150^\circ - 4t)} = \frac{\sin(t)}{\cos(t + 30^\circ)} \\
\Rightarrow & \cos(t + 30^\circ) = 2 \sin(t) \sin(150^\circ - 4t) \\
& = \cos(5t - 150^\circ) - \cos(150^\circ - 3t). \\
\text{Now, } & \cos(t + 30^\circ) + \cos(5t + 30^\circ) = \cos(3t + 30^\circ). \\
\text{Because } & \cos(A + B) + \cos(A - B) = 2\cos A \cos B, \\
\text{we get } & \cos(t + 30^\circ) + \cos(5t + 30^\circ) = 2 \cos(3t + 30^\circ) \cos(2t). \\
\Rightarrow & (2 \cos(2t) - 1)(\cos(3t + 30^\circ)) = 0. \\
\text{This gives } & t \text{ to be } 20^\circ \text{ or } 30^\circ. \\
\text{Recall that } & t = \frac{1}{2}x = \frac{1}{4}\angle ABC. \\
\text{Here we can see } & \angle ABC \neq 120^\circ \text{ because of the angle sum property.} \\
\therefore & \angle B = 80^\circ, \angle A = 60^\circ, \text{ and } \angle C = 40^\circ.
\end{align*}
~Lakshya Pamecha
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Find all functions $f:\Bbb{R}\to \Bbb{R}$ such that

for all real numbers $x,y,z,t$.


Let $n$ be a positive integer and let $x_1 \le x_2 \le \cdots \le x_n$ be real numbers. Prove that

with equality if and only if $x_1, x_2, ..., x_n$ form an arithmetic sequence.

Solution:
This problem needs a solution. If you have a solution for it, please help us out by adding it.
have
\begin{align*}\left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2 &=\left(2\sum_{1\le i\le j\le n}(x_j-x_i)\right)^2 \\
&= \left((2n-2)x_n+(2n-6)x_{n-1}+\dots +(2-2n)x_1\right)^2 \\
&\le ((2n-2)^2+(2n-6)^2+(2n-10)^2+\dots + (2-2n)^2)(x_1^2+x_2^2+\dots + x_n^2) \\
&= \frac{4(n-1)(n)(n+1)}{3}(x_1^2+x_2^2+\dots + x_n^2) \\
&= \frac{2(n^2-1)}{3}\cdot 2(nx_1^2 + nx_2^2 + \dots + nx_n^2) \\
&= \frac{2(n^2-1)}{3}\cdot 2\left((n-1)\left(\sum_{i=1}^{n}{x_i^2}\right) + \left(\sum_{i=1}^{n}{x_i}\right)^2 - 2\sum_{1\le i<j\le n}x_ix_j\right) \\
&= \frac{2(n^2-1)}{3}\cdot 2\left(\sum_{1\le i<j\le n}(x_i-x_j)^2\right) \\
&= \frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2
\end{align*}


In a convex quadrilateral $ABCD$, the diagonal $BD$ bisects neither the angle $ABC$
nor the angle $CDA$. The point $P$ lies inside $ABCD$ and satisfies
Prove that $ABCD$ is a cyclic quadrilateral if and only if $AP = CP.$

Solution:
This problem needs a solution. If you have a solution for it, please help us out by adding it.
Assume $ABCD$ is cyclic,
let $K$  be the intersection of $AC$ and $BE$, let $L$ be the intersection of $AC$ and $DF$,

$\angle PBC=\angle DBA$, so $AD=CE$, and $DE//AC$.
$\angle PDC=\angle BDA$, so $AB=CF$, and $AC//BF$.

~szhangmath


Let $ABCD$ be a fixed convex quadrilateral with $BC = DA$ and $BC \nparallel DA$. Let two variable
points $E$ and $F$ lie of the sides $BC$ and $DA$, respectively, and satisfy $BE = DF$. The lines $AC$ and $BD$ meet at $P$, the lines $BD$ and $EF$ meet at $Q$, the lines $EF$ and $AC$ meet at $R$. Prove that the circumcircles of the triangles $PQR$, as $E$ and $F$ vary, have a common point other than $P$.


(Dan Schwarz, Romania)
Let $P(x)$ be a polynomial of degree $n>1$ with integer coefficients, and let $k$ be a positive integer.  Consider the polynomial $Q(x) = P( P ( \ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times.  Prove that there are at most $n$ integers $t$ such that $Q(t)=t$.

Solution:
We use the notation $P^k(x)$ for $Q(x)$.
Lemma 1. The problem statement holds for $k=2$.
Proof.  Suppose that $a_1, \dotsc, a_k$, $b_1, \dotsc, b_k$ are integers such that $P(a_j) = b_j$ and $P(b_j) = a_j$ for all indices $j$.  Let the set $\{ a_1, \dotsc, a_k, b_1, \dotsc, b_k \}$ have $m$ distinct elements.  It suffices to show that $\deg (P) \ge m$.
If $a_j = b_j$ for all indices $j$, then the polynomial $P(x)-x$ has at least $m$ roots; since $P$ is not linear, it follows that $\deg P \ge m$ by the division algorithm.
Suppose on the other hand that $a_i \neq b_i$, for some index $i$.  In this case, we claim that $a_j + b_j$ is constant for every index $j$.  Indeed, we note that

so $\lvert a_j - a_i \rvert = \lvert b_j - b_i \rvert$.  Similarly,

so $\lvert a_j - b_i \rvert = \lvert b_j - a_i \rvert$.  It follows that $a_j + b_j = a_i + b_i$.
This proves our claim.  It follows that the polynomial

has at least $m$ roots.  Since $P$ is not linear it follows again that $\deg P \ge m$, as desired.  Thus the lemma is proven.  $\blacksquare$
Lemma 2. If $a$ is a positive integer such that $P^r(a)$ for some positive integer $r$, then $P^2(a) = a$.
Proof.  Let us denote $a_0 = a$, and $a_j = P^j(a)$, for positive integers $j$.  Then $a_0 = a_r$, and

It follows that $\lvert a_{j+1} - a_j \rvert$ is constant for all indices $j$; let us abbreviate this quantity $d$.  Now, since

it follows that for some index $j$,

or $a_j = a_{j+2} = P^2(a_j)$.  Since $a = a_r = P^{r-j}(a_j)$, it then follows that $P^2(a) = a$, as desired.  $\blacksquare$
Now, if there are more than $n$ integers $t$ for which $Q(t) = t$, then by Lemma 2, there are more than $n$ integers $t$ such that $P^2(t) = t$, which is a contradiction by Lemma 1.  Thus the problem is solved.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Kevin Buzzard and Edward Crane, United Kingdom)
Let $a$ and $b$ be positive integers.  Show that if $4ab-1$ divides $(4a^2-1)^2$, then $a=b$.

Solution:
Lemma. If there is a counterexample for some value of $a$, then there is a counterexample $(a,b)$ for this value of $a$ such that $b<a$.
Proof.  Suppose that $b >a$.  Note that $4ab -1 \equiv -1 \pmod{4a}$, but $(4a^2-1)^2 \equiv 1 \pmod{4a}$.  It follows that $(4a^2-1)^2/(4ab-1) \equiv -1 \pmod{4a}$.  Since

it follows that $(4a^2-1)^2/(4ab-1)$ can be written as $4ab'-1$, with $0<b'<a$.  Then $(a,b')$ is a counterexample for which $b'<a$.  $\blacksquare$
Now, suppose a counterexample exists.  Let $(a,b)$ be a counterexample for which $a$ is minimal and $b<a$.  We note that

and

Now,

Thus $(b,a)$ is a counterexample.  But $b<a$, which contradicts the minimality of $a$.  Therefore no counterexample exists.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled $1$, $2$, ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).
Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off.
Let $M$ be number of such sequences consisting of $k$ steps, resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on.
Determine $\frac {N}{M}$.

Solution:
For convenience, let $A$ denote the set $(1,2,\ldots n)$ and $B$ the set $(n+1,n+2,\ldots,2n)$.
We can describe each sequences of switching the lamps as a $k$-dimensional vector
$(a_1, a_2, \ldots, a_k)$, where $a_i \in A \cup B$ signifies which lamp was switched on the $i$-th move for $i=1,2,\ldots k$.
Let $\cal{N}$ consist of those sequences that contain each of the numbers in $A$ an odd number of times and each of the numbers in $B$ an even number of times. Similarly, let $\cal{M}$ denote the set of those sequences that contain no numbers from $B$ and each of the numbers in $A$ an odd number of times. By definition, $M=|\cal{M}|$ and $N=|\cal{N}|$.
Define the mapping $f:\cal{N} \rightarrow \cal{M}$ as
What we want to show now is that each element of $\cal{M}$ is an image of exactly $2^{k-n}$ elements from $\cal{N}$, which would imply $N = 2^{k-n}M$ and solve the problem.
Consider an arbitrary element $y$ of $\cal{M}$ and let $l_i$ be the number of appearances of the number $i$ in $y$ for $i=1,2,\ldots n$. Now consider the set of pre-images of $y$, that is $X_y = \{ x | f(x) = y \}$.
It is easy to see that each element $x\in X_y$ is derived from $y$ by flipping an even number of its $1$-s, $2$-s, and so on, where flipping means changing the number $j\in A$ to $j+n\in B$. Since each such set of flippings results in a unique $x$, all we want to count is the number of flippings. We can flip exactly $0, 2, 4,\ldots$ of the $1$-s, so that results in

flippings. Combine each of them with the $2^{l_2-1}$, $2^{l_3-1}$, etc. ways of flipping the $2$-s, $3$-s etc. respectively to get the total number of flippings:

This shows that $|X_y| = 2^{k-n}$ and the proof is complete.
--Vbarzov 03:04, 5 September 2008 (UTC)


Determine all functions $f$ from the set of positive integers to the set of positive integers such that, for all positive integers $a$ and $b$, there exists a non-degenerate triangle with sides of lengths
(A triangle is non-degenerate if its vertices are not collinear.)
Author: Bruno Le Floch, France

Solution:
Answer: The only such function is $f(x)=x$.
It is easy to see that this function satisfy the condition. We are going to proof that this is the only such function.
We start with
Lemma. If 1, $a$, $b$ are sides of a non-degenerate triangle then $a=b$.
Proof. In this case $a<b+1$, therefore $a \le b$. By the same reason, $b \le a$. Therefore $a=b$.
Let $u=f(1)$. Now consider the given condition for $a=1$. By Lemma we get that
First, suppose $u>1$. Then $f$ is a periodic function. But then $f$ is bounded by a constant $M$, i.e. $f(x)<M$. Then take, $a>2M$. We get that $a,f(b)$ and $f(b+f(a)-1)$ are sides of the triangle, but the first number is greater than $2M$ and other two are less than $M$, which is imposible. We get the contradiction, so $u$ could not be greater than 1.
So $u=f(1)=1$.
Property 1. For any $x$
Proof. Consider the given condition for $a=x$, $b=1$ and use Lemma.
Property 2. For any $x$ and $y$
Proof. Consider the given condition for $a=f(x+1)$, $b=y$ and use triangle inequality and Property 1.
Let $g(x)=f(x+1)-1$.
Property 3. For any $x$ and $y$
Proof. Follows from Property 2.
Property 4. For any $x$, $y$, $m$, $n$
Proof. Follows from Property 3.
Property 5. For any $n$, there is $k>n$, s.t. $g(k) \ge k$.
Proof. Because of the Property 1.
Property 6. $g(x)=x$.
Proof. Suppose, for some $x$, $g(x)=y\ne x$. Without lost of generality we can assume that $x<y$. Then there is a number $n$, such than any $k>n$ could be represented as $k=ax+by$, where $a>b$. Then $g(k)=g(ax+by)\ge ag(x)+bg(y)=ay+bx>ax+by=k$. That contradicts to the Property 5.
Therefore by definion of $g$,  $f(x)=x$.


Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed
Type 1) Choose a non-empty box $B_j$, $1\leq j \leq 5$, remove one coin from $B_j$ and add two coins to $B_{j+1}$;
Type 2) Choose a non-empty box $B_k$, $1\leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k+1}$ and $B_{k+2}$.
Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$ become empty, while box $B_6$ contains exactly $2010^{2010^{2010}}$ coins.
Author: Hans Zantema

Solution:
Let the notation $[a_1,a_2,a_3,a_4,a_5,a_6]$ be the configuration in which the $x$-th box has $a_x$ coin,
Let $T=2010^{2010^{2010}}$.

Our starting configuration is $[1,1,1,1,1,1]$

Compound move 1: $[a,0]\rightarrow[0,2a]$, this is just repeated type 1 move on all $a$ coins.
Compound move 2: $[a,0,0]\rightarrow[0,2^a,0]$, apply type 1 move on 1 of the coin to get $[a-1,2,0]$, then apply compound move 1 to the 2 coins to get $[a-1,0,2^2]$, apply type 2 move and get $[a-2,2^2,0]$, and repeat compound move 1 and type 2 move until $[0,2^a,0]$ is achieve.
Compound move 3: $[a,b,0,0]\rightarrow[a-1,2^b,0,0]$, apply compound move 2 to obtain $[a,0,2^b,0]$ and use type 2 move to get $[a-1,2^b,0,0]$
Compound move 4: $[a,0,0,0]\rightarrow[0,2^{2^{.^{.^{.^2}}}},0,0]$ with $a$ $2$'s. Apply compound move 3 $a$ times.
Compound move 5: $[a,0,0]\rightarrow[b,0,0]$ with $a>b$, use type 2 move $(a-b)$ times.
Let's follow this move:
Using Compound move 1, 4 and 5, We can obtain:
$[0,1,19,0,0,0]\rightarrow[0,1,0,X,0,0]\rightarrow[0,0,X,0,0,0]\rightarrow[0,0,0,Y,0,0]\rightarrow[0,0,0,T/4,0,0]\rightarrow[0,0,0,0,T/2,0]\rightarrow[0,0,0,0,0,T]$
, where $X, Y = 2^{2^{.^{.^{.^2}}}}$ where X has $19$ 2's and Y has $X$ 2's, and $Y$ is clearly bigger then $T/4$


Let $ABC$ be a triangle with $\angle BCA=90^{\circ}$, and let $D$ be the foot of the altitude from $C$. Let $X$ be a point in the interior of the segment $CD$. Let $K$ be the point on the segment $AX$ such that $BK=BC$. Similarly, let $L$ be the point on the segment $BX$ such that $AL=AC$. Let $M=\overline{AL}\cap \overline{BK}$. Prove that $MK=ML$.

Solution:
Let $\Gamma$, $\Gamma'$, $\Gamma''$ be the circumcircle of triangle $ABC$, the circle with its center as $A$ and radius as $AC$, and the circle with its center as $B$ and radius as $BC$, Respectively.
Since the center of $\Gamma$ lies on $BC$, the three circles above are coaxial to line $CD$.
Let Line $AX$ and Line $BX$ collide with $\Gamma$ on $P$ ($\neq A$) and $Q$ ($\neq B$), Respectively. Also let $R = AQ \cap BP$.
Then, since $\angle AYB = \angle AZB = 90^{\circ}$, by ceva's theorem, $R$ lies on $CD$.
Since triangles $ABC$ and $ACD$ are similar, $AL^2 = AC^2 = AD \cdot AB$, Thus $\angle ALD = \angle ABL$.
In the same way, $\angle BKD = \angle BAK$.
Therefore, $\angle ARD = \angle ABQ = \angle ALD$ making $(A, R, L, D)$ concyclic.
In the same way, $(B, R, K, D)$ is concyclic.
So $\angle ADR = \angle ALR = 90^{\circ}$, and in the same way $\angle BKR = 90^{\circ}$. Therefore, the lines $RK$ and $RL$ are tangent to $\Gamma'$ and $\Gamma''$, respectively.
Since $R$ is on $CD$, and $CD$ is the concentric line of $\Gamma'$ and $\Gamma''$, $RK^2 = RL^2$, Thus $RK = RL$. Since $RM$ is in the middle and $\angle ADR = \angle BKR = 90^{\circ}$,
we can say triangles $RKM$ and $RLM$ are congruent. Therefore, $KM = LM$.
Edit: I believe that this solution, which was posted on IMO 2012-4's page, was meant to be posted here.
~ Latex edit by Kscv
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $\mathbb Q_{>0}$ be the set of all positive rational numbers. Let $f:\mathbb Q_{>0}\to\mathbb R$ be a function satisfying the following three conditions:
(i) for all $x,y\in\mathbb Q_{>0}$, we have $f(x)f(y)\geq f(xy)$;
(ii) for all $x,y\in\mathbb Q_{>0}$, we have $f(x+y)\geq f(x)+f(y)$;
(iii) there exists a rational number $a>1$ such that $f(a)=a$.
Prove that $f(x)=x$ for all $x\in\mathbb Q_{>0}$.


For each positive integer $n$, the Bank of Cape Town issues coins of denomination $\tfrac{1}{n}$. Given a finite collection of such coins (of not necessarily different denominations) with total value at most $99+\tfrac{1}{2}$, prove that it is possible to split this collection into $100$ or fewer groups, such that each group has total value at most $1$.

Solution:
The bound is not tight. We'll prove the result for at most $k - \frac{k}{2k+1}$ with $k$ groups.
First, perform the following optimizations.
- If any coin of size $\frac{1}{2m}$ appears twice, then replace it with a single coin of size $\frac{1}{m}$.
- If any coin of size $\frac{1}{2m+1}$ appears $2m+1$ times, group it into a single group and induct downwards.
Apply this operation repeatedly until it cannot be done anymore.
Now construct boxes $B_0$, $B_1$, ...., $B_{k-1}$. In box $B_0$ put any coins of size $\tfrac 12$ (clearly there is at most one).
In the other boxes $B_m$, put coins of size $\frac{1}{2m+1}$ and $\frac{1}{2m+2}$ (at most $2m$ of the former and at most one of the latter).
Note that the total weight in the box is less than $1$.
Finally, place the remaining ``light coins of size at most $\frac{1}{2k+1}$ in a pile.
Then just toss coins from the pile into the boxes arbitrarily, other than the proviso that no box should have its weight exceed $1$.
We claim this uses up all coins in the pile. Assume not, and that some coin remains in the pile when all the boxes are saturated.
Then all the boxes must have at least $1 -\frac{1}{2k+1}$, meaning the total amount in the boxes is strictly greater than

which is a contradiction. (The inequality is strict since the pile has a coin leftover.)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f$:$\mathbb{R}\rightarrow\mathbb{R}$ satisfying the equation
$f(x+f(x+y))+f(xy) = x+f(x+y)+yf(x)$
for all real numbers $x$ and $y$.
Proposed by Dorlir Ahmeti, Albania

Solution:
$f(x+f(x+y)) + f(xy) = x + f(x+y) + yf(x)$ for all real numbers $x$ and $y$.
(1) Put $x=y=0$ in the equation,
We get$f(0 + f(0)) + f(0) = 0 + f(0) + 0$
or $f(f(0)) = 0$
Let $f(0) = k$, then $f(k) = 0$
(2) Put $x=0, y=k$ in the equation,
We get $f(0 + f(k)) + f(0) = 0 + f(k) + kf(0)$
But $f(k) = 0$ and $f(0) = k$
so, $f(0) + f(0) = f(0)^2$
or $f(0)[f(0) - 2] = 0$
Hence $f(0) = 0, 2$
Case $1$ : $f(0) = 0$
Put $x=0, y=x$ in the equation,
We get $f(0 + f(x)) + f(0) = 0 + f(x) + xf(0)$
or, $f(f(x)) = f(x)$
Say $f(x) = z$, we get $f(z) = z$
So, $f(x) = x$ is a solution -- fallacy
Case $2$ : $f(0) = 2$
Again put $x=0, y=x$ in the equation,
We get $f(0 + f(x)) + f(0) = 0 + f(x) + xf(0)$
or, $f(f(x)) + 2 = f(x) + 2x$
We observe that $f(x)$ must be a polynomial of power $1$ as any other power (for that matter, any other function) will make the $LHS$ and $RHS$ of different powers and will not have any non-trivial solutions. -- fallacy
Also, if we put $x=0$ in the above equation we get $f(2) = 0$
$f(x) = 2-x$ satisfies both the above.
Hence, the solutions are $\boxed{\color{red}{f(x) = x}}$ and $\boxed{\color{red}{f(x) = 2-x}}$.


The equation
is written on the board, with $2016$ linear factors on each side. What is the least possible value of $k$ for which it is possible to erase exactly $k$ of these $4032$ linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?


An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:
($1$) no one stands between the two tallest players,
($2$) no one stands between the third and fourth tallest players,
$\;\;\vdots$
($N$) no one stands between the two shortest players.
Show that this is always possible.


Let $a_1, a_2, \dots$ be an infinite sequence of positive integers. Suppose that there is an integer$N > 1$ such that, for each $n \geq N$, the number $\frac{a_1}{a_2}+\frac{a_2}{a_3}+\dots +\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}$ is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M.$


The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation:
If there are exactly $k > 0$ coins showing $H$, then he turns over the $k^{th}$ coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$, which stops after three operations.
(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For
example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$
possible initial configurations $C$.

Don't worry, this is way simpler than it's length may suggest :)
Claim: The expected value of $L(C)$ is $\frac{n(n+1)}{4}$.
We prove parts A and B simultaneously using induction.
Base case: $n=1$
$L(T)=0$ and $L(H)=1$, and these are the only possibilities, so clearly the process terminates and $E[L(C)] = \frac{1}{2} = \frac{1*2}{4}$.
Inductive step: Assume that for $n-1$ coins, the process always terminates, and $E[L(C)] = \frac{n(n-1)}{4}$. Define $E_{n-1} = E[L(C)]$ here. Now, for $n$ coins, define $E_{n} = E[L{C}]$ across all $2^n$ configurations. Consider cases on the last coin:
Case 1: Final coin is $T$
If the last coin is $T$, then we simply can forget about it, as we can flip it to heads only if we have n heads, which is impossible. This occurs with probablity $P_{T} = 1/2$, and will be identical to the general $n-1$ case; thus, this process terminates, and we will have an expected number of moves here of $E_{n-1}$.
Case 2: Final coin is $H$
The probability that this occurs is $P_{H} = 1/2$. The only way we have for the process to terminate now is for all coins to show heads, after which we can progressively flip each coin from right to left (this will take $n$ moves). Thus, we now have a new goal for the first $n-1$ coins (given the head at the end); get all heads.
We claim that this process is symmetrical to the original process on $n-1$ coins, and thus it terminates and has the expected number of moves $E_{n-1}$.
Proof: Let us have $k \ge 1$ heads in our group of n coins, of which $k-1$ are in the first n-1. We are supposed to flip the $k$'th coin from the left in the first n-1 coins, which is equivalent to flipping the $(n-k)$'th coin from the right (in the first $n-1$ coins, NOT all $n$ coins), but there are $n-k$ tails in the first $n-1$ coins! We now have a new process defined as follows:
Consider a configuration of $n-1$ coins with $x \ge 1$ tails, and flip the x'th coin from the right, and keep flipping until all coins are heads.
This is clearly symmetric to the original process, and will terminate if and only if the original process on $n-1$ coins does, and has the same expected number of moves as the original. Thus, the claim is proven.
Back to the case: We now have a process to get to all heads that will terminate with an expected number of steps of $E_{n-1}$, and then an n-step algorithm to reach the finish. Thus, here also, the process terminates, and we have a total expected number of steps as $E_{n-1}+n$.
Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. $\boxed{Q.E.D}$ Also, the expected value of steps can be easily computed now; $E_{n} = (P_{T})(E_{n-1})+(P_{H})(E_{n-1}+n) = E_{n-1}+n/2 = \frac{n(n-1}{4}+\frac{n}{2} = \boxed{\frac{n(n+1)}{4}}$ as desired. We are now done.
-Solution by thanosaops

We define a sequence $\{a_i\}_{i=1}^n$: $a_i=1$ if the $i$'th coin is $H$ and $a_i=0$ if the $i$'th coin is $T$. Then, $k$ will be the number of $1$'s in $\{a_i\}$ and after each operation, $a_k$ will be changed to $1-a_k$. Let $f(n)=\sum L\{a_i\}=$ sum of $L\{a_i\}$ over all possible $\{a_i\}$ (of length $n$).
We shall prove that the process terminates and find the value of $f(n)$ using strong induction.

Base case: Clearly, for $n=1$, the process terminates.
Induction hypothesis: For $n=1, 2, 3, \cdots, k$, the process terminates.
Inductive step: We claim that for $n=k+1$, the process terminates as well.

Case 1: $a_1=1$
This means that $\{a_i\}=\{1, a_2, a_3, \cdots, a_n\}$. With the proof of the claim in Solution 1, we can similarly prove that operating on $\{a_i\}$ is equivalent to operating on $\{a_2, a_3, \cdots, a_n\}$.
By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{1, 0, 0, \cdots, 0\}$ at the end of this process. Now, we operate one more time to change $a_1$ from $1$ to $0$. Hence, the process terminates.
We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_n\}+1$. Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case

Case 2: $a_1=0$ and $a_n=1$
This means that $\{a_i\}=\{0, a_2, a_3, \cdots, a_{n-1}, 1\}$. Operating on $\{a_i\}$ is now equivalent to operating on $\{a_2, a_3, \cdots, a_{n-1}\}$.
By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{0, 0, 0, \cdots, 0, 1\}$ at the end of this process. Now, since $k=1$, $a_1$ will become $1$. Now, $k=2$, so $a_2$ will become $1$ as well. This process will repeat until $k=n$ and $\{a_i\}$ has been changed to $\{1, 1, 1, \cdots, 1\}$. Now, since $k=n$, $a_n$ will become $0$. Now, $k=n-1$, so $a_{n-1}$ will become $0$ as well. This process will repeat again until $k=0$ and $\{a_i\}$ has been changed to $\{0, 0, 0, \cdots, 0\}$. Hence, the process terminates.
We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+(2n-1)$. Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case

Case 3: $a_n=0$
This means that $\{a_i\}=\{a_1, a_2, a_3, \cdots, a_{n-1}, 0\}$. Operating on $\{a_i\}$ is now equivalent to operating on $\{a_1, a_2, \cdots, a_{n-1}\}$.
By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{0, 0, 0, \cdots, 0, 0\}$ at the end of this process. Hence, the process terminates.
We can also see that $L\{a_i\}=L\{a_1, a_2, \cdots, a_{n-1}\}$. Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case

This is already sufficient to prove part A, but we want to find $f(n)$ too, and we have overcounted!
Case 4: $a_1=1$ and $a_n=0$ (This is what we have overcounted)
This means that $\{a_i\}=\{1, a_2, a_3, \cdots, a_{n-1}, 0\}$. Operating on $\{a_i\}$ is now equivalent to operating on $\{a_2, a_3, \cdots, a_{n-1}\}$.
By our induction hypothesis, this process will terminate, and hence $\{a_i\}$ will be changed to $\{1, 0, 0, \cdots, 0, 0\}$ at the end of this process. Now, we operate one more time to change $a_1$ from $1$ to $0$. Hence, the process terminates.
We can also see that $L\{a_i\}=L\{a_2, a_3, \cdots, a_{n-1}\}+1$. Hence, sum of $L\{a_i\}$ over all possible $\{a_i\}$ in this case

Hence, we have proven that for all configurations, the process terminates, $\boxed{Q.E.D.}$ Now, all that remains is to calculate $f(n)$.

This can be rearranged to give us

When $n=1$, $f(n)-n(n+1)\cdot2^{n-2}=0$. This is good, because now we know that $\forall n\in\mathbb{Z}^{+}, f(n)-n(n+1)\cdot2^{n-2}=0$ i.e. $f(n)=n(n+1)\cdot2^{n-2}$.
Now the average will be $\frac{n(n+1)\cdot2^{n-2}}{2^n}=\boxed{\frac{1}{4}n(n+1)}$
~IraeVid13


Two squirrels, Bushy and Jumpy, have collected 2021 walnuts for the winter. Jumpy numbers the walnuts from 1 through 2021, and digs 2021 little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves. In the $k$-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.
Prove that there exists a value of $k$ such that, on the $k$-th move, Jumpy swaps some walnuts $a$ and $b$ such that $a < k < b$.

Solution:
We will start by introducing some notation.
The proof works by counting the parity of upcomming bad nuts and hinges on the fact that 2021 is odd.
We start by proving that at any point in time there are an odd number of bad
nuts. Let $B$ be the number of bad nuts and $G$ the number of good nuts. A bad
nut is either part of two increasing or two decreasing pairs. Let the number
of increasing bad nuts be $B_1$ and decreasing bad nuts be $B_2$. A good nut
is part of one increasing and one decreasing pair. Let $I$ and $D$ be the
number of increasing and decreasing pairs respectively. Then
$2I = G + 2B_1$
$2D = G + 2B_2$
since we are double-counting each pair. Therefore $G$ must be even, and since $2021 = G + B$ is odd, $B$ must be odd.
If we can prove the existence of a bad current nut, we are done. We show that when a current nut is good, the number of bad upcomming nuts does not change parity after the move. Since there are and odd number of upcomming bad nuts before the first move (every nut is upcomming) and 0 upcomming bad nuts after the last move (there are 0 upcomming nuts), this will show not all current nuts can be good which completes the proof.
We now show that when the current nut is good, the number of bad upcomming nots does not change parity. Consider the $k$'th move and assume the current $n$ is good and lies in hole $H_i$. After the move, the current nut is no longer upcomming, but since it was asummed to be good, this does not contrubute to the number of bad upcomming nuts. The only nuts whose status can possibly change is the nuts in holes $H_{i-2}, H_{i-1}, H_{i+1}, H_{i+2}$. Since the current nut is good, its two neighbors $a,b$ in $H_{i-1}, H_{i+1}$ respectively are either both smaller or larger than $n$. We tackle the two cases seperately.
Case $a,b < n$
In this case neither $a$ nor $b$ are upcomming nuts at the time of the move and their status after the move is
irrelevant for the parity of bad upcomming nuts. Consider the nut $c$ in hole $H_{i-2}$. If $c$ is not upcomming, it is irrelevant. Assume $c$ is upcomming. Then $c > n$ and thus $c > a,b$. Therefore the nut pair $H_{i-2}, H_{i-1}$ is decreasing both before and after the move, so $c$ cannot change status. One can make an analogous argument for the nut on $H_{i+2}$. This completes the proof the the parity of upcomming bad nuts are unchanged in this case.
Case $a,b > n$
In this case the nuts $a,b$ are upcomming, so their status matters. Let $c$ be the nut in $H_{i-2}$. If the status of either of the holes $H_{i-2}, H_{i-1}$ change, it changes for both of them. This is because the pair $H_{i-1}, H_i$ is decreasing both before and after the move, so for a status change to occur it must be the case that it is the pair $H_{i-2}, H_{i-1}$ which changes direction (which in turn changes the status for both holes). If swapping $a$ and $b$ changes the direction of $H_{i-2}, H_{i-1}$, then either $a < c < b$ or $b < c < a$ is true. In both cases, $c > n$, so $c$ is an upcomming nut. Since the nuts in both $H_{i-1}$ and $H_{i+1}$ are upcomming both before and after the move, changing the status of either $H_{i-2}$ or $H_{i-1}$ yields a status change for two upcomming nuts. A completely analogous argument can be made for $H_{i+1}, H_{i+2}$.
This shows that if some upcomming nut changes status after the move, then an even number of upcomming nuts change status. This preserves the parity of the number of upcomming bad nuts and completes the proof.


Find all triples $(a,b,p)$ of positive integers with $p$ prime and

Solution:
Case 1: $b < p$
Case 2: $p \le b < 2p$

Case 3: $2p \le b$
Just like in case 2, $b!$ is divisible by $p$ so $a$ must also be divisible by $p$. However, $b!$ and $a^p$ are also both divisible by $p^2$, so remainders modulo $p^2$ tell us that no solutions exist.
Conclusion:
The only solutions are $(a,b,p) = (2,2,2), (3,4,3)$.

I considered the cases:
1) If \(a\) is even, then it must:
2) If \(a\) is odd, then it must:
Examining 1.a), we end up with an equation of the form \(a^p = p+1\), which has no integer solutions.
In case 1.b), \(b!\) can take values: 2, 6, 24, 120, 720, ..., so \(b!+2\) takes values: 4, 8, 26, 122, 722, .... We observe that the only perfect square is 4 among the possible cases, as for \(b \geq 5\), the result ends in 2, which is not a perfect square. Therefore, we have the triple \((2,2,2)\).
Case 2.a) yields \(a^2 = 3\), which is rejected.
Examining the last case 2.b), we have for \(b!\) the values: 2, 6, 24, 120, 720, 5040,
The analysis of the last case is incomplete, which is why I wasn't initially sure about the number of triples. Therefore, with this approach (which is not strictly documented), we find the triples: \((2,2,2), (3,4,3)\).


Let $n$ be a positive integer. A Japanese triangle consists of $1 + 2 + \dots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1$, $2$, $\dots$, $n$, the $i^{th}$ row contains exactly $i$ circles, exactly one of which is coloured red. A ninja path in a Japanese triangle is a sequence of $n$ circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with $n = 6$, along with a ninja path in that triangle containing two red circles.
[Image to be inserted; also available in solution video]

Solution: https://www.youtube.com/watch?v=jZNIpapyGJQ [Video contains solutions to all day 2 problems]


Two planes, $P$ and $Q$, intersect along the line $p$.  The point $A$ is in the plane $P$, and the point ${C}$ is in the plane $Q$; neither of these points lies on the straight line $p$.  Construct an isosceles trapezoid $ABCD$ (with $AB$ parallel to $DC$) in which a circle can be inscribed, and with  vertices $B$ and $D$ lying in the planes $P$ and $Q$, respectively.

Solution:
We first observe that we must have both lines $AB$ (which we shall denote $a$) and $DC$ (which we shall denote $c$) parallel to $p$, since if one of them is not, then neither can be and they must both intersect $p$ (since they are both coplanar with $p$), making them  skew.
Now we note since a circle can be inscribed in the trapezoid, we must have $AB + DC = AD + BC$, and since the trapezoid is isosceles, this implies that each of the trapezoid's legs has length equal to the average of the lengths of the bases.
We can find this average by dropping perpendicular $AA'$ to $c$ such that $A'$ is on $c$.  The average will be $A'C$, which is one of the sides of the rectangle with sides on $a$ and $c$ with vertices at $A$ and ${C}$.
We now draw a circle with center ${C}$ that contains $A'$.  The intersections of this circle with $a$ are the two possible values of $B$, from either of which it is trivial to determine the corresponding location for $D$.  It is worth noting that the intersection points may concur (in which case there is only one distinct possibility (a square)), or they may not occur at all.  Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Consider a cone of revolution with an inscribed sphere tangent to the base of the cone. A cylinder is circumscribed about this sphere so that one of its bases lies in the base of the cone. Let $V_1$ be the volume of the cone and $V_2$ be the volume of the cylinder.
a) Prove that $V_1 \neq V_2$;
b) Find the smallest number $k$ for which $V_1 = kV_2$; for this case, construct the angle subtended by a diamter of the base of the cone at the vertex of the cone.

Part (a):
Let $R$ denote the radius of the cone, and let $r$ denote the radius of the cylinder and sphere. Let $l$ denote the slant height of the cone, and let $h$ denote the height of the cone.
Consider a plane that contains the axis of the cone. This plane will slice the cone and sphere into a circle $\omega$ inscribed in an isosceles triangle $T$.
The area of $T$ may be computed in two different ways:

From this, we deduce that $r = \frac{Rh}{l+R}$.
Now, we calculate our volumes:

Now, we will compute the quantity $\frac{3(l+R)^3}{\pi R^5 h} (V_1 - V_2)$ and prove that it is always greater than $0$.
Let $x = \frac{h}{R}$. Clearly, $x$ can be any positive real number. Define $W_1 = \frac{3(l+R)^3}{\pi R^5 h} V_1$ and $W_2 = \frac{3(l+R)^3}{\pi R^5 h} V_2$. We will calculate $W_1$ and $W_2$ in terms of $x$ and then compute the desired quantity $W_1 - W_2$.
It is easy to see that:
Now, let $u = \sqrt{x^2+1}$. Since $x > 0$, it follows that $u > 1$. We now have:
Define $f(u) = W_1 - W_2$. It follows that:
We see that $f(u) > 8$ for all allowed values of $u$. Thus, $V_1 - V_2 > \frac{8\pi R^5 h}{3(l+R)^3}$, meaning that $V_1 > V_2$. We have thus proved that $V_1 \ne V_2$, as desired.
Part (b):
From our earlier work in calculating the volumes $V_1$ and $V_2$, we easily see that:

Re-expressing and simplifying, we have:

By the AM-GM Inequality, $(u-1) + \frac{4}{u-1} \ge 4$, meaning that $\frac{V_1}{V_2} \ge \frac{4}{3}$.
Equality holds if and only if $u-1 = \frac{4}{u-1}$, meaning that $u=3$ and $x = 2\sqrt{2}$.
If we check the case $x = \frac{h}{R} = 2\sqrt{2}$, we may calculate $V_1$ and $V_2$:

Indeed, we have $\frac{V_1}{V_2} = \frac{4}{3}$, meaning that our minimum of $k = \frac{4}{3}$ can be achieved.
Thus, we have proved that the minimum value of $k$ such that $V_1 = kV_2$ is $\frac{4}{3}$.
Now, let $\theta$ be the angle subtended by a diameter of the base of the cone at the vertex of the cone. We have the following:

From the double-angle formula for tangent,

This angle is easy to construct. Simply take any segment and treat it as a unit segment. Create a right triangle with legs of lengths $4\sqrt{2}$ and $7$. This is straightforward, and the angle opposite the leg of length $4\sqrt{2}$ will be the desired angle $\theta$.
It follows that we have successfully constructed the desired angle $\theta$.

Part a):
Let $r$ and $a$ denote the radius of the sphere and the radius of the base of the cone, respectively.
Consider a plane that contains a cross section of the cone. We get a circle (the sphere) inscribed in both an isosceles triangle (the cone) and a rectangle (the cylinder). Let $A$ and $A_1$ be the vertices at the base of the triangle and let $H_1 H_2 = h$ be the altitude through the third vertex $H_1$. Let $\theta$ be the angle with arms $AO$ and $AA_1$, where $O$ is the center of the circle; $0 < \theta < \frac{\pi}{4}$ .
We have $\tan \theta = \frac{r}{a}$ ; $0 < \tan \theta < 1$. For the two volumes we have $V_2 = \pi r^2 \times 2r = 2\pi r^3$ and $V_1 = \frac{\pi a^2 \times H_1 H_2}{3} = \frac{\pi a^3 \tan (\angle A_1 A H_1) }{3}$ .
Knowing $\angle A_1 A H_1 = 2 \times \angle A_1 A O = 2 \theta$, and using the formula for a double-angle tangent, we can simplify the result:
$V_1 = \frac{\pi a^3 \tan (\angle A_1 A H_1)}{3}$
$V_1 = \frac{2 \pi r^3 \tan \theta}{3 \tan^3 \theta (1 - \tan^2 \theta)}$
$V_1 = k V_2$, where $k = \frac{1}{3\tan^2 \theta (1 - \tan^2 \theta)}$
We see that the biquadratic equation $3 \tan^4 \theta - 3 \tan^2 \theta + 1 = 0$ has no real roots for $\tan \theta$, which means that $k \neq 1$. Therefore $V_1 \neq V_2$ .
Part b):
Let $\tan^2 \theta = x; 0 < x < 1$. Consider the function $f(x) = 3x - 3x^2$. The coefficient in front of $x^2$ is negative, which means the function has an upper bound, i.e. k has a lower bound (since it is the reciprocal of $f(x)$). Using the vertex formula for a quadratic function, we get $x = -\frac{b}{2a} = \frac{1}{2}$ , which gives us $f(x) = y_{max} = \frac{3}{4}$ . From there $k_{min} = \frac{4}{3}$ .
For $\tan^2 \theta$ we have $\tan^2 \theta = \frac{1}{2};   \tan \theta = +/- \frac{\sqrt{2}}{4}$ . We defined $\tan \theta$ to be in the interval (0;1), so $\tan \theta = \frac{\sqrt{2}}{4}$ . That gives us $\tan \angle A_1 A H_1 = \frac{4 \sqrt{2}}{7}$ . To find $2\theta$ we construct a right triangle with legs equal to $7$ and $4\sqrt{2}$ using a unit length reference.


Consider a plane $\epsilon$ and three non-collinear points $A,B,C$ on the same side of $\epsilon$; suppose the plane determined by these three points is not parallel to $\epsilon$. In plane $\epsilon$ take three arbitrary points $A',B',C'$. Let $L,M,N$ be the midpoints of segments $AA', BB', CC'$; Let $G$ be the centroid of the triangle $LMN$. (We will not consider positions of the points $A', B', C'$ such that the points $L,M,N$ do not form a triangle.) What is the locus of point $G$ as $A', B', C'$ range independently over the plane $\epsilon$?

Solution: We will consider the various points in terms of their coordinates in space.  We have $L=\frac{A+A^\prime}{2},M=\frac{B+B^\prime}{2},N=\frac{C+C^\prime}{2}$.  Since the centroid of a triangle is the average of the triangle's vertices, we have $G=\frac{1}{3}\left(L+M+N\right)=\frac{1}{6}\left(A+B+C+A^\prime+B^\prime+C^\prime\right)$.  It is clear now that $G$ is midpoint of the line segment connecting the centroid of $ABC$ and the centroid of $A^\prime B^\prime C^\prime$.  It is obvious that the centroid of $A^\prime B^\prime C^\prime$ can be any point on plane $\epsilon$.  Thus, the locus of $G$ is the plane parallel to $\epsilon$ and halfway between the centroid of $ABC$ and $\epsilon$.


Consider an isosceles triangle. Let $r$ be the radius of its circumscribed circle and $\rho$ the radius of its inscribed circle. Prove that the distance $d$ between the centers of these two circles is

Solution:
<geogebra>d1f93636341cbe0bc2f98c788171d8a55d94f8c8</geogebra>
Instead of an isosceles triangle, let us consider an arbitrary triangle $ABC$. Let $ABC$ have circumcenter $O$ and incenter $I$. Extend $AI$ to meet the circumcircle again at $L$. Then extend $LO$ so it meets the circumcircle again at $M$.
Consider the point where the incircle meets $AB$, and let this be point $D$. We have $\angle ADI = \angle MBL = 90^{\circ}, \angle IAD = \angle LMB$; thus, $\triangle ADI \sim \triangle MBL$, or $\frac {ID}{BL} = \frac {AI} {ML} \iff ID \cdot ML = 2r\rho = AI \cdot BL$.
Now, drawing line $BI$, we see that $\angle BIL = \frac {1}{2}\angle A + \frac {1}{2}\angle ABC, \angle IBL = \frac {1}{2}\angle ABC + \angle CBL = \frac {1}{2}\angle ABC + \frac {1}{2}\angle A$. Therefore, $BIL$ is isosceles, and $IL = BL$.
Substituting this back in, we have $2r\rho = AI\cdot IL$. Extending $OI$ to meet the circumcircle at $P,Q$, we see that $AI\cdot IL = PI\cdot QI$ by Power of a Point. Therefore, $2r\rho = PI \cdot QI = (PO + OI)(QO - OI) = (r + d)(r - d)$, and we have $2r\rho = r^2 - d^2 \iff d = \sqrt {r(r - 2\rho)}$, and we are done.


Five students, $A,B,C,D,E$, took part in a contest. One prediction was that the contestants would finish in the order $ABCDE$. This prediction was very poor. In fact no contestant finished in the position predicted, and no two contestants predicted to finish consecutively actually did so. A second prediction had the contestants finishing in the order $DAECB$. This prediction was better. Exactly two of the contestants finished in the places predicted, and two disjoint pairs of students predicted to finish consecutively actually did so. Determine the order in which the contestants finished.

Solution:
We are given that no contestant finished in the position predicted, and no two contestants predicted to finish consecutively actually did so in order $ABCDE$. None of them finished in that order. Also only two of them had their actual positions in $DAECB$. After imposing these two conditions the list of possible outcomes is:
(1)$CAEBD$,
(2)$DCAEB$,
(3)$DCEBA$,
(4)$EDACB$.
One more condition is that two disjoint pairs of students predicted to finish consecutively actually did so. Out of the above four in the list, (1) and (2) have $AE$ as the correctly predicted consecutive finishers(but only 1 pair), (3) has no correctly predicted consecutive finishers. But (4) has 2 disjoint correctly predicted consecutive finishers who are $DA$ and $CB$.
Hence, order is $EDACB$.


In tetrahedron $ABCD$, vertex $D$ is connected with $D_0$, the centroid of $\triangle ABC$. Lines parallel to $DD_0$ are drawn through $A,B$ and $C$. These lines intersect the planes $BCD, CAD$ and $ABD$ in points $A_1, B_1,$ and $C_1$, respectively. Prove that the volume of $ABCD$ is one third the volume of $A_1B_1C_1D_0$. Is the result true if point $D_o$ is selected anywhere within $\triangle ABC$?

Solution:
Let $A_{2}$ be the point where line $AD_{0}$ intersects line $BC$
Let $B_{2}$ be the point where line $BD_{0}$ intersects line $AC$
Let $C_{2}$ be the point where line $CD_{0}$ intersects line $AB$
From centroid properties we have:
$|AA_{2}|=3|D_{0}A_{2}|$
$|BB_{2}|=3|D_{0}B_{2}|$
$|CC_{2}|=3|D_{0}C_{2}|$
Therefore,
$\frac{|AA_{2}|}{|D_{0}A_{2}|}=3$
$\frac{|BB_{2}|}{|D_{0}B_{2}|}=3$
$\frac{|CC_{2}|}{|D_{0}C_{2}|}=3$
Since $\Delta D_{0}A_{2}A_{1}\sim \Delta AA_{2}A_{1}$, then $|AA_{1}|=|DD_{0}| \frac{|AA_{2}|}{|D_{0}A_{2}|}=3|DD_{0}|$
Since $\Delta D_{0}B_{2}B_{1}\sim \Delta BB_{2}B_{1}$, then $|BB_{1}|=|DD_{0}| \frac{|BB_{2}|}{|D_{0}B_{2}|}=3|DD_{0}|$
Since $\Delta D_{0}C_{2}C_{1}\sim \Delta CC_{2}C_{1}$, then $|CC_{1}|=|DD_{0}| \frac{|CC_{2}|}{|D_{0}C_{2}|}=3|DD_{0}|$
Since $|AA_{2}|=|BB_{2}|=|CC_{2}|$ and $AA_{1} \parallel BB_{1} \parallel CC_{1} \parallel DD_{0}$,
then $\Delta A_{1}B_{1}C_{1}\parallel \Delta ABC$, and $Area_{\Delta A_{1}B_{1}C_{1}}=Area_{\Delta ABC}$
Let $h_{D}$ be the perpendicular distance from $D$ to $\Delta ABC$
Let $h_{\Delta A_{1}B_{1}C_{1}}$ be the perpendicular distance from $\Delta A_{1}B_{1}C_{1}$ to $\Delta ABC$
$\frac{h_{\Delta A_{1}B_{1}C_{1}}}{h_{D}}=\frac{|AA_{2}|}{|D_{0}A_{2}|}=\frac{|BB_{2}|}{|D_{0}B_{2}|}=\frac{|CC_{2}|}{|D_{0}C_{2}|}=3$
$h_{\Delta A_{1}B_{1}C_{1}}=3h_{D}$
$\frac{1}{3}h_{\Delta A_{1}B_{1}C_{1}}Area_{\Delta A_{1}B_{1}C_{1}}=3\frac{1}{3}h_{D}Area_{\Delta ABC}$
$\frac{h_{\Delta A_{1}B_{1}C_{1}}Area_{\Delta A_{1}B_{1}C_{1}}}{3}=3\frac{h_{D}Area_{\Delta ABC}}{3}$
Since $Volume_{ABCD}=\frac{h_{D}Area_{\Delta ABC}}{3}$ and $Volume_{A_{1}B_{1}C_{1}D_{0}}=\frac{h_{\Delta A_{1}B_{1}C_{1}}Area_{\Delta A_{1}B_{1}C_{1}}}{3}$
then, $Volume_{A_{1}B_{1}C_{1}D_{0}}=3Volume_{ABCD}$
thus, $Volume_{ABCD}=\frac{1}{3}Volume_{A_{1}B_{1}C_{1}D_{0}}$
this proves that the volume of $ABCD$ is one third the volume of $A_1B_1C_1D_0$
The result is NOT true if point $D_o$ is selected anywhere within $\triangle ABC$ as ratios of $\frac{|AA_{2}|}{|D_{0}A_{2}|}$, $\frac{|BB_{2}|}{|D_{0}B_{2}|}$, and $\frac{|CC_{2}|}{|D_{0}C_{2}|}$ will have values other than 3 as the point is no longer a centroid.  Also, it will make the ratios $\frac{|AA_{2}|}{|D_{0}A_{2}|} \ne \frac{|BB_{2}|}{|D_{0}B_{2}|}\ne \frac{|CC_{2}|}{|D_{0}C_{2}|}$ which means that $\Delta A_{1}B_{1}C_{1} \nparallel \Delta ABC$ and the volume relationship will no longer hold true.
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


In a plane a set of $n$ points ($n\geq 3$) is given. Each pair of points is connected by a segment. Let $d$ be the length of the longest of these segments. We define a diameter of the set to be any connecting segment of length $d$. Prove that the number of diameters of the given set is at most $n$.

Solution: Image of problem Solution. Credits to user awe-sum.


In the interior of sides $BC, CA, AB$ of triangle $ABC$, any points $K, L,M$, respectively, are selected. Prove that the area of at least one of the triangles $AML, BKM, CLK$ is less than or equal to one quarter of the area of triangle $ABC$.

Solution:
Let the lengths of sides $BC$, $CA$, and $AB$ be $a$, $b$, and $c$, respectively. Let $BK=d$, $CL=e$, and $AM=f$.
Now assume for the sake of contradiction that the areas of $\Delta AML$, $\Delta BKM$, and $\Delta CLK$ are all at greater than one fourth of that of $\Delta ABC$. Therefore

In other words, $AM\cdot AL>\frac{1}{4}AB\cdot AC$, or $f(b-e)>\frac{bc}{4}$. Similarly, $d(c-f)>\frac{ac}{4}$ and $e(a-d)>\frac{ab}{4}$. Multiplying these three inequalities together yields

We also have that $d(a-d)\leq \frac{a^2}{4}$, $e(b-e)\leq \frac{b^2}{4}$, and $f(c-f)\leq \frac{c^2}{4}$ from the Arithmetic Mean-Geometric Mean Inequality. Multiplying these three inequalities together yields

This is a contradiction, which shows that our assumption must have been false in the first place. This proves the desired result.

Let $AR : AB = x, BP : BC = y, CQ : CA = z$. Then it is clear that the ratio of areas of $AQR, BPR, CPQ$ to that of $ABC$ equals $x(1-y), y(1-z), z(1-x)$, respectively. Suppose all three quantities exceed $\frac{1}{4}$. Then their product also exceeds $\frac{1}{64}$. However, it is clear by AM-GM that $x(1-x) \le \frac{1}{4}$, and so the product of all three quantities cannot exceed $\frac{1}{64}$ (by the associative property of multiplication), a contradiction. Hence, at least one area is less than or equal to $\frac{1}{4} [ABC]$.


For every natural number $n$, evaluate the sum

(The symbol $[x]$ denotes the greatest integer not exceeding $x$.)

Solution:
I shall prove that the summation is equal to $n$.
Let the binary representation of $n$ be $\overline{d_xd_{x-1}\dots d_1d_0}_2$, where $d_i\in\{0,1\}$ for all $i$, and $x=\lfloor \log_2 n\rfloor$. Note that if $d_i=0$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]$; and if $d_i=1$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]+1$. Also note that $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=0$ for all $i\geq x+1$. Therefore the given sum is equal to

where $S$ is the number of 1's in the binary representation of $n$. Legendre's Formula states that $n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]$, which proves the assertion. $\blacksquare$

We observe
But
so the result is just $n$. $\square$
~ilovepi3.14

By Hermite's identity, for real numbers $x,$
Hence our sum telescopes:
~Maximilian113


Prove that for all real numbers $x_1, x_2, y_1, y_2, z_1, z_2$, with $x_1 > 0, x_2 > 0, y_1 > 0, y_2 > 0, z_1 > 0, z_2 > 0, x_1y_1 - z_1^2 > 0, x_2y_2 - z_2^2 > 0$, the inequalityis satisfied. Give necessary and sufficient conditions for equality.

Solution:
Let $A=x_1y_1 - z_1^2>0$ and $B=x_2y_2 - z_2^2>0$
From AM-GM:
$\sqrt{AB} \le \frac{A+B}{2}$ with equality at $A=B$
$4AB \le (A+B)^2$
$\frac{4}{A+B} \le \frac{A+B}{AB}$
$\frac{8}{2(A+B)} \le \frac{A+B}{AB}$
$\frac{8}{2(A+B)} \le \frac{1}{A}+\frac{1}{B}$ [Equation 1]
$(x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2=x_1y_1+x_2y_2+x_1y_2+x_2y_1-z_1^2-2z_1z_2-z_2^2$
$(x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2=(A+B)+x_1y_2+x_2y_1-2z_1z_2$
since $x_1y_1>z_1^2$ and $x_2y_2>z_2^2$, and using the Rearrangement inequality
then $x_1y_1+x_2y_2-z_1z_1-z_2z_2 \le x_1y_2+x_2y_1-z_1z_2-z_1z_2$
$(A+B) \le  x_1y_2+x_2y_1-2z_1z_2$
$2(A+B) \le x_1y_1+x_2y_2+x_1y_2+x_2y_1-z_1^2-2z_1z_2-z_2^2$
$2(A+B) \le (x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2$ [Equation 2]
Therefore, we can can use [Equation 2] into [Equation 1] to get:
$\frac{8}{(x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2} \le \frac{1}{A}+\frac{1}{B}$
Then, from the values of $A$ and $B$ we get:
$\frac{8}{(x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2} \leq \frac{1}{x_1y_1 - z_1^2} + \frac{1}{x_2y_2 - z_2^2}$
With equality at $x_1y_1 - z_1^2=x_2y_2 - z_2^2>0$ and $x_1=x_2, y_1=y_2, z_1=z_2$
~Tomas Diaz. orders@tomasdiaz.com

This solution is actually more difficult but I added it here for fun to see the generalized case as follows:
Prove that for all real numbers $a_i, b_i$, for $i=1,2,...,n$ with $a_i > 0, b_i > 0$
and $\prod_{i=1}^{n-1}a_i-a_n^{n-1}>0, \prod_{i=1}^{n-1}b_i-b_n^{n-1}>0$ the inequality
is satisfied.
Let $A=\prod_{i=1}^{n-1}a_i-a_n^{n-1}$ and $\prod_{i=1}^{n-1}b_i-b_n^{n-1}>0$
From AM-GM:
$\sqrt{AB} \le \frac{A+B}{2}$ with equality at $A=B$
$4AB \le (A+B)^2$
$\frac{4}{A+B} \le \frac{A+B}{AB}$
$\frac{2^n}{2^{n-2}(A+B)} \le \frac{A+B}{AB}$
$\frac{2^n}{2^{n-2}(A+B)} \le \frac{1}{A}+\frac{1}{B}$ [Equation 3]
Here's the difficult part where I'm skipping steps:
we prove that $2^{n-2}(A+B) \le \prod_{i=1}^{n-1}(a_i + b_i) - (a_n + b_n)^{n-1}$
and replace in [Equation 3] to get:
$\frac{2^n}{\prod_{i=1}^{n-1}(a_i + b_i) - (a_n + b_n)^{n-1}} \le \frac{1}{A}+\frac{1}{B}$
and replace the values of $A$ and $B$ to get:
$\frac{2^n}{\prod_{i=1}^{n-1}(a_i + b_i) - (a_n + b_n)^{n-1}} \leq \frac{1}{\prod_{i=1}^{n-1}a_i-a_n^{n-1}} + \frac{1}{\prod_{i=1}^{n-1}b_i-b_n^{n-1}}$
with equality at $a_i=b_i$ for all $i=1,2,...,n$
Then set $n=3, a_1=x_1, a_2=y_1, a_3=z_1, b_1=x_2, b_2=y_2, b_3=z_3$ and substitute in the generalized inequality to get:
$\frac{8}{(x_1 + x_2)(y_1 + y_2) - (z_1 + z_2)^2} \leq \frac{1}{x_1y_1 - z_1^2} + \frac{1}{x_2y_2 - z_2^2}$
with equality at $x_1=x_2, y_1=y_2, z_1=z_2$
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


In a plane there are $100$ points, no three of which are collinear.  Consider all possible triangles having these point as vertices.  Prove that no more than $70 \%$ of these triangles are acute-angled.

Solution:
At most $3$ of the triangles formed by $4$ points can be acute. It follows that at most $7$ out of the $10$ triangles formed by any $5$ points can be acute. For given $10$ points, the maximum number of acute triangles is: the number of subsets of $4$ points times $\frac{3}{\text{the number of subsets of 4 points containing 3 given points}}$. The total number of triangles is the same expression with the first $3$ replaced by $4$. Hence at most $\frac{3}{4}$ of the $10$, or $7.5$, can be acute, and hence at most $7$ can be acute.
The same argument now extends the result to $100$ points. The maximum number of acute triangles formed by $100$ points is: the number of subsets of $5$ points times $\frac{7}{\text{the number of subsets of 5 points containing 3 given points}}$. The total number of triangles is the same expression with $7$ replaced by $10$. Hence at most $\frac{7}{10}$ of the triangles are acute.


Let $A = (a_{ij})(i, j = 1, 2, \cdots, n)$ be a square matrix whose elements are non-negative integers. Suppose that whenever an element $a_{ij} = 0$, the sum of the elements in the $i$th row and the $j$th column is $\geq n$. Prove that the sum of all the elements of the matrix is $\geq n^2 / 2$.

Take the the row or column (without loss of generality, a row) with the minimum possible sum $S$ of its elements. Let $z$ be the number of zeros in this row. We will assume $S < \frac{n}{2}$ once the other case is obvious. Clearly $S \ge n - z \Rightarrow z \ge n - S$. The total sum $T$ of all elements of the matrix is at least the number of zeros in this row multiplicated by $n - S$ (because the sum of the elements of a row and a column meeting in a zero is $\ge n$) plus the number of nonzero elements times $S$ (that is the minimum possible sum), it is,Note that, being $z \ge n - S$ and $n - S \ge S$, we can put $z - 1$ instead of $z$ and $n - z + 1$ instead of $n - z$ until we get $z = n - S$, what makes the sum become smaller. So we haveby AM - QM inequality.
The above solution was posted and copyrighted by Renan. The original thread for this problem can be found here: [1]

Denote $\ell_i,c_i$ the $i$th line and column and $s(\ell_i), s(c_i)$ the sum of the elements on that row. Let $M=\max_{\sigma \in S_n} | \{ 1\le i\le n| a_{i\sigma(i)}=0\} |$. For each permutation $\sigma\in S_n$, assign to it the numberNow pick a permutation $\sigma$ such that it generates $M$ and its assigned number is minimal. Suppose wlog that $\{ 1\le i\le n| a_{i\sigma(i)}=0\}=\{1,2,..,k\}$. If $k=n$, we are done as twice the sum of all elements is
So suppose $k<n$ and look at a $j$ such that $k+1\le j\le n$. By the maximality of $M$, $\ell_j$ can have $0$ only on the columns $\sigma(1),...,\sigma(k)$. Note that if $\ell_j$ has a $0$ on $c_{\sigma(r)}$ with $r\le k$, i.e. $a_{j\sigma(r)}=0$, by the minimality of the assigned number of $\sigma$, we have that $s(\ell_j)\ge s(\ell_r)$. However, if the column $c_{\sigma(j)}$ has a $0$ on $\ell_r$, i.e. $a_{r\sigma(j)}=0$, by the same argument we have $s(c_\sigma(j))\ge s(c_\sigma(r))$, hence $s(\ell_j)+s(c_{\sigma(j)})\ge s(r)+s(c_{\sigma(r)})\ge n$.
Suppose that $0$ appears exactly $t$ times on $\ell_j$. This means that $s(\ell_j)\ge n-t$. Suppose that the $0$s of $\ell_j$ appear on the columns $c_{\sigma(i_1)},...,c_{\sigma(i_t)}$. We have seen earlier that if $c_\sigma(j)$ has a $0$ on $i_1,..,i_t$ we have that $s(\ell_j)+s(c_{\sigma(j)})\ge n$. So suppose that it doesn't have $0$ on these lines. However, $c_{\sigma(j)}$ has $0$s only on the lines $\ell_1,..,\ell_k$ by the maximality of $M$, hence $c_{\sigma(j)}$ has at most $k-t$ zeroes, so $s(c_{\sigma(j)})\ge n-k+t$. We thus infer thatso $s(\ell_j)+s(c_{\sigma(j)})\ge n,\ \forall j\ge k+1$. By the hypothesis this is also true for $j\le k$ so summing over all values of $j$ we get that the sum is at least $\dfrac{n^2}{2}$.
The above solution was posted and copyrighted by Aiscrim. The original thread for this problem can be found here: [2]

If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum $S$ of the elements is at least $n^2/2$. This motivates us to consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be $k$. (If there is no such subset, $S\ge n^2$.)
Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these $k$ entries are on the main diagonal of the matrix, i.e. $a_{11}=a_{22}=\dots=a_{kk}=0$. Let $X=\sum_{1\le i,j\le k}a_{ij}$, $Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij}$ and $Z=\sum_{k<i,j\le n}a_{ij}$. Then applying the condition to $a_{11},\dots,a_{kk}$, we get $2X+Y\ge kn$.
If $i\le k<j$, then if $a_{ij}=a_{ji}=0$, then we may toss $a_{ii}$ out of our set and replace it with $a_{ij}$ and $a_{ji}$, to form a larger feasible set of elements, contradiction. Consequently, $a_{ij}+a_{ji}\ge 1$ for $i\le k<j$, which upon summation yields $Y\ge k(n-k)$. Finally, $Z\ge (n-k)^2$, trivially. Therefore,
The above solution was posted and copyrighted by randomusername. The original thread for this problem can be found here: [3]


Given four distinct parallel planes, prove that there exists a regular tetrahedron
with a vertex on each plane.

Let our planes be $\pi_1,\pi_2,\pi_3,\pi_4$, which we assume to be parallel to the $xy$-plane, listed in the increasing order of their $z$-coordinates. First take a plane $\pi$ orthogonal to $\pi_i$, which cuts $\pi_1,\pi_2,\pi_3$ along three lines $d_1,d_2,d_3$. On these three lines, take three vertices $A_1,A_2,A_3$ respectively of an equilateral triangle (it is well-known that this is possible; in fact, the problem here is the $3$-dimensional version of this), and then complete the two regular tetrahedra $A_1A_2A_3P_1,A_1A_2A_3P_2$ having $A_1A_2A_3$ as one of their faces. Both $P_i$ lie below $\pi_4$.
Now take another plane $\pi$ and repeat the construction above. If $\pi$ makes a small enough angle with the $\pi_i$'s, one of the $P_i$'s we get this time must lie above $\pi_4$. Now, if we move the initial position of $\pi$ towards the new one continuously and record the $z$-coordinates of $P_1,P_2$, these will be continuous functions of the angle that $\pi$ makes with $\pi_i$, and for one of the points $P_1,P_2$ the $z$-coordinate will move continuously from being smaller than that of $\pi_4$ to being larger than it, meaning that at some point, one of the points $P_1,P_2$ will lie on $\pi_4$, and this is what we want.
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

Let's denote the (directed) distance between two parallel planes p and p' by d (p; p'), and the (directed) distance between two parallel lines g and g' by d (g; g'). (Directed distances are defined as follows: If $p_1$, $p_2$, $p_3$, ... is a family of parallel planes in space, then we choose a unit vector $\overrightarrow{v}_p$ perpendicular to all of these planes (there are two such unit vectors, and we have to choose one of them), and then, by the directed distance between two of these planes $p_i$ and $p_j$, we denote the real number k such that the translation with translation vector $k\cdot\overrightarrow{v}_p$ maps the plane $p_i$ to the plane $p_j$. Similarly, we define the directed distance between two of a family of parallel lines in a plane.)
The problem can be rewritten as follows: Given four distinct parallel planes $p_1$, $p_2$, $p_3$, $p_4$ in space, prove that there exists a regular tetrahedron XYZW such that $X\in p_1$, $Y\in p_2$, $Z\in p_3$, $W\in p_4$.
In order to do this, it is enough to find a regular tetrahedron ABCD somewhere in space and four parallel planes $q_1$, $q_2$, $q_3$, $q_4$ such that $A\in q_1$, $B\in q_2$, $C\in q_3$, $D\in q_4$ and $d\left(q_1;\;q_2\right): d\left(q_2;\;q_3\right): d\left(q_3;\;q_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$. In fact, once we have found such a tetrahedron ABCD and such planes $q_1$, $q_2$, $q_3$, $q_4$, then, because of $p_1\parallel p_2\parallel p_3\parallel p_4$, $q_1\parallel q_2\parallel q_3\parallel q_4$ and $d\left(q_1;\;q_2\right): d\left(q_2;\;q_3\right): d\left(q_3;\;q_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$, there exists a similitude transformation which maps the planes $q_1$, $q_2$, $q_3$, $q_4$ to the planes $p_1$, $p_2$, $p_3$, $p_4$; this similitude transformation will then obviously map the regular tetrahedron ABCD with $A\in q_1$, $B\in q_2$, $C\in q_3$, $D\in q_4$ to a regular tetrahedron XYZW with $X\in p_1$, $Y\in p_2$, $Z\in p_3$, $W\in p_4$; hence, the existence of such a tetrahedron XYZW will be proven, and the problem will be solved.
So consider a regular tetrahedron ABCD lying arbitrarily in space; we try to find four parallel planes $q_1$, $q_2$, $q_3$, $q_4$ such that $A\in q_1$, $B\in q_2$, $C\in q_3$, $D\in q_4$ and $d\left(q_1;\;q_2\right): d\left(q_2;\;q_3\right): d\left(q_3;\;q_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$.
In fact, we start working in the plane ABC. Let T be the point on the line AC such that $AT: TC=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right)$ (where the segments AT and TC are directed). Let $g_2$ be the line BT, and let $g_1$ and $g_3$ be the parallels to the line $g_2=BT$ through the points A and C, respectively. Then, the lines $g_1$, $g_2$, $g_3$ are parallel and, by Thales, $d\left(g_1;\;g_2\right): d\left(g_2;\;g_3\right)=AT: TC$. Thus, $d\left(g_1;\;g_2\right): d\left(g_2;\;g_3\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right)$. Now, denote by $g_4$ the line in the plane ABC which is parallel to the lines $g_1$, $g_2$, $g_3$ and satisfies $d\left(g_1;\;g_2\right): d\left(g_2;\;g_3\right): d\left(g_3;\;g_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$.
Now, let $q_4$ be the plane passing through the line $g_4$ and the point D. Let $q_1$, $q_2$, $q_3$ be the planes parallel to $q_4$ and passing through the lines $g_1$, $g_2$, $g_3$, respectively (of course, we can construct such planes since the lines $g_1$, $g_2$, $g_3$ are parallel to $g_4$). Thus, we have found four parallel planes $q_1$, $q_2$, $q_3$, $q_4$ such that $A\in q_1$, $B\in q_2$, $C\in q_3$, $D\in q_4$, and these planes obviously satisfy $d\left(q_1;\;q_2\right): d\left(q_2;\;q_3\right): d\left(q_3;\;q_4\right)=d\left(g_1;\;g_2\right): d\left(g_2;\;g_3\right): d\left(g_3;\;g_4\right)$. Since $d\left(g_1;\;g_2\right): d\left(g_2;\;g_3\right): d\left(g_3;\;g_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$, we thus have $d\left(q_1;\;q_2\right): d\left(q_2;\;q_3\right): d\left(q_3;\;q_4\right)=d\left(p_1;\;p_2\right): d\left(p_2;\;p_3\right): d\left(p_3;\;p_4\right)$. Hence, according to the above, the problem is solved.
The above solution was posted and copyrighted by darij grinberg. The original thread for this problem can be found here: [2]


Let $a_1, a_2,\cdots, a_n$ be $n$ positive numbers, and let $q$ be a given real number such that $0<q<1.$ Find $n$ numbers $b_1, b_2, \cdots, b_n$ for which
(a) $a_k<b_k$ for $k=1,2,\cdots, n,$
(b) $q<\dfrac{b_{k+1}}{b_k}<\dfrac{1}{q}$ for $k=1,2,\cdots,n-1,$
(c) $b_1+b_2+\cdots+b_n<\dfrac{1+q}{1-q}(a_1+a_2+\cdots+a_n).$

Solution:
We notice that the constraints are linear, in the sense that if bi is a solution for ai, q, and bi' is a solution for ai', q, then for any k, k' > 0 a solution for kai + k'ai', q is kbi + k'bi'. Also a "near" solution for ah = 1, other ai = 0 is b1 = qh-1, b2 = qh-2, ... , bh-1 = q, bh = 1, bh+1 = q, ... , bn = qn-h. "Near" because the inequalities in (a) and (b) are not strict.
However, we might reasonably hope that the inequalities would become strict in the linear combination, and indeed that is true. Define br = qr-1a1 + qr-2a2 + ... + qar-1 + ar + qar+1 + ... + qn-ran. Then we may easily verify that (a) - (c) hold.


Let $P$ be a non-constant polynomial with integer coefficients. If $n(P)$ is the number of distinct integers $k$ such that $(P(k))^2=1,$ prove that $n(P)-\deg(P)\le2,$ where $\deg(P)$ denotes the degree of the polynomial $P.$

Solution:
Lemma: Let $P(x)$ be a polynomial with integer coefficients which is not constant. Then if $P(x)$ obtains $1$ (or $-1$) as its values for at least four times then $P(x)\neq -1$ ( or $P(x)\neq 1$) for all $x$.
Proof. Assume that $P(a)=P(b)=P(c)=P(d)=1$ for $a,b,c,d$ distince. Then if there's $u$ which $P(u)=-1$ then $2=P(a)-P(u)=...$ so $P(x)-P(u)-2=(x-a)(x-b)(x-c)(x-d)Q(x)$ where $Q(x)$ is a polynomial with the integer coefficients! So
$-2=(u-a)(u-b)(u-c)(u-d)Q(u)$ which is impossible cause $-2$ can not presents as product of more than three distince numbers! This proved the lemma!
Back to our problem: For convinet put $m=n(P)$ and $n=\deg P$. Firstly if $n\leq 2$ then $m-n\leq2$. Assume $n\geq3$. If equation $P(x)=1$ with more than three integer points (ie.. at least $4$) then equation $(P(x))^2=1$ implies $P(x)=1$ so $m\leq n$, ie... $m-n\leq 0\leq2$. The same case for equation $P(x)=-1$. So $m\leq 6$. If $n\geq4$ then $m-n\leq 6-n\leq 2$. Now assume that $n=3$. In this case if $m\leq 5$ then $m-n\leq 2$.
So let us show that $m<6$. In fact if $m=6$ then $P(x)-1=0$ has three integers distince roots, and the same for $P(x)+1=0$. So
$P(x)-1=k_1(x-a_1)(x-a_2)(x-a_3)$ and $P(x)+1=k_2(x-b_1)(x-b_2)(x-b_3)$ where $a_i$ distince and $b_j$ distince and all with $k_1,k_2$ are integers! Then
$k_2(x-b_1)(x-b_2)(x-b_3)-k_1(x-a_1)(x-a_2)(x-a_3)=2$ for all $x$. So $k_1=k_2=k$.
Finally, we have
$2=k(a_i-b_1)(a_i-b_2)(a_i-b_3)$ for $i=1,2,3$ and because that $\pm1$ can not presents as products of three distince numbers so $k=\pm1$, we may assume $k=1$. Because $2=(-2)\cdot 1\cdot -1$ so
$\{-2,1,-1\}=\{a_i-b_1,a_i-b_2,a_i-b_3\}$
This means $3a_i-(b_1+b_2+b_3)=-2+1-1=-2$. So we must have $3a_1=3a_2=3a_3$ which follows $a_1=a_2=a_3$, which contracts!. So $m\leq 5$ and we're done.
The above solution was posted and copyrighted by pluricomplex. The original thread for this problem can be found here: [1]


Find all polynomials $P$, in two variables, with the following properties:
(i) for a positive integer $n$ and all real $t, x, y$  (that is, $P$ is homogeneous of degree $n$),
(ii) for all real $a, b, c$,
(iii)

(i) If $n = 0$ : Clearly no solution
(ii) If $n = 1$ : $P(x, y) = ax+by \implies$ the identification yields directly $P(x,y) = x-2y$
(iii) If $n > 1$, $a = 1, \ b = 1, \ c =-2 \implies P(2,-2)+P(-1, 1)+P(-1, 1) = 0$ $\implies ((-2)^{n}+2) P(-1, 1) = 0 \implies P(-1, 1) = 0 \implies P(-y, y) = 0 \implies$ $P(x,y)$ is divisible by $(x+y)$
It is then easy to see that $\frac{P(x, y)}{(x+y)}$, of degree $n-1$ verifies all the equations.
The only solutions are thus $P(x, y) = (x-2y)(x+y)^{n-1}$
The above solution was posted and copyrighted by mathmanman. The original thread for this problem can be found here: [1]

$F(a,a,a) \implies P(2a,a)=0 \implies (x-2y)$ is a factor of $P(x,y)$.
We may write $P(x,y)=(x-2y)Q(x,y)$
$F(a,b,b) \implies 2P(a+b,b)+P(2b,a)=0 \implies 2(a+b-2b)Q(a+b,b)+2(b-a)Q(2b,a) \implies (a-b)(Q(a+b,b)-Q(2b,a))=0$
Thus $Q(a+b,b)=Q(2b,a) \forall a \neq b$
We may rewrite it as $Q(x,y)=Q(2y,x-y)=Q(2x-2y,3y-x=\cdots$
$Q(x+d,y-d)-Q(x,y)$ is a polynomial in $d$ of degree $n-1$ for any two fixed $x,y$,which has infinitely many zeroes,i.e,$0,2y-x,x-2y,6y-3x,\cdots$.Thus $Q(x+d,y-d)=Q(x,y)$ holds for all $d$.In particular it holds for $d=y$,i.e, $Q(x+y,0)=Q(x,y)$.Now consider the polynomial $R(x,y)=Q(x+y,0)-Q(x,y)$.Suppose that its not the zero polynomial.Then its degree $d$ is defined.With $t=\frac{x}{y}$ it can be wriiten as $y^dS(t)=y^d(A(t)-B(t))$.But $S(t)$ has infinitely many zeroes and this forces $A(t)=B(t)$,forcing $R(x,y)$ to be a zero polynomial.Contradiction!.Thus $Q(x+y,0)$ and $Q(x,y)$ are identical polynomials.This forces $Q(x,y)=c(x+y)^{n-1}$.With $Q(1,0)=1$ we get $c=1$.Thus
The above solution was posted and copyrighted by JackXD. The original thread for this problem can be found here: [2]


A sequence $(u_{n})$ is defined by

Prove that for any positive integer $n$ we have

(where $\lfloor x\rfloor$ denotes the smallest integer $\leq$ $x$)$.$

Solution:
Let the sequence $(x_n)_{n \geq 0}$ be defined as
\[
x_{0}=0,x_{1}=1, x_{n}=x_{n-1}+2x_{n-2}
\]
We notice

Because the roots of the characteristic polynomial $x_{n}=x_{n-1}+2x_{n-2}$ are $-1$ and $2$. \\newline We also see $\frac{2^1-(-1)^1}{3}=1=x_1$, $\frac{2^2-(-1)^2}{3}=1=x_2$
We want to prove

This is done by induction
Base Case:
For $n=1$ ses det $2^{1-0}+2^{0-1}=2^{1}+2^{-1}$
Inductive step:
Assume $2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}$
We notice

We then want to show

This can be done using induction
Base Case
For $n=1$, it is clear that  and  Therefore, the base case is proved.
Inductive Step
Assume for all natural $k<n$ at $a_k=2^{x_k}+2^{-x_k}$\newline
Then we have that:

From our first induction proof we have that:

Then:

We notice
$\left[a_n\right]=\left[2^{x_n}+2^{-x_n}\right]=2^{x_n}$, Because $2^{x_n} \in \mathbb{N}$ and $2^{-x_n}<1$, for all $n>0$
Finally we conclude


Let $f(n)$ be a function $f: \mathbb{N}^{+}\to\mathbb{N}^{+}$. Prove that if  for each positive integer $n$, then $f(n)=n$.

Solution:
We will prove this via induction. First we will prove there is a $t$ such that $f(t)=1$ and then that $t=1$ is the only such solution.
Define the sequence $a_n$ with $a_0>1$ for $a_0\in \mathbb{N}$ and $a_k=f(a_{k-1}-1)$. By the given inequality we have that $f(a_n)>f(a_{n+1})$, this can be used to form a inequality chain of decreasing positive integers:
By Infinite Descent, this sequence must terminate, and the only way it can terminate is if we input something into $f$ that is outside of its range. This can only happen if $a_n=1$ since the range and domain of $f$ are the positive integers. Since $a_0\neq 1$, there is a integer $t$ ($a_{n-1}-1$) such that $f(t)=1$.
Now if $t\neq 1$, then $f(t)=1>f(f(t-1))$, which is impossible since $f(f(t-1))\ge 1$ by the range of $f$, so we have $t=1$ is the only time when $f(t)=1$.
Now for the inductive step.
Assume that $f(n)=n$ for all $n<k$ and these are the only times these values occur. We will prove that $f(k)=k$ and that this is the only time this value occurs. Define the sequence $a_n$ similarly, except that $a_0>k$, by the reasoning above, there is a $a_m$ such that $f(a_m)=1$, by the inductive assumption, this means that $a_m=f(a_{m-1}-1)=1$, we can repeat the inductive assumption to get that $a_{m-k+1}=k$. This implies that $f(a_{m-k}-1)=k$. Thus, there is a $t$ such that $f(t)=k$.
Now for that $t$, we have $k>f(f(t-1))$, which means that $k+1>t$ by the inductive assumption which implies $t=k$ since we must have $t>k-1$, otherwise $f(t)<k$. So $t=k$ is the only time when $f(t)=k$
So the inductive step is complete. Therefore, by induction $f(n)=n$ for all positive integers $n$.


Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that:

Solution:
First the part $a_{2n-1}=0$ It's pretty obvious. Let's make a sequence $b$ of 1 and -1, setting 1 when the frog jumps left and -1 when it jumps right. If the frog would want to come to vertex E from vertex A, then $\sum b_{i}$ from $i =1$ to $i =2n-1$ should be equal to either 4 or -4. But this sum is odd, so we have $a_{2n-1}= 0$
Now the less obvious part.
Let's name $f(X,y)$ the number of ways, in which we can come to vertex X in y moves.
Then
$f(E,2n) = f(F,2n-1)+f(D, 2n-1) = f(C, 2n-2)+f(G, 2n-2) =$
$f(D, 2n-3)+f(B, 2n-3)+f(F, 2n-3)+f(H, 2n-3) =$
$2f(D, 2n-5)+2f(F, 2n-5)+4f(H,2n-5)+4f(B, 2n-5) =$
$4[ f(B,2n-5)+f(D, 2n-5)+f(F,2n-5)+f(H, 2n-5) ]-2 [ f(F,2n-5)+f(D,2n-5)] =$
$4f(E,2n-2)-2f(E,2n-4)$
Now we can find a solution to this recurrence or simply prove by induction the given answer.
This solution was posted and copyrighted by Myszon11. The original thread for this problem can be found here: [1]
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


The function $f(x,y)$ satisfies
(1) $f(0,y)=y+1,$
(2) $f(x+1,0)=f(x,1),$
(3) $f(x+1,y+1)=f(x,f(x+1,y)),$
for all non-negative integers $x,y$. Determine $f(4,1981)$.

Solution:
We observe that $f(1,0) = f(0,1) = 2$ and that $f(1, y+1) = f(0, f(1,y)) = f(1,y) + 1$, so by induction, $f(1,y) = y+2$.  Similarly, $f(2,0) = f(1,1) = 3$ and $f(2, y+1) = f(2,y) + 2$, yielding $f(2,y) = 2y + 3$.
We continue with $f(3,0) + 3 = 8$; $f(3, y+1) + 3 = 2(f(3,y) + 3)$; $f(3,y) + 3 = 2^{y+3}$; and $f(4,0) + 3 = 2^{2^2}$; $f(4,y) + 3 = 2^{f(4,y) + 3}$.
It follows that $f(4,1981) = 2^{2\cdot ^{ . \cdot 2}} - 3$ when there are 1984 2s, Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $S$ be a square with sides length $100$. Let $L$ be a path within $S$ which does not meet itself and which is composed of line segments $A_0A_1,A_1A_2,A_2A_3,\ldots,A_{n-1}A_n$ with $A_0=A_n$. Suppose that for every point $P$ on the boundary of $S$ there is a point of $L$ at a distance from $P$ no greater than $\frac {1} {2}$. Prove that there are two points $X$ and $Y$ of $L$ such that the distance between $X$ and $Y$ is not greater than $1$ and the length of the part of $L$ which lies between $X$ and $Y$ is not smaller than $198$.

Solution:
Let the square be A'B'C'D'. The idea is to find points of L close to a particular point of A'D' but either side of an excursion to B'.
We say L approaches a point P' on the boundary of the square if there is a point P on L with PP' ≤ 1/2. We say L approaches P' before Q' if there is a point P on L which is nearer to A0 (the starting point of L) than any point Q with QQ' ≤ 1/2.
Let A' be the first vertex of the square approached by L. L must subsequently approach both B' and D'. Suppose it approaches B' first. Let B be the first point on L with BB' ≤ 1/2. We can now divide L into two parts L1, the path from A0 to B, and L2, the path from B to An.
Take X' to be the point on A'D' closest to D' which is approached by L1. Let X be the corresponding point on L1. Now every point on X'D' must be approached by L2 (and X'D' is non-empty, because we know that D' is approached by L but not by L1). So by compactness X' itself must be approached by L2. Take Y to be the corresponding point on L2. XY ≤ XX' + X'Y ≤ 1/2 + 1/2 = 1. Also BB' ≤ 1/2, so XB ≥ X'B' - XX' - BB' ≥ X'B' - 1 ≥ A'B' - 1 = 99. Similarly YB ≥ 99, so the path XY ≥ 198.


Let $a$, $b$ and $c$ be the lengths of the sides of a triangle. Prove that
$a^2 b(a-b) + b^2 c(b-c) + c^2 a(c-a) \geq 0$.
Determine when equality occurs.

By Ravi substitution, let $a = y+z$, $b = z+x$, $c = x+y$. Then, the triangle condition becomes $x, y, z > 0$. After some manipulation, the inequality becomes:
$xy^3 + yz^3 + zx^3 \geq xyz(x+y+z)$.
By Cauchy, we have:
$(xy^3 + yz^3 + zx^3)(z+x+y) \geq xyz(y+z+x)^2$ with equality if and only if $\frac{xy^3}{z} = \frac{yz^3}{x} =\frac{zx^3}{y}$. So the inequality holds with equality if and only if x = y = z. Thus the original inequality has equality if and only if the triangle is equilateral.

Without loss of generality, let $a \geq b \geq c > 0$. By Muirhead or by AM-GM, we see that $a^3 b + a^3 c + b^3 c + b^3 a + c^3 a + c^3 b \geq 2(a^2 b^2 + a^2 c^2 + b^2 c^2)$.
If we can show that $a^3 b + b^3 c+ c^3 a  \geq a^3 c +  b^3 a + c^3 b$, we are done, since then $2(a^3 b + b^3 c+ c^3 a ) \geq a^3 b + a^3 c + b^3 c + b^3 a + c^3 a + c^3 b \geq 2(a^2 b^2 + a^2 c^2 + b^2 c^2)$, and we can divide by $2$.
We first see that, $(a^2 + ac + c^2) \geq (b^2 + bc + c^2)$, so $(a-c)(b-c)(a^2 + ac + c^2) \geq (a-c)(b-c)(b^2 + bc + c^2)$.
Factoring, this becomes $(a^3 - c^3)(b-c) \geq (a-c)(b^3 - c^3)$. This is the same as:
$(a^3 - c^3)(b-c) + (b^3 - c^3)(c-a) \geq 0$.
Expanding and refactoring, this is equal to $a^3 (b-c) + b^3(c-a) + c^3 (a-b) \geq 0$. (This step makes more sense going backwards.)
Expanding this out, we have
$a^3b + b^3 c + c^3 a \geq a^3 c + b^3 a + c^3 b$,
which is the desired result.

Let $s$ be the semiperimeter, $\frac{a+b+c}{2}$, of the triangle. Then, $a=s-\frac{-a+b+c}{2}$, $b=s-\frac{a-b+c}{2}$, and $c=s-\frac{a+b-c}{2}$. We let $x=\frac{-a+b+c}{2},$ $y=\frac{a-b+c}{2}$, and $z=\frac{a+b-c}{2}.$ (Note that $x,y,z$ are all positive, since all sides must be shorter than the semiperimeter.) Then, we have $a=s-x$, $b=s-y$, and $c=s-z$. Note that $x+y+z=s$, so  Plugging this into  and doing some expanding and cancellation, we get  The fact that each term on the left hand side has at least two variables multiplied motivates us to divide the inequality by $2xyz$, which we know is positive from earlier so we can maintain the sign of the inequality. This gives  We move the negative terms to the right, giving  We rewrite this as  where $r$ is any real number. (This works because if we evaulate the cyclic sum, then as long as the coefficients of $x$ and $y$ on the right sum to 1 the right side will be $x+y+z$.
Thus, we need to show that there exists a real number $r$ such that $\frac{x^2}{y}\geq rx+(1-r)y$ for all positive $x,y$. We claim that $r=2$ works. This becomes $\frac{x^2}{y}\geq2x-y$, and since $y$ is positive we can multiply by $y$ to yield $x^2\geq2xy-y^2$, or $(x-y)^2\geq0$, which is obviously true by the Trivial Inequality. Thus, we are done with part (a).
(To clarify how this works, we have $\frac{x^2}{y}\geq 2x-y$, $\frac{y^2}{z}\geq 2y-z$, and $\frac{z^2}{x}\geq 2z-x$, we add these inequalities to get $\frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x}\geq x+y+z.$)
Equality occurs if and only if $\frac{x^2}{y}=2x-y$, $\frac{y^2}{z}=2y-z$, and $\frac{z^2}{x}=2z-x$ at the same time, since if they are not all equal then the left side will be greater than the right side. From there, it is easy to see that the equality case is $x=y=z$, which is $a=b=c$.
~john0512

"Solution from 111 problems in Algebra and Number Theory"
WLOG, we can assume that $a\geq b\geq c$. getting that $\frac{1}{a}\leq \frac{1}{b} \leq \frac{1}{c}; a(b+c-a)\leq b(a+c-b)\leq c(a+b-c)$
Applying rearrangement inequality to it, getting that $\frac{a(b+c-a)}{c}+\frac{b(a+c-b)}{a}+\frac{c(a+b-c)}{b}\leq \frac{a(b+c-a)}{a}+\frac{b(a+c-b)}{b}+\frac{c(a+b-c)}{c}=a+b+c$, which equivalent to $\frac{a(b-a)}{c}+\frac{b(c-b)}{a}+\frac{c(a-c)}{b} \leq 0$ Time $abc$ at both side and get the desired inequality ~bluesoul


Let $a,b,c,d$ be odd integers such that $0<a<b<c<d$ and $ad=bc$. Prove that if $a+d=2^k$ and $b+c=2^m$ for some integers $k$ and $m$, then $a=1$.

Let $f:[1,b]\rightarrow \mathbb{R},\ f(x)=x+\dfrac{bc}{x}$. As $f^\prime (x)=1-\dfrac{bc}{x^2}\le 0$, we infer that $f(x)\ge f(b)=b+c,\ \forall x\in [1,b]$; in particular, $a+d=f(a)\ge b+c\Leftrightarrow k\ge m$.
Now, $ad=bc\Leftrightarrow a(2^k-a)=b(2^m-b)\Leftrightarrow (b-a)(a+b)=2^m(b-2^{k-m}a)$, hence $2^m|(b-a)(a+b)$. It is easy to see that for $x,y\in \mathbb{Z}$, if $v_2(x\pm y)\ge 2$, then $v_2(x\mp y)=1$. If $v_2(b-a)\ge 2$, $v_2(a+b)=1$, so $v_2(b-a)\ge m-1\Rightarrow b>2^{m-1}$, which is in contradiction with the fact that $b<\dfrac{b+c}{2}=2^{m-1}$. Thereby, $v_2(a+b)\ge m-1,\ v_2(b-a)=1$.
Write $a+b=2^{m-1}\alpha$. If $\alpha \ge 2\Rightarrow2^m\le a+b<b+c=2^m$, contradiction; so $a+b=2^{m-1}$ and $b-a=2\beta$, or equivalently $a=2^{m-2}-\beta,\ b=2^{m-2}+\beta$ ( $m>2$ otherwise $b+c=2\Leftrightarrow b=c=1$ or $b+c=4\Leftrightarrow c=3,b=1\Rightarrow a=0$ , contradiction )
Substituting back, $(b-a)(a+b)=2^m(b-2^{k-m}a)\Leftrightarrow 2^m\beta=2^m(2^{m-2}+\beta-2^{k-m}a)\Leftrightarrow 2^{k-m}a=2^{m-2}$
As $m>2$ and $a$ is odd, we get that $a=1$. Furthermore, $k=2m-2$, hence $d=2^{2m-2}-1$. Now $b(2^m-b)=2^{2m-2}-1\Leftrightarrow \left ( b-(2^{m-1}-1) \right ) \left ( b-(2^{m-1}+1)\right )=0$ which together with the fact that $b<c$, we get that $b=2^{m-1}-1,\ c=2^{m-1}+1$, so the family of the solutions $(a,b,c,d)$ is described by the set
This solution was posted and copyrighted by TheFunkyRabbit. The original thread for this problem can be found here: [1]

Note that, if $k\leqslant m$, then using $a+d\leqslant b+c$, and $ad=bc$, we get $(d-a)^2\leqslant (c-b)^2$, which is clearly impossible. Thus, $k>m$ must hold.
Next, observe that, $b+c =2^m$ and $b<c$ implies $b<2^{m-1}$. Keeping this in mind, we now observe that, $bc=b(2^m-b)=ad=a(2^k-a)$, implies $b\cdot 2^m - a\cdot 2^k = (b-a)(b+a)$. Thus, $2^m \mid (b-a)(b+a)$. Now, note also that, if $d={\rm gcd}(b-a,b+a)$, then $d\mid 2b$, and thus, the largest power of $2$ dividing either $b-a$ or $b+a$ is exactly $2$. Clearly, $b-a<2^{m-1}$, and thus, $2^{m-1}\mid b+a$. Moreover, if $b+a\geqslant 2\cdot 2^{m-1}$, then we again have a contradiction, as $b,a<2^{m-1}$. Thus, $b+a=2^{m-1}$. This yields, $b-a = 2(b-a\cdot 2^{k-m})$, which brings us, $b=(2^{k-m+1}-1)a$. Now, using $b+a=2^{k-m+1}a = 2^{m-1}$, we immediately obtain $a=2^{2m-k-2}$. This immediately establishes (since $a$ is odd), that $a=1$.
This solution was posted and copyrighted by grupyorum. The original thread for this problem can be found here: [2]


For every real number $x_1$, construct the sequence $x_1,x_2,\ldots$ by setting $x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)$ for each $n \geq 1$.  Prove that there exists exactly one value of $x_1$ for which $0<x_n<x_{n+1}<1$ for every $n$.

By recursive substitution, one can write $x_n=P_n(x_1)$ , where $P_n$ is a polynomial with non-negative coefficients and zero constant term. Thus, $P_n(0)=0$, $P_n$ is strictly increasing in $[0,+\infty)$ , and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n(x_1)=+\infty$. We can therefore define the inverse $P_n^{-1}$ of $P_n$ on $[0,+\infty)$. It follows that $x_1=P_n^{-1}(x_n)$, $P_n^{-1}(0)=0$, $P_n^{-1}$ is strictly increasing in $[0,+\infty)$, and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n^{-1}(x_1) =+\infty$.
Denote by $\displaystyle a_n=P_n^{-1}(1-\frac{1}{n})$ and $b_n=P_n^{-1}(1)$. By the monotonicity of $P_n^{-1}$ we have $a_n<b_n$ for each $n$. Note that:
(a) $\displaystyle x_n<x_{n+1} \Leftrightarrow x_n>1-\frac{1}{n} \Leftrightarrow P_n^{-1}(x_n)>P_n^{-1}(1-\frac{1}{n}) \Leftrightarrow x_1>a_n$;
(b) $\displaystyle x_n<1 \Leftrightarrow P_n^{-1}(x_n)<P_n^{-1}(1) \Leftrightarrow x_1<b_n$.
Thus, $0<x_n<x_{n+1}<1,\forall n$ holds if and only if $a_n<x_1<b_n,\forall n$, or $\displaystyle x_1 \in \bigcap_{n=1}^{+\infty}(a_n,b_n)$. We need to show that $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)$ is a singleton. We have:
(c) if $x_1=a_n$, then $x_n=1-\frac{1}{n}$, which implies that $x_{n+1}=1-\frac{1}{n}<1-\frac{1}{n+1}=P_{n+1}(a_{n+1})$, and $x_1<a_{n+1}$. It follows that $a_n<a_{n+1},\forall n$; and
(d) if $x_1=b_n$, then $x_n=1$, which implies that $x_{n+1}=1+\frac{1}{n}>1=P_{n+1}(b_{n+1})$, and $x_1>b_{n+1}$. It follows that $b_n>b_{n+1},\forall n$; and
Thus, $a_n<a_{n+1}<b_{n+1}<b_n, \forall n$. Therefore, the two sequences $\{a_n\}_{n=1}^{+\infty}$ and $\{b_n\}_{n=1}^{+\infty}$ converge, and their limits $a$ and $b$ satisfy $a \leq b$. Hence, $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)=[a,b]$ is non-empty, which demonstrates the existence of $x_1$.
Now, suppose that $a \leq x_1 \leq x_1' \leq b$. We have $x_{n+1}'-x_{n+1} = (x_n'-x_n)(x_n'+x_n+\frac{1}{n}) \geq (x_n'-x_n)(2-\frac{1}{n}) \geq (x_n'-x_n)$ for each $n$, so that $x_n'-x_n \geq x_1'-x_1$ for each $n$. However, $1-\frac{1}{n}<x_n \leq x_n'<1$, so that $0 \leq x_n'-x_n<\frac{1}{n}$, which implies that $\displaystyle \lim_{n \rightarrow +\infty}(x_n'-x_n)=0$. Therefore, $x_1' \leq x_1$, proving unicity.
This solution was posted and copyrighted by DAFR. The original thread for this problem can be found here: [1]

For each $n \ge 1$ let $I_n$ be the interval of real numbers $0 \textless x \textless 1$ such that if $x=x_1$, we will have $x_n \textless x_{n+1} \textless 1$. (That is, the values of $x_1$ which make $x_{n+1}$ "work"). We must prove these intervals intersect at one point.
First, I prove they intersect. Notice that as $x_1$ increases, $x_n$ and $x_{n+1}$ do too. So if $I_n=(a_n,b_n)$ it is easy to see $a_n=x_1$ will give $x_n=x_{n+1}=1-1/n$ and $b_n=x_1$ will give $x_{n+1}=1$ (the "extremal" values $x_{n+1}$ can take are given by the extremal values $x_1$ can take).
But if $a_n=x_1$ we see that $x_{n+1} \textless 1-1/(n+1)$ and so $x_{n+1} \textgreater x_{n+2}$ and similarly $x_1=b_n$ gives $x_{n+1}=1$ which gives a $x_{n+2}$ too big. So basically when $x_1$ only barely works for $x_{n+1}$, it won't work for $x_{n+2}$. So $I_{n+1}$ is a subset of $I_n$.
So we have an infinite sequence of open intervals, each contained inside the previous one. Therefore their intersection must contain at least one number. This guarantees the existence of $x_1$.
But, we must prove that $x_1$ can't take two different values. Suppose it could. Suppose $x_1=a,b$ both work. Let $x_i$ be the sequence generated by $a$ and $x_i'$ the sequence generated by $b$, and let $l_i=x_i'-x_i$ (wlog $a \textless b$). Then we see $l_{n+1}=l_n(2x_n+l_n+1/n) \textgreater l_n$ for $n \ge 2$ since $2x_n \textgreater 1$ since $x_n \textgreater 1-1/n \ge 1/2$. So there exists a constant $C$ such that $x_k' \ge x_k+C$ for $k \ge 2$. But since $x_k, x_k' \in (1-1/k, 1)$, this is impossible. So we're done.
This solution was posted and copyrighted by JuanOrtiz. The original thread for this problem can be found here: [2]

Consider, now, the following observations:
(a) If, at any point, $x_{n+1}\le x_n$, then from here we know that
and therefore the sequence $\{x_n\}$ will be monotonically decreasing after one point.
(b) If some $x$ does satisfy $0<x_n<x_{n+1}<1$ for all $n$, then $1-\frac{1}{n}<x_n<1$ for all $n$, and therefore by Squeeze's theorem $\lim_{n\to\infty}x_n = 1$.
(c) If $x_n\ge 1$ for some $n$, then $x_{n+1}=x_n(x_n+\frac 1n)>x_n^2\ge 1$ and so $x_{n+m}>(x_{m+1})^{2^{m-1}}$ which then gives $\lim_{n\to\infty}x_n=+\infty$.
(d) If $x_1=0$, then for each $n$, $x_n=0$. If $x_1\to\infty$ then for each $n$ (fixed), $x_n\to\infty$. Thus, we can denote a mapping $f_n:\mathbb{R}^{\ge 0}\to \mathbb{R}^{\ge 0}$ that maps $x_1$ to $x_n$, which is continuous and monotonically increasing, with $\lim_{x\to +\infty} f_n(x)=+\infty$ so $f_n$ is bijective.
Let's first show uniqueness. Suppose that $\{x_n\}$ and $\{y_n\}$ are both such sequences. We have $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ and suppose that $y_1>x_1$. Then for all $n$,
 so inductively, $\frac{y_{n+1}}{x_{n+1}}>(\frac{y_{1}}{x_{1}})^n$ with $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=+\infty$.
However, $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ gives $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=\frac{1}{1}=1$, contradiction.
Hence, the $x_1$ that satisfies this must be unique.
Next, let's show existence. We have seen from above that, $y_1>x_1$ implies $y_n>x_n$, and that if $x_n>1$ for some $n$ then $\{x_n\}$ is monotonically increasing after some point. Suppose no such $x_1$ exists. Let
\[
A=\{x_1: \exists n: x_{n+1}<x_n\}\qquad B=\{x_1: \exists n: x_n>1\}
\]then if $x\in A$, $y\in A$ for all $y<x$ and similarly $x\in B$, $y\in B$ for all $y>B$. Notice also an wasy fact that $1\in B$, so $A$ is bounded. Define, now, $c=glb(A)$. As we assumed $A\cup B=\mathbb{R}^+$, this $c$ implies that $x_1<c\to x_1\in A$ and $x_1>c\to x_1\in B$. It remains to ask whether $c\in A$ or $c\in B$.
If $c\in A$, then for this $x_1:=c$, $x_n\le 1-\frac{1}{n}$ and so $x_{n+1}<1-\frac{1}{n+1}$. Let $y_{n+1}$ be such that $x_{n+1}<y_{n+1}<1$. By above, there's exactly one $y_1$ with $f_{n+1}(y_1)<y_{n+1}$, and notice that $y_1>x_1=c$ by the monotonicity of $f_{n+1}$. This means that there exists $y_1>c\in A$, contradicting the definition of glb. A similar contradiction (but opposite direction) can also be established for the case $c\in B$.
Hence $c$ is neither in $A$ or $B$, means that $x_1=c$ should satisfy the problem condition. Q.E.D.
This solution was posted and copyrighted by Anzoteh. The original thread for this problem can be found here: [3]