Let $S_r=x^r+y^r+z^r$ with $x,y,z$ real. It is known that if $S_1=0$,
$(*)$ $\frac{S_{m+n}}{m+n}=\frac{S_m}{m}\frac{S_n}{n}$
for $(m,n)=(2,3),(3,2),(2,5)$, or $(5,2)$. Determine all other pairs of integers $(m,n)$ if any, so that $(*)$ holds for all real numbers $x,y,z$ such that $x+y+z=0$.

Claim Both $m,n$ can not be even.
Proof
$x+y+z=0$ ,$\implies x=-(y+z)$.
Since $\frac{S_{m+n}}{m+n} = \frac{S_m S_n}{mn}$,
by equating cofficient of $y^{m+n}$ on LHS and RHS ,get
$\frac{2}{m+n}=\frac{4}{mn}$.
$\implies  \frac{m}{2} + \frac {n}{2} = \frac{m\cdot n}{2\cdot2}$.
So we have, $\frac{m}{2} \biggm{|} \frac{n}{2}$ and $\frac{n}{2} \biggm{|} \frac{m}{2}$.
$\implies m=n=4$.
So we have $S_8=2(S_4)^2$.
Now since it will true for all real $x,y,z,x+y+z=0$.
So choose $x=1,y=-1,z=0$.
$S_8=2$ and $S_4=2$ so $S_8 \neq 2 S_4^2$.
This is contradiction. So, at least one of $m,n$ must be odd. WLOG assume $n$ is odd and m is even. The coefficient of $y^{m+n-1}$ in $\frac{S_{m+n}}{m+n}$ is $\frac{\binom{m+n}{1} }{m+n} =1$
The coefficient of $y^{m+n-1}$ in $\frac{S_m\cdot S_n}{m\cdot n}$ is $\frac{2}{m}$.
Therefore, $\boxed{m=2}$.
Now choose $x=y=\frac1,z=(-2)$. (sic)
Since $\frac{S_{n+2}}{2+n}=\frac{S_2}{2}\frac{S_n}{n}$ holds for all real $x,y,z$ such that $x+y+z=0$.
We have $\frac{2^{n+2}-2}{n+2} = 3\cdot\frac{2^n-2}{n}$. Therefore,
\begin{equation*}
\label{eq:l2}
\frac{2^{n+1}-1}{n+2} =3\cdot\frac{2^{n-1}-1}{n}\ldots
\tag{**}
\end{equation*}
Clearly $(\ref{eq:l2})$ holds for $n\in\{5,3\}$.
And one can say that for $n\ge 6$,
$\text{RHS of (\ref{eq:l2})}<\text{LHS of (\ref{eq:l2})}$.
So our answer is $(m,n)=(5,2),(2,5),(3,2),(2,3)$.
-ftheftics (edited by integralarefun)


If a point $A_1$ is in the interior of an equilateral triangle $ABC$ and point $A_2$ is in the interior of $\triangle{A_1BC}$, prove that
$I.Q. (A_1BC) > I.Q.(A_2BC)$,
where the isoperimetric quotient of a figure $F$ is defined by
$I.Q.(F) = \frac{\text{Area (F)}}{\text{[Perimeter (F)]}^2}$

Solution:
First, an arbitrary triangle $ABC$ has isoperimetric quotient (using the notation $[ABC]$ for area and $s = \frac{a + b + c}{2}$):
Lemma. $\tan x \tan (A - x)$ is increasing on $0 < x < \frac{A}{2}$, where $0 < A < 90^\circ$.
Proof.
 is increasing on the desired interval, because $\cos (A - 2x)$ is increasing on $0 < x < \frac{A}{2}.$
Let $x_1, y_1, z_1$ and $x_2, y_2, z_2$ be half of the angles of triangles $A_1 BC$ and $A_2 BC$ in that order, respectively. Then it is immediate that $30^\circ > y_1 > y_2$, $30^\circ > z_1 > z_2$, and $x_1 + y_1 + z_1 = x_2 + y_2 + z_2 = 90^\circ$. Hence, by Lemma it follows that

Multiplying this inequality by $\frac{1}{4}$ gives that $I.Q[A_1 BC] > I.Q[A_2 BC]$, as desired.


Prove that there exists a positive integer $k$ such that $k\cdot2^n+1$ is composite for every integer $n$.

Solution:
Indeed, $\boxed{k=2935363331541925531}$ has the requisite property.
To see why, consider the primes $3,\ 5,\ 17,\ 257,\ 65537,\ 6700417,\ 641$, and observe that
Moreover,
We conclude that
And $k>>3,5,17,257,65537,6700417,641$ so the relevant values will, in fact, always be composite. $\blacksquare$


$A,B$, and $C$ are three interior points of a sphere $S$ such that $AB$ and $AC$ are perpendicular to the diameter of $S$ through $A$, and so that two spheres can be constructed through $A$, $B$, and $C$ which are both tangent to $S$. Prove that the sum of their radii is equal to the radius of $S$.

Solution:
Let the two tangent spheres be $S_1$ and $S_2$, and let $O, O_1, O_2$ and $R, R_1, R_2$ be the origins and radii of $S, S_1, S_2$ respectively. Then $AO$ stands normal to the plane $P$ through $\Delta ABC$. Because both spheres go through $A$, $B$, and $C$, the line $O_1 O_2$ also stands normal to $P$, meaning $AO$ and $O_1 O_2$ are both coplanar and parallel. Therefore the problem can be flattened to the plane $P'$ through $A$, $O$, $O_1$ and $O_2$.
Let $X, Y, Z, M, N$ be points on $P'$ such that $X = S \cap O O_1,  \quad Y = S_1 \cap S_2 \neq A,  \quad   Z = S \cap O O_2,   \quad  M = O_1 Y \cap AO,    \quad N = O_2 Y \cap AO$
Let $J$ be the three circles radical center, meaning $JX$ and $JZ$ are tangent segments to $S$ and $J \in AY$.
Because  $Y \in P \iff \angle NAY = \angle YAM = 90 ^{\circ},$ we have that $\overline{YN}$ and $\overline{YM}$ are diameters.
This means that $\angle OZN = \angle ZNY = \angle JZY$ and $\angle MXO = \angle YMX= \angle YXJ$.
And because $\angle ZNO = 180^{\circ} - \angle AYZ = \angle ZYJ$ and $\angle OMX = 180^{\circ} -\angle XYA = \angle JYX,$ we have that $\Delta JZY \sim \Delta OZN$ and $\Delta JYX \sim \Delta OMX$.
We then conclude that $\overline{OM} = \overline{OX} \enspace \frac {\overline{JY} }{ \overline{JX}}  = \overline{OZ} \enspace \frac {\overline{JY} }{ \overline{JZ}}  = \overline{ON}$
Let $a \top b$ denote line $a$ bisecting line segment $b$.
Since $O_1 O_2 || MN$ it follows that $OY \, \top \, \overline{MN} \Rightarrow OY \, \top \,  \overline{O_1 O_2}$.
Similarly we have that $O_1 O_2 \, \top \, \overline{YM} \Rightarrow O_1 O_2 \, \top \,  \overline{OY}$.
And so $O_1 O O_2 Y$ is a parallelogram because $\overline{OY}$ and $\overline{O_1 O_2}$ bisect each other, meaning $R = \overline{OZ} = \overline{O O_2} + \overline{O_2 Z} = \overline{O_1 Y}+ R_2 = R_1 + R_2$
$Quod \enspace Erat \enspace Demonstrandum$


On a given circle, six points $A$, $B$, $C$, $D$, $E$, and $F$ are chosen at random, independently and uniformly with respect to arc length. Determine the probability that the two triangles $ABC$ and $DEF$ are disjoint, i.e., have no common points.

Solution:
First we give the circle an orientation (e.g., letting the circle be the unit circle in polar coordinates).  Then, for any set of six points chosen on the circle, there are exactly $6!$ ways to label them one through six. Also, this does not affect the probability we wish to calculate. This will, however, make calculations easier.
Note that, for any unordered set of six points chosen from the circle boundary, the number of ways to number them such that they satisfy this disjoint-triangle property is constant: there are six ways to choose which triangle will be numbered with the numbers one through three, and there are $(3!)^2$ ways to arrange the numbers one through three and four through six on these two triangles. Therefore, for any given configuration of points, there are $6^3=216$ ways to label them to have this disjoint-triangle property. There are, however, $6!=720$ ways to label the points in all, so given any six unordered points, the probability that when we inflict an ordering we produce the disjoint-triangle property is $216/720=3/10$.
Since this probability is constant for any configuration of six unordered points we choose, we must have that $3/10$ is the probability that we produce the disjoint-triangle property if we choose the points as detailed in the problem statement.


Prove that the zeros of

cannot all be real if $2a^2<5b$.

Solution:
We prove the contrapositive: if the polynomial in question has the five real roots $x_1, x_2, x_3, x_4, x_5$, then $5b \le 2a^2$.
Because $a = -(x_1 + x_2 + x_3 + x_4 + x_5)$ and $b = x_1x_2 + x_1x_3 + ... + x_4x_5$ by Vieta's Formulae, we have
(by Cauchy-Schwarz)
so $5b \le 2a^2$, as desired.

Lemma:
For all real numbers $x_1,x_2,\cdots x_5$,

By the trivial inequality,

Making such an inequality for all the variable pairs and summing them, we find the lemma is true.
Now, let our roots be $x_1,x_2,\cdots,x_5$. By Vieta's, $a=x_1+x_2+\cdots+x_5$ and $b=x_1x_2+x_1x_3+\cdots+x_4x_5$
If we show that for all real $x_1,x_2,\cdots, x_5$ that $2a^2\ge 5b$, then we have a contradiction and all of $x_1,x_2,\cdots, x_5$ cannot be real. We start by rewriting $2a^2\ge 5b$ as

We divide by $2$ and find

Expanding the LHS, we have

We subtract the sum in brackets, and then multiply by $2$ to find

which is true by our lemma.


Each set of a finite family of subsets of a line is a union of two closed intervals. Moreover, any three of the sets of the family have a point in common. Prove that there is a point which is common to at least half the sets of the family.

Solution:
Let us first see that this works for anything less than three sets.
Obviously, due to the second condition given, they all share at least one point in common.
Now, let us see that it works for three or more sets.
First, take any three of the subsets in the family of sets.
Let them be A, B, and C.
We know that they share at least one point in common. Let us take the pair of segments that have the shortest length when you take the union of the pair. Let us denote this segment D. Evidently, if you take any other set of points, it must intersect D at least at one point. In order to minimize the number of intersections between the other varying segments, we must have at close to 1/2 of the remaining segments as possible intersecting each other. However, if we note, putting them that way forces at least 1/2 of the segments in each section.


Six segments $S_1, S_2, S_3, S_4, S_5,$ and $S_6$ are given in a plane. These are congruent to the edges $AB, AC, AD, BC, BD,$ and $CD$, respectively, of a tetrahedron $ABCD$. Show how to construct a segment congruent to the altitude of the tetrahedron from vertex $A$ with straight-edge and compasses.

Solution:
Throughout this solution, we denote the length of a segment $S$ by $|S|$.
In this solution, we employ several lemmas. Two we shall take for granted: given any point $A$ and a line $\ell$ not passing through $A$, we can construct a line $\ell'$ through $A$ parallel to $\ell$; and given any point $A$ on a line $\ell$, we can construct a line $\ell'$ through $A$ perpendicular to $\ell$.
Lemma 1: If we have two segments $S$ and $T$ on the plane with non-zero length, we may construct a circle at either endpoint of $S$ whose radius is $|T|$.
Proof: We can construct arbitrarily many copies of $T$ by drawing a circle about one of its endpoints through its other endpoint, and then connecting the center of this circle with any other point on the circle. We can construct copies of $T$ like this until we create a circle of radius $|T|$ and center $P_1$ that intersects segment $S$. We can then take this intersection point $P_2$ and draw a line $\ell$ through it perpendicular to $S$, and draw a circle with center $P_2$ passing through $P_1$, and consider its intersection $P_3$ with $\ell$. Note that $P_2P_3\perp S$ and $|P_2P_3|=|T|$. Take an endpoint $P_4$ of $S$: then draw a line through $P_3$ parallel to $S$, and a line through $P_4$ parallel to $P_2P_3$. Let these two lines intersect at $P_5$. Then $P_2P_3P_5P_4$ is a rectangle, so $|P_4P_5|=|T|$. Our desired circle is then a circle centered at $P_4$ through $P_5$.
Lemma 2: Given three collinear points $A$, $B$, $C$ in this order, if $|AB|=a$ and $|BC|=b$ with $a>b$, then we can construct a segment of length $\sqrt{a^2-b^2}$.
Proof: From Lemma 1, we can construct a circle through $C$ with radius $a$, and then construct a perpendicular through $B$ to $AC$: these two objects intersect at $D$ and $E$. Both $BD$ and $DE$ have length $\sqrt{a^2-b^2}$, from the Pythagorean Theorem.
Proof of the original statement: Note that we can construct a triangle $B'C'D'$ congruent to triangle $BCD$ by applying Lemma 1 to segments $S_4$, $S_5$, and $S_6$. Similarly, we can construct $A_B$ and $A_C$ outside triangle $B'C'D'$ such that $A_BC'D'\cong ACD$ and $A_CB'D'\cong ABD$.
Let $A'$ be a point outside of the plane containing $S_1$ through $S_6$ such that $A'B'C'D'\cong ABCD$. Then the altitudes of triangles $A_BC'D'$ and $A'C'D'$ to segment $C'D'$ are congruent, as are the altitudes of triangles $A_CB'D'$ and $A'B'D'$ to segment $B'D'$. However, if we project the altitudes of $A'C'D'$ and $A'B'D'$ from $A'$ onto the plane, their intersection is the base of the altitude of tetrahedron $A'B'C'D'$ from $A'$. In addition, these altitude projections are collinear with the altitudes of triangles $A_BC'D'$ and $A_CB'D'$. Therefore, the altitudes of $A_BC'D'$ and $A_CB'D'$ from $A_B$ and $A_C$ intersect at the base $X'$ of the altitude of $A'B'C'D'$ from $A'$. In summary, we can construct $X'$ by constructing the perpendiculars from $A_B$ and $A_C$ to $C'D'$ and $B'D'$ respectively, and taking their intersection.
Let $Y'$ be the intersection of $A_BX'$ with $C'D'$. Then the altitude length we seek to construct is, from the Pythagorean Theorem, $\sqrt{|A_BY'|^2-|X'Y'|^2}$. We can directly apply Lemma 2 to segment $A_BY'X'$ to obtain this segment. This shows how to construct a segment of length $A'X'$.


Consider an open interval of length $1/n$ on the real number line, where $n$ is a positive integer. Prove that the number of irreducible fractions $p/q$, with $1\le q\le n$, contained in the given interval is at most $(n+1)/2$.

Solution:
Let $I$ be an open interval of length $1/n$ and $F_n$ the set of fractions $p/q\in I$ with $p,q\in\mathbb{Z}$, $\gcd(p,q)=1$ and $1\leq q\leq n$.
Assume that $\frac{p}{q}\in F_n$. If $k\in\mathbb{Z}$ is such that $1\leq kq\leq n$, and $p'\in\mathbb{Z}$ is such that $\gcd(p',kq)=1$, then

