IMO 1960 - Problem 7

Problem: A sphere is inscribed in a regular cone. Around the sphere a cylinder is circumscribed so that its base is in the same plane as the base of the cone. Let $V_1$ be the volume of the cone and $V_2$ the volume of the cylinder.
(a) Prove that $V_1=V_2$ is impossible.
(b) Find the smallest $k$ for which $V_1=kV_2$, and in this case construct the angle at the vertex of the cone.
Solution: Let $A$ be the vertex of the cone, $O$ the center of the sphere, $S$ the center of the base of the cone, $B$ a point on the base circle, and $r$ the radius of the sphere. Let $\angle{SAB}=\alpha$. We easily obtain $AS=\frac{r(1+sin(\alpha))}{sin(\alpha)}$ and $SB=\frac{r(1+sin(\alpha)tan(\alpha)}{sin(\alpha)}$ and hence $V_1=\pi.SB^2.\frac{SA}{3}=\pi.r^3.\frac{(1+sin(\alpha))^2}{3sin(\alpha)(1-sin(\alpha))}$. We also have $V_2=2\pi.r^3$ and hence $k=\frac{(1+sin(\alpha))^2}{6sin(\alpha)(1-sin(\alpha))}\implies (1+6k)sin^2(\alpha)+2(1-3k)sin(\alpha)+1=0$.
The discriminant of this quadratic must be nonnegative: $(1-3k)^2-(1+6k)\ge 0\implies k\ge \frac{4}{3}$. Hence we cannot have $k=1$. For $k=\frac{4}{3}$ we have $sin(\alpha)=\frac{1}{3}$, whose construction is elementary.

IMO 1960 - Problem 6

Problem: An isosceles trapezoid with bases $a$ and $b$ and height $h$ is given.
(a) On the line of symmetry construct the point $P$ such that both (non-base) sides are seen form $P$ with an angle of $90^0$.
(b) Find the distance of $P$ from one of the bases of the trapezoid .
(c) Under what conditions for $a,b$ and $h$ can be the point $P$ be constructed (analyze all possible cases) ?
Solution: Let $E,F$ respectively be the midpoints of the bases $AB,CD$ of the isosceles trapezoid $ABCD$.
(a) The point $P$ is on the intersection of $EF$ and the circle with diameter $BC$.
(b) Let $x=EP$. Since $\triangle{BEP}\sim \triangle{PFC}$, we have $x(h-x)=\frac{ab}{4}\implies x_{1,2}=\frac{h\pm \sqrt{h^2-ab}}{2}$.
(c) If $h^2>ab$ there are two solutions, if $h^2=ab$ there is only one solution, and if $h^2<ab$ there are no solutions.

IMO 1960 - Problem 5

Problem: A cube $ABCDA'B'C'D'$ is given.
(a) Find the locus of all midpoints of segments $XY$, where $X$ is any point on segment $AC$ and $Y$ any point on segment $B'D'$.
(b) Find the locus of all point $Z$ on segments $XY$ such that $\vec{ZY}=2\vec{XZ}$.
Solution:
(a) The locus of the points is the square $EFGH$ where these four points are the centers of the faces $ABB'A',BCC'B',CDD'C'$ and $DAA'D'$.
(b) The locus of the points is the rectangle $IJKL$ where these points are on $AB',CB',CD'$ and $AD'$ at a distance of $\frac{AA'}{3}$ with respect to the plane $ABCD$.

IMO 1960 - Problem 4

Problem: Construct a triangle $ABC$ whose lengths of heights $h_a$ and $h_b$ (from $A$ and $B$, respectively) and length of median $m_a$ (from $A$) are given.
Solution: Analysis. Let $A'$ and $B'$ be the feet of the perpendiculars from $A$ and $B$, respectively, to the opposite sides, $A_1$ the midpoint of $BC$, and let $D'$ be the foot of the perpendicular from $A_1$ to $AC$. We then have $AA_1=m_a$, $AA'=h_a,\angle{AA'A_1}=90^0,A_1D'=\frac{h_b}{2}$ and $\angle{AD'A_1}=90^0$.
Construction. We construct the quadrilateral $AD'A_1A'$( starting from the circle with diameter $AA_1$). Then $C$ is the intersection of $A'A_1$ and $AD'$, and $B$ is on the line $A_1C$ such that $CA_1=A_1B$ and $\mathscr{B}(B,A_1,C)$.
Dicussion. We must have $m_a\ge h_a$ and $m_a\ge \frac{h_b}{2}$. The number of solutions is $0$ if $m_a=h_a=\frac{h_b}{2},1$ if two of $m_a,h_a,\frac{h_b}{2}$ are equal, and $2$ otherwise.

IMO 1960 - Problem 3

Problem: A right - angled triangle $ABC$ is given for which the hypotenuse $BC$ has length $a$ and is divided into $n$ equal segments, where $n$ is odd. Let $\alpha$ be the angle with which the point $A$ sees segment containing the middle of the hypotenuse. Prove that: $tan(\alpha)=\frac{4nh}{(n^2-1)a}$.
Solution: Let $B'C'$ be the middle of the $n=2k+1$ segments and let $D$ be the foot of the perpendicular from $A$ to the hypotenuse. Let us assume $\mathscr{B}(C,D,C',B',B)$. Then from $CD<BD,CD+BD=a$, and $CD.BD=h^2$ we have $CD^2-a.CD+h^2=0\implies CD=\frac{a-\sqrt{a^2-4h^2}}{2}$. Let us define $\angle{DAC'}=\gamma$ and $\angle{DAB'}=\beta$; then $tan(\beta)=\frac{DB'}{h}$ and $tan(\gamma)=\frac{DC'}{h}$. Since $DB'=CB'-CD=\frac{(k+1)a}{2k+1}-\frac{c-\sqrt{c^2-4h^2}}{2}$ and $DC'=\frac{ka}{2k+1}-\frac{c-\sqrt{c^2-4h^2}}{2}$, we have : $tan(\alpha)=tan(\beta-\gamma)=\frac{tan(\beta)-tan(\gamma)}{1+tan(\beta).tan(\gamma)}=\frac{\frac{a}{(2k+1)h}}{1+\frac{a^2-4h^2}{4h^2}-\frac{a^2}{4h^2(2k+1)^2}}=\frac{4h(2k+1)}{4ak(k+1)}=\frac{4nh}{(n^2-1)a}$.

IMO 1960 - Problem 2

Problem: For which real numbers $x$ does the following inequality hold: $\frac{4x^2}{(1-\sqrt{1+2x})^2}<2x+9?$
Solution: The LHS term is well-defined for $x\ge \frac{-1}{2}$ and $x\ne 0$. Furthermore, $\frac{4x^2}{(1-\sqrt{1+2x})^2}=(1+\sqrt{1+2x})^2$. Since $f(x)=(1+\sqrt{1+2x})^2-2x-9=2\sqrt{1+2x}-7$ is increasing and since $f(\frac{45}{8})=0$, it follows that the inequality holds precisely for $\frac{-1}{2}\le x<\frac{45}{8}$ and $x\ne 0$.

IMO 1960 - Problem 1

Problem: Find all the three-digit numbers for which one obtains, when dividing the number by $11$, the sum of squares of the digits of the initial number.
Solution: Given the number $\overline{acb},$ since $11|\overline{acb}$, it follows that $c=a+b$ or $c=a+b-11$. In the first case, $a^2+b^2+(a+b)^2=10a+b$, and in the second case, $a^2+b^2+(a+b-11)^2=10(a-1)+b$. In the first case the LHS is even, and hence $b\in \left\{0,2,4,6,8\right\}$, while in the second case it is odd, and hence $b\in \left\{1,3,5,7,9\right\}$. Analyzing the $10$ quadratic equation for $a$ we obtains that the only valid solutions are $550$ and $803$.

Putnam 2018 - B3

Problem: Find all positive integers $n<10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n-1$ and $n-2$ divides $2^n-2$.
Solution: Since $n|2^{n}\implies n=2^{k}$ for some $k\ge 0$. Substituting into the second divisibility, $2^{k}-1|2^{2^{k}}-1$. Now we use the result $gcd(2^{a}-1,2^{b}-1)=2^{gcd(a,b)}-1$ to see $gcd(2^{2^{k}}-1,2^{k}-1)=2^{gcd(2^{k},k)}-1=2^{k}-1$, therefore $gcd(2^{k},k)=k$ and $k|2^{k}$, so $k=2^{m}$. Therefore, $n=2^{2^{m}}$. Substituting into the final divisibility,
$2^{2^{m}}-2|2^{2^{2^{m}}}-2\implies 2^{2^{m}-1}-1|2^{2^{2^{m}-1}}-1$. Using the exponential divisible sequence property twice, $gcd(2^{2^{2^{m}-1}}-1,2^{2^{m}-1}-1)=2^{gcd(2^{2^{m}-1},2^{m}-1)}-1=2^{2^{gcd(2^{m},m)}-1}-1=2^{2^{m}-1}-1,$
therefore $gcd(2^{m},m)=m$ and $m=2^{l}$ for some $l\ge 0$. Therefore $n=2^{2^{2^{l}}}$ for $l=0,1,2,3$ giving the solutions $n=4,16,65536,2^{256}$. Note that $2^{256}<2^{300}=8^{100}<10^{100}$, therefore these all satisfy $n<10^{100}$. Clearly for $l\ge 4,n=2^{2^{2^{l}}}\ge 2^{2^{16}}=2^{65536}>>10^{100}$.

IMO 1959 - Problem 6

Problem: Let $\alpha$ and $\beta$ be two planes intersenting at a line $p$. In $\alpha$ a point $A$ is given and in $\beta$ a point $C$ is given, neither of which lies on $p$. Construct $B$ in $\alpha$ and $D$ in $\beta$ such that $ABCD$ is an equilateral trapezoid, $AB\parallel CD,$ in which a circle can be inscribed.
Solution: 
Analysis. For $AB\parallel CD$ to hold evidently neither must intersect $p$ and hence constructing lines $r$ in $\alpha$ through $A$ and $s$ in $\beta$ through $C$, both being parallel to $p$, we get that $B\in r$ and $D\in s$. Hence the problem reduces to a planar problem in $\gamma$, determined by $r$ and $s$. Denote by $A'$ the foot of the perpendicular from $A$ to $s$. Since $ABCD$ is isosceles and has an incircle, it follows $AD=BC=\frac{AB+CD}{2}=A'C$. The remaining parts of the problem are now obvious.

IMO 1959 - Problem 5

Problem: A segment $AB$ is given and on it a point $M$. On the same side of $AB$ squares $AMCD$ and $BMFE$ are constructed. The circumcircles of the two squares, whose centers are $P$ and $Q$, intersects in $M$ and another point $N$.
(a) Prove that lines $FA$ and $BC$ intersect at $N$.
(b) Prove that all such constructed lines $MN$ pass through the same point $S$, regardless of the selention of $M$.
(c) Find the locus of the midpoints of all segments $PQ$, as $M$ varies along the segment $AB$.
Solution: 
(a) It suffices to prove that $AF\bot BC$, since then for the intersection point $X$ we have $\angle{AXC}=\angle{BXF}=90^0$, implying that $X$ belongs to the circumcircles of both squares and thus that $X=N$. The relation $AF\bot BC$ holds because from $MA=MC,MF=MB$, and $\angle{AMC}=\angle{FMB}$ it follows that $\triangle{AMF}$ is obtained by rotating $\triangle{BMC}$ by $90^0$ around $M$.
(b) Since $N$ is on the circumcircle of $BMFE$, it follows that $\angle{ANM}=\angle{MNB}=45^0$. Hence $MN$ is the bisector of $\angle{ANB}$. It follows that $MN$ passes through the midpoint of the arc $AB$ of the circle with diameter $AB$(i.e, the circumcircle of $\triangle{ABN}$) not containing $N$.
(c) Let us introduce a coordinate system such that $A=(0,0),B=(b,0)$ and $M=(m,0)$. Setting in general $W=(x_W,y_W)$ for an arbitrary point $W$ and denoting by $R$ the midpoint of $PQ$, we have $y_R=\frac{y_P+y_Q}{2}=\frac{m+b-m}{4}=\frac{b}{4}$ and $x_R=\frac{x_P+x_Q}{2}=\frac{m+m+b}{4}=\frac{2m+b}{4}$, the parameter $m$ varying from $0$ to $b$. Thus the locus of all points $R$ is the closed segment $R_1R_2$ where $R_1=(\frac{b}{4},\frac{b}{4})$ and $R_2=(\frac{b}{4},\frac{3b}{4})$.

IMO 1959 - Problem 4

Problem: Construct a right-angled triangle whose hypotenuse $c$ is given if it is known that the median from the right angle equals the geometric mean of the remaining two sides of the triangle.
Solution: Analysis. Let $a$ and $b$ be the other two sides of the triangle. From the conditions of the problem we have $c^2=a^2+b^2$ and $\frac{c}{2}=\sqrt{ab}\iff \frac{3}{2}c^2=a^2+b^2+2ab=(a+b)^2\iff \sqrt{\frac{3}{2}}c=a+b$. Given a desired $\triangle{ABC}$ let $D$ be a point on ($AC$ such that $CD=CB$). In that case, $AD=a+b=\sqrt{\frac{3}{2}}c,$ and also, since $BC=CD$, it follows that $\angle{ADB}=45^0$.
Construction. From a segment of length $c$ we elementarily construct a segment $AD$ of length $\sqrt{\frac{3}{2}}c$. We then construct a ray $DX$ such that $\angle{ADX}=45^0$ and a circle $k(A,c)$ that intersects the ray at point $B$.
Finally, we construct the perpendicular from $B$ to $AD$; point $C$ is the foot of that perpendicular.
Proof. It holds that $AB=c$ and since $CB=CD$, it also holds that $AC+CB=AC+CD=AD=\sqrt{\frac{3}{2}}c$. From this it follows that $\sqrt{AC.CB}=\frac{c}{2}$. Since $BC$ is perpendicular to $AD$, it follows that $\angle{BCA}=90^0$. Thus $ABC$ is the desired triangle.
Dicussion. Since $AB\sqrt{2}=\sqrt{2}c>\sqrt{\frac{3}{2}}c=AD>AB$, the circle $k$ intersects the ray $DX$ in exactly two points, which correspond to two symmetric solutions.

IMO 1959 - Problem 3

Problem: Let $x$ be an angle and let the real number $a,b,c,cos(x)$ satisfy the following equation: $acos^2(x)+bcos(x)+c=0$.
Write the analogous quadratic equation for $a,b,c,cos(2x)$. Compare the given and the obtained equality for $a=4,b=2,c=-1$.
Solution: Multiplying the equality by $4(acos^2(x)-bcos(x)+c)$, we obtain $4a^2cos^4x+2(4ac-2b^2)cos^2(x)+4c^2=0$. Plugging in $2cos^2(x)=1+cos(2x)$ we obtain (after quite a bit of manipulation):
$a^2cos^2(2x)+(2a^2+4ac-2b^2)cos(2x)+(a^2+4ac-2b^2+4c^2)=0$.
For $a=4,b=2$ and $c=-1$ we get $4cos^2(x)+2cos(x)-1=0$ and $16cos^(2x)+8cos(2x)-4=0\implies 4cos^2(2x)+2cos(2x)-1=0$

IMO 1959 - Problem 2

Problem 2: For which real number $x$ do the following equations hold:
(a) $\sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=\sqrt{2},$
(b) $\sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=1,$
(c) $\sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=2,$
Solution: For the square roots to be real we must have $2x-1\ge 0\implies x\ge \frac{1}{2}$ and $x\ge \sqrt{2x-1}\implies (x-1)^2\ge 0,$ which always holds. Then we have $\sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=c\iff c^2=2x+2\sqrt{(x-1)^2}=2x+2|x-1|=\left\{\begin{array}{I} 2,\frac{1}{2}\le x\le 1,\\ 4x-2,x\ge 1\end{array}\right.$
(a) $c^2=2$. The equation holds for $\frac{1}{2}\le x\le 1$.
(b) $c^2=1$. The equation has no solution.
(c) $c^2=4$. The equation holds for $4x-2=4\implies x=\frac{3}{2}$.

IMO 1959- Problem 1

Problem: For every integer $n$ prove that the fraction $\frac{21n+4}{14n+3}$ cannot be reduced any further.
Solution: The desired result $(14n+3,21n+4)=1$ follows from $3(14n+3)-2(21n+4)=1$.

IMO 1994- Problem 6

Problem: Show that there exists a set $A$ of positive integers with the following property: For any infinite set $S$ of primes there exists two positive integers $m\in A$ and $n\notin A$ each of which is a product of $k$ distinct elements of $S$ for some $k\ge 2$.
Solution: Let $A$ be the of all positive integers of the form $q_1q_2...q_{q_1}$ where $q_1<q_2<...<q_{q_1}$ are primes. For any infinite set $S=\left\{p_1,p_2,...,\right\}$ of primes with $p_1<p_2,...$, we can satisfy he requirement of the problem by taking $k=p_1,m=p_1p_2...p_k$ and $n=p_2p_3...p_{k+1}$.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1994- Problem 5

Problem: Let $\mathbb{S}$ be the set of real numbers strictly greater than $-1$. Find all functions $f:\mathbb{S}\to \mathbb{S}$ satisfying the two conditions:
(i) $f(x)+f(y)+xf(y)=y+f(x)+yf(x)$ for all $x$ and $y$ in $\mathbb{S}$.
(ii) $\frac{f(x)}{x}$ is strictly increasing on each of the intervals $-1<x<0$  and $0<x$.
Solution: Condition (ii) implies that $f(x)=x$ has at most three solutions, one in $(-1,0),$ one equal to $0$ and the third in $(0,\infty)$.
Suppose $f(u)=u$ for some $u\in (-1,0)$. Setting $x=y=u$ in (i), we get $f(u^2+2u)=u^2+2u\in (-1,0)$.
This means $u^2+2u=u$. But then $u\notin (-1,0)$. The case $f(v)=v$ for some $v>0$ leads to a similar contradiction.
  However, $f(x+(1+x)f(x))=x+(1+x)f(x)$ for all $x\in \mathbb{S}$. So we have $x+(1+x)f(x)=0$ which gives $f(x)=-\frac{x}{1+x}$.
It's routine to check that $f(x)=-\frac{x}{1+x}$ satisfies the desired property.
Source:http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1994- Problem 4

Problem: Determine all ordered pairs $(m,n)$ of positive integers such that $\frac{n^3+1}{mn-1}$ is an integer.
Solution: Note that $mn-1$ and $m^3$ are relative prime. That $mn-1$ dividing $n^3+1$ is therefore equivalent to $mn-1$ dividing $m^3(n^3+1)=m^3n^3-1+m^3+1$, which is in turn equivalent to $mn-1$ dividing $m^3+1$. If $m=n$, we have $\frac{n^3+1}{n^2-1}=n+\frac{1}{n-1}$. This is an integer if and only if $n=2$. We now consider the case $m>n$. If $n=1,\frac{2}{m-1}$ is an integer. This is so if and only if $m=2,3$. Suppose $n\ge 2$. Note that $n^3+1\equiv 1(\text{ mod }n)$ while $mn-1\equiv -1(\text{ mod }n)$. Hence $\frac{n^3+1}{mn-1}=kn-1$ for some positive integer $k$. Now $kn-1<\frac{n^3+1}{n^2-1}=n+\frac{1}{n-1}$ or $(k-1)n<1+\frac{1}{n-1}$. Hence $k=1$, so that $n^3+1=(mn-1)(n-1)$. This yields $m=\frac{n^2+1}{n+1}=n+1+\frac{2}{n-1}$, which is an integer if and only if $n=2,3$. In each case, we have $m=5$. In summary, there are $9$ solutions, namely $(2,2),(2,1),(3,1),(5,2),(5,3),(1,2),(1,3),(2,5),(3,5)$
the last $4$ obtained by symmetry.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1994- Problem 3

Problem: For any positive integer $k$, let $f(k)$ be the number of elements in the set $\left\{k+1,k+2,...,2k\right\}$ whose base $2$ representation has precisely three $1s$.
(a) Prove that, for each positive integer $m$, there exists at least one positive integer $k$ such that $f(k)=m$.
(b) Determine all positive integers $m$ for which there exists exactly one $k$ with $f(k)=m$.
Solution: Let $g(k)$ denote the number of elements in the set $\left\{1,...,n\right\}$ whose binary representation has exactly three ones. Then $f(k)$ and $g(k)$ are both increasing and $f(k)=g(2k)-g(k)$. Hence
   $f(k+1)-f(k)=g(2k+2)-g(k+1)-g(2k)+g(k)=g(2k+2)-g(2k)-[g(k+1)-g(k)]$
Since either both $2k+2$ is counted in $g(2k+2)$ and $k+1$ is counted in $g(k+1)$ or neither is. Thus $f(k+1)-f(k)$ is either $1$ or $0$ depending on where $2k+1$ is counted in $g(2k+1)$ or not. Since $f(2^n)=C_{n+1}^3-C_{n}^3=C_{n}^2$, the image of $f$ is $\mathbb{N}\cup \left\{0\right\}$. This proves (a)
.
Let $m$ be any positive integer for which there is only one $k$ with $f(k)=m$. Then $f(k+1)-f(k)=1=f(k)-f(k-1)$.
The former means $2k+1$ is counted in $g(2k+2)$, or equivalently, the binary representation of $k$ has exactly two ones. The same holds for $k-1$. This happens only when the last two digits of $k-1$ are $01$. In other words, $k=2^n+2$. But
$f(2^n+2)=g(2^{n+1}+4)-g(2^n+2)=1+g(2^{n+1})-g(2^n)=1+C_{n}^2$
Thus the answer is any number of the form $1+C_{n}^2,n\ge 2$.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1994- Problem 2

Problem: $ABC$ is an isosceles triangle with $AB=AC$. Suppose that:
(i) $M$ is the midpoint of $BC$ and $O$ is the point on the line $AM$ such that $OB$ is perpendicular to $AB$.
(ii) $Q$ is an arbitrary point on the segment $BC$ different from $B$ and $C$.
(iii) $E$ lies on the line $AB$ and $F$ lies on the line $AC$ such that $E,Q$ and $F$ are distinct and collinear.
Prove that $OQ$ is perpendicular to $EF$ if and only if $QE=QF$.
Solution: First assume that $OQ$ is perpendicular to $EF$. Now $OEBQ$ and $OCFQ$ are cyclic.
Hence $\angle{OEQ}=\angle{OBQ}=\angle{OCQ}=\angle{OFQ}$. It follows that $QE=QF$.
Suppose now that $QE=QF$ and that the perpendicular through $O$ to $EF$ meet $BC$ at $Q'\ne Q$. Draw the line through $Q'$ parallel to $EF$, meeting the lines $AB$ and $AC$ at $E'$ and $F'$,respectively. Then $Q'E'=Q'F'$ as before. Let $AQ'$ meet $EF$ at $N$. Then $N\ne Q$ and $NE=NF$, so that $QE\ne QF$, a contradiction. So $Q'=Q$.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1994- Problem 1

Problem: Let $m$ and $n$ be positive integers. Let $a_1,a_2,...,a_m$ be distinct elements of $\left\{1,2,...,n\right\}$ such that whenever $a_i+a_j\le n$ for some $i,j,1\le i\le j\le m$, there exists $k$, $1\le k\le m,$ with $a_i+a_j=a_k$. Prove that: $\frac{a_1+a_2+...+a_m}{m}\ge \frac{n+1}{2}$.
Solution: Without loss of generality, we may assume that $a_1>a_2>...>a_m$. We claim that $a_i+a_{m+1-i}\ge n+1$ for $i=1,...,m$. The result then follows readily. To prove the claim ,we assume that on the contrary that it's false. Thus there exists $i$ such that $a_i+a_{m+1-i}<n+1$. Then $a_i<a_i+a_m<a_i+a_{m-1}<...<a_i+a_{m+1-i}\le n$. Thus $\left\{a_i+a_m,a_i+a_{m-1},...,a_{i}+a_{m+1-i}\right\}\subseteq \left\{a_1,a_2,...,a_{i-1}\right\}$
which is impossible. Thus the claim follows.
Source: http://sms.math.nus.edu.sg/simo/IMO_Problems/94.pdf

IMO 1995- Problem 6

Problem: Let $p$ be an odd prime. Find the number of $p$- element subsets $A$ of $\left\{1,2,...,2p\right\}$ such that the sum if all elements of $A$ is divisible by $p$.
Solution: For any $p$-element subset $A$ of $\left\{1,2,...,2p\right\}$, denote by $s(A)$ the sum of the elements of $A$. Of the $C_{2p}^{p}$ such subsets, $B=\left\{1,2,...,p\right\}$ and $C=\left\{p+1,p+2,...,2p\right\}$ satisfy $s(B)\equiv s(C)\equiv 0(\text{ mod }p)$. For $A\ne B,C$, we have $A\cap B\ne \emptyset \ne A\cap C$. Partition the $C_{2p}^{p}-2p-$ element subsets other than $b$ and $C$ into groups of size $p$ as follows. Two subsets $A$ and $A'$ are in the same group if and only if $A'\cap C=A\cap C$ and $A'\cap B$ is a cyclic permutation of $A\cap B$ within $B$. Suppose $A\cap B$ has $n$ elements, $0\le n<p$. For some $m$ such that $0<m<p$,
$A'\cap B=\left\{x+m:x\in A\cap B,x+m\le p\right\}\cup \left\{x+m-p:x\in A\cap B,x\le p<x+m\right\}$.
Hence $s(A')-s(A)\equiv mn(\text{ mod }p)$, but $mn$ is not divisible by $p$. It follows that exactly one subset $A$ in each group satisfies $s(A)\equiv 0(\text{ mod }p)$, and the total number of such subsets is $p^-1(C_{2p}^{p}-2)+2$.
Second solution: Let $\omega$ be a primitive $pth$ root of unity. Then
$a_0+a_1\omega+...+a_{p-1}\omega^{p-1}=0$ iff $a_0=a_1=...=a_{p-1}$
Also $\prod\limits_{k=1}^{2p}(x-\omega^k)=(x^{p}-1)^2=2^{2p}-2x^{p}+1$.
If $t(\omega)=\sum a_i\omega^{i}$, then $a_i$ is the number of combinations with $i_1+...+i_p\equiv i(\text{ mod }p)$.
Therefore :$(a_0-2)+a_1\omega+...+a_{p-1}^{p-1}\equiv 0$
and $a_0-2=a_1=...=a_p$. So $|S|=\frac{C_{2p}^{p}-2}{p}+2$
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

IMO 1995 - Problem 5

Problem: Let $ABCDEF$ be a convex hexagon with $AB=BC=CD,DE=EF=FA$ and $\angle{BCD}=\angle{EFA}=\frac{\pi}{3}$. Let $G$ and $H$ be two points interior to the hexagon such that angles $AGB$ and $DHE$ are both $\frac{2\pi}{3}$. Prove that: $AG+GB+GH+DH+HE\ge CF$.
Solution: Note that $BCD$ and $EFA$ are equilateral triangles. Hence $BE$ is an axis of symmetry of $ABDE$. Reflect $BCD$ and $EFA$ about $BE$ to $BC'A$ and $EF'D$ respectively. Since $\angle{BGA}=180^0-\angle{AC'B}$, $G$ lies on the circumcircle of $ABC'$. By Ptolemy's Theorem, $AG+GB=C'G$. Similarly, $DH+HE=HF'$. It follows that:
$CF=C'F'\le C'G+GH+HF'=AG+GB+GH+DH+HE,$ with equality if and only if $G$ and $H$ both lie on $C'F'$
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

IMO 1995- Problem 4

Problem: The positive real numbers $x_0,x_1,...,x_{1995}$ satisfy $x_0=x_{1995}$ and $x_{i-1}+\frac{2}{x_{i-1}}=2x_i+\frac{1}{x_i}$ for $i=1,2,...,1995$. Find the maximum value that $x_0$ can have.
Solution: The given condition is equivalent to $(2x_i^2-x_{i-1})(x_i-\frac{1}{x_{i-1}})=0$
which yield $x_i=\frac{x_{i-1}}{2}$ and $x_i=\frac{1}{x_{i-1}}$. We shall prove by induction that $x_i=2^{k_i}x_0^{\epsilon_{i}}$, where $|k_i|\le i$ and $\epsilon_i=(-1)^{k_i+i}$. This is true for $i=0$, with $k_0=0,\epsilon_0=1$. Assume that it is true for $i-1$. Then for $x_i=\frac{1}{2}x_{i-1}$, we have $k_i=k_{i-1}-1$ and $\epsilon_i=\epsilon_{i-1}$. For $x_i=\frac{1}{x_{i-1}}$, we have $k_i=-k_{i-1}$ and $\epsilon_{i}=-\epsilon_{i-1}$. In each case, it is immediate that $|k_i|\le i$ and $\epsilon_i=(-1)^{k_i+i}$. Thus $x_0=x_{1995}=2^{k}x_0^{\epsilon}$ where $k=k_{1995}$ and $\epsilon=\epsilon_{1995}$. Thus $|k|\le 1995$ and $\epsilon=(-1)^{1995+k}$. If $k$ is odd then $\epsilon=1$ and this is impossible. Thus $k$ is even and $\epsilon=-1$ and $x_0^2=2^k$. Since $|k|\le 1995$, we have $k\le 1994$. Hence $x_0\le 2^{997}$. The value $x_0=2^{997}$ can be attained by choosing $x_i=\frac{1}{2}x_{i-1}$ for $i=1,2,...,1994$ and $x_{1995}=\frac{1}{x_{1994}}$.
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

IMO 1995 - Problem 3

Problem: Determine all integers $n>3$ such that there are $n$ points $A_1,A_2,...,A_n$ in the plane which satisfy the following two conditions simultaneously.
(a) No three lie on the same line
(b) There exist real numbers $p_1,p_2,...,p_n$ such that the area of $\triangle{A_iA_jA_k}$ is equal to $p_i+p_j+p_k$ for $1\le i<j<k\le n$.
Solution: We claim $n=4$ is the only answer. For $n=4$, let $A_1A_2A_3A_4$ be a unit square and let $p_1=p_2=p_3=p_4=\frac{1}{6}$. It remains to show no solution exists for $n=5$ which implies that there no solution for any $n\ge 5$.
 Suppose to the contrary that there is solution with $n=5$. Denote the area of $\triangle{A_iA_jA_k}$ by $[ijk]=p_i+p_j+p_k$. We cannot have $p_i=p_j$. If for example $p_4=p_5,$ then $[124]=[125]$ and $[234]=[235]$, which implies that $A_4A_5$ is parallel to both $A_1A_2$ and $A_2A_3$. This is impossible since $A_1,A_2,A_3$ are not collinear. We also observe that if $A_iA_jA_kA_l$ is convex, then $p_i+p_k=p_j+p_l$. This follows from $[ijk]+[kli]=[jkl]+[lij]$.
Consider the convex hull of $A_1,...,A_5$, we have $3$ cases. First, suppose that the convex hull is a pentagon $A_1A_2A_3A_4A_5$. Since $A_1A_2A_3A_4$ and $A_1A_2A_3A_5$ are convex, our observation yields $p_1+p_3=p_2+p_4$ and $p_1+p_3=p_2+p_5$. Hence $p_4=p_5$, a contradiction.
Next we suppose that the convex hull is a quadrilateral $A_1A_2A_3A_4$. We may assume that $A_5$ is within $A_3A_4A_1$. Then $A_1A_2A_3A_5$ is convex and we have the same contradiction as before.
Finally suppose that the convex hull is a triangle $A_1A_2A_3$. Since $[124]+[234]+[314]=[125]+[235]+[315]$ we have $p_4=p_5$, a contradiction.
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

IMO 1995 - Problem 2

Problem: Let $a,b$ and $c$ be positive real numbers such that $abc=1$. Prove that: $\frac{1}{a^3(b+c)}+\frac{1}{b^3(a+c)}+\frac{1}{c^3(a+b)}\ge \frac{3}{2}$.
Solution: Let $S$ be the right hand side and $T=a(b+c)+b(a+c)+c(a+b)=2(ab+bc+ca)\ge 6(abc)^{\frac{2}{3}}=6$. Then by Cauchy's inequality, we have :
$ST\ge (\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^2=\frac{T^2}{4}$.
Thus $S\ge \frac{T}{4}\ge \frac{3}{2}$ as desired.
Second solution: Let $x=\frac{1}{a},y=\frac{1}{b},z=\frac{1}{c}$. Then $xyz=1$ and $S=\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}$.
By Cauchy's inequality,
[(x+y)+(z+x)+(x+y)] S\ge (x+y+z)^2.
or $S\ge \frac{x+y+z}{2}\ge \frac{3}{2}(xyz)^{\frac{1}{3}}=\frac{3}{2}$ as desired.
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

IMO 1995- Problem 1

Problem: Let $A,B,C,D$ be distinct points on a line, in that order. The circles with diameters $AC$ and $BD$ intersect at $X$ and $Y$. $O$ is an arbitrary point on line $XY$ but not on $AD$. $CO$ intersects the circle with diameter $AC$ again at $M$, and $BO$ intersects the other circle again at $N$. Prove that $AM,DN$ and $XY$ are concurrent.
Solution: The result is trivial if $O$ coincides with $X$ or $Y$. Suppose it does not. From $ON.ON=OX.OY=OC.OM,$
$BCMN$ is cyclic. If $O$ is on the segment $XY$, then
$\angle{MAD}+\angle{MNB}+\angle{BND}=\angle{MAD}+\angle{MCA}+\angle{AMC}=180^0$.
If $O$ is not on the segment $XY$, then
$\angle{MAD}=180^0-\angle{AMC}-\angle{MAC}=180^0-\angle{BND}-\angle{ONM}=\angle{MND}$.
In either case, $ADNM$ is also cyclic. Let $AM$ and $DN$ intersect at $Z$. Let the line $ZX$ intersect the first circle at $Y_1$ and the second at $Y_2$. Then $ZX.ZY_1=ZA.ZM=ZD.ZN=ZX.ZY_2$.
Hence $Y_1=Y_2=Y$ and indeed $Z$ lies on $XY$.
Source: https://sms.math.nus.edu.sg/Simo/IMO_Problems/95.pdf

Taiwan TST 2014

Problem: Positive integers $x_1,x_2,...,x_n(n\ge 4)$ are arranged in a circle such that each $x_i$ divides the sum of the neighbors, that is $\frac{x_{i-1}+x_{i+1}}{x_i}=k_i$ is an integer for each $i$, where $x_0=x_n,x_{n+1}=x_1$. Prove that: $2n\le k_1+k_2+...+k_n<3n$.

Solution: We first establish the lower bound. Note that:

$\sum\limits_{i=1}^{n}k_i=\sum\limits_{i=1}^{n}(\frac{x_{i+1}}{x_i}+\frac{x_{i-1}}{x_i})\ge (2n)\sqrt[2n]{1}=2n$, where the inequality is $AM-GM$.

We claim that the upper bound holds for all $n\ge 2$. We proceed by induction on $n$. Consider the base case $n=2$. Here, $k_1=\frac{2x_2}{x_1},$ and $k_2=\frac{2x_1}{x_2}$. Note that $k_1,k_2\in \mathbb{N}$ and $k_1k_2=4$, so either $k_1=4$ and $k_2=1$ or $k_1=k_2=2$. In the first case, we get $(x,2x)$, in the second we get $(x,x)$, both of which work.

Assume the upper bound holds for $n-1$. Now consider the situation for $n$. WLOG, let $x_n$ be the maximum element. There are three cases.

Case 1: $k_n\ge 3$. In this case, $x_1+x_{n-1}\ge 3x_n$. However, this clearly violates the maximality of $x_n$, so this case does not exist.

Case 2: $k_n=2$. In this case, $x_1+x_{n-1}=2x_n$. The only way to not violate maximality of $x_n$ is for $x_{n-1}=x_1=x_n$. However, one quickly sees that this implies that the whole sequence is constant, in which case the average of the $k_is$ is $2$, so this case is resolved.

Case 3: $k_n=1$. Now, $x_n=x_1+x_{n-1}$. Note that:

$\frac{k_1+...+k_n}{n}=\frac{k_1+k_{n-1}+k_n+\sum\limits_{i=2}^{n-2}k_i}{n}$

$=\frac{3+\frac{x_{n-2}+x_1}{x_{n-1}+\frac{x_2+x_{n-1}}{x_1}}}{n}<\frac{3+3(n-1)}{n}=3$, where the inequality follows from the inductive hypothesis. Therefore, our induction, and our proof is complete.

Source: https://artofproblemsolving.com/community/c473124h1546246_more_combinatorics

USAMO 2009

Problem: Let $n$ be a positive integer. Determine the size of the largest subsets of $\left\{-n,-n+1,...,n-1,n\right\}$ which does not contain three elements $a,b,c$( not necessarily distinct) satisfying $a+b+c=0$.
Solution: We claim the answer is $n$ for $n$ even and $n+1$ for $n$ odd. In both cases, we simply take the subsets of all odd numbers as an equality case.
Let $P$ be the set of positive numbers in our subset, and $N$ be the set of negative numbers( note that $0$ is not in our subset since $0+0+0=0$). Now, the condition is equivalent to saying that $-P,-N,P+N$ are disjoint.
Note that: $P+N=\left\{p+n:p\in P,n\in N\right\}$.
We now claim that $|P+N|\ge |P|+|N|-1$. To do this, let $P=\left\{x_1<...<x_m\right\}$ and let $N=\left\{y_1<...<y_n\right\}$. Then, the following elements are in $P+N:$
$x_1+y_1<x_2+y_1<...<x_m+y_1<x_m+y_2<...<x_m+y_n$
This proves the claim. Now, since $-P,-N,P+N$ are disjoint, we have that:
$|-P|+|-N|+|P+N|\le 2n+1\implies |P|+|N|+|P|+|N|-1\le 2n+1$
$\implies |P|+|N|\le n+1$.
This completes the proof for the odd case, but this is not strong enough for the even case.
We will now show that in fact $|P|+|N|\le n$ if $n$ is even. Assume not, so then equality must hold in all the above inequalities. Therefore, $(-P)\cup (-N)\cup (P+N)=\left\{-n,...\right\},$ and $|P+N|=|P|+|N|-1$. To start, since $0\notin P,N$, we must have that $n,-n\notin P+N$, so $n\in P$ and $-n\in N$.
Say that some $x\in P$. Then, since $-n\in N$, we must have that $x-n\in P+N$. However, since $-P,-N,P+N$ are disjoint, we must have that $x-n\notin -P,$ or $n-x\in P$. Thus,
$x\in P\implies n-x\notin P$. Therefore, one seems that from the numbers $1,...,n$, at most $1+\frac{n-2}{2}=\frac{n}{2}$ of them can be in $P$(note that $\frac{n}{2}\notin P$ since $\frac{n}{2}\in P\implies n-\frac{n}{2}\notin P$). Similar, one can show that there are at most $\frac{n}{2}$ elements in $N$. However, this implies $|P|+|N|\le n,$ which is a contradiction, since we started by assuming $|P|+|N|>n$. Therefore, for $n$ even, we can have at most $n$ elements in the subset.
Source: https://artofproblemsolving.com/community/c473124h1546246_more_combinatorics

Middle European Mathematical Olympiad T-2

Problem: Determine all functions $f:\mathbb{R}\to \mathbb{R}$ such that: $xf(xy)+xyf(x)\ge f(x^2)f(y)+x^2y$ holds for all $x,y\in \mathbb{R}$.
Solution: Let $(x,y)$ denote the assertion $xf(xy)+xyf(x)\ge f(x^2)f(y)+x^2y$.
$(x,x)\implies (x^2-f(x^2))(x-f(x))\le 0,$denote this by $(1)$
$(0,0)\implies f(0)=0$
$(1,1)\implies f(1)=1$.
$(x,1)\implies 2xf(x)\ge f(x^2)+x^2\implies f(x)^2-f(x^2)\ge (f(x)-x)^2,$denoted this by $(2)$.
Now, suppose that there exists $a\ge 0$ such that $a>f(a)$.
$(1)\implies (a^2-f(a^2))(a-f(a))\le 0\implies a^2-f(a^2)\le 0\implies -f(a^2)\le -a^2$.
$(2)\implies (f(a)-a)^2\le f(a)^2-f(a^2)\le f(a)^2-a^2=(f(a)-a)(f(a)+a)$
As $f(a)-a<0$, we get $f(a)-a\ge f(a)+a\implies 2a\le 0$, which isn't true. So $f(x)\ge x$ for every $x\ge 0$.
That means $f(x^2)\ge x^2\forall x$.
$(1)\implies x\ge f(x)\forall x\implies \boxed{f(x)=x\forall x\ge 0}$
$(x<0,y<0)\implies x(yf(x)-xf(y))\ge 0\implies yf(x)\le xf(y)$, and let that be $(3)$.
$(y,x)\rightarrow (3)\implies xf(y)\le yf(x)\implies xf(y)=yf(x)\implies f(x)=cx\forall x<0$.
$(2)\implies 2xf(x)\ge f(x^2)+x^2\ge 2x^2\implies x(f(x)-x)\ge 0\implies f(x)\le x\forall x<0$
So, $\boxed{f(x)=cx\forall x<0}$ with $c\ge 1$.
It's easy to see that:
$\boxed{f(x)=\left\{\begin{array}{I} x\text{ if }x\ge 0\\cx\text{ if }x<0 \end{array}\right.,c\ge 1}$
Source: https://artofproblemsolving.com/community/c6h607043_functional_inequality

Iran TST 2014 third exam - Problem 6

Problem: The incircle of a non-isosceles triangle $ABC$ with the center $I$ touches the side $BC$ at $D$. Let $X$ is a point on arc $BC$ from circumcircle of triangle $ABC$ such that if $E,F$ are feet of perpendicular from $X$ on $BI,CI$ and $M$ is midpoint of $EF$ we have $MB=MC$.
Prove that: $\angle{BAD}=\angle{CAX}$.
Solution: 
Let $\angle{CBA}=2a,\angle{BCA}=2b$.
Let $Q,W,R$ are foot of perpendicular from $E,M,F$ on $BC$.
$MB=MC\implies BW=WC$, but $M$ is midpoint of $EF\implies WQ=WR\implies BQ=CR\implies BE.cos(a)=CF.cos(b)$.
Let $I_a$ is $A-excenter$.
Let $T,S$ are foot of perpendicular from $X$ to $BI_a,CI_a\implies \frac{XT}{XS}=\frac{BE}{CF}=\frac{cos(b)}{cos(a)}=\frac{sin\angle{BCI_a}}{sin\angle{CBI_a}}=\frac{sin\angle{XI_aB}}{sin\angle{XI_aC}}\implies XI_a$ is symmedian of triangle $CI_aB$.
Let $L$ is midpoint of arc $BAC$, $\angle{LBC}=\angle{LCB}=\angle{CI_aB}\implies LB,LC$ are tangent to circumcircle of triangle $CI_aB$.
$\frac{BX}{CX}=\frac{sin\angle{BLX}}{sin\angle{CLX}}=(\frac{cos(b)}{cos(a)})^2(1)$.
$\frac{sin\angle{BAD}}{sin\angle{CAD}}=\frac{AC.BD}{AB.CD}=\frac{tan(b)}{tan(a)}.\frac{sin(2a)}{sin(2b)}=(\frac{cos(a)}{cos(b)})^2(2)$.
$(1)(2)\implies \frac{sin\angle{BAD}}{sin\angle{CAD}}=\frac{sin\angle{CLX}}{sin\angle{XLB}},(\angle{BAD}+\angle{CAD}=\angle{CLX}+\angle{BLX})\implies \angle{CAX}=\angle{CLX}=\angle{BAD}$.
So we are done.
Source: https://artofproblemsolving.com/community/c6h590555p3497371