Therefore $\frac{p'}{kq}\notin I\supset F_n$. This means that $\frac{p}{q}$ is the only fraction in $F_n$ with denominator $q$ or multiple of $q$.
Therefore, from each of the pairs in $P=\left\{(k,2k):\ 1\leq k\leq \left\lfloor\frac{n+1}{2}\right\rfloor\right\}$ at most one element from each can be a denominator of a fraction in $F_n$.
Hence $|F_n|\leq |P|\leq\frac{n+1}{2}$


In the polynomial $x^4 - 18x^3 + kx^2 + 200x - 1984 = 0$, the product of $2$ of its roots is $- 32$. Find $k$.

Using Vieta's formulas, we have:

From the last of these equations, we see that $cd = \frac{abcd}{ab} = \frac{-1984}{-32} = 62$. Thus, the second equation becomes $-32+ac+ad+bc+bd+62=k$, and so $ac+ad+bc+bd=k-30$. The key insight is now to factor the left-hand side as a product of two binomials: $(a+b)(c+d)=k-30$, so that we now only need to determine $a+b$ and $c+d$ rather than all four of $a,b,c,d$.
Let $p=a+b$ and $q=c+d$. Plugging our known values for $ab$ and $cd$ into the third Vieta equation, $-200 = abc+abd + acd + bcd = ab(c+d) + cd(a+b)$, we have $-200 = -32(c+d) + 62(a+b) = 62p-32q$. Moreover, the first Vieta equation, $a+b+c+d=18$, gives $p+q=18$. Thus we have two linear equations in $p$ and $q$, which we solve to obtain $p=4$ and $q=14$.
Therefore, we have $(\underbrace{a+b}_4)(\underbrace{c+d}_{14}) = k-30$, yielding $k=4\cdot 14+30 = \boxed{86}$.

We start as before: $ab=-32$ and $cd=62$. We now observe that a and b must be the roots of a quadratic, $x^2+rx-32$, where r is a constant (secretly, r is just -(a+b)=-p from Solution #1). Similarly, c and d must be the roots of a quadratic $x^2+sx+62$.
Now

Equating the coefficients of $x^3$ and $x$ with their known values, we are left with essentially the same linear equations as in Solution #1, which we solve in the same way. Then we compute the coefficient of $x^2$ and get $k=\boxed{86}.$

Let the roots of the equation be $a,b,c,$ and $d$. By Vieta's,

Since $abcd=-1984$ and $ab=-32$, then, $cd=62$. Notice thatcan be factored intoFrom the first equation, $c+d=18-a-b$. Substituting it back into the equation,Expanding,So, $a+b=4$ and $c+d=14$. Notice thatPlugging all our values in,
~ kante314


The geometric mean of any set of $m$ non-negative numbers is the $m$-th root of their product.
$\quad (\text{i})\quad$ For which positive integers $n$ is there a finite set $S_n$ of $n$ distinct positive integers such that the geometric mean of any subset of $S_n$ is an integer?
$\quad (\text{ii})\quad$ Is there an infinite set $S$ of distinct positive integers such that the geometric mean of any finite subset of $S$ is an integer?

Solution:
a) We claim that for any numbers $p_1$, $p_2$, ... $p_n$, $p_1^{n!}, p_2^{n!}, ... p_n^{n!}$ will satisfy the condition, which holds for any number $n$.
Since $\sqrt[n] ab = \sqrt[n] a * \sqrt[n] b$, we can separate each geometric mean into the product of parts, where each part is the $k$th root of each member of the subset and the subset has $k$ members.
Assume our subset has $k$ members. Then, we know that the $k$th root of each of these members is an integer (namely $p^{n!/k}$), because $k \leq n$ and thus $k  |  n!$. Since each root is an integer, the geometric mean will also be an integer.
b) If we define $q$ as an arbitrarily large number, and $x$ and $y$ as numbers in set $S$, we know that ${\sqrt[q]{\frac{x}{y}}}$ is irrational for large enough $q$, meaning that it cannot be expressed as the fraction of two integers. However, both the geometric mean of the set of $x$ and $q-1$ other arbitrary numbers in $S$ and the set of $y$ and the same other $q-1$ numbers are integers, so since the other numbers cancel out, the geometric means divided, or ${\sqrt[q]{\frac{x}{y}}}$, must be rational. This is a contradiction, so no such infinite $S$ is possible.
-aops111 (first solution dont bully me)

(i) The solution is the same as in the first solution
(ii)
Let $p$ and $q$ be some prime numbers, and let $v_p(n)$ be the largest number such that $p^{v_p(n)}$ divides $n$. $v_p(n)$ is also the exponent of $p$ in the prime factorization of $n$ (or $0$, if $p$ isn't a divisor of $n$). Then, because $S$ is infinite, we can choose $q-1$ numbers $a_1, a_2, ... a_{q-1}$ in $S$ such that $v_p(a_i)$ all give the same remainder when divided by $q$. (Otherwise, because $v_p(n) \mod q$ has $q$ distinct values, $S$ could contain at most $q(p-2)$ numbers, which is finite.) Call that remainder $r$.
Now take some integer $b$ in $S$, not part of the other $q-1$ values. Together, their product must be a $q$th power, meaning
$q|v_p(a_1a_2...a_{q-1}b)$ Thus, $v_p(a_1a_2...a_{q-1}b) \equiv 0 \pmod q$. It can be seen easily that for two positive integers $x$ and $y$ we have $v_p(ab) = v_p(a) + v_p(b)$, and by definition $v_p(a_i) \equiv r \pmod q$, so we can write $v_p(b) + (q-1)r \equiv 0 \pmod q$. Adding $r$ to both sides we have $v_p(b) \equiv v_p(b) + qr \equiv r \pmod q$.
The choice of $b$ was arbitrary, meaning for all numbers $n$ in $S$, $v_p(n)$ modulo $q$ is the constant $r$, whether part of $a_1, a_2... a_{q-1}$ or not. The choice of $q$ was also arbitrary, thus for two integers $m$ and $n$ in $S$, $v_p(m) = v_p(n)$. Otherwise, we could pick $q$ larger than both values, and get a contradiction. Thus for all  numbers $n$ in $S$, $v_p(n)$ is constant. The choice of $p$ was also arbitrary, meaning any two distinct numbers in $S$ have the same prime factorization. By the fundamental theorem of arithmetic, this means the two numbers are the same, contradicting with them being distinct. Thus, no such $S$ exists.
-Circling


$P$, $A$, $B$, $C$, and $D$ are five distinct points in space such that $\angle APB = \angle BPC = \angle CPD = \angle DPA = \theta$, where $\theta$ is a given acute angle. Determine the greatest and least values of $\angle APC + \angle BPD$.

Solution:
Greatest value is achieved when all the points are as close as possible to all being on a plane.
Since $\theta < \frac{\pi}{2}$, then $\angle APC + \angle BPD < \pi$
Smallest value is achieved when point P is above and the remaining points are as close as possible to colinear when $\theta > 0$, then $\angle APC + \angle BPD > 0$
and the inequality for this problem is:
$0 < \angle APC + \angle BPD < \pi$
~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.


A difficult mathematical competition consisted of a Part I and a Part II with a combined total of $28$ problems. Each contestant solved $7$ problems altogether. For each pair of problems, there were exactly two contestants who solved both of them. Prove that there was a contestant who, in Part I, solved either no problems or at least four problems.

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


$P(x)$ is a polynomial of degree $3n$ such that

Determine $n$.

Solution:
By Lagrange Interpolation Formula $f(x) = 2\sum_{p=0}^{n}\left ( \prod_{0\leq r\neq3p\leq 3n}^{{}}\frac{x-r}{3p-r} \right )+ \sum_{p=1}^{n}\left ( \prod_{0\leq r\neq3p-2\leq 3n}^{{}} \frac{x-r}{3p-2-r}\right )$
and hence $f(3n+1) = 2\sum_{p=0}^{n}\left ( \prod_{0\leq r\neq3p\leq 3n}^{{}}\frac{3n+1-r}{3p-r} \right )+ \sum_{p=1}^{n}\left ( \prod_{0\leq r\neq3p-2\leq 3n}^{{}} \frac{3n+1-r}{3p-2-r}\right )$
after some calculations we get $f(3n+1) =\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )+1$
Given $f(3n+1)= 730$ so we have to find $n$ such that $\left ( \binom{3n+1}{0}- \binom{3n+1}{3}+\binom{3n+1}{6}- ... \right )\left ( 2.(-1)^{3n}-1 \right )= 729$
Lemma: If $p$ is even  $\binom{p}{0}- \binom{p}{3}+ \binom{p}{6}- \cdots = \frac{2^{p+1}sin^{p}\left ( \frac{\pi}{3} \right )(i)^{p}\left ( cos\left ( \frac{p\pi}{3} \right ) \right )}{3}$
and if  $p$ is odd  $\binom{p}{0}- \binom{p}{3}+ \binom{p}{6}- \cdots = \frac{-2^{p+1}sin^{p}\left ( \frac{\pi}{3} \right )(i)^{p+1}\left ( sin\left ( \frac{p\pi}{3} \right ) \right )}{3}$
$i$ is $\sqrt{-1}$
Using above lemmas we do not get any solution when $n$ is odd, but when $n$ is even $3n+1=13$ satisfies the required condition, hence $n=4$


Determine whether or not there are any positive integral solutions of the simultaneous equations

with distinct integers $x_1,x_2,\cdots,x_{1985}$.

Solution:
Lemma: For a positive integer $n$, $1^3+2^3+\cdots +n^3 = (1+2+\cdots +n)^2$ (Also known as Nicomachus's theorem)
Proof by induction: The identity holds for $1$. Suppose the identity holds for a number $n$. It is well known that the sum of first $n$ positive integers is $\frac{n(n+1)}{2} = \frac{n^2+n}{2}$. Thus its square is $\frac{n^4+2n^3+n^2}{4}$. Adding $(n+1)^3=n^3+3n^2+3n+1$ to this we get $\frac{n^4+6n^3+13n^2+12n+4}{4}$, which can be rewritten as $\frac{(n^4+4n^3+6n^2+4n+1)+2(n^3+3n^2+3n+1)+(n^2+2n+1)}{4}$ This simplifies to $\frac{(n+1)^4+2(n+1)^3+(n+1)^2}{4} = ({\frac{(n+1)^2+(n+1)}{2}})^2 = (1+2+\cdots +n+(n+1))^2$. The induction is complete.
Let $j$ be the sum $1+2+\cdots 1985$, and let $k$ be the sum $1^2 + 2^2 + \cdots + 1985^2$. Then assign $x_i$ the value $ik^4$ for each $i = 1, 2,\cdots 1985$. Then:
Thus, a positive integral solution exists.
-Circling


Determine each real root of
$x^4-(2\cdot10^{10}+1)x^2-x+10^{20}+10^{10}-1=0$
correct to four decimal places.

Solution:
The equation can be re-written as
We first prove that the equation has no negative roots.
Let $x\le 0.$ The equation above can be further re-arranged as

The right hand side of the equation is negative. Therefore  and we have
$-1<(x+10^5)(x-10^5) <2.$ Then the left hand side of the equation is bounded by

However, since $|(x+10^5)(x-10^5)|\le 2$ and $x<0,$ it follows that $|x+10^5| <\frac{2}{|x-10^5|}<2\times 10^{-5}$ for negative $x.$ Then $x<2\times 10^{-5}-10^5.$ The right hand side of the equation is then a large negative number. It cannot be equal to the left hand side which is bounded by 9.
Now let $x>0.$ When $x=10^5,$ the left hand side of equation (1) is negative. Therefore the equation has real roots on both side of $10^5$, as its leading coefficient is positive. We will prove that $x=10^5$ is a good approximation of the roots (within $10^{-2}$). In fact, we can solve the "quadratic" equation (1) for $(x+10^5)(x-10^5)$:

Then
Easy to see that
$|x-10^5| <1$ for positve $x.$ Therefore, $10^5-1<x<10^5+1.$ Then
Let $x_1$ be a root of the equation with $x_1<10^5.$ Then $0<10^5-x_1<10^{-2}$ and

An aproximation of $x_1$ is defined as follows:

We check the error of the estimate:
The first absolute value
The second absolute value

through a rationalized numerator.Therefore $|\tilde{x}_1-x_1|\le 10^{-6}.$
For a real root $x_2$ with $x_2>10^5,$ we choose

We can similarly prove it has the desired approximation.


Let $A,B,C,D$ denote four points in space such that at most one of the distances $AB,AC,AD,BC,BD,CD$ is greater than $1$. Determine the maximum value of the sum of the six distances.

Solution:
Suppose that $AB$ is the length that is more than $1$. Let spheres with radius $1$ around $A$ and $B$ be $S_A$ and $S_B$. $C$ and $D$ must be in the intersection of these spheres, and they must be on the circle created by the intersection to maximize the distance. We have $AC + BC + AD + BD = 4$.
In fact, $CD$ must be a diameter of the circle. This maximizes the five lengths $AC$, $BC$, $AD$, $BD$, and $CD$. Thus, quadrilateral $ACBD$ is a rhombus.
Suppose that $\angle CAD = 2\theta$. Then, $AB + CD = 2\sin{\theta} + 2\cos{\theta}$. To maximize this, we must maximize $\sin{\theta} + \cos{\theta}$ on the range $0^{\circ}$ to $90^{\circ}$. However, note that we really only have to solve this problem on the range $0^{\circ}$ to $45^{\circ}$, since $\theta > 45$ is just a symmetrical function.
For $\theta < 45$, $\sin{\theta} \leq \cos{\theta}$. We know that the derivative of $\sin{\theta}$ is $\cos{\theta}$, and the derivative of $\cos{\theta}$ is $-\sin{\theta}$. Thus, the derivative of $\sin{\theta} + \cos{\theta}$ is $\cos{\theta} - \sin{\theta}$, which is nonnegative between $0^{\circ}$ and $45^{\circ}$. Thus, we can conclude that this is an increasing function on this range.
It must be true that $2\sin{\theta} \leq 1$, so $\theta \leq 30^{\circ}$. But, because $\sin{\theta} + \cos{\theta}$ is increasing, it is maximized at $\theta = 30^{\circ}$. Thus, $AB = \sqrt{3}$, $CD = 1$, and our sum is $5 + \sqrt{3}$.
~mathboy100


There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor -1$ of them, each of whom knows both or else  knows neither of the two. Assume that "know" is a symmetrical relation; $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$.


Let $a_1,a_2,a_3,\cdots$ be a non-decreasing sequence of positive integers. For $m\ge1$, define $b_m=\min\{n: a_n \ge m\}$, that is, $b_m$ is the minimum value of $n$ such that $a_n\ge m$. If $a_{19}=85$, determine the maximum value of $a_1+a_2+\cdots+a_{19}+b_1+b_2+\cdots+b_{85}$.

Solution:
We create an array of dots like so: the array shall go out infinitely to the right and downwards, and at the top of the $i$th column we fill the first $a_i$ cells with one dot each. Then the $19$th row shall have 85 dots. Now consider the first 19 columns of this array, and consider the first 85 rows. In row $j$, we see that the number of blank cells is equal to $b_j-1$. Therefore the number of filled cells in the first 19 columns of row $j$ is equal to $20-b_j$.
We now count the number of cells in the first 19 columns of our array, but we do it in two different ways. First, we can sum the number of dots in each column: this is simply $a_1+\cdots+a_{19}$. Alternatively, we can sum the number of dots in each row: this is $(20-b_1)+\cdots +(20-b_{85})$. Since we have counted the same number in two different ways, these two sums must be equal. Therefore

Note that this shows that the value of the desired sum is constant.


$(\text{a})$ Do there exist 14 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 11$?
$(\text{b})$ Do there exist 21 consecutive positive integers each of which is divisible by one or more primes $p$ from the interval $2\le p \le 13$?

Solution:
(a)     To solve part (a), we first note that for any 14 consecutive positive integers, exactly 7 are even (divisible by 2) and therefore satisfy the criteria. We can remove these from the problem, and simplify it to the following question, which is equivalent to part (a):
"Do there exist 7 consecutive positive odd integers each of which is divisible by one or more primes $p$ from the interval $3\le p \le 11$?"
Among any 7 consecutive positive odd integers, the following holds:

For every one of these seven integers to be divisible by one of 3, 5, 7, or 11, there must be 3 multiples of 3, 2 multiples of 5, 1 multiple of 7, and 1 multiple of 11. Additionally, none of these integers may be a multiple of any two of the four aforementioned primes. Otherwise, the Pigeonhole Principle dictates that at least one integer is not divisible by any of the four, thus failing to meet the criteria. But this cannot be. Calling the consecutive odd integers $a_1, a_2, \dots, a_7$, we note that $a_1$, $a_4$, and $a_7$ must be multiples of 3, and therefore cannot be multiples of 5, 7, or 11. But for there to be two multiples of 5, they must be one of the two pairs $(a_1,a_6)$ and $(a_2,a_7)$. But each of these pairs contains a multiple of 3, and so at least one of the 7 odd integers is divisible by none of the primes 3, 5, 7, or 11. Therefore the answer to part (a) is no.
(b)    To solve part (b), we use a strategy similar to the one used in part (a), reducing part (b) to this equivalent question:
"Do there exist 10 consecutive positive odd integers each of which is divisible by one or more primes $p$ from the interval $3\le p \le 13$?"
(We will ignore the case where the first of the 21 integers is odd, resulting in 11 odd integers instead of 10, as it is only true if the weaker, 10-integer argument is also true.)
Among any 10 consecutive positive odd integers, the following holds:

For every one of these ten integers to be divisible by one of 3, 5, 7, 11, or 13, there must be 4 multiples of 3, 2 multiples of 5, 2 multiples of 7, 1 multiple of 11, and 1 multiple of 13. As before, none of these integers may be a multiple of any two of the five primes. Calling the consecutive odd integers $a_1, a_2, \dots, a_{10}$, we note that $a_1$, $a_4$, $a_7$, and $a_{10}$ must be multiples of 3, and therefore cannot be multiples of 5, 7, 11, or 13. Unlike part (a), however, this stipulation is not a dead end. Let the multiples of 5 be $a_3$ and $a_8$ and let the multiples of 7 be $a_2$ and $a_9$. The multiples of 11 and 13 are $a_5$ and $a_6$, in some order (it doesn't really matter which). An example of a sequence of 21 consecutive positive integers satisfying part (b) is the integers from 9440 to 9460 (inclusive), which can be obtained by solving modular equations that result from these statements. So the answer to part (b) is yes.


During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of mathematicians, there was some moment when both were asleep simultaneously. Prove that, at some moment, three of them were sleeping simultaneously.

Solution:
We shall assume to the contrary that there was never a time when three mathematicians were sleeping simultaneously, and derive a contradiction.
As a subtle but logically necessary note, we will assume without loss of generality that no two events (an event is one mathematician either falling asleep or waking up) happen at the same time.
We have (5 choose 2) = 10 sleeping-pairs of mathematicians to account for.  Also, since 5 mathematicians each fell asleep 2 times, we have a total of 10 occasions on which a mathematician fell asleep.  Now, if two mathematicians are ever asleep simultaneously, then one of them fell asleep while the other was already asleep.  However, because of the "no three asleep at once" rule, if a mathematician falls asleep, then at most one other mathematician could have been asleep already.  Therefore, each occasion when a mathematician falls asleep can account for at most one sleeping-pair.  It would appear that we have just enough to make it.  However, when the first mathematician falls asleep, no other mathematicians are asleep...
Hey, wait a minute.  Couldn't one mathematician, or even two, have been already asleep when the lecture started?  In fact, the wording of the problem does not forbid this, and this permits us to construct an easy counterexample:
Call the mathematicians A,B,C,D,E.  A starts out asleep.  B sleeps; A wakes; C sleeps; B wakes; D sleeps; C wakes; E sleeps; D wakes; A sleeps; E wakes; then, C sleeps; A wakes; E sleeps; C wakes; B sleeps; E wakes; D sleeps; B wakes; A sleeps; D wakes.  This creates, in order, the sleeping-pairs AB, BC, CD, DE, EA, then AC, CE, EB, BD, DA; each mathematician falls asleep and wakes up exactly twice, and at no time are three mathematicians asleep.
Well, this must be considered a hole in the problem as written.  However, if we add the (nontrivial) assumption that the mathematicians were all awake when the lecture began, then it follows that the first occasion when a mathematician falls asleep can only account for zero sleeping-pairs, and the remaining 9 occasions can only account for 9 of 10 sleeping-pairs, and so there must be some pair of mathematicians that are not simultaneously asleep during the lecture.  So our assumption to the contrary implies an impossible sequence of events.  Therefore, that assumption must be wrong, and there must be a moment when three mathematicians are asleep.


What is the smallest integer $n$, greater than one, for which the root-mean-square of the first $n$ positive integers is an integer?
$\mathbf{Note.}$ The root-mean-square of $n$ numbers $a_1, a_2, \cdots, a_n$ is defined to be

Solution:
Let's first obtain an algebraic expression for the root mean square of the first $n$ integers, which we denote $I_n$. By repeatedly using the identity
$(x+1)^3 = x^3 + 3x^2 + 3x + 1$, we can write

and
 We can continue this pattern indefinitely, and thus for any
positive integer $n$,

Since $\sum_{j=1}^n j  = n(n+1)/2$, we obtain

Therefore,

Requiring that $I_n$ be an integer, we find that
 where $k$ is an integer. Using the Euclidean algorithm, we see that
$\gcd(2n+1, n+1) = \gcd(n+1,n) = 1$, and so $2n+1$ and $n+1$ share no
factors greater than 1. The equation above thus implies that $2n+1$
and $n+1$ is each proportional to a perfect square. Since $2n+1$ is
odd, there are only two possible cases:
Case 1: $2n+1 = 3 a^2$ and $n+1 = 2b^2$, where $a$ and $b$ are integers.
Case 2: $2n+1 = a^2$ and $n+1 = 6b^2$.
In Case 1,  $2n+1 = 4b^2 -1 = 3a^2$. This means that $(4b^2 -1)/3 = a^2$ for some integers $a$ and $b$. We proceed by checking whether
$(4b^2-1)/3$ is a perfect square for $b=2, 3, 4, \dots$. (The solution
$b=1$ leads to $n=1$, and we are asked to find a value of $n$
greater than 1.) The smallest positive integer $b$ greater than 1 for
which $(4b^2-1)/3$ is a perfect square is $b=13$, which results in $n=337$.
In Case 2, $2n+1 = 12b^2 - 1 = a^2$. Note that $a^2 = 2n+1$ is an odd square, and hence is congruent to $1 \pmod 4$. But $12b^2 -1 \equiv 3 \pmod 4$ for any $b$, so Case 2 has no solutions.
Alternatively, one can proceed by checking whether $12b^2 -1$ is a perfect square for $b=1, 2 ,3 ,\dots$. We find that $12b^2 -1$ is not a perfect square for $b = 1,2, 3, ..., 7, 8$, and $n= 383$ when $b=8$. Thus the smallest positive integers $a$ and $b$ for which $12b^2- 1 = a^2$ result in a value of $n$ exceeding the value found in Case 1, which was 337.
In summary, the smallest value of $n$ greater than 1 for which $I_n$ is an integer is $\boxed{337}$.


Two distinct circles $K_1$ and $K_2$ are drawn in the plane. They intersect at points $A$ and $B$, where $AB$ is the diameter of $K_1$. A point $P$ on $K_2$ and inside $K_1$ is also given.
Using only a "T-square" (i.e. an instrument which can produce a straight line joining two points and the perpendicular to a line through a point on or off the line), find a construction for two points $C$ and $D$ on $K_1$ such that $CD$ is perpendicular to $AB$ and $\angle CPD$ is a right angle.


By a partition $\pi$ of an integer $n\ge 1,$ we mean here a representation of $n$ as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if $n=4,$ then the partitions $\pi$ are $1+1+1+1,$ $1+1+2,$ $1+3, 2+2,$ and $4$).
For any partition $\pi,$ define $A(\pi)$ to be the number of $1$'s which appear in $\pi,$ and define $B(\pi)$ to be the number of distinct integers which appear in $\pi$ (E.g., if $n=13$ and $\pi$ is the partition $1+1+2+2+2+5,$ then $A(\pi)=2$ and $B(\pi) = 3$).
Prove that, for any fixed $n,$ the sum of $A(\pi)$ over all partitions of $\pi$ of $n$ is equal to the sum of $B(\pi)$ over all partitions of $\pi$ of $n.$

Solution:
Let $S(n) = \sum\limits_{\pi} A(\pi)$ and let $T(n) = \sum\limits_{\pi} B(\pi).$ We will use generating functions to approach this problem -- specifically, we will show that the generating functions of $S(n)$ and $T(n)$ are equal.
Let us start by finding the generating function of $S(n).$ This function counts the total number of 1's in all the partitions of $n.$ Another way to count this is by counting the number of partitions of $n$ that contain $x$ 1's and multiplying this by $x,$ then summing for $1\leq x \leq n.$ However, the number of partitions of $n$ that contain $x$ 1's is the same as the number of partitions of $n-x$ that contain no 1's, so

The number of partitions of $m$ with no 1's is the coefficient of $x^m$ in

Note that there is no $(1+x+x^2+x^3+\ldots)$ term in $F(x)$ because we cannot have any 1's in the partition.
Let $c_m$ be the coefficient of $x^m$ in the expansion of $F(x),$ so we can rewrite it as $F(x)=c_0+c_1x+c_2x^2+c_3x^3+\ldots.$ We wish to compute $S(n)=1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0.$
Consider the power series $G(x)=(x+2x^2+3x^3+4x^4+\ldots)F(x).$

If we expand the first line, we see that the coefficient of $x^n$ in $G(x)$ for any $n$ is $1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0,$ which is exactly $S(n)$! So by definition, $G(x)=\frac{x}{1-x} \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}$ is the generating function of $S(n).$
Now let's find the generating function of $T(n).$ Notice that counting the number of distinct elements in each partition and summing over all partitions is equivalent to counting how many partitions of $n$ contain i and then summing for all $1\leq i \leq n.$
So,

However, the number of partitions of n that contain a $i$ is the same as the total number of partitions of $n-i,$ so
The generating function for the number of partitions is
Let's write the expansion of $P(x)$ as $P(x)=d_0+d_1x+d_2x^2+d_3x^3+\ldots,$ so we wish to find $T(n)=d_0+d_1+d_2+\ldots+d_{n-1}.$
Consider the power series $H(x)=(x+x^2+x^3+x^4+\ldots)P(x).$

If we expand the first line, we see that the coefficient of $x^n$ in $H(x)$ for any $n$ is $d_{n-1}+d_{n-2}+\ldots+d_0,$ which is precisely $T(n).$ This means $H(x)$ is the generating function of $T(n).$
Thus, the generating functions of $S(n)$ and $T(n)$ are the same, so $S(n)=T(n)$ for all $n$ and we are done.
~Peggy


Find all solutions to $(m^2+n)(m + n^2)= (m - n)^3$, where m and n are non-zero integers.

Solution:
Expanding both sides,
Note that $m^3$ can be canceled and as $n \neq 0$, $n$ can be factored out.
Writing this as a quadratic equation in $n$: .
The discriminant $b^2-4ac$ equals
, which we want to be a perfect square.
Miraculously, this factors as $m(m-8)(m+1)^2$. This is square iff (if and only if) $m^2-8m$ is square or $m+1=0$. It can be checked that the only nonzero $m$ that work are $-1, 8, 9$. Finally, plugging this in and discarding extraneous roots gives all possible ordered pairs $(m, n)$ as .


The feet of the angle bisectors of $\Delta ABC$ form a right-angled triangle. If the right-angle is at $X$, where $AX$ is the bisector of $\angle A$, find all possible values for $\angle A$.


$X$ is the smallest set of polynomials $p(x)$ such that:
Show that if $r(x)$ and $s(x)$ are distinct elements of $X$, then $r(x) \neq s(x)$ for any $0 < x < 1$.

Solution:
Let $s(x)$ be an arbitrary polynomial in $X.$ Then $0<s(x)<1$ when $0<x<1.$ Define $X_1=\{s(x)\in X:s(x)=x\cdot s_1(x)$ for some $s_1(x)\in X\},$ and $X_2=\{t(x)\in X: t(x)=x+(1-x)t_1(x)$ for some $t_1(x)\in X\}.$
If $s(x) \in X_1$ and $t(x)\in X_2,$ we have $s(x) <x<t(x)$ for all $x$ with $0<x<1.$ Therefore $s(x)\ne t(x)$ for any $0<x<1.$
For any $s(x), t(x) \in X_1$, Let $s(x)=x\cdot s_1(x)$ and $t(x)=x\cdot t_1(x)$ for $s_1(x), t_1(x) \in X.$ If $s_1(x) \ne t_1(x)$ for $0<x<1,$ then
$s(x)-t(x)=x(s_1(x)-t_1(x))\ne 0$ for $0<x<1.$
Similarly, for any $s(x), t(x) \in X_2$, Let $s(x)=x+(1-x) s_1(x)$ and $t(x)=x+(1-x) t_1(x)$ for $s_1(x), t_1(x) \in X.$ If $s_1(x) \ne t_1(x)$ for $0<x<1,$ then
$s(x)-t(x)=(1-x)(s_1(x)-t_1(x))\ne 0$ for $0<x<1.$
The proof is done by an induction.
J.Z.


M is the midpoint of XY. The points P and Q lie on a line through Y on opposite sides of Y, such that $|XQ| = 2|MP|$ and $\frac{|XY|}2 < |MP| < \frac{3|XY|}2$. For what value of $\frac{|PY|}{|QY|}$ is $|PQ|$ a minimum?


$a_1, a_2, \cdots, a_n$ is a sequence of 0's and 1's. T is the number of triples $(a_i, a_j, a_k)$ with $i<j<k$ which are not equal to (0, 1, 0) or (1, 0, 1). For $1\le i\le n$, $f(i)$ is the number of $j<i$ with $a_j = a_i$ plus the number of $j>i$ with $a_j\neq a_i$. Show that $T=\sum_{i=1}^n f(i)\cdot\left(\frac{f(i)-1}2\right)$. If n is odd, what is the smallest value of T?


The repeating decimal $0.ab\cdots k\overline{pq\cdots u}=\frac mn$, where $m$ and $n$ are relatively prime integers, and there is at least one decimal before the repeating part. Show that $n$ is divisble by 2 or 5 (or both). (For example, $0.011\overline{36}=0.01136363636\cdots=\frac 1{88}$, and 88 is divisible by 2.)

First, split up the nonrepeating parts and the repeating parts of the decimal, so that the nonrepeating parts equal to $\frac{a}{b}$ and the repeating parts of the decimal is equal to $\frac{c}{d}$.
Suppose that the length of  $0.ab\cdots k$ is $p$ digits. Then $\frac{a}{b} = \frac{0.ab\cdots k}{10^{p+1}}$ Since $0.ab\cdots k < 10^{p+1}$, after reducing the fraction, there MUST be either a factor of 2 or 5 remaining in the denominator. After adding the fractions $\frac{a}{b}+\frac{c}{d}$, the simplified denominator $n$ will be $\\lcm(b,d)$ and since $b$ has a factor of $2$ or $5$,  $n$ must also have a factor of 2 or 5.
$\blacksquare$

It is well-known that $0.ab...k \overline{pq...u} = \frac{ab...u - ab...k}{99...900...0}$, where there are a number of 9s equal to the count of digits in $pq...u$, and there are a number of 0s equal to the count of digits $c$ in $ab...k$. Obviously $ab...k$ is different from $pq...u$ (which is itself the repeating part), so the numerator cannot have $c$ consecutive terminating zeros, and hence the denominator still possesses a factor of 2 or 5 not canceled out. This completes the proof.


The cubic polynomial $x^3+ax^2+bx+c$ has real coefficients and three real roots $r\ge s\ge t$. Show that $k=a^2-3b\ge 0$ and that $\sqrt k\le r-t$.

By Vieta's Formulas, $a=-r-s-t$, $b=rs+st+rt$, and $c=-rst$.
Now we know $k=a^2-3b$; in terms of r, s, and t, then,

Now notice that we can multiply both sides by 2, and rearrange terms to get
$2k=(r-s)^2+(s-t)^2+(r-t)^2$.
But since $r, s, t\in \mathbb{R}$, the three terms of the RHS are all non-negative (as the square of a real number is always non-negative), and therefore their sum is also non-negative -- that is, $2k\ge 0 \Rightarrow k\ge 0$.
Now, we will show that $\sqrt k\le r-t$.
We can square both sides, and the inequality will hold since they are both non-negative (it is given that $r\ge t$, therefore $r-t\ge 0$). This gives $k \le r^2-2rt+t^2$.
Now we already have $k=r^2+s^2+t^2-rs-st-rt$, so substituting this for k gives

Note that this is a quadratic. Since its leading coefficient is positive, its value is less than 0 when s is between the two roots. Using the quadratic formula:

The quadratic is 0 when s is equal to r or t, and the inequality
holds when its value is less than or equal to 0 -- that is, $r\ge s\ge t$.
(Its value is less than or equal to 0 when s is between the roots, since the
graph of the quadratic opens upward.)
In fact, the problem tells us this is true. Q.E.D.

From Vieta's Formula (which tells us that $a = -(r+s+t)$ and $b = rs + st + rt$), we have that

clearly non-negative. To prove $\sqrt{k} \le r - t$, it suffices to prove the square of this relation, or  This in turn simplifies to  or  which is clearly true as $r \ge s \ge t$. This completes the proof.

By Vieta's Formulas, $a = -(r+s+t)$ and $b = rs + st + rt$. $k = (r+s+t)^2 - 3(rs + st + rt) = r^2+s^2+t^2-rs-st-rt = \frac{(r-s)^2 + (s-t)^2 + (r-t)^2}{2}$.
To show that $k \ge 0$, simply note that by the trivial inequality, all three squares are greater than $0$ as they are the squares of real numbers.
To show that $\sqrt{k} \le r-t$, since both are positive, it is sufficient to show that $k \le (r-t)^2$. $\frac{(r-s)^2 + (s-t)^2 + (r-t)^2}{2} \le (r-t)^2$ implies that $k \le (r-t)^2$. $\frac{(r-s)^2 + (s-t)^2 - (r-t)^2}{2} \le 0$. Let $y = r-s$ and $z = s-t$. We then have $\frac{y^2 + z^2 - (y+z)^2}{2} \le 0 \implies -2yz \le 0$, which is clearly true as both $y$ and $z$ are positive.


Let $X$ be the set $\{ 1, 2, \cdots , 20\}$ and let $P$ be the set of all 9-element subsets of $X$. Show that for any map $f: P\mapsto X$ we can find a 10-element subset $Y$ of $X$, such that $f(Y-\{k\})\neq k$ for any $k$ in $Y$.


$\Delta ABC$ is a triangle with incenter $I$. Show that the circumcenters of $\Delta IAB$, $\Delta IBC$, and $\Delta ICA$ lie on a circle whose center is the circumcenter of $\Delta ABC$.

Let the circumcenters of $\Delta IAB$, $\Delta IBC$, and $\Delta ICA$ be $O_c$, $O_a$, and $O_b$, respectively. It then suffices to show that $A$, $B$, $C$, $O_a$, $O_b$, and $O_c$ are concyclic.
We shall prove that quadrilateral $ABO_aC$ is cyclic first. Let $\angle BAC=\alpha$, $\angle CBA=\beta$, and $\angle ACB=\gamma$. Then $\angle ICB=\gamma/2$ and $\angle IBC=\beta/2$. Therefore minor arc $\overarc{BIC}$ in the circumcircle of $IBC$ has a degree measure of $\beta+\gamma$. This shows that $\angle CO_aB=\beta+\gamma$, implying that $\angle BAC+\angle BO_aC=\alpha+\beta+\gamma=180^{\circ}$. Therefore quadrilateral $ABO_aC$ is cyclic.
This shows that point $O_a$ is on the circumcircle of $\Delta ABC$. Analagous proofs show that $O_b$ and $O_c$ are also on the circumcircle of $ABC$, which completes the proof. $\blacksquare$

Let $M$ denote the midpoint of arc $AC$. It is well known that $M$ is equidistant from $A$, $C$, and $I$ (to check, prove $\angle IAM = \angle AIM = \frac{\angle BAC + \angle ABC}{2}$), so that $M$ is the circumcenter of $AIC$. Similar results hold for $BIC$ and $CIA$, and hence $O_c$, $O_a$, and $O_b$ all lie on the circumcircle of $ABC$.

Extend $CI$ to point $L$ on $(ABC)$. By The Incenter-Excenter Lemma, B, I, A are all concyclic. Thus, L is the circumcenter of triangle $IAB$. In other words, $L=O_c$, so $O_c$ is on $(ABC)$. Similarly, we can show that $O_a$ and $O_b$ are on $(ABC)$, and thus, $A,B,C,O_a,O_b,O_c$ are all concyclic. It follows that the circumcenters are equal.

Let the centers be $T, R, S$. We want to show that $ABC$ and $TRS$ have the same circumcircle. By Fact 5 we know that $CATB$ lie on a circle and similarly with the others. Thus the two triangles have the same circumcircle.
~coolmath_2018


Let $p(x)$ be the polynomial $(1-x)^a(1-x^2)^b(1-x^3)^c\cdots(1-x^{32})^k$, where $a, b, \cdots, k$ are integers. When expanded in powers of $x$, the coefficient of $x^1$ is $-2$ and the coefficients of $x^2$, $x^3$, ..., $x^{32}$ are all zero. Find $k$.

First, note that if we reverse the order of the coefficients of each factor, then we will obtain a polynomial whose coefficients are exactly the coefficients of $p(x)$ in reverse order. Therefore, if

we define the polynomial $q(x)$ to be

noting that if the polynomial has degree $n$, then the coefficient of $x^{n-1}$ is $-2$, while the coefficients of $x^{n-k}$ for $k=2,3,\dots, 32$ are all $0$.
Let $P_n$ be the sum of the $n$th powers of the roots of $q(x)$. In particular, by Vieta's formulas, we know that $P_1=2$. Also, by Newton's Sums, as the coefficients of $x^{n-k}$ for $k=2,3,\dots,32$ are all $0$, we find that

Thus $P_n=2^n$ for $n=1,2,\dots, 32$. Now we compute $P_{32}$. Note that the roots of $(x^n-1)^{a_n}$ are all $n$th roots of unity. If $\omega=e^{2\pi i/n}$, then the sum of $32$nd powers of these roots will be

If $\omega^{32}\ne 1$, then we can multiply by $(\omega^{32}-1)/(\omega^{32}-1)$ to obtain

But as $\omega^n=1$, this is just $0$. Therefore the sum of the $32$nd powers of the roots of $q(x)$ is the same as the sum of the $32$nd powers of the roots of

The $32$nd power of each of these roots is just $1$, hence the sum of the $32$nd powers of the roots is

On the other hand, we can use the same logic to show that

Subtracting (2) from (1) and dividing by 32, we find

Therefore, $a_{32}=2^{27}-2^{11}$.

By a limiting process, we can extend the problem to that of finding a sequence $b_1, b_2, \ldots$ of integers such that

(The notation comes from the Alcumus version of this problem.)
If we take logarithmic derivatives on both sides, we get

and upon multiplying both sides by $-z$, this gives us the somewhat simple form

Expanding all the fractions as geometric series, we get

Comparing coefficients, we get

for all positive integers $n$. In particular, as in Solution 1, we get

from which the answer $b_{32} = 2^{27} - 2^{11}$ follows.
Remark: To avoid the question of what an infinite product means in the context of formal power series, we could instead view the problem statement as saying that

modular arithmetic for polynomials can be defined in exactly the same way as modular arithmetic for integers. Uniqueness of the $b_n$'s comes from the fact that we have

for all $n\leq 33$ by further reduction modulo $z^n$ (as $z^n\mid z^{33}$ for $n\leq 33$), so we could uniquely solve for the $b_n$'s one at a time. (This idea can be pushed further to explain why it's fine to pass to the infinite product version of the problem.)
To convert the above solution to one that works with polynomials modulo $z^{33}$, note that the derivative is not well-defined, as for instance, $1$ and $1 + z^{33}$ are equivalent modulo $z^{33}$, but their derivatives, $0$ and $33z^{32}$, are not. However, the operator $f(z)\mapsto zf'(z)$ is well-defined. The other key idea is that for any $n$, modulo $z^n$, polynomials of the form $1 - zf(z)$ are invertible, with inverse

Therefore, for the polynomial in the problem, call it $g(z)$, we can still form the expression $zg'(z)/g(z)$, which is what we originally got by taking the logarithmic derivative and multiplying by $z$, and expand it to eventually get

which gets us the same relations (for $n\leq 32$).

From the starting point of Solution 2,

taking reciprocals and expanding with geometric series gives us

On the right, we have the generating function for the number of monic polynomials of degree $n$ over the field $\mathbb{F}_2$ of two elements, and on the left, we have the factorisation of this generating function that considers the breakdown of any given monic polynomial into monic irreducible factors. As such, we have the interpretation

From here, to determine $b_n$, we analyse the elements of $\mathbb{F}_{2^n}$, of which there are $2^{n}$ in total. Given $\alpha\in\mathbb{F}_{2^n}$, if the minimal polynomial $f_{\alpha}$ of $\alpha$ has degree $d$, then $d\mid n$ and all other roots of $f_{\alpha}$ appear in $\mathbb{F}_{2^n}$. Moreover, if $d\mid n$ and $f$ is an irreducible polynomial of degree $d$, then all roots of $f$ appear in $\mathbb{F}_{2^n}$. (These statements are all well-known in the theory of finite fields.) As such, for each $d\mid n$, there are precisely $db_d$ elements of $\mathbb{F}_{2^n}$ of degree $d$, and we obtain the same equation as in Solution 2,

The rest is as before.


For each positive integer $n$, let

Find, with proof, integers $0 < a,\ b,\ c,\ d < 1000000$ such that $T_{1988} = a S_{1989} - b$ and $U_{1988} = c S_{1989} - d$.

Solution:
We note that for all integers $n \ge 2$,
It then follows that
If we let $n=1989$, we see that $(a,b,c,d) = (1989,1989,1990, 2\cdot 1989)$ is a suitable solution.  $\blacksquare$
Notice that it is also possible to use induction to prove the equations relating $T_n$ and $U_n$ with $S_n$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.

Consider a graph with $20$ vertices and $14$ edges. The sum of the degrees of the vertices is $28$; by the Pigeonhole Principle at least $12$ vertices have degrees of $1$ and at most $8$ vertices have degrees greater than $1$. If we keep deleting edges of vertices with degree greater than $1$ (a maximum of $8$ such edges), then we are left with at least $6$ edges, and all of the vertices have degree either $0$ or $1$. These $6$ edges represent the $6$ games with $12$ distinct players.

Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total.  We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game.  Let there be $m$ games with both slots filled and $n$ games with only one slot filled, so $2m+n=20$.  Since there are only 14 games, $m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6$, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.

Assume the contrary.
Consider the largest set of disjoint edges $E$. By assumption it has less than $6$ edges, i.e. maximum $10$ vertices.
Call it a vertex set $V$.
$10$ vertices remain outside $V$ and each has to be attached to at least one edge.
Now, if any two vertices outside $V$ are connected by, say, edge $e$, we could have included $e$ in $E$ and gotten a larger disjoint set, so - a contradiction.
Therefore the only option would be that all vertices outside $V$ are connected each by one edge to some vertices inside $V$. That would take $10$ edges, but $E$ already includes $5$ - again a contradiction.
All possibilities yield a contradiction, so our assumption can not be correct.
(Cases when largest set $E$ is smaller than $6$ are equivalent and weaker)


Let $P(z)= z^n + c_1 z^{n-1} + c_2 z^{n-2} + \cdots + c_n$ be a polynomial in the complex variable $z$, with real coefficients $c_k$. Suppose that $|P(i)| < 1$. Prove that there exist real numbers $a$ and $b$ such that $P(a + bi) = 0$ and $(a^2 + b^2 + 1)^2 < 4 b^2 + 1$.

Solution:
Let $z_1, \dotsc, z_n$ be the (not necessarily distinct) roots of $P$, so that

Since all the coefficients of $P$ are real, it follows that if $w$ is a root of $P$, then $P( \overline{w}) = \overline{ P(w)} = 0$, so $\overline{w}$, the complex conjugate of $w$, is also a root of $P$.
Since

it follows that for some (not necessarily distinct) conjugates $z_i$ and $z_j$,

Let $z_i = a+bi$ and $z_j = a-bi$, for real $a,b$.  We note that

Thus

Since $P(a+bi) = P(z_i) = 0$, these real numbers $a,b$ satisfy the problem's conditions.  $\blacksquare$


Let $ABC$ be an acute-angled triangle whose side lengths satisfy the inequalities $AB < AC < BC$. If point $I$ is the center of the inscribed circle of triangle $ABC$ and point $O$ is the center of the circumscribed circle, prove that line $IO$ intersects segments $AB$ and $BC$.

Solution:
Consider the lines that pass through the circumcenter $O$. Extend $AO$, $BO$, $CO$ to $D$,$E$,$F$ on $a$,$b$,$c$, respectively.
We notice that $IO$ passes through sides $a$ and $c$ if and only if $I$ belongs to either regions $AOF$ or $COD$.

Since $AO = BO = CO = R$, we let $\alpha = \angle OAC = \angle OCA$, $\beta = \angle BAO = \angle ABO$, $\gamma = \angle BCO = \angle CBO$.
We have $c < b < a\implies C < B < A\implies$ $\gamma+\alpha <\beta+\gamma <\alpha+\beta\implies\gamma <\alpha <\beta$
Since $IA$ divides angle $A$ into two equal parts, it must be in the region marked by the $\beta$ of angle $A$, so $I$ is in $ABD$.
Similarly, $I$ is in $ACF$ and $ABE$. Thus, $I$ is in their intersection, $AOF$. From above, we have $IO$ passes through $a$ and $c$. $\blacksquare$


Let $u$ and $v$ be real numbers such that

Determine, with proof, which of the two numbers, $u$ or $v$, is larger.

Solution:
The answer is $v$.
We define real functions $U$ and $V$ as follows:

We wish to show that if $U(u)=V(v)=8$, then $u <v$.
We first note that when $x \le 0$, $x^{12}-x \ge 0$, $x-1 < 0$, and $9x^9 \le 0$, so

Similarly, $V(x) \le 0 < 8$.
We also note that if $x \ge 9/10$, then

Similarly $V(x) > 8$.  It then follows that $u, v \in (0,9/10)$.
Now, for all $x \in (0,9/10)$,

Since $V$ and $U$ are both strictly increasing functions over the nonnegative reals, it then follows that

so $u<v$, as desired.  $\blacksquare$


A certain state issues license plates consisting of six digits (from 0 through 9). The state requires that any two plates differ in at least two places. (Thus the plates $\boxed{027592}$ and $\boxed{020592}$ cannot both be used.) Determine, with proof, the maximum number of distinct license plates that the state can use.

Consider license plates of $n$ digits, for some fixed $n$, issued with the same criteria.
We first note that by the pigeonhole principle, we may have at most $10^{n-1}$ distinct plates.  Indeed, if we have more, then there must be two plates which agree on the first $n-1$ digits; these plates thus differ only on one digit, the last one.
We now show that it is possible to issue $10^{n-1}$ distinct license plates which satisfy the problem's criteria.  Indeed, we issue plates with all $10^{n-1}$ possible combinations for the first $n-1$ digit, and for each plate, we let the last digit be the sum of the preceding digits taken mod 10.  This way, if two plates agree on the first $n-1$ digits, they agree on the last digit and are thus the same plate, and if two plates differ in only one of the first $n-1$ digits, they must differ as well in the last digit.
It then follows that $10^{n-1}$ is the greatest number of license plates the state can issue.  For $n=6$, as in the problem, this number is $10^5$.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A sequence of functions $\, \{f_n(x) \} \,$ is defined recursively as follows:

(Recall that $\sqrt {\makebox[5mm]{}}$ is understood to represent the positive square root.) For each positive integer $n$, find all real solutions of the equation $\, f_n(x) = 2x \,$.

Solution:
We define $f_0(x) = 8$.  Then the recursive relation holds for $n=0$, as well.
Since $f_n (x) \ge 0$ for all nonnegative integers $n$, it suffices to consider nonnegative values of $x$.
We claim that the following set of relations hold true for all natural numbers $n$ and nonnegative reals $x$:

To prove this claim, we induct on $n$.  The statement evidently holds for our base case, $n=0$.
Now, suppose the claim holds for $n$.  Then

The claim therefore holds by induction.  It then follows that for all nonnegative integers $n$, $x=4$ is the unique solution to the equation $f_n(x) = 2x$.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Suppose that necklace $\, A \,$ has 14 beads and necklace $\, B \,$ has
19. Prove that for any odd integer $n \geq 1$, there is a way to number
each of the 33 beads with an integer from the sequence

so that each integer is used once, and adjacent beads correspond to
relatively prime integers. (Here a "necklace" is viewed as a circle in
which each bead is adjacent to two other beads.)

Solution:
Lemma.  For every positive odd integer $n$, there exists a nonnegative integer $k \le 17$ such that $n+k$ is relatively prime to $n+k+15$, $n+k+1$ is relatively prime to $n+k+14$.
Proof.  Consider the positive integers $n, n+1, n+2$.  Note that at most one of these is divisible by 3, and at most one is divisible by 5.  Therefore one of these, say $n+a$, is divisible by neither, and is therefore relatively prime to 15.  Furthermore, $n+a+1$ and $n+(a+15)+1$ have different residues mod 13, so one of them, say $n+b+1$, is relatively prime to 13.  Since $n+b \equiv n+a \pmod{15}$, $n+b$ is relatively prime to 15.  But

so $n+b$ is relatively prime to $n+b+15$.  Also,

so $n+b+1$ is relatively prime to $n+b+14$.  Finally, $b \le a+15 \le 17$.  It follows that setting $k=b$ satisfies the lemma.  $\blacksquare$
Let $k$ be an integer as described in the lemma.  We place the integers $n, \dotsc, n+k, n+k+15, \dotsc, n+32$ on the necklace with 19 beads, and the integers $n+k+1, \dotsc, n+k+14$ on the necklace with 14 beads, in those orders.  Since $n$ is odd, $n$ is relatively prime to $n+32 = n+2^5$.  By definition, $n+k$ and $n+k+15$ are relatively prime, as are $n+k+1$ and $n+k+14$; finally, $a$ and $a+1$ are relatively prime for all integers $a$.  It follows that each bead in this arrangement is relatively prime to its neighbors.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Find, with proof, the number of positive integers whose base-$n$ representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by $\pm 1$ from some digit further to the left.  (Your answer should be an explicit function of $n$ in simplest form.)

Solution:
Let a $k$-good sequence be a sequence of distinct integers $\{ a_i \}_{i=1}^k$ such that for all integers $2\le i \le k$, $a_i$ differs from some preceding term by $\pm 1$.
Lemma.  Let $a$ be an integer.  Then there are $2^{k-1}$ $k$-good sequences starting on $a$, and furthermore, the terms of each of these sequences constitute a permutation of $k$ consecutive integers.
Proof. We induct on $k$.  For $k=1$, the lemma is trivially true.  Now, suppose the lemma holds for $k$.  If $\{ a_i \}_{i=1}^{k+1}$ is a $(k+1)$-good sequence, then $\{ a_i \}_{i=1}^k$ is a $k$-good sequence which starts on $a$, so it is a permutation of $k$ consecutive integers, say $m, \dotsc, M$.  Then the only possibilities for $a_{k+1}$ are $m-1$ and $M+1$; either way, $\{ a_i \}_{i=1}^{k+1}$ constitutes a permutation of $k+1$ consecutive integers.  Since there are $2^k$ possible sequences $\{a_i\}_{i=1}^k$, and 2 choices of $a_{k+1}$ for each of these sequences, it also follows that there are $2^k \cdot 2 = 2^{k+1}$ $(k+1)$-good sequences which start on $a$.  Thus the lemma holds by induction.  $\blacksquare$
We now consider the number of desired positive integers with $k$ digits.  Evidently, $k$ must be less than or equal to $n$.  We also note that the digits of such an integer must constitute a $k$-good sequence.  Since the minimum of this sequence can be any of the digits $0, \dotsc, n-k$, unless the minimum is 0 and is the first digit (in which case the only possible sequence is an increasing arithmetic sequence), and there are $2^{k-1}$ $k$-good sequences up to translation, it follows that there are $(n-k+1) 2^{k-1}-1$ desired positive integers with $k$ digits.  Thus the total number of desired positive integers is

which is equal to $2^{n+1} - 2(n+1)$, our answer.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


An acute-angled triangle $ABC$ is given in the plane. The circle with diameter $\, AB \,$ intersects altitude $\, CC' \,$ and its extension at points $\, M \,$ and $\, N \,$, and the circle with diameter $\, AC \,$ intersects altitude $\, BB' \,$ and its extensions at $\, P \,$ and $\, Q \,$. Prove that the points $\, M, N, P, Q \,$ lie on a common circle.

Let $A'$ be the intersection of the two circles (other than $A$). $AA'$ is perpendicular to both $BA'$, $CA'$ implying $B$, $C$, $A'$ are collinear. Since $A'$ is the foot of the altitude from $A$: $A$, $H$, $A'$ are concurrent, where $H$ is the orthocentre.
Now, $H$ is also the intersection of $BB'$, $CC'$ which means that $AA'$, $MN$, $PQ$ are concurrent. Since $A$, $M$, $N$, $A'$ and $A$, $P$, $Q$, $A'$ are cyclic, $M$, $N$, $P$, $Q$ are cyclic by the radical axis theorem.

Define $A'$ as the foot of the altitude from $A$ to $BC$. Then, $AA' \cap BB' \cap CC'$ is the orthocenter. We will denote this point as $H$.
Since $\angle AA'C$ and $\angle AA'B$ are both $90^{\circ}$, $A'$ lies on the circles with diameters $AC$ and $AB$.
Now we use the Power of a Point theorem with respect to point $H$. From the circle with diameter $AB$ we get $AH \cdot A'H = MH \cdot NH$. From the circle with diameter $AC$ we get $AH \cdot A'H = PH \cdot QH$. Thus, we conclude that $PH \cdot QH = MH \cdot NH$, which implies that $P$, $Q$, $M$, and $N$ all lie on a circle.

Let $\omega_1$ be the circumcircle with diameter $AB$ and $\omega_2$ be the circumcircle with diameter $AC$.  We claim that the second intersection of $\omega_1$ and $\omega_2$ other than $A$ is $A'$, where $A'$ is the feet of the perpendicular from $A$ to segment $BC$.  Note that  so $A'$ lies on $\omega_1.$  Similarly, $A'$ lies on $\omega_2$.  Hence, $AA'$ is the radical axis of $\omega_1$ and $\omega_2$.  By the Radical Lemma, it suffices to prove that the intersection of lines $MN$ and $PQ$ lie on $AA'$.  But, $MN$ is the same line as $CC'$ and $PQ$ is the same line as $BB'$.  Since $AA', BB'$, and $CC'$ intersect at the orthocenter $H$, $H$ lies on the radical axis $AA'$ and we are done. $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


In triangle $ABC$, angle $A$ is twice angle $B$, angle $C$ is obtuse, and the three side lengths $a, b, c$ are integers.  Determine, with proof, the minimum possible perimeter.

(diagram by integralarefun)
After drawing the triangle, also draw the angle bisector of $\angle A$, and let it intersect $\overline{BC}$ at $D$. Notice that $\triangle ADC\sim \triangle BAC$, and let $AD=x$. Now from similarity,

However, from the angle bisector theorem, we have

but $\triangle ABD$ is isosceles, so

so all sets of side lengths which satisfy the conditions also meet the boxed condition.
Notice that $\text{gcd}(a, b, c)=1$ or else we can form a triangle by dividing $a, b, c$ by their greatest common divisor to get smaller integer side lengths, contradicting the perimeter minimality. Since $a$ is squared, $b$ must also be a square because if it isn't, then $b$ must share a common factor with $b+c$, meaning it also shares a common factor with $c$, which means $a, b, c$ share a common factor—a contradiction. Thus we let $b = x^2, b+c = y^2$, so $a = xy$, and we want the minimal pair $(x,y)$.
By the Law of Cosines,
Substituting $a^2 = b^2 + bc$ yields $\cos B = \frac{b+c}{2a} = \frac{y}{2x}$. Since $\angle C > 90^{\circ}$, $0^{\circ} < \angle B < 30^{\circ} \Longrightarrow \sqrt{3} < \frac{y}{x} < 2$. For $x \le 3$ there are no integer solutions. For $x = 4$, we have $y = 7$ that works, so the side lengths are $(a, b, c)=(28, 16, 33)$ and the minimal perimeter is $\boxed{77}$.


For any nonempty set $\,S\,$ of numbers, let $\,\sigma(S)\,$ and $\,\pi(S)\,$ denote the sum and product, respectively, of the elements of $\,S\,$.  Prove that

where "$\Sigma$" denotes a sum involving all nonempty subsets $S$ of $\{1,2,3, \ldots,n\}$.

Solution:
Let $N(m)$ denote the set $\{1, \dotsc, m\}$.  Since $\sigma(\varnothing)$, the empty sum, is equal to zero, and $\pi(\varnothing)$, the empty product, is equal to 1, the equation

is equivalent to the desired equation when $n >0$.  We will prove this equation, but first, we prove a lemma.
Lemma.  For all nonnegative integers $n$, $\sum_{S \subseteq N(n)} \frac{1}{\pi(S)} = n+1$.
Proof. Evidently,

But the terms of this sum are the coefficients of the polynomial $P(x) = \prod_{k=1}^n (x + 1/k)$, and the sum of the coefficients of this polynomial is

as desired.  $\blacksquare$
We now prove our equation by induction on $n$.  For $n=0$, we have the simple equation 0=0.
Suppose the equation holds when $n=a$.  Then

By inductive hypothesis,

and by the lemma,

Since $(a+2)(s+1) = (a+3)(a+1) = (a+2)^2 -1$, our equation thus holds by induction.  Thus the problem statement is proven.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Show that, for any fixed integer $\,n \geq 1,\,$ the sequence

is eventually constant.
[The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$. Also $a_i \pmod{n}$ means the remainder which results from dividing $\,a_i\,$ by $\,n$.]

Suppose that the problem statement is false for some integer $n \ge 1$.  Then there is a least $n$, which we call $b$, for which the statement is false.
Since all integers are equivalent mod 1, $b\neq 1$.
Note that for all integers $b$, the sequence $2^0, 2^1, 2^2, \dotsc$ eventually becomes cyclic mod $b$.  Let $k$ be the period of this cycle.  Since there are $k-1$ nonzero residues mod $b$. $1 \le k\le b-1 < b$.  Since

does not become constant mod $b$, it follows the sequence of exponents of these terms, i.e., the sequence

does not become constant mod $k$.  Then the problem statement is false for $n=k$.  Since $k<b$, this is a contradiction.  Therefore the problem statement is true.  $\blacksquare$
Note that we may replace 2 with any other positive integer, and both the problem and this solution remain valid.

We’ll prove by strong induction that for every natural number $n$, the sequence $a_1, a_2, \ldots$ is eventually constant. Since every term of the sequence is $0 \mathrm{\ mod\ } 1$, the claim is true when $n = 1$. Assuming that it’s true for $1, \ldots, n$, we’ll now show that it’s true for $n + 1$ as well.
Suppose first that $n + 1$ is odd. Since $\varphi(n + 1) < n + 1$, by our inductive hypothesis there exists an $m$ such that

Since $n + 1$ is coprime to powers of $2$, it follows by Euler’s theorem that

or equivalently

which is what we wanted to show.
Now suppose that $n + 1$ is even. Write $n + 1 = 2^{k} \cdot s$, where $1 \leq s < n + 1$ is odd. The series must eventually be constant $\textrm{mod\ } 2^k$, since $a_m = 0 \textrm{\ mod\ } {2^k}$ for large enough $m$. And by our inductive hypothesis, the series must also eventually be constant $\textrm{mod\ } s$. So for large enough $m$,

Since $2^k$ and $s$ are coprime, these equations are also true modulo $2^k \cdot s = n + 1$. So

which completes the proof.


Let $\, a =(m^{m+1} + n^{n+1})/(m^m + n^n), \,$ where $\,m\,$ and $\,n\,$ are positive integers.  Prove that $\,a^m + a^n \geq m^m + n^n$.
[You may wish to analyze the ratio $\,(a^N - N^N)/(a-N),$ for real $\, a \geq 0 \,$ and integer $\, N \geq 1$.]

Solution:
Let us assume without loss of generality that $m\ge n$.  We then note that

Similarly,
We note that equations $(*)$ and $(**)$ imply that $n \le a \le m$.  Then $a/m \le 1 \le a/n$, so

Multiplying this inequality by $m^m n^n(m-n)/(m^m+n^n)$, we have

It then follows that

Rearranging this inequality, we find that $a^m + a^n \ge m^m + n^n$, as desired.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $\, D \,$ be an arbitrary point on side $\, AB \,$ of a given triangle $\, ABC, \,$ and let $\, E \,$ be the interior point where $\, CD \,$ intersects the external common tangent to the incircles of triangles $\, ACD \,$ and $\, BCD$. As $\, D \,$ assumes all positions between $\, A \,$ and $\, B \,$, prove that the point $\, E \,$ traces the arc of a circle.

Let the incircle of $ACD$ and the incircle of $BCD$ touch line $AB$ at points $D_a,D_b$, respectively; let these circles touch $CD$ at $C_a$, $C_b$, respectively; and let them touch their common external tangent containing $E$ at $T_a,T_b$, respectively, as shown in the diagram below.
We note that

On the other hand, since $EC_a$ and $ET_a$ are tangents from the same point to a common circle, $EC_a = T_aE$, and similarly $EC_b = ET_b$, so

On the other hand, the segments $T_a T_b$ and $D_a D_b$ evidently have the same length, and $D_a D_b = D_aD + DD_b$, so $EC_a + EC_b = D_aD + DD_b$. Thus

If we let $s_a$ be the semiperimeter of triangle $ACD$, then $CC_a = s_a - AD$, and $D_aD = s_a - AC$, so

Similarly,

so that

Thus $E$ lies on the arc of the circle with center $C$ and radius $(AB+BC-AB)/2$ intercepted by segments $CA$ and $CB$.  If we choose an arbitrary point $X$ on this arc and let $D$ be the intersection of lines $CX$ and $AB$, then $X$ becomes point $E$ in the diagram, so every point on this arc is in the locus of $E$. $\blacksquare$

Define the same points as in the first solution.  First extend $T_aT_b$ to intersect $AB$ at a point $P$; without loss of generality let $A$ lie in between $B$ and $P$.  Then the incircle of $\triangle ACD$ is also the incircle of $\triangle PED$, while the incircle of $\triangle BCD$ is the $P$-excircle of $\triangle PED$.  It follows that $EC_a = C_bD$; denote this equality by $(*)$.
Now remark that

Hence

is a constant equal to $r := \tfrac{AC+BC-AB}2$, and so $C$ lies on the circle with center $C$ and radius $r$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Find, as a function of $\, n, \,$ the sum of the digits of

where each factor has twice as many digits as the previous one.

Solution:
The answer is $9 \cdot 2^n$.
Let us denote the quantity $\prod_{k=0}^n \bigl( 10^{2^k}-1 \bigr)$ as $P_n$.  We wish to find the sum of the digits of $P_n$.
We first note that

so $P_{n-1}$ is a number of at most $2^n$ digits.  We also note that the units digit is not equal to zero.  We may thus represent $P_{n-1}$ as

where the $d_k$ are digits and $d_0 \neq 0$.  Then

Thus the digits of $P_n$ are

and the sum of these is evidently $9 \cdot 2^n$, as desired.  $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Consider the points $M_k = (1, \tan k^\circ)$ in the coordinate plane with origin $O=(0,0)$, for integers $0 \le k \le 89$.
Evidently, the angle between segments $OM_a$ and $OM_b$ is $(b-a)^\circ$, and the length of segment $OM_a$ is $1/\cos a^\circ$.  It then follows that the area of triangle $M_aOM_b$ is $\tfrac{1}{2} \sin(b-a)^\circ \cdot OM_a \cdot OM_b = \tfrac{1}{2} \sin(b-a)^\circ / (\cos a^\circ \cdot \cos b^\circ)$.  Therefore

so

as desired.  $\blacksquare$

First multiply both sides of the equation by $\sin 1$, so the right hand side is $\frac{\cos 1}{\sin 1}$.  Now by rewriting $\sin 1=\sin((k+1)-k)=\sin(k+1)\cos(k)+\sin(k)\cos(k+1)$, we can derive the identity $\tan(n+1)-\tan(n)=\frac{\sin 1}{\cos(n)\cos(n+1)}$.  Then the left hand side of the equation simplifies to $\tan 89-\tan 0=\tan 89=\frac{\sin 89}{\cos 89}=\frac{\cos 1}{\sin 1}$ as desired.

Multiply by $\sin{1}$. We get:
$\frac {\sin{1}}{\cos{0}\cos{1}} + \frac {\sin{1}}{\cos{1}\cos{2}} + ... + \frac {\sin{1}}{\cos{88}\cos{89}} = \frac {\cos{1}}{\sin{1}}$
we can write this as:
$\frac {\sin{1 - 0}}{\cos{0}\cos{1}} + \frac {\sin{2 - 1}}{\cos{1}\cos{2}} + ... + \frac {\sin{89 - 88}}{\cos{88}\cos{89}} = \frac {\cos{1}}{\sin{1}}$
This is an identity $\tan{a} - \tan{b} = \frac {\sin{(a - b)}}{\cos{a}\cos{b}}$
Therefore;
$\sum_{i = 1}^{89}[\tan{k} - \tan{(k - 1)}] = \tan{89} - \tan{0} = \cot{1}$, because of telescoping.
but since we multiplied $\sin{1}$ in the beginning, we need to divide by $\sin{1}$. So we get that:
$\frac {1}{\cos{0}\cos{1}} + \frac {1}{\cos{1}\cos{2}} + \frac {1}{\cos{2}\cos{3}} + .... + \frac {1}{\cos{88}\cos{89}} = \frac {\cos{1}}{\sin^2{1}}$
as desired. QED

Let $S = \frac{1}{\cos 0^\circ\cos 1^\circ} + \frac{1}{\cos 1^\circ\cos 2^\circ} + ... + \frac{1}{\cos 88^\circ\cos 89^\circ}$.
Multiplying by $\sin 1^\circ$ gives
Notice that $\frac{\sin((x+1^\circ)-x)}{\cos 0^\circ\cos 1^\circ} = \tan (x+1^\circ) - \tan x$ after expanding the sine, and so
 so


For a nonempty set $S$ of integers, let $\sigma(S)$ be the sum of the elements of $S$. Suppose that $A = \{a_1, a_2, \ldots, a_{11}\}$ is a set of positive integers with $a_1 < a_2 < \cdots < a_{11}$ and that, for each positive integer $n \le 1500$, there is a subset $S$ of $A$ for which $\sigma(S) = n$. What is the smallest possible value of $a_{10}$?

Solution:
Let's a $n$-$p$ set be a set $Z$ such that $Z=\{a_1,a_2,\cdots,a_n\}$, where $\forall i<n$, $i\in \mathbb{Z}^+$, $a_i<a_{i+1}$, and for each $x\le p$, $x\in \mathbb{Z}^+$, $\exists Y\subseteq Z$, $\sigma(Y)=x$, $\nexists \sigma(Y)=p+1$.
(For Example $\{1,2\}$ is a $2$-$3$ set and $\{1,2,4,10\}$ is a $4$-$8$ set)
Furthermore, let call a $n$-$p$ set a $n$-$p$ good set if $a_n\le p$, and a $n$-$p$ bad set if $a_n\ge p+1$ (note that $\nexists \sigma(Y)=p+1$ for any $n$-$p$ set. Thus, we can ignore the case where $a_n=p+1$).
Furthermore, if you add any amount of elements to the end of a $n$-$p$ bad set to form another $n$-$p$ set (with a different $n$), it will stay as a $n$-$p$ bad set because $a_{n+x}>a_{n}>p+1$ for any positive integer $x$ and $\nexists \sigma(Y)=p+1$.
Lemma) If $Z$ is a $n$-$p$ set, $p\leq 2^n-1$.
For $n=1$, $p=0$ or $1$ because $a_1=1 \rightarrow p=1$ and $a_1\ne1\rightarrow p=0$.
Assume that the lemma is true for some $n$, then $2^n$ is not expressible with the $n$-$p$ set. Thus, when we add an element to the end to from a $n+1$-$r$ set, $a_{n+1}$ must be $\le p+1$ if we want $r>p$ because we need a way to express $p+1$. Since $p+1$ is not expressible by the first $n$ elements, $p+1+a_{n+1}$ is not expressible by these $n+1$ elements. Thus, the new set is a $n+1$-$r$ set, where $r\leq p+1+a_{n+1} \leq 2^{n+1}-1$
Lemma Proven
The answer to this question is $\max{(a_{10})}=248$.
The following set is a $11$-$1500$ set:
$\{1,2,4,8,16,32,64,128,247,248,750\}$
Note that the first 8 numbers are power of $2$ from $0$ to $7$, and realize that any $8$ or less digit binary number is basically sum of a combination of the first $8$ elements in the set. Thus, $\exists Y\subseteq\{1,2,4,8,16,32,64,128\}$, $\sigma(Y)=x \forall 1\le x\leq 255$.
$248\le\sigma(y)+a_9\le502$ which implies that $\exists A\subseteq\{1,2,4,8,16,32,64,128,247\}$, $\sigma(A)=x \forall 1\le x\leq 502$.
Similarly $\exists B\subseteq\{1,2,4,8,16,32,64,128,247,248\}$, $\sigma(A)=x \forall 1\le x\le750$ and $\exists C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}$, $\sigma(A)=x \forall 1\leq x\leq 1500$.
Thus, $\{1,2,4,8,16,32,64,128,247,248,750\}$ is a $11$-$1500$ set.
Now, let's assume for contradiction that $\exists a_{10}\leq 247$ such that ${a_1, a_2, \dots, a_{11}}$ is a $11$-$q$ set where $q\geq 1500$
${a_1, a_2, \dots a_8}$ is a $8$-$a$ set where $a\leq 255$ (lemma).
$max{(a_9)}=a_{10}-1\leq 246$
Let ${a_1, a_2, \dots, a_{10}}$ be a $10$-$b$ set where the first $8$ elements are the same as the previous set. Then, $256+a_9+a_{10}$ is not expressible as $\sigma(Y)$. Thus, $b\leq 255+a_9+a_{10}\leq 748$.
In order to create a $11$-$d$ set with $d>748$ and the first $10$ elements being the ones on the previous set, $a_{11}\leq 749$ because we need to make $749$ expressible as $\sigma(Y)$. Note that $b+1+a_{11}$ is not expressible, thus $d<b+1+a_{11}\leq 1498$.
Done but not elegant...


Chords $AA'$, $BB'$, and $CC'$ of a sphere meet at an interior point $P$ but are not contained in the same plane.  The sphere through $A$, $B$, $C$, and $P$ is tangent to the sphere through $A'$, $B'$, $C'$, and $P$.  Prove that $AA'=BB'=CC'$.

Consider the plane through $A,A',B,B'$.  This plane, of course, also contains $P$. We can easily find the $\triangle APB$ is isosceles because the base angles are equal. Thus, $AP=BP$. Similarly, $A'P=B'P$. Thus, $AA'=BB'$. By symmetry, $BB'=CC'$ and $CC'=AA'$, and hence $AA'=BB'=CC'$ as desired.
$\mathbb{QED.}$
By another person ^v^
The person that came up with the solution did not prove that  $\triangle APB$ is isosceles nor the base angles are congruent. I will add on to the solution.
There is a common tangent plane that pass through $P$ for the $2$ spheres that are tangent to each other.
Since any cross section of sphere is a circle. It implies that $A$, $A'$, $B$, $B'$ be on the same circle ($\omega_1$), $A$, $B$, $P$ be on the same circle ($\omega_2$), and $A'$, $B'$, $P$ be on the same circle ($\omega_3$).
$m\angle APB= m\angle A'PB'$ because they are vertical angles. By power of point, $(AP)(A'P)=(BP)(B'P)\rightarrow\frac{AP}{B'P}=\frac{BP}{A'P}$
By the SAS triangle simlarity theory, $\triangle APB \sim\triangle B'PA'$. That implies that $\angle ABP\cong\angle B'PA'$.

Let's call the interception of the common tangent plane and the plane containing $A$, $A'$, $B$, $B'$, $P$, line $l$.
$l$ must be the common tangent of $\omega_2$ and $\omega_3$.
The acute angles form by $l$ and $\overline{AA'}$ are congruent to each other (vertical angles) and by the tangent-chord theorem, the central angle of chord $\overline{AP}$ and $\overline{A'P}$ are equal.
Similarly the central angle of chord $\overline{BP}$ and $\overline{B'P}$ are equal.
The length of any chord with central angle $2\theta$ and radius $r$ is $2r\sin\left({\theta}\right)$, which can easily been seen if we drop the perpendicular from the center to the chord.
Thus, $\frac{AP}{A'P}=\frac{BP}{B'P}$.
By the SAS triangle simlarity theory, $\triangle APB \sim\triangle A'PB'$. That implies that $\angle ABP\cong\angle B'PA'$.
That implies that $\angle ABP\cong\angle A'PB'\cong\angle B'PA'$. Thus, $\triangle A'PB'$ is an isosceles triangle and since $\triangle APB \sim\triangle A'PB'$, then$\triangle APB$ must be an isosceles triangle too.

Call the large sphere $O_1$, the one containing $A$ $O_2$, and the one containing $A'$ $O_3$.  The centers are $c_1$, $c_2,$ and $c_3$.
Since two spheres always intersect in a circle , we know that A,B, and C must lie on a circle ($w_1$)completely contained in $O_1$ and $O_2$
Similarly, A', B', and C' must lie on a circle ($w_2$) completely contained in $O_1$ and $O_3$.
So, we know that 3 lines connecting a point on $w_1$ and P hit a point on $w_2$.  This implies that $w_1$ projects through P to $w_2$, which in turn means that $w_1$ is in a plane parallel to that of $w_2$.  Then, since $w_1$ and $w_2$ lie on the same sphere, we know that they must have the same central axis, which also must contain P (since the center projects through P to the other center).
So, all line from a point on $w_1$ to P are of the same length, as are all lines from a point on $w_2$ to P.  Since AA', BB', and CC' are all composed of one of each type of line, they must all be equal.


Let $\, P(z) \,$ be a polynomial with complex coefficients which is of degree $\, 1992 \,$ and has distinct zeros. Prove that there exist complex numbers $\, a_1, a_2, \ldots, a_{1992} \,$ such that $\, P(z) \,$ divides the polynomial $\left( \cdots \left( (z-a_1)^2 - a_2 \right)^2 \cdots - a_{1991} \right)^2 - a_{1992}$.

Solution:
Since the zeros $z_{1}, z_{2}, \ldots, z_{1992}$ of the polynomial $P(z)$ are distinct, the polynomial $P(z)$ divides the polynomial

if and only if $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;1992\right\}$. So it is enough to show that for any $1992$ complex numbers $z_{1}, z_{2}, \dots, z_{1992}$, there exist $1992$ complex numbers $a_{1}, a_{2}, \ldots, a_{1992}$, such that the polynomial

satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;1992\right\}$. This is a special case of the following lemma.
Lemma: Let $n$ be a positive integer, and $z_{1}, z_{2}, \ldots, z_{n}$ be $n$ complex numbers. Then, there exist $n$ complex numbers $a_{1}, a_{2},\ldots, a_{n}$ such that the polynomial $Q\left(z\right) = \left( \ldots \left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{n-1}\right)^{2}-a_{n}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;n\right\}$.
Proof: We use induction over $n$.
For $n = 1$, the lemma is trivial, since $Q\left(z\right)=z-a_{1}$, so we can take $a_{1}=z_{1}$, and then the polynomial $Q\left(z\right)=z-z_{1}$ clearly satisfies $Q\left(z_{1}\right)=0$.
Let $k$ be a positive integer. Assume that for $n = k$, the lemma is true. Therefore, there exist $k$ complex numbers $a_{1}, a_{2}, \ldots, a_{k}$ such that the polynomial $Q\left(z\right)=\left(\ldots\left( \left(z-a_{1}\right)^{2}-a_{2}\right)^{2}\ldots-a_{k-1}\right)^{2}-a_{k}$ satisfies $Q\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;k\right\}$. Then we wish to prove that for any $k + 1$ complex numbers $z_{1}, z_{2}, \ldots, z_{k+1}$, there exist $k + 1$ complex numbers $b_{1}, b_{2}, \ldots, b_{k+1}$ such that the polynomial $R\left(z\right)=\left(\ldots\left( \left(z-b_{1}\right)^{2}-b_{2}\right)^{2}\ldots-b_{k}\right)^{2}-b_{k+1}$ satisfies $R\left(z_{i}\right)=0$ for every $i\in\left\{1;\;2;\;\ldots;\;k+1\right\}$. We will construct this polynomial $R$ from the polynomial $Q$.
Let $b_{i}=a_{i}$ for every $i\le k-1$, and let $b_{k}=a_{k}+\frac{1}{2}Q\left(z_{k+1}\right)$ and $b_{k+1}=\frac{1}{4}\left(Q\left(z_{k+1}\right)\right)^{2}$. Then,

Then as $Q\left(z_{i}\right)=0$ for $i\in\left\{1;\;2;\;\ldots;\;k\right\}$, we have

for all $i\in\left\{1;\;2;\;\ldots;\;k\right\}$. Also,

Thus, $R\left(z_{i}\right)=0$ holds for every $i\in\left\{1;\;2;\;\ldots;\;k+1\right\}$, and this proves the lemma for $n = k + 1$. Hence, the induction step is complete, and the lemma is proven.
As the problem is a special case of the lemma ($n=1992$), we are done.


For each integer $n\ge 2$, determine, with proof, which of the two positive real numbers $a$ and $b$ satisfying

is larger.

Square and rearrange the first equation and also rearrange the second.

It is trivial that

since $a-1$ clearly cannot equal $0$ (Otherwise $a^n=1\neq 1+1$).  Thus

where we substituted in equations (1) and (2) to achieve (5).  Notice that from $a^{n}=a+1$ we have $a>1$.  Thus, if $b>a$, then $b^{2n-1}-1>a^{2n-1}-1$.  Since $a>1\Rightarrow a^{2n-1}-1>0$, multiplying the two inequalities yields $b^{2n}-b>a^{2n}-a$, a contradiction, so $a> b$.  However, when $n$ equals $0$ or $1$, the first equation becomes meaningless, so we conclude that for each integer $n\ge 2$, we always have $a>b$.

Define $f(x)=x^n-x-1$ and $g(x)=x^{2n}-x-3a$. By Descarte's Rule of Signs, both polynomials' only positive roots are $a$ and $b$, respectively. With the Intermediate Value Theorem and the fact that $f(1)=-1$ and $f(2)=2^n-3>0$, we have $a\in(1,2)$.
Thus, $-3a\in(-6,-3)$, which means that $g(1)=-3a<0$. Also, we find that $g(a)=a^{2n}-4a$. All that remains to prove is that $g(a)>0$, or $a^{2n}-4a>0$. We can then conclude that $b$ is between $1$ and $a$ from the Intermediate Value Theorem. From the first equation given, $a^{2n}=(a+1)^2=a^2+2a+1$. Subtracting $4a$ gives us $a^2-2a+1>0$, which is clearly true, as $a\neq1$. Therefore, we conclude that $1<b<a<2$.


Consider functions $f : [0, 1] \rightarrow \mathbb{R}$ which satisfy
Find, with proof, the smallest constant $c$ such that
for every function $f$ satisfying (i)-(iii) and every $x$ in $[0, 1]$.

Solution:
My claim: $c\ge2$
Lemma 1) $f\left(\left(\frac{1}{2}\right)^n\right)\le\left(\frac{1}{2}\right)^n$ for $n\in \mathbb{Z}, n\ge0$
For $n=0$, $f(1)=1$ (ii)
Assume that it is true for $n-1$, then $f\left(\left(\frac{1}{2}\right)^{n}\right)+f\left(\left(\frac{1}{2}\right)^{n}\right)\le f\left(\left(\frac{1}{2}\right)^{n-1}\right)\le \left(\frac{1}{2}\right)^{n-1}$
$f\left(\left(\frac{1}{2}\right)^{n}\right)\le \left(\frac{1}{2}\right)^{n}$
By principle of induction, lemma 1 is proven.
Lemma 2) For any $x$, $\left(\frac{1}{2}\right)^{n+1}<x\le\left(\frac{1}{2}\right)^n\le1$ and $n\in \mathbb{Z}$, $f(x)\le\left(\frac{1}{2}\right)^n$.
$f(x)+f\left(\left(\frac{1}{2}\right)^n-x\right)\le f\left(\left(\frac{1}{2}\right)^{n}\right)\le \left(\frac{1}{2}\right)^{n}$ (lemma 1 and (iii) )
$f(x)\le\left(\frac{1}{2}\right)^n$ (because $f\left(\left(\frac{1}{2}\right)^n-x\right)\ge0$ (i) )

$\forall 0\le x\le 1$, $\left(\frac{1}{2}\right)^{n-1}\ge2x\ge \left(\frac{1}{2}\right)^n\ge f(x)$. Thus, $c=2$ works.

Let's look at a function $g(x)=\left\{\begin{array}{ll}0&0\le x\le \frac{1}{2};\\1&\frac{1}{2}<x\le1;\\\end{array}\right\}$
It clearly have property (i) and (ii). For $0\le x\le\frac{1}{2}$ and WLOG let $x\le y$, $f(x)+f(y)=0+f(y)\le f(y)$
For $\frac{1}{2}< x\le 1$, $x+y>1$. Thus, property (iii) holds too. Thus $g(x)$ is one of the legit function.

$\lim_{x\rightarrow\frac{1}{2}^+} cx \ge \lim_{x\rightarrow\frac{1}{2}^+} g(x)=1$
$\frac{1}{2}c>1$
$c>2$ but approach to $2$ when $x$ is extremely close to $\frac{1}{2}$ from the right side.
$\mathbb{Q.E.D}$


Let $a$, $b$ be odd positive integers. Define the sequence $(f_n)$ by putting $f_1 = a$,
$f_2 = b$, and by letting $f_n$ for $n\ge3$ be the greatest odd divisor of $f_{n-1} + f_{n-2}$.
Show that $f_n$ is constant for $n$ sufficiently large and determine the eventual
value as a function of $a$ and $b$.

Solution:
Part 1) Prove that $f_n$ is constant for sufficiently large $n$.
Note that if there is some $f_n=f_{n-1}$ for any $n$, then $\frac{f_{n}+f_{n-1}}{2}=f_n$, which is odd. Thus, $f_{n+1}=f_n=f_{n-1}$ and by induction, all $f_p$ is constant for $p\ge n$.
Also note that $f_n>0$ since average of $2$ positive number is always positive.
Thus, assume for contradiction, $\nexists n$, $f_n=f_{n-1}$.
Then, $f_{n+1}\le\frac{f_{n}+f_{n-1}}{2}< \max (f_{n},f_{n-1})$, $f_{n+2}\le\frac{f_{n+1}+f_{n}}{2}< \max (f_{n},f_{n+1})\le\max (f_{n},f_{n-1})$
Thus, $\max (f_{n},f_{n-1})> \max (f_{n+1},f_{n+2})$ and that means that $\max (f_{2n},f_{2n+1})$ is a strictly decreasing function and it must reach $0$ as $n\rightarrow\infty$, which contradict with the fact that $f_n>0$.
Part 1 proven.

Part 2) Show that the constant is $\gcd(a,b)$.
For any $f_n$ where $\gcd(a,b)=d\ne1$. $f_n=dg_n$ for $g_n$ with the same property except with $g_1=\frac{a}{d}$ and $g_2=\frac{b}{d}$.
Therefore, if I prove that the constant for any $f_n$ with relatively prime $a$, $b$ is $1$, then I have shown that part 2 is true.
Lemma) If $\gcd(f_n,f_{n-1})=1$, then $\gcd(f_n,f_{n+1})=1$.
Assume for contradiction that $\gcd(f_n,f_{n+1})=d\ne1$, since both $f_n$ and $f_{n+1}$ are odd, $d$ is not divisible by $2$.
$f_{n+1}=\frac{f_n+f_{n-1}}{2^n}$ for some $n\in \mathbb{Z}^+$ such that $f_{n+1}$ is odd.
$(2^n)f_{n+1}-f_n=f_{n-1}$
$d(p+q)=f_{n-1}$, where $p$ and $q$ is another integer.
Thus, $f_{n-1}$ is divisible by $d$ which contradicts with the assumption that $\gcd(f_n,f_{n-1})=1$.
Lemma proven
By induction, $\gcd(f_n,f_{n-1})=1$ since $\gcd(a,b)=\gcd(f_1,f_2)=1$.
Since there must exist some $n$ where $f_n=f_{n+1}$ (part 1), $\gcd(f_n,f_{n+1})=f_n=1$.
$\mathbb{Q.E.D}$


Let $a_0, a_1, a_2,\cdots$ be a sequence of positive real numbers satisfying $a_{i-1}a_{i+1}\le a^2_i$
for $i = 1, 2, 3,\cdots$ . (Such a sequence is said to be log concave.) Show that for
each $n > 1$,

Solution:
Notice that because

we may subtract $\dfrac{(a_1 + a_2 + \dots + a_{n-1})(a_0 + a_1 + \dots + a_n)}{n^2}$ from both sides of the inequality and observe that it is sufficient to prove that

or
Fortunately, this is an easy inequality. Indeed, from AM-GM applied on each group of terms we have

and so it suffices to prove

or, after taking both sides to the $(n^2 - 1)$ power, simplifying, and taking the $n$-th root of both sides, to prove

This easily follows from the Fact that $a_0 a_n \le a_i a_{n-i}$ for $1 \le i \le n-1$. Indeed, we are given that

Multiply all inequalities together and cancel $a_1, a_2^2, a_3^2, \dots, a_{n-2}^2, a_{n-1}$ to give $a_0 a_n \le a_1 a_{n-1}$. Similarly, by multiplying all inequalities except the first and the last, we deduce that $a_2 a_{n-2} \ge a_1 a_{n-1} \ge a_0 a_n$, and a simple induction argument proves the verity of the Fact for $1 \le i \le \frac{n}{2}$, and so by the Commutative Property the Fact is true for all $1 \le i \le n-1$, as desired. Now multiply each inequality of the Fact for $i = 1, 2, 3, \dots, n-1$ to give the desired result.
Note: The Fact can be generalized into a Lemma: $a_x a_w \le a_y a_z$ whenever $x \le y \le z \le w$ and $x + w = y + z$. The proof is similar to that of the Fact and is left as an exercise to the reader.
--User suli, April 15, 2015.


Let $\, k_1 < k_2 < k_3 <\cdots\,$, be positive integers, no two consecutive, and let $\, s_m = k_1+k_2+\cdots+k_m\,$, for $\, m = 1,2,3,\ldots\;\;$. Prove that, for each positive integer $n$, the interval $\, [s_n, s_{n+1})\,$, contains at least one perfect square.

Solution:
We want to show that the distance between $s_n$ and $s_{n+1}$ is greater than the distance between $s_n$ and the next perfect square following $s_n$.
Given $s_n=\sum_{i=1}^{n}k_i$, where no $k_i$ are consecutive, we can put a lower bound on $k_n$. This occurs when all $k_{i+1}=k_i+2$:

Rearranging, $k_{n,min}=\frac{s_n}{n}+n-1$. So, $k_n\geq\frac{s_n}{n}+n-1$, and the distance between $s_n$ and $s_{n+1}$ is $k_{n+1}\geq k_n+2\geq\frac{s_n}{n}+n+1$.
Also, let $d(s_n)$ be the distance between $s_n$ and the next perfect square following $s_n$. Let's look at the function $d(x)$ for all positive integers $x$.
When $x$ is a perfect square, it is easy to see that $d(x)=2\sqrt{x}+1$.
Proof: Choose $x=m^2$. $d(m^2)=(m+1)^2-m^2=2m+1=2\sqrt{m^2}+1$.
When $x$ is not a perfect square, $d(x)<2\sqrt{x}+1$.
Proof: Choose $x=m^2+p$ with $0<p<2m+1$. $d(m^2+p)=(m+1)^2-m^2-p=2m+1-p<2m+1=2\sqrt{m^2}+1<2\sqrt{m^2+p}+1$.
So, $d(x)\leq 2\sqrt{x}+1$ for all $x$ and $d(s_n)\leq 2\sqrt{s_n}+1$ for all $s_n$.
Now, it suffices to show that $k_{n+1}\geq d(s_n)$ for all $n$.

So, $k_{n+1}\geq d(s_n)$ and all intervals between $s_n$ and $s_{n+1}$ will contain at least one perfect square.

We see that by increasing $n$ by some amount, we simply shift our interval by a finite amount. It suffices to consider the case $n=1$ (since this can be inducted across all positive integers). Let $k_1=x$. We want the smallest interval, so we have $[x, 2x+2]$. Simple induction reveals that the ration of consecutive squares grows slower than our linear bound. We now consider sufficiently small $x$ (where $\frac{(n+1)^2}{n^2}<2$). This first happens at $n=3$. By simple casework, our answer is as desired $\blacksquare$.

We will first prove by Induction on $n\in\mathbb{N}$ that $(k_{n}+1)^2\geq4(k_1+k_2+\cdots +k_{n}).$ Denote this statement by $P(n).$
For the Base Case let $n=1,$ we know that;
Hence, the Base Case holds.
For the Inductive Step, suppose that $P(m)$ holds for some $k\in\mathbb{N},$ we will prove that $P(m+1)$ holds as well.
Assume for contradiction that $P(m+1)$ doesn't hold, then we know that;
We know that since $k_m$ and $k_{m-1}$ are not consecutive, we have;
But this contradicts the Inductive Hypothesis that  thus our assumption was false and the Inductive Step is complete.
Hence, we have proved that $P(n)$ holds, and we will use $P(n)$ to solve the original problem.
Now suppose that for some positive integer $n$, the interval $\, [s_n, s_{n+1})\,$ does not contain any perfect square, then we know that there must exist two perfect squares of consecutive integers, such that the smaller one is lesser than $s_n$ and the larger one greater than or equal to $s_{n+1}.$
We thus know that there exists some $x\in\mathbb{N}$ such that;
By Inequality 1;
Hence, we know that;
Combining this with Inequality 2 gives;
We know that since $k_{n+1}$ are not consecutive, $k_n+1\leq k_{n+1}-1,$ hence, we have;
But this contradicts the statement $P(n)$ which was proved earlier.
$\square$


The sides of a $99$-gon are initially colored so that consecutive sides are red, blue, red, blue,..., red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides
are red, blue, red, blue, red, blue,..., red, yellow, blue?

Solution:
We proceed by representing the colors as numbers, i.e. Red = 0, Blue = 1, Yellow = 2. Thus, we start with some sequence 0101...012 and are trying to end up with the sequence 1010...0102. Generate a second sequence of terms by subtracting each term by the following term and taking it modulus 3, i.e. (1-0, 0-1, 1-0, 0-1, ... 0-1, 1-0, 0-2, 2-1) = 1212...2111 is the sequence generated using the start sequence. The sequence generated using the end sequence is (0-1, 1-0, 0-1, 1-0, ... 1-0, 0-1, 1-2, 2-0) = 2121...2122. Observe that the sum of terms generated by the start sequence is different from the sum of terms generated by the end sequence.
We must now prove that changing the color of a side does not change the sum of the generated sequence. We do this by noting that we can only change the color of a side if its adjacent sides have the same color as each other. Thus, changing a side does not change the sum of terms in the generated sequence, as the term generated by the changing side and the side to its left is simply the "negative" of the term generated by the changing side and the side to its right (i.e. 212 to 202 changes 12 to 21).
Since it is impossible to change the sum of terms in the generated sequence, and the sequences generated by the start and end sequences have two different sums, it is impossible to perform a series of such modifications that change the start sequence to the end sequence.


A convex hexagon $ABCDEF$ is inscribed in a circle such that $AB=CD=EF$ and diagonals $AD,BE$, and $CF$ are concurrent. Let $P$ be the intersection of $AD$ and $CE$. Prove that $\frac{CP}{PE}=(\frac{AC}{CE})^2$.

Solution:
Let the diagonals $AD$, $BE$, $CF$ meet at $Q$.
First, let's show that the triangles $\triangle AEC$ and $\triangle QED$ are similar.
$\angle ACE=\angle ADE$ because $A$,$C$,$D$ and $E$ all lie on the circle, and $\angle ADE=\angle QDE$. $\angle AEB=\angle CED$ because $AB=CD$, and $A$,$B$,$C$,$D$ and $E$ all lie on the circle. Then,
$\angle AEB=\angle CED \rightarrow \angle AEB+\angle BEC=\angle CED+\angle BEC \rightarrow \angle AEC=\angle QED$
Therefore, $\triangle AEC$ and $\triangle QED$ are similar, so $AC/CE=QD/DE$.
Next, let's show that $\triangle AEC$ and $\triangle CDQ$ are similar.
$\angle AEC=\angle ADC$ because $A$,$C$,$D$ and $E$ all lie on the circle, and $\angle ADC=\angle CDQ$. $\angle EAD=\angle ECD$ because $A$,$C$,$D$ and $E$ all lie on the circle. $\angle DAC=\angle ECF$ because $CD=EF$, and $A$,$C$,$D$,$E$ and $F$ all lie on the circle. Then,
$\angle EAC=\angle EAD+\angle DAC=\angle ECD+\angle ECF=\angle DCQ$
Therefore, $\triangle AEC$ and $\triangle CDQ$ are similar, so $AC/CE=CQ/QD$.
Lastly, let's show that $\triangle CPQ$ and $\triangle EPD$ are similar.
Because $CD=EF$ and $C$,$D$,$E$ and $F$ all lie on the circle, $CF$ is parallel to $DE$. So, $\triangle CPQ$ and $\triangle EPD$ are similar, and $CQ/DE=CP/PE$.
Putting it all together, $\frac{CP}{PE}=\frac{CQ}{DE}=\frac{AC}{CE}\cdot \frac{QD}{DE}=(\frac{AC}{CE})^2$.
Borrowed from https://mks.mff.cuni.cz/kalva/usa/usoln/usol943.html