The symbols $(a,b,\ldots,g)$ and $[a,b,\ldots, g]$ denote the greatest common divisor and least common multiple, respectively, of the positive integers $a,b,\ldots, g$. For example, $(3,6,18)=3$ and $[6,15]=30$. Prove that

Consider an arbitrary prime $p$. Let $p^\alpha$, $p^\beta$, and $p^\gamma$ be the greatest powers of $p$ that divide $a$, $b$, and $c$.
WLOG let $\alpha \leq \beta \leq \gamma$.
Examining each factor in the equation, we see that the largest power of $p$ that divides the left hand side is $2\gamma -(\beta+\gamma+\gamma) = -\beta$, and the largest power of $p$ that divides the right hand side is 2\alpha -($\alpha + \beta + \alpha) = -\beta$. Since every prime has the same power in both expressions, the expressions are equal. $\blacksquare$

Let $p = (a, b, c)$, $pq = (a, b)$, $pr = (b, c)$, and $ps = (c, a)$. Then it follows that $q, r, s$ are pairwise coprime and $a = pqsa'$, $b = pqrb'$, and $c = prsc'$, with $a', b', c'$ pairwise coprime as well. Then, we wish to show

which can be checked fairly easily.

Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.
Dividing both sides of the equation by $(a,b,c)^2$, and then multiplying both sides by $[a,b][b,c][c,a]$ gives us
Now, we look at the prime factorisations of $a,b,c$. Let

where all of the $x_1, y_1, z_1$ are nonnegative integers (they could be 0).
Thus, we have
and
Now, we see that $\left(\frac{[a,b,c]}{(a,b,c)}\right) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.$ Squaring the LHS will just double all the exponents on the RHS.
Also, we have $[a,b]=2^{\max(x_1,y_1)} \cdot 3^{\max(x_2,y_2)} \cdot 5^{\max(x_3,y_3)} \cdots$. We can also build similar equations for $[b,c],[c,a],(a,b),(b,c)(c,a)$, using 2 of $x,y,z$ and either the minimum of the exponents or the maximum.
We see that when we multiply $[a,b]$, $[b,c]$, and $[a,c]$ together, the exponents of the prime factorization will be $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(z_i,x_1)$, where $i$ is chosen for the $i$'th prime.
When we multiply $(a,b)$, $(b,c)$, and $(a,c)$ together, the exponents of the prime factorization will be $\min(x_i,y_i)+ \min(y_i,z_i)+ \min(z_i,x_1)$, where $i$ is chosen for the $i$'th prime.
Thus, when we divide the former by the latter, we have $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))$. We wish to prove that this is equal to the exponents we got from $([a,b,c]/(a,b,c))^2$.
In other words, this problem is now down to proving that  for any nonnegative integers $x_i, y_i, z_i$. WLOG, let $x_i \le y_i \le z_i$. Thus, computing maximums and minimums, this equation turns into
Finally, canceling out the $y_i$'s and collecting like terms, we see the RHS is $2z_i - 2x_i$, which is equal to the LHS. Thus, this equation is true, and we are done. $\square$

Let
where $\gcd(A,B,C)=\gcd(x,y,z)=1$. (Existence proof missing.) Then, $\operatorname{lcm}(a,b,c)^2=(dxyzABC)^2$ and $\operatorname{lcm}(a,b)=dxyzAB$. Using this cyclically, we have
Now, note that $\gcd(a,b,c)^2=d^2$ and $\gcd(a,b)=dx$. Using this cyclically, we have

-brainiacmaniac31
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A given tetrahedron $ABCD$ is isosceles, that is, $AB=CD, AC=BD, AD=BC$. Show that the faces of the tetrahedron are acute-angled triangles.

Suppose $\triangle ABD$ is fixed.
By the equality conditions, it follows that the maximal possible value of $BC$ occurs when the four vertices are coplanar, with $C$ on the opposite side of $\overline{AD}$ as $B$.
In this case, the tetrahedron is not actually a tetrahedron, so this maximum isn't actually attainable.
For the sake of contradiction, suppose $\angle ABD$ is non-acute.
Then, $(AD)^2\geq (AB)^2+(BD)^2$.
In our optimal case noted above, $ACDB$ is a parallelogram, so

However, as stated, equality cannot be attained, so we get our desired contradiction.

It's not hard to see that the four faces are congruent from SSS Congruence. Without loss of generality, assume that $AB\leq BC \leq CA$. Now assume, for the sake of contradiction, that each face is non-acute; that is, right or obtuse. Consider triangles $\triangle ABC$ and $\triangle ABD$. They share side $AB$. Let $k$ and $l$ be the planes passing through $A$ and $B$, respectively, that are perpendicular to side $AB$. We have that triangles $ABC$ and $ABD$ are non-acute, so $C$ and $D$ are not strictly between planes $k$ and $l$. Therefore the length of $CD$ is at least the distance between the planes, which is $AB$. However, if $CD=AB$, then the four points $A$, $B$, $C$, and $D$ are coplanar, and the volume of $ABCD$ would be zero. Therefore $CD>AB$. However, we were given that $CD=AB$ in the problem, which leads to a contradiction. Therefore the faces of the tetrahedron must all be acute.

Let $\vec{a} = \overrightarrow{DA}$, $\vec{b} = \overrightarrow{DB}$, and $\vec{c} = \overrightarrow{DC}$. The conditions given translate to

We wish to show that $\vec{a}\cdot\vec{b}$, $\vec{b}\cdot\vec{c}$, and $\vec{c}\cdot\vec{a}$ are all positive. WLOG, $\vec{a}\cdot\vec{a}\geq \vec{b}\cdot\vec{b}, \vec{c}\cdot\vec{c} > 0$, so it immediately follows that $\vec{a}\cdot\vec{b}$ and $\vec{a}\cdot\vec{c}$ are positive. Adding all three equations,

In addition,

Equality could only occur if $\vec{a} = \vec{b} + \vec{c}$, which requires the vectors to be coplanar and the original tetrahedron to be degenerate.

Suppose for the sake of contradiction that $\angle BAC$ is not acute. Since all three sides of triangles $BAC$ and $CDB$ are congruent, those two triangles are congruent, meaning $\angle BDC=\angle BAC>90^{\circ}$. Construct a sphere with diameter $BC$. Since angles $BAC$ and $BDC$ are both not acute, $A$ and $D$ both lie on or inside the sphere. We seek to make $AD=BC$ to satisfy the conditions of the problem. This can only occur when $AD$ is a diameter of the sphere, since both points lie on or inside the sphere. However, for $AD$ to be a diameter, all four points must be coplanar, as all diameters intersect at the center of the sphere. This would make tetrahedron $ABCD$ degenerate, creating a contradiction. Thus, all angles on a face of an isosceles tetrahedron are acute.

Proof by contradiction: Assume at least one of the tetrahedron's faces are obtuse. WLOG, assume $\angle BAC$ is an obtuse angle. Using SSS congruence to prove that all four faces of the tetrahedron are congruent also shows that the angles surrounding point $A$ are congruent to angles in triangle $ABC$; namely, $\angle BAD$ is congruent to $\angle ABC$, and $\angle CAD$ is congruent to $\angle ACB$. Since the internal angles of triangle $ABC$ must add to 180 degrees, so do the angles surrounding point A. Now lay triangle $ABC$ on a flat surface. A diagram would make it clear that from the perspective of an aerial view, the "apparent" measures of $\angle BAD$ and $\angle CAD$ (which are most likely distorted visually, assuming these angles stick up vertically from the flat surface on which triangle $ABC$ lies) can never exceed the true measures of those angles (equality happens when these angles also lie flat on top of triangle $ABC$). This means that these two angles can never join to form side AD (because $\angle BAC$ is more than the sum of $\angle BAD$ and $\angle CAD$ - a direct consequence of the facts that $\angle BAC$ is obtuse and all three angles add up to 180 degrees), so the tetrahedron with obtuse triangle faces is impossible.

Lemma: given triangle $ABC$ and the midpoint of $BC$, which we will call $M$, we can say that if $AM > \frac{BC}{2}$, then $\angle A < 90$.
Proof: Since $M$ is the midpoint of $BC$, $BM = MC = \frac{BC}{2}$. Since it is given that $AM > \frac{BC}{2}$, we can substitute $\frac{BC}{2}$ to get two inequalities:

The above inequalities imply that $\angle C > \angle CAM$ and $\angle B > \angle BAM$. Adding these inequalities and simplifying the RHS, we have that $\angle C + \angle B > \angle A$. Adding $\angle A$ to both sides, replacing the LHS with $180$ and dividing by $2$ gets us that $\angle A < 90$. This is our desired inequality, so we are done.
Note that all faces of this tetrahedron are congruent, by SSS.
In particular, we will use that $\triangle ABD \cong \triangle BAC$. WLOG, assume that $\angle ADB$ is the largest angle in triangle $ABD$.
Because $\triangle ABD \cong \triangle BAC$, the median from $D$ to $AB$ is equal length to the median from $C$ to $AB$. These points meet at $E$, the midpoint of $AB$. By the triangle inequality,
By substituting $CD$ with $AB$ (this is a given in the problem) and $CE$ with $DE$, and then dividing by $2$, we get that
By the lemma we showed at the start, this implies that $\angle ADB < 90$, and since we said that $\angle ADB$ was the largest angle, triangle $ADB$ must be acute. Since all of the faces of this tetrahedron are congruent, then, all of the faces must be acute.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after $n$ selections ($n>1$), the product of the $n$ numbers selected will be divisible by 10.

Solution:
For the product to be divisible by 10, there must be a factor of 2 and a factor of 5 in there.
The probability that there is no 5 is $\left( \frac{8}{9}\right)^n$.
The probability that there is no 2 is $\left( \frac{5}{9}\right)^n$.
The probability that there is neither a 2 nor 5 is $\left( \frac{4}{9}\right)^n$, which is included in both previous cases.
The only possibility left is getting a 2 and a 5, making the product divisible by 10.
By complementarity and principle of inclusion-exclusion, the probability of that is $1- \left( \left( \frac{8}{9}\right)^n + \left( \frac{5}{9}\right)^n - \left( \frac{4}{9}\right)^n\right)=\boxed{1-(8/9)^n-(5/9)^n+(4/9)^n}$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $R$ denote a non-negative rational number. Determine a fixed set of integers $a,b,c,d,e,f$, such that for every choice of $R$,

Solution:
Note that when $R$ approaches $\sqrt[3]{2}$, $\frac{aR^2+bR+c}{dR^2+eR+f}$ must also approach $\sqrt[3]{2}$ for the given inequality to hold. Therefore

which happens if and only if

We cross multiply to get $a\sqrt[3]{4}+b\sqrt[3]{2}+c=2d+e\sqrt[3]{4}+f\sqrt[3]{2}$. It's not hard to show that, since $a$, $b$, $c$, $d$, $e$, and $f$ are integers, then $a=e$, $b=f$, and $c=2d$.
Note, however, that this is a necessary but insufficient condition. For example, we must also have $a^2<2bc$ to ensure the function does not have any vertical asymptotes (which would violate the desired property). A simple search shows that $a=0$, $b=2$, and $c=2$ works.


A given convex pentagon $ABCDE$ has the property that the area of each of the five triangles $ABC$, $BCD$, $CDE$, $DEA$, and $EAB$ is unity. Show that all pentagons with the above property have the same area, and calculate that area. Show, furthermore, that there are infinitely many non-congruent pentagons having the above area property.

Solution:
Lemma: Convex pentagon $A_0A_1A_2A_3A_4$ has the property that $[A_0A_1A_2] = [A_1A_2A_3] = [A_2A_3A_4] = [A_3A_4A_0] = [A_4A_0A_1]$ if and only if $\overline{A_{n - 1}A_{n + 1}}\parallel\overline{A_{n - 2}A_{n + 2}}$ for $n = 0, 1, 2, 3, 4$ (indices taken mod 5).
Proof: For the "only if" direction, since $[A_0A_1A_2] = [A_1A_2A_3]$, $A_0$ and $A_3$ are equidistant from $\overline{A_1A_2}$, and since the pentagon is convex, $\overline{A_0A_3}\parallel\overline{A_1A_2}$. The other four pairs of parallel lines are established by a symmetrical argument, and the proof for the other direction is just this, but reversed.

Let $A'B'C'D'E'$ be the inner pentagon, labeled so that $A$ and $A'$ are opposite each other, and let $a, b, c, d, e$ be the side lengths of the inner pentagon labeled opposite their corresponding vertices. From the lemma, pentagon $A'B'C'D'E'$ is similar to pentagon $ABCDE$ with $AB = m(A'B')$ and parallelogram $ABCB'$ (and cyclic) has area 2. Supposing

we have

Since $BCDC'$ and $CDED'$ are parallelograms, $BD' = EC' = (m - 1)a$. Triangle $EB'C'$ is similar to triangle $ECB$, so $me = BC = \left(\frac{2m - 1}{m - 1}\right)e$, and with the requirement that $m > 1$,

Now, we compute that $[AC'D'] = \frac{1}{2m - 1} = \sqrt{5} - 2$, and similar computation for the other four triangles gives $R = 5\sqrt{5} - 10$. From the aforementioned pentagon similarity, $Q = P/m^2 = \left(\frac{7 - 3\sqrt{5}}{2}\right)P$. Solving for $P$, we have
To show that there are infinitely many pentagons with the given property, we start with triangle $A'B'C'$ and construct the original pentagon using the required length ratios. This triangle has three continuous degrees of freedom, and the condition that the equal areas be specifically unity means that there are two continuous degrees of freedom in which the configuration can vary, which implies the desired result.
Alternatively, one can shear a regular pentagon, a transformation which preserves areas and the property of a pair of lines being parallel.


Two points $P$ and $Q$ lie in the interior of a regular tetrahedron $ABCD$. Prove that angle $PAQ < 60^\circ$.

Let the side length of the regular tetrahedron be $a$. Link and extend $AP$ to meet the plane containing triangle $BCD$ at $E$; link $AQ$ and extend it to meet the same plane at $F$. We know that $E$ and $F$ are inside triangle $BCD$ and that $\angle PAQ = \angle EAF$
Now let’s look at the plane containing triangle $BCD$ with points $E$ and $F$ inside the triangle. Link and extend $EF$ on both sides to meet the sides of the triangle $BCD$ at $I$ and $J$, $I$ on $BC$ and $J$ on $DC$. We have $\angle EAF < \angle IAJ$
But since $E$ and $F$ are interior of the tetrahedron, points $I$ and $J$ cannot be both at the vertices and $IJ < a$, $\angle IAJ < \angle BAD = 60$. Therefore, $\angle PAQ < 60$.
Solution with graphs posted at
http://www.cut-the-knot.org/wiki-math/index.php?n=MathematicalOlympiads.USA1973Problem1
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
hurdler: Remark on solution 1: This proof is not rigorous, in the very last step. The last step needs more justification.


Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined as follows:
Thus, the first few terms of the sequences are:
Prove that, except for the "1", there is no term which occurs in both sequences.

Solution:
We can look at each sequence $\bmod{8}$:
The third and fourth terms are $3$ and $5$ $\bmod{8}$. Plugging into the formula, we see that the next term is $11\equiv 3\bmod{8}$, and plugging $5$ and $3$, we get that the next term is $13\equiv 5\bmod{8}$. Thus the sequence $X$ repeats, and the pattern is $3,5,3,5,\dots$.
The first and second terms are $1$ and $7$ $\bmod{8}$. Plugging into the formula, we see that the next term is $17\equiv 1\bmod{8}$, and plugging $7$ and $1$, we get that the next term is $23\equiv 7\bmod{8}$. Thus the sequence $Y$ repeats, and the pattern is $1,7,1,7,\dots$.

Combining both results, we see that $X_i$ and $Y_j$ are not congruent $\bmod{8}$ when $i\geq 3$ and $j\geq 2$. Thus after the "1", the terms of each sequence are not equal.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Three distinct vertices are chosen at random from the vertices of a given regular polygon of $(2n+1)$ sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points?

Solution:
There are $\binom{2n+1}{3}$ ways how to pick the three vertices. We will now count the ways where the interior does NOT contain the center. These are obviously exactly the ways where all three picked vertices lie among some $n+1$ consecutive vertices of the polygon.
We will count these as follows: We will go clockwise around the polygon. We can pick the first vertex arbitrarily ($2n+1$ possibilities). Once we pick it, we have to pick $2$ out of the next $n$ vertices ($\binom{n}{2}$ possibilities).
Then the probability that our triangle does NOT contain the center is
And then the probability we seek is


Determine all the roots, real or complex, of the system of simultaneous equations

Solution: Let $x$, $y$, and $z$ be the roots of the cubic polynomial $t^3+at^2+bt+c$. Let $S_1=x+y+z=3$, $S_2=x^2+y^2+z^2=3$, and $S_3=x^3+y^3+z^3=3$. From this, $S_1+a=0$, $S_2+aS_1+2b=0$, and $S_3+aS_2+bS_1+3c=0$. Solving each of these, $a=-3$, $b=3$, and $c=-1$. Thus $x$, $y$, and $z$ are the roots of the polynomial $t^3-3t^2+3t-1=(t-1)^3$. Thus $x=y=z=1$, and there are no other solutions.

Let $P(t)=t^3-at^2+bt-c$ have roots x, y, and z. Then  using our system of equations, so $P(1)=0$. Thus, at least one of x, y, and z is equal to 1; without loss of generality, let $x=1$. Then we can use the system of equations to find that $y=z=1$ as well, and so $\boxed{(1,1,1)}$ is the only solution to the system of equations.

Let $a=x-1,$ $b=y-1$ and $c=z-1.$ Then

We have

Then one of $a, b$ and $c$ has to be 0, and easy to prove the other two are also 0. So $\boxed{(1,1,1)}$ is the only solution to the system of equations.
J.Z.

We are going to use Intermediate Algebra Techniques to solve this equation.
Let's start with the first one: $x+y+z=3$. This will be referred as the FIRST equation.
We are going to use the first equation to relate to the SECOND one ($x^2+y^2+z^2=3$) and the THIRD one ($x^3+y^3+z^3=3)$.
Squaring this equation: $x^2+y^2+z^2+2xy+2yz+2xz=9$
Subtracting this equation from the 2nd equation in the problem, we have $2xy+2yz+2xz=6$, so $xy+xz+yz=3$.
Now we try the same idea with the cubed terms. Cube the first equation:
$x^3+y^3+z^3+3xy^2+3xz^2+3yx^2+3yz^2+3zx^2+3zy^2=27$. Plug in $x^3+y^3+z^3=3$ and factor partially:
$3+3(x^2(y+z)+y^2(x+z)+z^2(x+y))+6xyz=27$.
Now here is the key step. Note that $z=3-x-y, y=3-x-z, x=3-y-z$. So we are going to substitute $y+z, x+z, x+y$ for each of the expressions and we get: $-x^3+3x^2-y^3+3y^2-z^3+3z^2=8-2xyz$ (I rearranged it a bit).
Resubstituting in the second and third equation: $-3+3(3)=8-2xyz$. So $xyz=1$.
So now we have three equations for the elementary symmetric sums of $x,y,z$:
Equation 4: $x+y+z=3$ (this is also equation 1)
Equation 5: $xy+yz+xz=3$
Equation 6: $xyz=1$.
If we call the solutions of $t^3-3t^2+3t-1=0$ (Equation 7) $a,b,c$, then $x,y,z$ are the three roots $a,b,c$ but in some order. Notice that Equation 7 can be factored as $(t-1)^3=0$, which means that $t=1$. Therefore $(x,y,z)$ are permutations of $(1,1,1)$ in some order, which can be only $(1,1,1)$. (This step uses Vieta's formulas)
Therefore, the only solution is $\boxed{(x,y,z)=(1,1,1)}$.
~hastapasta

From the question
Equation 1 : $x+y+z=3$
Equation 2 : $x^2+y^2+z^2=3$
Equation 3 : $x^3+y^3+z^3=3$
From Eq(1) and Eq(2),
Equation 4 : $(x+y+z)^2=9 \implies x^2+y^2+z^2+2\sum xy = 9 \implies \sum xy = 3$
From Eq(1), Eq(3), and the fact that $(x+y+z)^3=x^3+y^3+z^3+3\prod(x+y)$,
Equation 5 : $(x+y+z)^3=x^3+y^3+z^3+3\prod(x+y)= 27 \implies \prod(x+y)=8$
As from Eq(1),  $\ x+y=3-z$,$\ y+z=3-x$,  $\ z+x = 3- y$
Equation 6 : $\prod(3-x) =8$
Now let there be a cubic function $f(t)$ with the roots $x,y,z$ so from the relation between roots and coefficients,
Equation 7 : $f(t)= t^3-3t^2+3t-d$   (As we don't know the product let the constant be $d$)
As $f(t) = (t-x)(t-y)(t-z)$ then at $t=3$,
Equation 8 : $f(3)=9-d=(3-x)(3-y)(3-z)$
And from Eq(6),
Equation 9 : $d= -1$
So finally,
Equation 10 : $f(t)=t^3-3t^2+3t-1=(t-1)^{3}$
So, $\ (x,y,z)=(1,1,1)$
~Sparrow_1827
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression.

Solution:
Assume that the cube roots of three distinct prime numbers can be three terms of an arithmetic progression. Let the three distinct prime numbers be $p$, $q$, and $r.$ WLOG, let $p<q<r.$
Then,

where $m$, $n$ are distinct integers, and $d$ is the common difference in the progression. Then we have

Because $p$, $q$, $r$ are distinct primes, $pqr$ is not a perfect cube. Thus, the LHS is irrational but the RHS is rational, which is a contradiction. So, the cube roots of three distinct prime numbers cannot be three terms of an arithmetic progression.

Assume the contrary and suppose that the cube roots of three distinct prime numbers, $p_1^\frac{1}{3}$, $p_2^\frac{1}{3}$, and $p_3^\frac{1}{3}$, form an increasing arithmetic progression. Then we can write $p_2^\frac{1}{3} = p_1^\frac{1}{3} + md$ and $p_3^\frac{1}{3} = p_1^\frac{1}{3} + nd$ for some positive integral $d, m, n$ with $m < n$. Thus,

for some real $r$. Because $m$ and $n$ are integral, r is rational.
This equation rearranges to
Note that if $a-b=x$, then  from the binomial theorem. As a result, cubing both sides of the equation gives
Lemma: The sum, product, and difference of two rational numbers are all rational, and that of a rational and irrational number are all irrational.
Proof: The first part is trivial if we write the fractions as $\frac{m}{n}$ and $\frac{p}{q}$, and find the common denominators or simplify fractions as
needed. The second part follows by contradiction: if the sum of a rational number and irrational number is rational, then the irrational number must be the difference of two rational numbers, which is rational. This is a contradiction; likewise for difference and product.
The LHS (left-hand side) of (*) is clearly rational (in fact, integral), and so the RHS must also be rational. This is the case for the first two terms $r^3p_2$ and $-(r-1)^3p_1$. But it is not the case for the third term. The number $(p_1p_2p_3)^\frac{1}{3}$ is irrational because $p_1p_2p_3$, the product of three distinct primes, cannot be a perfect cube. Hence, $-3r(r-1)(p_1p_2p_3)^\frac{1}{3}$, the product of a rational and an irrational number, is irrational, and the RHS is therefore the sum of two rational terms and one irrational term. This is irrational by the lemma, and hence we have a rational equalling an irrational, contradiction. It follows that the cube roots of three distinct prime numbers cannot form an arithmetic sequence.


Let $a$, $b$, and $c$ denote three distinct integers, and let $P$ denote a polynomial having all integral coefficients.  Show that it is impossible that $P(a)=b$, $P(b)=c$, and $P(c)=a$.

Solution:
It suffices to show that if $a,b,c$ are integers such that $P(a) = b$, $P(b)=c$, and $P(c)= a$, then $a=b=c$.
We note that

so the quanitities $(a-b), (b-c), (c-a)$ must be equal in absolute value.  In fact, two of them, say $(a-b)$ and $(b-c)$, must be equal.  Then

so $a=b= P(a)$, and $c= P(b) = P(a) = b$, so $a$, $b$, and $c$ are equal, as desired.  $\blacksquare$

Let $k$ be the value $(a-b), (b-c), (c-a)$ are equal to in absolute value. Assume $k$ is nonzero. Then each of $(a-b), (b-c), (c-a)$ is equal to $k$ or $-k$, so  where $m$ is one of -3, -1, 1, or 3. In particular, neither $m$ nor $k$ is zero, contradiction. Hence, $k = 0$, and $a, b, c$ are equal, yielding a final contradiction of the existence of these variables. $\blacksquare$
In fact, this approach generalizes readily. Suppose that $n$ is an odd integer, and that there exist $n$ distinct integers $a_1, a_2, ..., a_n$ such that $P(a_i) = a_{i+1}$ and $P(a_n) = 1$, for $1 \le i \le n-1$. Then we have  so the differences are all equal in absolute value and thus equal to $k$ or $-k$ for some integer $k$. Adding the differences (in the order they are written) gives $0 = mk$ for some odd integer $m$, so $m$ is nonzero and hence $k = 0$. Thus, all the $a_i$ are equal, a contradiction of their distinctness, so the sequence $a_i$ cannot exist.

Consider the polynomial $Q(x) = (b-a)P(x) - (c-b)x - b^2 + ac.$ By using the facts that $P(a) = b$ and $P(b) = c$, we find that $Q(a) = Q(b) = 0.$ Thus, the polynomial $Q(x)$ has a and b as roots, and we can write $Q(x) = (x-a)(x-b)R(x)$ for some polynomial $R(x)$. Because $Q(x)$ and $(x-a)(x-b)$ are monic polynomials with integral coefficients, their quotient, $R(x)$, must also have integral coefficients, as can be demonstrated by simulating the long division. Thus, $Q(c)$, and hence $Q(c) - (x-a)(x-b)$, must be divisible by $(c-a)(c-b)$. But if $x=c-a$ and $y=c-b$, then we must have, after rearranging terms and substitution, that $(x-y)^2$ is divisible by $xy$. Equivalently, $S = x^2 + y^2$ is divisible by $xy$ (after canceling the $2xy$ which is clearly divisble by $xy$). Because S must be divisible by both x and y, we quickly deduce that x is divisible by y and y is divisible by x. Thus, x and y are equal in absolute value. A similar statement holds for a cyclic pemutation of the variables, and so x, y, and z are all equal in absolute value. The conclusion follows as in the first solution.

Assume for the sake of contradiction that is possible for unique integers $a,b,c$. Let $P(x)=d_1x^n+d_2x^{n-1}+\cdots+d_n.$ Note that

Subtracting the second from the first, third from second, and first from third gives

 By the RHS, note that $a-b\mid P(a)-P(b)$ so $\lvert{a-b}\rvert\leq\lvert{b-c}\rvert.$  Similarly, $\lvert{b-c}\rvert\leq\lvert{c-a}\rvert$ and $\lvert{c-a}\rvert\leq\lvert{a-b}\rvert.$  Hence, $\lvert{a-b}\rvert\leq\lvert{b-c}\rvert\leq\lvert{c-a}\rvert\leq\lvert{a-b}\rvert$ so $\lvert{a-b}\rvert=\lvert{b-c}\rvert=\lvert{c-a}\rvert.$  Assume WLOG that $a>b>c$ so $a-b=a-c$ and $b-c=c-a.$  From the first equation, we get $b=c$ and substituting this in the second gives $c=a.$  Hence, $a=b=c$, contradicting the uniqueness of $a,b,c.$ $\blacksquare$

Assume that $a, b$ and $c$ are distinct integers which satisfy the given conditions. Then we have $P(c) = P(P(b)) = P(P(P(a))) = a$. Similarly $P(P(P(b))) = b$ and $P(P(P(c))) = c$. Since the polynomial has integer coefficients, this implies that the polynomial $P$ is $P(x) = x$. But this is a contradiction since then $P(a) = b$ can only be true if $a = b$ which contradicts the fact that $a, b$ and $c$ are distinct integers.

We get that $a-b|b-c, b-c|c-a, c-a|a-b$. Thus, we can say that $(b-c) = (a-b)k, (c-a) = (b-c)j, (a-b) = (c-a)m$, for non zero integers, not necesarily positive, k, j, and m. Multiplying these equations and canceling, we get that $kjm$=1. This means that either k=1, m=1, j=1, or two of the variables are equal to 1 and the other is equal to -1. If all of the variables are equal to zero, plugging in gives us that $a=b=c$, contradictory to the conditions given in the problem statement. If two of the variables are equal to -1, and the other is equal to 1, then WLOG let $k=m=-1, j=1$. But this implies that the distinct integer condition is not satisfied, and hence, this case is invalid. Thus, it is impossible. $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Prove that if $a$, $b$, and $c$ are positive real numbers, then

Consider the function $f(x)=x\ln{x}$. $f''(x)=\frac{1}{x}>0$ for $x>0$; therefore, it is a convex function and we can apply Jensen's Inequality:
Apply AM-GM to get
which implies
Rearranging,
Because $f(x) = e^x$ is an increasing function, we can conclude that:
which simplifies to the desired inequality.

Note that $(a^ab^bc^c)(a^bb^cc^a)(a^cb^ac^b)=\left((abc)^{(a+b+c)/3}\right)^3$.
So if we can prove that $a^ab^bc^c\ge a^bb^cc^a$ and $a^ab^bc^c\ge a^cb^ac^b$, then we are done.
WLOG let $a\ge b\ge c$.
Note that $(a^ab^bc^c)\cdot \left(\dfrac{c}{a}\right)^{a-b}\cdot \left(\dfrac{c}{b}\right)^{b-c}=a^bb^cc^a$. Since $\dfrac{c}{a} \le  1$, $\dfrac{c}{b} \le  1$, $a-b \ge 0$, and $b-c \ge 0$, it follows that $a^ab^bc^c \ge a^bb^cc^a$.
Note that $(a^ab^bc^c)\cdot \left(\dfrac{b}{a}\right)^{a-b}\cdot \left(\dfrac{c}{a}\right)^{b-c}=a^cb^ac^b$. Since $\dfrac{b}{a} \le  1$, $\dfrac{c}{a} \le  1$, $a-b \ge 0$, and $b-c \ge 0$, it follows that $a^ab^bc^c \ge a^cb^ac^b$.
Thus, $(a^ab^bc^c)^3\ge (a^ab^bc^c)(a^bb^cc^a)(a^cb^ac^b)=\left((abc)^{(a+b+c)/3}\right)^3$, and cube-rooting both sides gives $a^ab^bc^c\ge (abc)^{(a+b+c)/3}$ as desired.

WLOG let $a\ge b\ge c$. Let $b = ax$ and $c = ay$, where $x \ge 1$ and $y \ge 1$.
We want to prove that $(a)^{a}(ax)^{ax}(ay)^{ay} \ge (a \cdot ax \cdot ay)^{\frac{a + ax + ay}{3}}$.
Simplifying and combining terms on each side, we get $a^{a + ax + ay}x^{ax}y^{ay} \ge a^{a + ax + ay}(xy)^{\frac{a + ax + ay}{3}}$.
Since $a > 0$, we can divide out $a^{a + ax + ay}$ to get $x^{ax}y^{ay} \ge (xy)^{\frac{a + ax + ay}{3}}$.
Take the $a$th root of each side and then cube both sides to get $x^{3x}y^{3y} \ge (xy)^{1 + x + y}$.
This simplifies to $x^{2x-1}y^{2y-1} \ge x^{y}y^{x}$.
Since $2x - 1 \ge x$ and $2y - 1 \ge y$, we only need to prove $x^{x}y^{y} \ge x^{y}y^{x}$ for our given $x, y$.
WLOG, let $y \ge x$ and $y =kx$ for $k \ge 1$. Then our expression becomes
$x^{x}(xk)^{xk} \ge x^{xk}(xk)^{x}$
$x^{x+xk}k^{xk} \ge x^{x+xk}k^{x}$
$k^{xk} \ge k^{x}$
$k^k \ge k$
This is clearly true for $k \ge 1$.

WLOG let $a\ge b\ge c$. Then sequence $(a,b,c)$ majorizes $(\frac{a+b+c}{3},\frac{a+b+c}{3},\frac{a+b+c}{3})$. Thus by Muirhead's Inequality, we have $\sum_{sym} a^ab^bc^c \ge \sum_{sym} a^{\frac{a+b+c}{3}}b^{\frac{a+b+c}{3}}c^{\frac{a+b+c}{3}}$, so $a^ab^bc^c \ge (abc)^{\frac{a+b+c}{3}}$.

Let $x=\frac{a}{\sqrt[3]{abc}},$ $y=\frac{b}{\sqrt[3]{abc}}$ and $z=\frac{c}{\sqrt[3]{abc}}.$ Then $xyz=1$ and a straightforward calculation reduces the problem to

WLOG, assume $x\ge y\ge z.$ Then $x\ge 1,$ $z\le 1$ and $xy=\frac{1}{z} \ge 1.$ Therefore,
J.Z.

Cubing both sides of the given inequality gives
If we take $a^{3a}b^{3b}c^{3c}$ as the product of $3a$ $a$'s, $3b$ $b$'s, and $3c$ $c's$, we get that
by GM-HM, as desired.

Replacing $a$ with $ak$, $b$ with $bk$, and $c$ with $ck$, for some positive real $k$ we get:
$a^{ak}k^{ak}b^{bk}k^{bk}c^{ck}k^{ck} = a^{ak}b^{bk}c^{ck}k^{ak+bk+ck} \ge {k^3abc}^{{ak+bk+ck}/3} = k^{ak+bk+ck}{abc}^{{ak+bk+ck}/3}$
This means that this inequality is homogeneous since both sides have the same power of $k$ as a factor. Since the inequality is homogeneous, we can scale $abc$ so that their product is $1$, i.e. $abc = 1$. This makes the inequality turn into something much more nicer to deal with. Now we have to prove:
$a^ab^bc^c \ge 1$ given that $abc = 1$.
Note that $a^a \ge a$ even if $a \le 1$. Therefore $a^a \ge a$, $b^b \ge b$, and $c^c \ge c$. Multiplying these together we get:
$a^ab^bc^c \ge abc = 1$. This proves the desired result. Equality holds when $a = b = c = 1$.

Let $\log_2a=x$, $\log_2b=y$ and $\log_2c=z$, and WLOG $a\ge b\ge c >0$.
Then we have both $a\ge b\ge c$ and $x\ge y \ge z$.
By the rearrangement inequality,
$ax+by+cz\ge ay + bz +cx$ and
$ax+by +cz\ge az+bx+cy$.
Summing,
$2(ax+by+cz)\ge a(y+z)+b(x+z)+c(x+y)$
Adding $ax+by+cz$,we get
$ax+by+cz\ge \frac{(a+b+c)(x+y+z)}{3}$.
Now we substitute back for $x,y,z$ to get:
$\log_2a^ab^bc^c\ge \log_2(abc)^{\frac{a+b+c}{3}}$.
Raising $2$ to the power of each side, we get
$a^ab^bc^c\ge (abc)^{\frac{a+b+c}{3}}$

Assume without loss of generality that $a\le b\le c$. Then, we have

It follows that

We can "distribute" the exponents, which gives

Notice that in the $b^{(c-b)/3}$ in the denominator of the third fraction can be brought out of the denominator by negating its exponent. This gives

We can move around terms on the left to get

Now we combine the exponents in the numerators. This gives

We multiply both sides by $\left(a^{(b-a)/3}\right)\left(a^{(c-a)/3}\right),$ which gives

We then multiply both sides by $\left(b^{(c-a)/3}\right)\left(c^{(b-a)/3}\right):$

Multiplying both sides by $\left(b^{(b-a)/3}\right)\left(c^{(c-a)/3}\right),$ then simplifying both sides with exponent laws, gives

Finally, we multiply both sides by $(abc)^a.$ Combining exponents one last time gives the desired

--MenuThreeOne
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Two boundary points of a ball of radius 1 are joined by a curve contained in the ball and having length less than 2. Prove that the curve is contained entirely within some hemisphere of the given ball.

Solution:
Question: Why is the curve necessarily on a great circle? The curve is arbitrary–in space. Also, there is only one great circle through the two points, as three points determine a plane–a counterexample to this claim would then be readily found.
Draw a Great Circle containing the two points and the curve. Then connect the two points with a chord in the circle. The circle has radius 1, so the circle has diameter 2, so the two points are all but diametrically opposite. Therefore we can draw a diameter $EF$ parallel to the chord but not on it.
Now take the plane through EF perpendicular to AG. This creates two hemispheres, and the curve is in one and only one of them.

Let the curve intersect the sphere at points A and B. Let B' be the point diametrically opposite A, and let $Q$ be the plane through the center O of the sphere perpendicular to $BB'$ and passing through the midpoint of $BB'$. We claim that the curve must be in the hemisphere divided by $Q$ containing points A and B.
Assume the contrary and suppose that the curve intersects $Q$ at point C. Reflect the portion of the curve from C to B to obtain a same-length curve from C to B'. Then the length of the curve equals the length of the new curve from A to B', which is at least the distance from A to B', or 2. This is a contradiction to the claim that the length of the curve is less than 2, so the curve must be contained in the hemisphere divided by $Q$ containing points A and B.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A father, mother and son hold a family tournament, playing a two person board game with no ties. The tournament rules are:
(i) The weakest player chooses the first two contestants.
(ii) The winner of any game plays the next game against the person left out.
(iii) The first person to win two games wins the tournament.
The father is the weakest player, the son the strongest, and it is assumed that any player's probability of winning an individual game from another player does not change during the tournament. Prove that the father's optimal strategy for winning the tournament is to play the first game with his wife.

Solution:
There are three possible strategies for the father:
1)  Sit out the first game
2)  Play the first game against the weaker of the other two players (the mother).  This person is referred to throughout the solution as "the weaker player".
3)  Play the first game against the stronger of the other two players (the son).  This person is referred to throughout the solution as "the stronger player".
Strategy 1 is dominated by both strategy 2 and strategy 3.  If strategy 1 is used and the weaker player wins the first game, it becomes strategy 2, but with the father starting behind 0-1.  Likewise, if strategy 1 is used and the stronger player wins the first game, it becomes strategy 3, but with the father again starting behind 0-1.
Thus, the father must play the first game.
By the pigeonhole principle, there may be no more than 4 games; once the 4th game is finished, someone will have won two games.  Let $W$ denote a game the father wins, let $L$ denote a game the father loses, and let $x$ denote a game the father does not participate in.  Then, with the knowledge that the father plays the first game, the following ways for the father to win two games are possible:
(A)  $WW$
(B)  $WLxW$
(C)  $LxWW$
If the father wins the first game, then he must either win the second game (A), or sit out the third game to win the fourth game (B).
If the father loses the first game, then he must sit out the second game and win the third and fourth games (C).
Now we must determine which gives the largest probability of the father winning: playing the first game against the weaker player or the stronger player.  We define the following probabilities:
$x$ is the chance of the father defeating the weaker player.  $(1-x)$ is the chance of the weaker player defeating the father.
$y$ is the chance of the father defeating the stronger player.  $(1-y)$ is the chance of the stronger player defeating the father.
$z$ is the chance of the weaker player defeating the stronger player.  $(1-z)$ is the chance of the stronger player defeating the weaker player.
Note that $x > y$, and all of $x, y$ and $z$ are less than $0.5$.
If the father plays the weaker player first, we split the probability of winning the tournament in the three mutually exclusive cases above:
$P(A) = xy$ because the father must defeat the weaker player, then the father must defeat the stronger player.
$P(B) = x(1-y)zx$ because the father must defeat the weaker player, then stronger player must defeat the father.  Third, the weaker player must defeat the stronger player (because if the stronger player wins a second game, the tournament is over).  Fourth, the father plays the weaker player a second time and must win.
$P(C) = (1-x)(1-z)yx$ because the weaker player must defeat the father, followed by the stronger player defeating the weaker player (because if the weaker player wins two in a row, he wins the tournament).  The father must then defeat the stronger player and the weaker player in the third and fourth game, respectively.
From this, the total probability of the father winning by playing the weaker player first is:
$P(TOTAL) = P(A) + P(B) + P(C) = xy + x(1-y)zx + (1-x)(1-z)yx$
Likewise, we compute the probability of the father winning if he plays the stronger player first.  We do this by symmetry:
All $x$ will turn into $y$, because whenever the father defeated the weaker player before, he must defeat the stronger player now.
All $y$ will turn into $x$, because whenever the father defeated the stronger player before, he must defeat the weaker player now.
All $z$ will turn into $(1-z)$, because whenever the weaker player defeated the stronger player, now the stronger player must defeat the weaker player.
All $(1-z)$ will turn into $z$, because whenever the stronger player defeated the weaker player, now the weaker player must defeat the stronger player.
Applying these transformations and calling the new probabilities $P'$, we find that:
$P'(TOTAL) = P'(A) + P'(B) + P'(C) = yx + y(1-x)(1-z)y + (1-y)zxy$
We compare these probabilities.
$P(A) = P'(A)$.  This makes sense, as the probabilitiy of the father winning the first two games is the same, regardless of the order in which they are played.
$P(B) > P'(C)$:  Calculating $P(B) / P'(C)$, we get $x^2(1-y)z / xy(1-y)z$, which simplifies to $x/y$.
Since $x > y$
$x/y > 1$
$P(B) / P'(C) > 1$
so $P(B) > P'(C)$.
$P(C) > P'(B)$:  Calculating $P(C) / P'(B)$, we get $(1-x)(1-z)yx / (1-x)(1-z)y^2$, which simpllifies again to $x/y$.  Thus, $P(C) > P'(B)$
Adding the above equations and inequalities, we see that $P(TOTAL) > P'(TOTAL)$, and thus the father is better off playing the weaker of the two players (ie the mother) first.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Consider the two triangles $\triangle ABC$ and $\triangle PQR$ shown in Figure 1.  In $\triangle ABC$, $\angle ADB = \angle BDC = \angle CDA = 120^\circ$.  Prove that $x=u+v+w$.

We rotate figure $PRQM$ by a clockwise angle of $\pi/3$ about $Q$ to obtain figure $RR'QM'$:
Evidently, $MM'Q$ is an equilateral triangle, so triangles $MRM'$ and $ABC$ are congruent.  Also, triangles $PMQ$ and $RM'Q$ are congruent, since they are images of each other under rotations.  Then

Then by symmetry,
But $ABC$ is composed of three smaller triangles.  The one with sides $w,v,a$ has area $\tfrac{1}{2} wv \sin 120^\circ = \frac{wv \sqrt{3}}{4}$.  Therefore, the area of $ABC$ is

Also, by the Law of Cosines on that small triangle of $ABC$, $a^2 = w^2 + wv+ v^2$, so by symmetry,

Therefore

But the area of triangle $PQR$ is $x^2 \sqrt{3}/4$.  It follows that $u+v+w=x$, as desired.  $\blacksquare$

Rotate $\triangle ABC$ $60$ degrees clockwise about $A$ to get $\triangle AB'C'$. Observe that $\triangle ADD'$ is equilateral, which means $D'D=AD=u$. Also, $B',D',D,C$ are collinear because $\angle B'D'A + \angle AD'D = 120+60=180$ and $\angle CDA + \angle DD'A = 120+60=180$. The resulting $\triangle B'AC$ has side lengths $b,c,u+v+w$ and the angle opposite side $u+v+w$ has magnitude $A+60$.
If we perform the rotation about points $B$ and $C$, we get two triangles. One has side lengths $a,c,u+v+w$ and the angle opposite side $u+v+w$ has magnitude $B+60$, and the other has side lengths $b,c,u+v+w$ and the angle opposite side $u+v+w$ has magnitude $C+60$.
These three triangles fit together because $(A+60)+(B+60)+(C+60) = 360$. The result is an equilateral triangle of side length $u+v+w$.

As in the first solution, we rotate and establish that $\triangle MRM' \cong \triangle ABC$.
Let $X$ and $Y$ be points on $\overline{RQ}$ and $\overline{PQ}$, respectively, such that $M$ lies on $\overline{XY}$ and $\overline{XY}\parallel \overline{PR}$.  We note that $m\angle RXM = 120^\circ$.  The rotation then takes $Y$ to $X$, so $m\angle RXM'=m\angle PYM = 120^\circ$.
It follows that $RX=BD=v$, $MX=AD=u$, $M'X=CD=w$.
Since $m\angle MXM' = 120^\circ$ and $m\angle MQM' = 60^\circ$, $MXM'Q$ is cyclic.
By Ptolemy's theorem,

Finally, $RQ = RX+XQ = u+v+w$, as desired.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $A,B,C,D$ denote four points in space and $AB$ the distance between $A$ and $B$, and so on. Show that

If we project points $A,B,C,D$ onto the plane parallel to $\overline{AB}$ and $\overline{CD}$, $AB$ and $CD$ stay the same but $BC, AC, AD, BD$ all decrease, making the inequality sharper. Thus, it suffices to prove the inequality when $A,B,C,D$ are coplanar:

Let $AD=a, AC=b, BC=c, BD=d, AB=m, CD=n$. We wish to prove that $a^2+b^2+c^2+d^2\ge m^2+n^2$. Let us fix $\triangle BCD$ and the length $AB$ and let $A$ vary on the circle centered at $B$ with radius $m$. If we find the minimum value of $a^2+b^2$, which is the only variable quantity, and prove that it is larger than $m^2+n^2-c^2-d^2$, we will be done.
First, we express $a^2+b^2$ in terms of $c,d,m,\theta,\phi$, using the Law of Cosines:

$a^2+b^2$ is a function of $\theta$, so we take the derivative with respect to $\theta$ and obtain that $a^2+b^2$ takes a minimum when
Define $p=a^2+b^2$ and $q=c^2+d^2$:

Let

It is clear that every other case can be reduced to this.
Then, with the distance formula and expanding,
which rearranges to the desired inequality.

Because the distances are all squared, we must only prove the result in one dimension, and then we can just add up the three individual inequalities for the $x$, $y$, and $z$ dimension to get the desired result. Let $x_a$, $x_b$, $x_c$, and $x_d$ be the positions of $A$, $B$, $C$, and $D$ respectively. Then we must show that,
So we are done.

Let $a$, $b$, $c$, $d$ correspond to the position vectors of points A, B, C, and D, respectively, with respect to an arbitrary origin O. Let us also for simplicity define $a^2 = a \cdot a = ||a||^2$, where $||a||$ is the magnitude of vector $a$. Because squares are non-negative, $a^2$ is non-negative for all vectors $a$. Thus,

Because dot product is linear, we expand to obtain

from which we add $a^2 + b^2 + c^2 + d^2$ to both sides, rearrange, and complete the square to get

As $(a-b)^2 = ||a-b||^2 = ||AB||^2 = AB^2$ and likewise for the others,

which is what we wanted to prove.
NOTES:
1. Equality holds when the vector equality $a + b = c + d$ holds, which occurs when A, B, C, and D are the vertices of a (planar) parallelogram, in that order.
2. The algebra employed here is almost identical to the algebra used in Solution 3, which means that Solution 3 is just a simplification of this solution.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


If $P(x)$ denotes a polynomial of degree $n$ such that  for $k=0,1,2,\ldots,n$, determine $P(n+1)$.

Let $Q(x) = (x+1)P(x) - x$, and clearly, $Q(x)$ has a degree of $n+1$.
Then, for $k=0,1,2,\ldots,n$, $Q(k) = (k+1)P(k) - k = (k+1)\cdot \dfrac{k}{k+1} - k = 0$.
Thus, $k=0,1,2,\ldots,n$ are the roots of $Q(x)$.
Since these are all $n+1$ of the roots of the $n+1^{\text{th}}$ degree polynomial, by the Factor Theorem, we can write $Q(x)$ as  where $c$ is a constant.
Thus,
We plug in $x = -1$ to cancel the $(x+1)P(x)$ and find $c$:

Finally, plugging in $x = n+1$ to find $P(n+1)$ gives:

If $n$ is even, this simplifies to $P(n+1) = \dfrac{n}{n+2}$. If $n$ is odd, this simplifies to $P(n+1) = 1$. $\Box$
~Edits by BakedPotato66

It is fairly natural to use Lagrange's Interpolation Formula on this problem:
through usage of the Binomial Theorem. $\square$
~lpieleanu (minor editing and reformatting)
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Two given circles intersect in two points $P$ and $Q$. Show how to construct a segment $AB$ passing through $P$ and terminating on the two circles such that $AP\cdot PB$ is a maximum.

Solution:
A maximum $AP \cdot PB$ cannot be attained if $AB$ intersects segment $O_1O_2$ because a larger value can be attained by making one of $A$ or $B$ diametrically opposite $P$, which (as is easily checked) increases the value of both $AP$ and $PB$. Thus, assume $AB$ does not intersect $O_1O_2$.
Let $E$ and $F$ be the centers of the small and big circles, respectively, and $r$ and $R$ be their respective radii.
Let $M$ and $N$ be the feet of $E$ and $F$ to $AB$, and $\alpha = \angle APE$ and $\epsilon = \angle BPF$
We have:

$AP\times PB$ is maximum when the product $\cos{\alpha} \cos{\epsilon}$ is a maximum.
We have $\cos{\alpha} \cos{\epsilon}= \frac{1}{2} [\cos(\alpha +\epsilon) + \cos(\alpha -\epsilon)]$
But $\alpha +\epsilon = 180^{\circ} - \angle EPF$ and is fixed, so is $\cos(\alpha +\epsilon)$.
So its maximum depends on $cos(\alpha -\epsilon)$ which occurs when $\alpha=\epsilon$. To draw the line $AB$:
Draw a circle with center $P$ and radius $PE$ to cut the radius $PF$ at $H$. Draw the line parallel to $EH$ passing through $P$. This line meets the small and big circles at $A$ and $B$, respectively.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A deck of $n$ playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is $(n+1)/2$.

We begin by induction. Our base case is naturally when $n = 3$, as there can be no less than $3$ cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires $2$ moves. This indeed is equal to $(3 + 1)/2$. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact $(n + 1)/2$. Now, we see that to simulate the case with $n + 1$ cards, we simply must add a card to our deck. By our assumption, we can expect to turn up $(n + 1)/2$ cards to be turned up, including our second ace. Thus ahead of our second ace, we expect $(n - 1)/2$ cards , and after it $(n - 1)/2$ as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now $((n + 1)/2) + 1/2)$, or $(n + 2)/2$, the desired outcome for the $n + 1$ case.

Although we can induct as in the situation above, we can use a more direct approach.
Consider a deck.  The second ace is in the $k$th place.  If we draw the deck backwards (which has equal probability as drawing it forwards), then we will draw it in the $n+1-k$th place, since the $n$th place will become the first, the $n-1$th the second, etc.
Also, note that when second ace is still the second ace when we draw the deck backwards. (we need to note this, else this argument holds for the first ace and third ace as well)
Now, this implies that the expected location of the second ace is in the $(k+n+1-k)/2=(n+1)/2$ place.

Like Solution 2, this solution is also a direct solution.
The three aces divide the deck into four piles with a non-negative number of cards. Let $a$, $b$, $c$, and $d$ be the number of cards in the first, second, third, and fourth piles, respectively, given a random deck $D$. Also, let $E(a), E(b), E(c), E(d)$ denote the expected value of $a$, $b$, $c$, and $d$ over all decks $D$. Then $a + b + c + d = n - 3$ (the deck minus the three aces).
For every deck $D$, there must exist other decks that permute the values of $a$, $b$, $c$, $d$. (i.e. if there is a deck with $a = 2, b = 3, c = 1, d = 4,$ there exists a deck with $a = 1, b = 2, c = 3, d = 4$.) Therefore, the value of $a$ over all decks $D$ is a permutation of the value of $b$ over all such decks, and as a result $E(a) = E(b)$. A similar result holds for $b$, $c$, and $d$, and so $E(a) = E(b) = E(c) = E(d)$. Because  $E(a) = E(b) = \frac{n-3}{4}$. We want to compute the number of cards up to and including the second ace, which is just  as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


If $A$ and $B$ are fixed points on a given circle and $XY$ is a variable diameter of the same circle, determine the locus of the point of intersection of lines $AX$ and $BY$. You may assume that $AB$ is not a diameter.

Solution:
WLOG, assume that the circle is the unit circle centered at the origin. Then the points $A$ and $B$ have coordinates $(-a,b)$ and $(a,b)$ respectively and $X$ and $Y$ have coordinates $(r,s)$ and $(-r,-s)$. Note that these coordinates satisfy $a^2 + b^2 = 1$ and $r^2 + s^2 = 1$ since these points are on a unit circle. Now we can find equations for the lines:

Solving these simultaneous equations gives coordinates for $P$ in terms of $a, b, r,$ and $s$:
$P = \left(\frac{as}{b},\frac{1 - ar}{b}\right)$. These coordinates can be parametrized in Cartesian variables as follows:

Now solve for $r$ and $s$ to get $r = \frac{1-by}{a}$ and $s = \frac{bx}{a}$ . Then since $r^2 + s^2 = 1, \left(\frac{bx}{a}\right)^2 + \left(\frac{1-by}{a}\right)^2 = 1$ which reduces to $x^2 + (y-1/b)^2 = \frac{a^2}{b^2}.$ This equation defines a circle and is the locus of all intersection points $P$. In order to define this locus more generally, find the slope of this circle function using implicit differentiation:

Now note that at points $A$ and $B$, this slope expression reduces to $y' = \frac{-b}{a}$ and $y' = \frac{b}{a}$ respectively, values which are identical to the slopes of lines $AO$ and $BO$. Thus we conclude that the complete locus of intersection points is the circle tangent to lines $AO$ and $BO$ at points $A$ and $B$ respectively.

Notice that $m\angle AYP=\frac{1}{2}m\overarc{AB}$ (Inscried angle theorem) and that $m\angle XAY=90$ since $XY$ is a diameter, and thus subtends an arc of $180$. This will hold for all $X$ and all $Y$, and so by AA similarity, the angle $APY$ will be constant for all P, thus implying that the points A, B, and all P will be concyclic.
If we assume that the center of this circle is $H$, we know that $m\angle AHB=2m\angle APB=2(90-\frac{1}{2}\overarc{AB})=180-\overarc{AB}$. We can assume that $\overline{AH}$ and $\overline{BH}$ intersect the original circle at points $M$, and $N$ respectively. This will give us that $m\angle AHB=\frac{1}{2}|m\overarc{MN}-m\overarc{AB}|$ (Since $H$ lies on the perpendicular bisector of $AB$, we know that $M$, $N$ will be on the same side of $AB$.) Now we also know that $m\overarc{MN}\leq m\overarc{AB}$ or $m\overarc{MN}\leq 360-m\overarc{AB}$. The only case where $m\overarc{MN}$ satisfies the measure of $\angle AHB$, is when $M=A$ and $N=B$, implying that $AH$ and $BH$ are tangents, and so $H$ is the intersection of the tangents from $A$ and $B$ to the original circle.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Determine all integral solutions of $a^2+b^2+c^2=a^2b^2$.

Solution:
Either $a^2=0$ or $a^2>0$. If $a^2=0$, then $b^2=c^2=0$. Symmetry applies for $b$ as well. If $a^2,b^2\neq 0$, then $c^2\neq 0$. Now we look at $a^2\bmod{4}$:
$a^2\equiv 0\bmod{4}$: Since a square is either 1 or 0 mod 4, then all the other squares are 0 mod 4. Let $a=2a_1$, $b=2b_1$, and $c=2c_1$. Thus $a_1^2+b_1^2+c_1^2=4a_1^2b_1^2$. Since the LHS is divisible by four, all the variables are divisible by 4, and we must do this over and over again, and from infinite descent, there are no non-zero solutions when $a^2\equiv 0\bmod{4}$.
$a^2\equiv 1\bmod{4}$: Since $b^2\neq 0\bmod{4}$, $b^2\equiv 1\bmod{4}$, and $2+c^2\equiv 1\bmod{4}$. But for this to be true, $c^2\equiv 3\bmod{4}$, which is an impossibility. Thus there are no non-zero solutions when $a^2\equiv 1\bmod{4}$.
Thus the only solution is the solution above: $(a,b,c)=0$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


If the sum of the lengths of the six edges of a trirectangular tetrahedron $PABC$ (i.e., $\angle APB=\angle BPC=\angle CPA=90^o$) is $S$, determine its maximum volume.

Solution:
Let the side lengths of $AP$, $BP$, and $CP$ be $a$, $b$, and $c$, respectively. Therefore $S=a+b+c+\sqrt{a^2+b^2}+\sqrt{b^2+c^2}+\sqrt{c^2+a^2}$. Let the volume of the tetrahedron be $V$. Therefore $V=\frac{abc}{6}$.
Note that $(a-b)^2\geq 0$ implies $\frac{a^2-2ab+b^2}{2}\geq 0$, which means $\frac{a^2+b^2}{2}\geq ab$, which implies $a^2+b^2\geq ab+\frac{a^2+b^2}{2}$, which means $a^2+b^2\geq \frac{(a+b)^2}{2}$, which implies $\sqrt{a^2+b^2}\geq \frac{1}{\sqrt{2}} \cdot (a+b)$. Equality holds only when $a=b$. Therefore
$S\geq a+b+c+\frac{1}{\sqrt{2}} \cdot (a+b)+\frac{1}{\sqrt{2}} \cdot (c+b)+\frac{1}{\sqrt{2}} \cdot (a+c)$
$=(a+b+c)(1+\sqrt{2})$.
$\frac{a+b+c}{3}\geq \sqrt[3]{abc}$ is true from AM-GM, with equality only when $a=b=c$. So $S\geq (a+b+c)(1+\sqrt{2})\geq 3(1+\sqrt{2})\sqrt[3]{abc}=3(1+\sqrt{2})\sqrt[3]{6V}$. This means that $\frac{S}{3(1+\sqrt{2})}=\frac{S(\sqrt{2}-1)}{3}\geq \sqrt[3]{6V}$, or $6V\leq \frac{S^3(\sqrt{2}-1)^3}{27}$, or $V\leq \frac{S^3(\sqrt{2}-1)^3}{162}$, with equality only when $a=b=c$. Therefore the maximum volume is $\frac{S^3(\sqrt{2}-1)^3}{162}$.

Note that by AM-GM
so  Proceed as before.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


If $P(x)$, $Q(x)$, $R(x)$, and $S(x)$ are all polynomials such that

prove that $x-1$ is a factor of $P(x)$.

In general we will show that if $m$ is an integer less than $n$ and $P_0, \dotsc, P_{m-1}$ and $S$ are polynomials satisfying

then $P_k(1) = 0$, for all integers $0 \le k \le m-1$.  For the problem, we may set $n=5$, $m=3$, and then note that since $P(1)= 0$, $(x-1)$ is a factor of $P(x)$.
Indeed, let $\omega_1, \dotsc, \omega_{n-1}$ be the $n$th roots of unity other than 1.  Then for all integers $1 \le i \le n-1$,

for all integers $1 \le i \le n$.  This means that the $(m-1)$th degree polynomial

has $n-1 > m-1$ distinct roots.  Therefore all its coefficients must be zero, so $P_k = 0$ for all integers $0 \le k \le m-1$, as desired.  $\blacksquare$

Let $\zeta, \xi, \rho$ be three distinct primitive fifth roots of unity.
Setting $x = \zeta, \xi$, we have

These equations imply that

or

But by symmetry,

Since $\xi \neq \rho$, it follows that $Q(1) = R(1) = 0$.  Then, as noted above,

so $(x-1)$ is a factor of $P(x)$, as desired.  $\blacksquare$

Let $z, z^2, z^3$ be three of the 5th roots of unity not equal to one that satisfy $1 + z + z^2 + z^3 + z^4 = 0$ as a result. Plugging them into the equation gives the linear system of equations in $(A(1), B(1), C(1))$:

Direct observation gives $(A(1), B(1), C(1)) = (0,0,0)$ as a solution, and there are no others because the system of equations is linear. Hence, $A(1) = 0$, and so $(x-1)$ is a factor of $A(x)$, as desired. $\blacksquare$
Note: We can generalize this approach to prove the claim in Solution 1 in an equally fast, concise, and readily understandable fashion.


Determine all pairs of positive integers $(m,n)$ such that
$(1+x^n+x^{2n}+\cdots+x^{mn})$ is divisible by $(1+x+x^2+\cdots+x^{m})$.

Denote the first and larger polynomial to be $f(x)$ and the second one to be $g(x)$. In order for $f(x)$ to be divisible by $g(x)$ they must have the same roots. The roots of $g(x)$ are the (m+1)th roots of unity, except for 1. When plugging into $f(x)$, the root of unity is a root of $f(x)$ if and only if the terms $x^n, x^{2n}, x^{3n}, \cdots x^{mn}$ all represent a different (m+1)th root of unity not equal to 1.
Note that if $\\gcd(m+1,n)=1$, the numbers $n, 2n, 3n, \cdots, mn$ represent a complete set of residues minus 0 modulo $m+1$. However, if $gcd(m+1,n)=a$ not equal to 1, then $\frac{(m+1)(n)}{a}$ is congruent to $0 \pmod {m+1}$ and thus a complete set is not formed. Therefore, $f(x)$ divides $g(x)$ if and only if $\boxed{\\gcd(m+1,n)=1}.$ $\blacksquare$

We could instead consider $f(x)$ modulo $g(x)$. Notice that $x^{m+1} = 1 \pmod {g(x)}$, and thus we can reduce the exponents of $f(x)$ to their equivalent modulo $m+1$. We want the resulting $h(x)$ with degree less than $m+1$ to be equal to $g(x)$ (of degree $m$), which implies that the exponents of $f(x)$ must be all different modulo $m+1$. This can only occur if and only if $gcd(m+1, n) = 1$, and this is our answer, as shown in Solution 1.

Notice that $1+x^n+x^{2n}+...+x^{mn}=\frac{x^{mn+n}-1}{x^n-1}$ and $1+x+x^2+...+x^m=\frac{x^{m+1}-1}{x-1}$, so it remains to prove that $(x^n-1)(x^{m+1}-1) \mid (x^{mn+n}-1)(x-1)$. It is clear that $(x^n-1) \mid (x^{mn+n}-1)$ and $(x^{m+1}-1) \mid (x^{mn+n}-1)$. For any $k \in \mathbb{N}$, we can use the fact that $x^k-1=\prod_{d \mid k} \Phi _d(x)$, where $\Phi _d(x)$ is the dth cyclotomic polynomial. If $\gcd(m+1,n) = d > 1$, then $x^{m+1}-1$ and $x^n-1$ share a common cyclotomic polynomial; namely, $\Phi _d(x)$. But since all the factors of $x^{mn+n}-1$ are distinct, $(x^{mn+n}-1)(x-1)$ cannot be divisible by $(x^n-1)(x^{m+1}-1)$. We find that $\gcd(m+1,n) = 1$ must be the solution, since the only shared polynomial is $\Phi _1(x)=x-1$, and we are done.


If $a$ and $b$ are two of the roots of $x^4+x^3-1=0$, prove that $ab$ is a root of $x^6+x^4+x^3-x^2-1=0$.

Solution:
Given the roots $a,b,c,d$ of the equation $x^{4}+x^{3}-1=0$.
First, Vieta's relations give $a+b+c+d = -1 , ab+ac+ad+bc+bd+cd=0, abc+abd+acd+bcd=0, abcd = -1$.
Then $cd=-\frac{1}{ab}$ and $c+d=-1-(a+b)$.
The other coefficients give $ab+(a+b)(c+d)+cd = 0$ or $ab+(a+b)[-1-(a+b)]-\frac{1}{ab}=0$.
Let $a+b=s$ and $ab=p$.
Thus, $0=ab+ac+ad+bc+bd+cd=p+s(-1-s)-\frac{1}{p}$.   (1)
Also, $0=abc+abd+acd+bcd=p(-1-s)-s/p$.
Solving this equation for $s$, $s= \frac{-p^2}{p^2+1}$.
Substituting into (1): $\frac{p^{6}+p^{4}+p^{3}-p^{2}-1}{p(p^2+1)^2}=0$.
Conclusion: $p =ab$ is a root of $x^{6}+x^{4}+x^{3}-x^{2}-1=0$.


Prove that if the opposite sides of a skew (non-planar) quadrilateral are congruent, then the line joining the midpoints of the two diagonals is perpendicular to these diagonals, and conversely, if the line joining the midpoints of the two diagonals of a skew quadrilateral is perpendicular to these diagonals, then the opposite sides of the quadrilateral are congruent.

Solution:
We first prove that if the opposite sides are congruent, then the line joining the midpoints of the two diagonals is perpendicular to these diagonals.
Let the vertices of the quadrilateral be A, B, C, D, in that order. Thus, the opposite sides congruent condition translates to (after squaring):

Let the position vectors of A, B, C, D be a, b, c, d with respect to an arbitrary origin $O$. Define the square of a vector $a^2 = a \cdot a$. Thus, $(a-b)^2 = (c-d)^2$ and so  Similarly,  Subtracting the second equation from the first eventually results in  which factors as
Let M and N be the midpoints of $AC$ and $BD$, with position vectors $m = \frac{a+c}{2}$ and $n = \frac{b+d}{2}$, respectively. Then notice that the perpendicularity condition for vectors gives $MN$ perpendicular to $AC$. Similarly (by adding the equations), we find that $MN$ is perpendicular to $BD$, completing the first part of the proof.
Proving the converse is straightforward also: indeed, $MN$ perpendicular to both diagonals gives

Adding and subtracting the equations eventually simplifies to

or $AB^2 = CD^2$ and $AD^2 = BC^2$. This reduces to $AB = CD$ and $AD = BC$, as desired. $\blacksquare$

Let $A, B, C, D$ be position vectors rather than the specified points. We're given that $|A-B| = |C-D| \rightarrow |A-B|^2=|C-D|^2 \rightarrow (A-B) \cdot (A-B) = (C-D) \cdot (C-D) \rightarrow \\ A \cdot A - 2A \cdot B + B \cdot B - C \cdot C + 2C \cdot D - D \cdot D=0$. We're also given that $|A-D| = |C-B| \rightarrow |A-D|^2=|C-B|^2 \rightarrow (A-D) \cdot (A-D) = (C-B) \cdot (C-B) \rightarrow \\ A \cdot A - 2A \cdot D + D \cdot D - C \cdot C + 2C \cdot B - B \cdot B=0$. Adding the two equations gives $2A \cdot A - 2A \cdot B - 2A \cdot D - 2 C \cdot C + 2C \cdot D + 2C \cdot B = 0$. Dividing by 4 and rearranging gives $\frac{A+C-B-D}{2} \cdot (A-C) = 0$. On the left hand side of this equation, one of the two factors is the vector between the midpoints of the two diagonals, and the other factor is on of the two diagonals. Their dot product is $0$, so they are perpendicular. The same methods can be used to show that the vector between the two midpoints is perpendicular to the other diagonal. We can employ this process in reverse to get the converse (this isn't completely simple, but I'm lazy so it's left as an exercise i guess).


If $a,b,c,d,e$ are positive numbers bounded by $p$ and $q$, i.e, if they lie in $[p,q], 0 < p$, prove that

and determine when there is equality.

Solution:
Fix four of the variables and allow the other to vary. Suppose, for example, we fix all but $x$. Then the expression on the LHS has the form $(r + x)(s + \frac{1}{x}) = (rs + 1) + sx + \frac{r}{x}$, where $r$ and $s$ are fixed. But this is convex. That is to say, as $x$ increases if first decreases, then increases. So its maximum must occur at $x = p$ or $x = q$. This is true for each variable.
Suppose all five are $p$ or all five are $q$, then the LHS is 25, so the inequality is true and strict unless $p = q$. If four are $p$ and one is $q$, then the LHS is $17 + 4\left(\frac{p}{q} + \frac{q}{p}\right)$. Similarly if four are $q$ and one is $p$. If three are $p$ and two are $q$, then the LHS is $13 + 6\left(\frac{p}{q} + \frac{q}{p}\right)$. Similarly if three are $q$ and two are $p$.
$\frac{p}{q} + \frac{q}{p} \geq 2$ with equality iff $p = q$, so if $p < q$, then three of one and two of the other gives a larger LHS than four of one and one of the other. Finally, we note that the RHS is in fact $13 + 6\left(\frac{p}{q} + \frac{q}{p}\right)$, so the inequality is true with equality iff either (1) $p = q$ or (2) three of $v, w, x, y, z$ are $p$ and two are $q$ or vice versa.


Given that $a,b,c,d,e$ are real numbers such that
$a+b+c+d+e=8$,
$a^2+b^2+c^2+d^2+e^2=16$.
Determine the maximum value of $e$.

By Cauchy Schwarz, we can see that $(1+1+1+1)(a^2+b^2+c^2+d^2)\geq (a+b+c+d)^2$
thus $4(16-e^2)\geq (8-e)^2$
Finally, $e(5e-16) \geq 0$ which means $\frac{16}{5} \geq e \geq 0$
so the maximum value of $e$ is $\frac{16}{5}$.
from: Image from Gon Mathcenter.net

Seeing as we have an inequality with constraints, we can use Lagrange multipliers to solve this problem.
We get the following equations:
$(1)\hspace*{0.5cm} a+b+c+d+e=8\\ (2)\hspace*{0.5cm} a^{2}+b^{2}+c^{2}+d^{2}+e^{2}=16\\ (3)\hspace*{0.5cm} 0=\lambda+2a\mu\\ (4)\hspace*{0.5cm} 0=\lambda+2b\mu\\ (5)\hspace*{0.5cm} 0=\lambda+2c\mu\\ (6)\hspace*{0.5cm} 0=\lambda+2d\mu\\ (7)\hspace*{0.5cm} 1=\lambda+2e\mu$
If $\mu=0$, then $\lambda=0$ according to $(6)$ and $\lambda=1$ according to $(7)$, so $\mu \neq 0$. Setting the right sides of $(3)$ and $(4)$ equal yields $\lambda+2a \mu= \lambda+2b \mu \implies 2a\mu=2b \mu \implies a=b$. Similar steps yield that $a=b=c=d$. Thus, $(1)$ becomes $4d+e=8$ and $(2)$ becomes $4d^{2}+e^{2}=16$. Solving the system yields $e=0,\frac{16}{5}$, so the maximum possible value of $e$ is $\frac{16}{5}$.

A re-writing of Solution 1 to avoid the use of Cauchy Schwarz. We have
 and

The second equation times 4, then minus the first equation,

The rest follows.
J.Z.


$ABCD$ and $A'B'C'D'$ are square maps of the same region, drawn to different scales and superimposed as shown in the figure. Prove that there is only one point $O$ on the small map that lies directly over point $O'$ of the large map such that $O$ and $O'$ each represent the same place of the country. Also, give a Euclidean construction (straight edge and compass) for $O$.

The point is obviously unique, because the two maps have different scales (but if P and Q where two fixed points the distance between them would be the same on both maps).
Let the small map square be A'B'C'D' and the large be ABCD, where X and X' are corresponding points. We deal first with the special case where A'B' is parallel to AB. In this case let AA' and BB' meet at O. Then triangles OAB and OA'B' are similar, so O must represent the same point. So assume A'B' is not parallel to AB.
Let the lines A'B' and AB meet at W, the lines B'C' and BC meet at X, the lines C'D' and CD meet at Y, and the lines D'A' and DA meet at Z. We claim that the segments WY and XZ meet at a point O inside the smaller square. W cannot lie between A' and B' (or one of the vertices A', B' of the smaller square would lie outside the larger square). If it lies on the opposite side of A' to B', then Y must lie on the opposite side of C' to D'. Thus the segment WY must cut the side A'D' at some point Z' and the side B'C' at some point X'. The same conclusion holds if W lies on the opposite side of B' to A', because then Y must lie on the opposite side of D' to C'. Similarly, the segment XZ must cut the side A'B' at some point W' and the side C'D' at some point Y'. But now the segments X'Z' and W'Y' join pairs of points on opposite sides of the small square and so they must meet at some point O inside the small square.
Now the triangles WOW' and YOY' are similar (WW' and YY' are parallel). Hence OW/OY = OW'/OY'. So if we set up coordinate systems with AB as the x-axis and AD as the y-axis (for the large square) and A'B' as the x'-axis and A'D' as the y'-axis (for the small square) so that corresponding points have the same coordinates, then the y coordinate of O equals the y' coordinate of O. Similarly, XOX' and ZOZ' are similar, so OX/OZ = OX'/OZ', so the x-coordinate of O equals its x'-coordinate. In other words, O represents the same point on both maps.

The point is obviously unique because of the different scale and angle, which can also be seen as the point can and must be the unique center of spiral similarity taking ABCD to A'B'C'D', as under the spiral similarity the center does not move. (Recall that a spiral similarity is a dilation combined with a rotation, and that there is a unique spiral similarity taking any segment to another segment, provided the four points do not make a parallelogram.)
To construct this center of spiral similarity, reference EGMO Lemma 10.1. Draw line DD' and AA', and let them intersect at point X. Draw circles through points X,A,D and X,A',D' (using the perpendicular bisector constructions to find the center of the circle using two chords). The intersection point of the two circles other than X is the center of spiral similarity, and hence is O, which represents the same point on both maps.


An integer $n$ will be called good if we can write
$n=a_1+a_2+\cdots+a_k$,
where $a_1,a_2, \ldots, a_k$ are positive integers (not necessarily distinct) satisfying
$\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}=1$.
Given the information that the integers 33 through 73 are good, prove that every integer $\ge 33$ is good.

Solution:
Lemma: If $g$ is a good integer, then so is $2g + 2$ and $2g + 9$.
Proof: Let $g = a_1 + a_2 + \cdots + a_k$ such that  where the $a_i$ are positive integers. Then, notice that  so $g_1 = 2 + 2a_1 + 2a_2 + ... + 2a_k = 2 + 2g$ is also a good integer. Furthermore,  so $g_2 = 3 + 6 + 2a_1 + 2a_2 + ... + a_k = 9 + 2g$ is also good.
This completes the lemma. Now, we use induction to show that the integers from 33 to $n$ are all good, where $n \ge 33$.
Base case: Our given takes care of $33 \le n \le 73$.
Inductive step: Assume the integers between 33 and $k > 73$, inclusive, are all good. Now, we casework on parity of $k+1$.
If $k+1$ is odd, then write $k+1 = 2g + 9$ for some integer $g$.
It follows that because $k \ge 74$, we must have

Thus, $33 \le g < \frac{k}{2}$, and so $g$ is good by the inductive hypothesis. Applying the lemma gives $2g + 9 = k+1$ as a good integer.
If $k+1$ is even, write $k+1 = 2g+2$ for some integer $g$. Therefore,  so that $33 < g < \frac{k}{2}$, meaning that $g$ is a good integer by the inductive hypothesis. From the lemma, $k+1$ must be good as well.
This completes the inductive step and thus the induction. Therefore, all integers $n \ge 33$ are good integers.


(a) Prove that if the six dihedral (i.e. angles between pairs of faces) of a given tetrahedron are congruent, then the tetrahedron is regular.
(b) Is a tetrahedron necessarily regular if five dihedral angles are congruent?

Solution:
(a) Let $ABCD$ be the said tetrahedron, and let the inscribed sphere of $ABCD$ touch the faces at $W, X, Y, Z$. Then, $OW, OX, OY, OZ$ are normals to the respective faces. We know that the angle between any two normals is equal, so we have $|OW|=|OX|=|OY|=|OZ|$ at equal angles. Now, since  and similar for the other sides, we have that $WXYZ$ is a regular tetrahedron. Now, the faces of $ABCD$ are the tangent planes at $W$, $X$, $Y$, and $Z$. Then, consider a $120^{\circ}$ rotation about $OW$. The rotation sends $X\mapsto Y$, $Y\mapsto Z$, and $Z\mapsto X$. Thus we have $AB=AC$, $AC=AD$, $AD=AB$, and $BC=CD=DB$. Performing rotations about the other axes yields that $ABCD$ has equal edges, so it is regular.
(b) Consider the normals $OW, OX, OY, OZ$. We can perform a transformation in which we slightly shift $X$, $Y$, and $Z$ closer such that $\triangle XYZ$ is still equilateral, and such that all angles between every pair of normals is less that $180^{\circ}$. Then, shift $W$ such that $WX=WY=XY$. Then five of the distances are equal but the sixth is not.
~ tc1729


Nine mathematicians meet at an international conference and discover that among any three of them, at least two speak a common language. If each of the mathematicians speak at most three languages, prove that there are at least three of the mathematicians who can speak the same language.

Solution: Suppose no three mathematicians speak the same language. Then person A can share some language with at most 3 other delegates, because if he shared some language with 4 delegates there would be 3 with the same language. So there are 5 delegates who do not share a language with A. Let one of them be B. Using the same logic, one the remaining 4, let it be C, does not share a language with B. Now A, B, C do not have any common languages. Contradiction.


Determine all non-negative integral solutions $(n_1,n_2,\dots , n_{14})$ if any, apart from permutations, of the Diophantine Equation $n_1^4+n_2^4+\cdots +n_{14}^4=1599$.

Recall that $n_i^4\equiv 0,1\bmod{16}$ for all integers $n_i$. Thus the sum we have is anything from 0 to 14 modulo 16. But $1599\equiv 15\bmod{16}$, and thus there are no integral solutions to the given Diophantine equation.

In base $16$, this equation would look like:
We notice that the unit digits of the LHS of this equation should equal to $F_{16}$. In base $16$, the only unit digits of fourth powers are $0$ and $1$. Thus, the maximum of these $14$ terms is 14 $1's$ or $E_{16}$. Since $E_{16}$ is less than $F_{16}$, there are no integral solutions for this equation.


$N$ is the north pole. $A$ and $B$ are points on a great circle through $N$ equidistant from $N$. $C$ is a point on the equator. Show that the great circle through $C$ and $N$ bisects the angle $ACB$ in the spherical triangle $ABC$ (a spherical triangle has great circle arcs as sides).

Solution:
Since $N$ is the north pole, we define the Earth with a sphere of radius one in space with $N=(0,0,1)$ and sphere center $O=(0,0,0)$
We then pick point $N$ on the sphere and define the $xz$-plane as the plane that contains great circle points $A$ , $B$, and $N$ with the $x$-axis perpendicular to the $z$-axis and in the direction of $A$.
Using this coordinate system and $x$, $y$, and $z$ axes $A=(cos(\phi),0,sin(\phi))$ where $\phi$ is the angle from the $xy$-plane to $A$ or latitude on this sphere with $\frac{-\pi}{2} < \phi < \frac{\pi}{2}$
Since $A$ and $B$ are points on a great circle through $N$ equidistant from $N$, then $B=(-cos(\phi),0,sin(\phi))$
Since $C$ is a point on the equator, then $C=(cos(\theta),sin(\theta),0)$ where $\theta$ is the angle on the $xy$-plane from the origin to $C$ or longitude on this sphere with $-\pi < \phi \le \pi$
We note that vectors from the origin to points $N$, $A$, $B$, and $C$ are all unit vectors because all those points are on the unit sphere.
So, we're going to define points $N$, $A$, $B$, and $C$ as unit vectors with their coordinates.
We also define the following vectors as follows:
Vector $\overrightarrow{V_{CN}}$ is the unit vector in the direction of arc $CN$ and tangent to the great circle of $CN$ at $C$
Vector $\overrightarrow{V_{CA}}$ is the unit vector in the direction of arc $CA$ and tangent to the great circle of $CA$ at $C$
Vector $\overrightarrow{V_{CB}}$ is the unit vector in the direction of arc $CB$ and tangent to the great circle of $CB$ at $C$
To calculate each of these vectors we shall use the cross product as follows:
$\overrightarrow{V_{CN}}=(\overrightarrow{C}\times\overrightarrow{N})\times\overrightarrow{C}$
$\overrightarrow{V_{CN}}=(\left\langle cos(\theta),sin(\theta),0 \right\rangle\times\left\langle 0,0,1 \right\rangle)\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
$\overrightarrow{V_{CN}}=\left\langle sin(\theta),-cos(\theta),0 \right\rangle\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
$\overrightarrow{V_{CN}}=\left\langle 0,0,sin^{2}(\theta)+cos^{2}(\theta) \right\rangle$
$\overrightarrow{V_{CN}}=\left\langle 0,0,1 \right\rangle$
Vector $\overrightarrow{V_{CA}}$:
$\overrightarrow{V_{CA}}=(\overrightarrow{C}\times\overrightarrow{A})\times\overrightarrow{C}$
$\overrightarrow{V_{CA}}=(\left\langle cos(\theta),sin(\theta),0 \right\rangle\times\left\langle cos(\phi),0,sin(\phi) \right\rangle)\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
$\overrightarrow{V_{CA}}=\left\langle sin(\theta)sin(\phi),-cos(\theta)sin(\phi),-sin(\theta)cos(\phi) \right\rangle\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
Since we're only interested in the $z$ component of the vector
$\overrightarrow{V_{CA}}=\left\langle V_{CA_{x}},V_{CA_{y}},sin^{2}(\theta)sin(\phi)+cos^{2}(\theta)sin(\phi) \right\rangle$
$\overrightarrow{V_{CA}}=\left\langle V_{CA_{x}},V_{CA_{y}},sin(\phi) \right\rangle$
Vector $\overrightarrow{V_{CB}}$:
$\overrightarrow{V_{CB}}=(\overrightarrow{C}\times\overrightarrow{b})\times\overrightarrow{C}$
$\overrightarrow{V_{CB}}=(\left\langle cos(\theta),sin(\theta),0 \right\rangle\times\left\langle -cos(\phi),0,sin(\phi) \right\rangle)\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
$\overrightarrow{V_{CB}}=\left\langle sin(\theta)sin(\phi),-cos(\theta)sin(\phi),sin(\theta)cos(\phi) \right\rangle\times \left\langle cos(\theta),sin(\theta),0 \right\rangle$
Since we're only interested in the $z$ component of the vector
$\overrightarrow{V_{CB}}=\left\langle V_{CB_{x}},V_{CB_{y}},sin^{2}(\theta)sin(\phi)+cos^{2}(\theta)sin(\phi) \right\rangle$
$\overrightarrow{V_{CB}}=\left\langle V_{CB_{x}},V_{CB_{y}},sin(\phi) \right\rangle$
Since we're working with unit vectors, then we can use dot products on the vectors with their angles as follows:
$cos(\angle ACN) = \overrightarrow{V_{CA}}\cdot \overrightarrow{V_{CN}}$
$cos(\angle ACN) = \left\langle V_{CA_{x}},V_{CA_{y}},sin(\phi) \right\rangle \cdot \left\langle 0,0,1 \right\rangle = 0*V_{CA_{x}}+0*V_{CA_{y}}+1*sin(\phi)=sin(\phi)$
Likewise,
$cos(\angle BCN) = \overrightarrow{V_{CB}}\cdot \overrightarrow{V_{CN}}$
$cos(\angle BCN) = \left\langle V_{CB_{x}},V_{CB_{y}},sin(\phi) \right\rangle \cdot \left\langle 0,0,1 \right\rangle = 0*V_{CB_{x}}+0*V_{CB_{y}}+1*sin(\phi)=sin(\phi)$
Therefore,
$cos(\angle ACN) = cos(\angle BCN)$ and thus $\angle ACN = \angle BCN$
Since those angles are equal, it proves that the great circle through $C$ and $N$ bisects the $\angle ACB$ in the spherical triangle $ABC$
~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_1, a_2, \ldots, a_n$ is an arbitrary sequence of positive integers. A member of the sequence is picked at
random. Its value is $a$. Another member is picked at random, independently of the first. Its value is $b$. Then a third value, $c$. Show that the probability that $a + b +c$ is divisible by $3$ is at least $\frac14$.

Solution:
Let x equal the probability of picking an element of the sequence equivalent to 0 mod 3, y equal those 1 mod 3, and z equal those 2 mod 3. Then, considering that 0+0+0, 1+1+1, 2+2+2, and 0+1+2 are divisible by 3, we obtain the equivalent inequality in the First Hint. This simplifies to $x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ Now, we attempt to prove that $x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ for all nonnegative real numbers x, y, z; our inequality will follow from this. But this is just Schur's Inequality with r = 1! This completes the proof.
Note: Schur's Inequality states that $x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0$. This can be proven by setting WLOG $x \ge y \ge z$ and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?


$P$ lies between the rays $OA$ and $OB$. Find $Q$ on $OA$ and $R$ on $OB$ collinear with $P$ so that $\frac{1}{PQ} + \frac{1}{PR}$ is as large as possible.

Perform the inversion with center $P$ and radius $\overline{PO}.$ Lines $OA,OB$ go to the circles $(O_1),(O_2)$ passing through $P,O$ and the line $QR$ cuts $(O_1),(O_2)$ again at the inverses $Q',R'$ of $Q,R.$ Hence
$\frac{1}{PQ}+\frac{1}{PR}=\frac{PQ'+PR'}{PO^2}=\frac{Q'R'}{PO^2}$
Thus, it suffices to find the line through $P$ that maximizes the length of the  segment $\overline{Q'R'}.$ If $M,N$ are the midpoints of $PQ',PR',$ i.e. the projections of $O_1,O_2$ onto $QR,$ then from the right trapezoid $O_1O_2NM,$ we deduce that $O_1O_2 \ge MN = \frac{_1}{^2}Q'R'.$ Consequently, $2 \cdot O_1O_2$ is the greatest possible length of $Q'R',$ which obviously occurs when $O_1O_2NM$ is a rectangle. Hence, $Q,R$ are the intersections of $OA,OB$ with the perpendicular to $PO$ at $P.$

Let $r = OP, x = \angle OPR, a = \angle POR,$ and $b = \angle POQ.$ Then $\angle ORP = \pi - x - a$ and $\angle OQP = x - b.$ Using the Law of Sines on $\triangle OPR$ gives

and using the Law of Sines on $\triangle OPQ$ gives

Note that $r, a,$ and $b$ are given constants.
Hence,
Clearly, this quantity is maximized when $\sin x = 1.$ Because $x$ must be less than $\pi$, $\frac{1}{PQ} + \frac{1}{PR}$ is as large as possible when $x = \frac{\pi}{2},$ or when line $QR$ is perpendicular to line $PO$.


Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $[n]$ with $|A_1|=|A_2|=\cdots =|A_{n+1}|=3$.  Prove that $|A_i\cap A_j|=1$ for some pair $\{i,j\}$.

Solution:
Suppose the problem statement does not hold. It is clear that $n \ge 4$. Choose the smallest $n$ such that $|A_i \cap A_j| \neq 1$ for each $\{i, j\}$.
First, the $(n+1)$ subsets have $3(n+1)$ elements (some repeated) in conjunction. Because there are $n$ elements of $[n]$ total, by the Pigeonhole Principle one element of $[n]$, say $k$, is in at least four subsets. Let these subsets be $A_1, A_2, A_3, A_4$, without loss of generality, and let $A_1$ have elements $k, m, n$. Then without loss of generality let $A_2$ have elements $k, m, p$. If set $A_3$ has elements $k, n, p$, then simple casework shows that it is impossible to create $A_4$ without having $A_4$ intersect one of $A_1, A_2, A_3$ at exactly one element. Thus assume $A_3$ has elements $k, m, q$. Then $A_4$ has elements $k, m, r$. Consider each remaining set $A_i$. Then $A_i$ either contains both $k, m$ or none of them. Because there are $(n-2)$ distinct elements of $[n]$ apart from $k, m$, at most $(n-2)$ subsets can contain $k, m$. Then at least 3 subsets do not contain $k, m$, and it is easy to see that they are disjoint from those subsets that do contain $k, m$. Thus, we can partition $[n]$ into two subsets, one of which is the union of the $t$ subsets that do contain $k, m$, and the other is the union of the $(n+1)-t$ subsets that do not contain $k, m$. Because the latter subset has $(n-t-2) < (n+1)-t - 1$ elements, we may use infinite descent to contradict the minimality of $n$. The proof is complete.


Find the maximum possible number of three term arithmetic progressions in a monotone sequence of $n$ distinct reals.

Solution:
Consider the first few cases for $n$ with the entire $n$ numbers forming an arithmetic sequence
If $n = 3$, there will be one ascending triplet (123). Let's only consider the ascending order for now.
If $n = 4$, the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total.
If $n = 5$, the first 4 numbers give 2 triplets, and the 5th number gives 2 more triplets (135 and 345).
Repeating a few more times, we can quickly see that if $n$ is even, the nth number will give  more triplets in addition to all the prior triplets from the first $n-1$ numbers.
If $n$ is odd, the $n$th number will give  more triplets.
Let $f(n)$ denote the total number of triplets for $n$ numbers. The above two statements are summarized as follows:
If $n$ is even,
If $n$ is odd,
Let's obtain the closed form for when $n$ is even:
Now obtain the closed form when $n$ is odd by using the previous result for when $n$ is even:
Note the ambiguous wording in the question! If the "arithmetic progression" is allowed to be a disordered subsequence, then every progression counts twice, both as an ascending progression and as a descending progression.
Double the expression to account for the descending versions of each triple, to obtain:
~Lopkiloinm (corrected by integralarefun)


$A + B + C$ is an integral multiple of $\pi$. $x, y,$ and $z$ are real numbers. If $x\sin(A)+y\sin(B)+z\sin(C)=x^2\sin(2A)+y^2\sin(2B)+z^2\sin(2C)=0$, show that $x^n\sin(nA)+y^n \sin(nB) +z^n \sin(nC)=0$ for any positive integer $n$.

Solution:
Let $a=xe^{iA}$, $b=ye^{iB}$, $c=ze^{iC}$ be numbers in the complex plane.
Note that $A+B+C=k\pi$ implies $abc=xyz(e^{ik\pi})=\pm xyz$ which is real. Also note that $x\sin(A), y\sin(B), z\sin(C)$ are the imaginary parts of $a, b, c$ and that $x^2\sin(2A), y^2\sin(2B), z^2\sin(2C)$ are the imaginary parts of $a^2, b^2, c^2$ by de Moivre's Theorem. Therefore, $a+b+c$ and $a^2+b^2+c^2$ are real because their imaginary parts sum to zero.
Finally, note that $\frac{1}{2}\left((a+b+c)^2-(a^2+b^2+c^2)\right)=ab+bc+ac$ is real as well.
It suffices to show that $P_n=a^n+b^n+c^n$ is real for all positive integer $n$, which can be shown by induction.
Newton Sums gives the following relationship between sums of the form $P_k=a^k+b^k+c^k$

Where $S_1=a+b+c$, $S_2=ab+bc+ac$, and $S_3=abc$. It is given that $P_0, P_1, P_2$ are real. Note that if  $P_{k-1}, P_{k-2}, P_{k-3}$ are real, then clearly $P_k$ is real because all other parts of the above equation are real, completing the induction.


The insphere of a tetrahedron touches each face at its centroid. Show that the tetrahedron is regular.

Solution:
Let $ABCD$ be the tetrahedron, and let $P$ and $Q$ be the points at which the insphere touches faces $ABC$ and $ABD$ respectively (and therefore the centroids of those faces). Looking at the plane containing $P$, $A$, and $Q$, we see that the intersection of the sphere and the plane is a circle, and that $AP$ and $AQ$ are both tangent to said circle. $[AP]$ and $[AQ]$ are tangents to the circle from the same point and thus have the same length. The same goes for $[BP]$ and $[BQ]$. Thus, triangles $ABP$ and $ABQ$ are congruent, and $\mathbf{\angle PAB = \angle QAB}$.
Let the intersection of $AP$ and $BC$ be $M$, and let the intersection of $AQ$ and $BD$ be $N$. Then $AM$ and $AN$ are medians of $ABC$ and $ABD$, and thus $|AM| = \frac{3}{2}|AP| = \frac{3}{2}|AQ| = |AN|$. We already know from the previous congruence that $\angle{MAB} = \angle{PAB} = \angle{QAB} = \angle{NAB}$, and $|AB|$ is equal to itself. Thus, $MAB$ and $NAB$ are also congruent to each other. Finally, $|BC| = 2|BM| = 2|BN| = |BD|$ (Because $M$ and $N$ are midpoints of $BC$ and $BD$ respectively), and from the congruence of $MAB$ and $NAB$ we have $\angle{CBA} = \angle{MBA} = \angle{NBA} = \angle{DBA}$, and again $|AB|$ is equal to itself. Thus $ABC$ and $ABD$ are congruent, thus $\mathbf{|AC| = |AD|}$ and $\mathbf{|BC| = |BD|}$.
By applying the same logic to faces $BCD$ and $ACD$ we get $|AC| = |BC|$ and $|AD| = |BD|$. Finally, applying the same logic to faces $ACB$ and $ACD$ we get $|AB| = |AD|$ and $|CB| = |CD|$. Putting all these equalities together, we get that all edges of the tetrahedron are equal, and thus the tetrahedron is regular. $\blacksquare$


If $x, y, z$ are reals such that $0\le x, y, z \le 1$, show that $\frac{x}{y + z + 1} + \frac{y}{z + x + 1} + \frac{z}{x + y +  1} \le 1 - (1 - x)(1 - y)(1 - z)$

Solution:
Rewrite the given inequality so that $1$ is isolated on the right side. Set the left side to be $f(x, y, z)$. Now a routine computation shows
$\frac{\partial^2 f}{\partial x^2} = \frac{2y}{(x + z + 1)^3} + \frac{2z}{(x + y + 1)^3}\geq 0$
which shows that $f$ is convex (concave up) in all three variables. Thus the maxima can only occur at the endpoints, i.e. if and only if $x, y, z \in \{0,1\}$. Checking all eight cases shows that the value of the expression cannot exceed 1.


Prove that if $n$ is not a multiple of $3$, then the angle $\frac{\pi}{n}$ can be trisected with ruler and compasses.

Solution:
Let $n=3k+1$.  Multiply throughout by $\pi/3n$. We get
$\frac{\pi}{3} = \frac{\pi \times k}{n} + \frac{\pi}{3n}$
Re-arranging, we get
$\frac{\pi}{3} - \frac{\pi \times k}{n} = \frac{\pi}{3n}$
A way to interpret it is that if we know the value $k$, then the remainder angle of subtracting $k$ times the given angle from $\frac{\pi}{3}$ gives us $\frac{\pi}{3n}$, the desired trisected angle.
This can be extended to the case when $n=3k+2$ where now, the equation becomes
$\frac{\pi}{3} - \frac{\pi \times k}{n} = \frac{2\pi}{3n}$
Hence in this case, we will have to subtract $k$ times the original angle from $\frac{\pi}{3}$ to get twice the the trisected angle. We can bisect it after that to get the trisected angle.


What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a train link. No three towns, $A, B, C$ are such that the links between $AB, AC$ and $BC$ are all air, all bus or all train.

Solution:
Assume $AB$, $AC$, and $AD$ are all rail.
None of $BC$, $CD$, or $CD$ can be rail, as those cities would form a rail triangle with $A$.
If $BC$ is bus, then $BD$ is bus as well, as otherwise $B$ has all three types.
However, $CD$ cannot be rail (as $\triangle ACD$ would be a rail triangle), bus (as $BCD$ would be a bus triangle), or ferry (as $C$ and $D$ would have all three types).
Therefore, no city can have three connections of the same type.
Assume there are 5 towns - $A$, $B$, $C$, $D$, and $E$.
Two connections from $A$ must be of one type, and two of another; otherwise there would be at least three connections of the same type from $A$, which has been shown to be impossible.
Let $AB$ and $AC$ be rail connections, and $AD$ and $AE$ be bus.
Assume $CD$ is air.
$BC$ cannot be rail ($\triangle ABC$ would be a rail triangle) or bus ($C$ would have all three types), so $BC$ must be air.
$DE$ cannot be bus ($\triangle ADE$ would be a bus triangle) or rail ($D$ would have all three types), so $DE$ must be air.
$BE$ cannot be rail ($E$ would have all three types) or bus ($B$ would have all three types), so $BE$ must be air.
However, $BD$ cannot be rail ($D$ would have all three types), bus ($B$ would have all three types), or air ($D$ would have three air connections).
Therefore, the assumption that $CD$ is air is false.
$CD$ can equally be rail or bus; assume it is bus.
$BC$ cannot be rail ($\triangle ABC$ would be a rail triangle) or air ($C$ would have all three types), so $BC$ must be bus.
$BD$ cannot be air ($B$ would have all three types) or bus ($D$ would have three bus connections), so $BD$ must be rail.
$DE$ cannot be air ($D$ would have all three types) or bus ($D$ would have three bus connections), so $DE$ must be rail.
$CE$ cannot be air ($C$ would have all three types) or bus ($E$ would have three bus connections), so $CE$ must be rail.
The only connection remaining is $BE$, which cannot be orange as both $B$ and $D$ would have all three types, but this means there are no air connections.
Therefore, it is impossible with five (or more) towns.
A four-town mapping is possible:
$AB$, $BC$, $CD$, and $DA$ are connected by bus.
$AC$ is connected by rail.
$BD$ is connected by air.
Therefore, the maximum number of towns is $4$.


Show that for any triangle, $\frac{3\sqrt{3}}{2}\ge \sin(3A) + \sin(3B) + \sin (3C) \ge -2$.
When does the equality hold?

Solution:
Given three angles that add to 180°, one can construct a triangle from them.  This is true even if the angles are negative; however, the resulting triangle could then be recognized as having only positive angles, and the interpretation with negative angles (and, likely, negative side lengths) might be considered perverse.  In this case, the problem must be interpreted as ruling out such "perverse" triangles; otherwise, its angles could be -30°, -20°, and 230°, in which case sin(3x) becomes -1, -√3/2, and -1/2 respectively, which add to about -2.3, contradicting the problem statement.
The constraints on the angles of a non-perverse triangle are: $0\degree\leq A,B,C\leq180\degree$ (Error compiling LaTeX. Unknown error_msg), and $A+B+C=180\degree$ (Error compiling LaTeX. Unknown error_msg).
In fact, at this point, we only care about 3A, 3B, and 3C.  Let us call them x, y, and z.  We have:
0 ≤ x,y,z ≤ 540°; x+y+z = 540°.  Prove $\frac{3\sqrt{3}}{2}\ge \sin(x) + \sin(y) + \sin (z) \ge -2$.
Now.  Without loss of generality, assume x ≤ y ≤ z.  It follows that x ≤ 180° and z ≥ 180° [otherwise, x+y+z would be strictly greater than 180°, or strictly less than 180°, respectively].
Since sin(u) is nonnegative over the interval [0, 180°], and -1 ≤ sin u ≤ 1 for all real u, we can immediately use the x ≤ 180° result to show that sin x + sin y + sin z ≤ 0 + -1 + -1 = -2.  This proves the lower bound on sin x + sin y + sin z; equality occurs when sin x = 0 and sin y = sin z = -1, and this is reachable only when y = z = 270° and x = 0°, which translates into A = 0° and B = C = 90°.  (This might be considered a degenerate triangle and ruled out; in that case, the lower bound could be stated as a strict one.)
Now for the upper bound.  It is true that sin(u) is non-positive over the interval [180°, 360°].  Also, 3√3/2 is greater than 2 (it is roughly 2.6): if you square it, you get 27/4, while if you square 2, you get 16/4.  So... We know z ≥ 180°.  If z ≤ 360°, then sin z ≤ 0, and then sin x + sin y + sin z ≤ 1 + 1 + 0 = 2 < 3√3/2.  Therefore, we need merely handle the case where z ≥ 360°.  sin(u + 360°) = sin(u), so we may as well subtract 360° from z.  Then the problem effectively becomes:
"Given 0 ≤ x,y,z ≤ 180° and x+y+z = 180°, prove that sin x + sin y + sin z ≤ 3√3/2.  Also find when you get equality."
This is probably a well-known theorem, but I shall address it here anyway.
Let us suppose that {x,y,z} is the selection of x,y,z given the above constraints with the largest value of sin x + sin y + sin z.  It suffices to show that, for this selection, sin x + sin y + sin z ≤ 3√3/2.  We shall see that, given these constraints, sin x + sin y + sin z increases when you move any two variables closer together, and it is maximized when x=y=z.
Lemma with some general expository use: A special case of a result called "Jensen's inequality".  If f(x) is well-behaved and f'(x) is strictly decreasing over an open interval (a, b), then, for any {x,y} selected from that interval with x ≠ y, $2f(\frac{x + y}{2}) > f(x) + f(y).$
So.  sin(u) is well-behaved, and sin'(u) = cos(u), which is strictly decreasing over the open interval (0, 180°).  Suppose that {x,y,z} are not all the same value.  Then, without loss of generality, suppose x ≠ y.  Let a = (x+y)/2.  Then the selection {a,a,z} also satisfies the constraints 0 ≤ a,a,z ≤ 180° and a+a+z ≤ 180°.  Furthermore, by the above lemma, 2*sin a > sin x + sin y, so this new selection {a,a,z} has a larger corresponding value sin a + sin a + sin z than the selection {x,y,z}.  This contradicts our original assumption that {x,y,z} was chosen to have the largest value of sin x + sin y + sin z.  Therefore, x=y=z.
Then, since x+y+z = 180°, we conclude x=y=z=60°.  Then sin x + sin y + sin z = 3 * sin 60° = 3 * √3/2.  So 3√3/2 is indeed the maximum value of sin x + sin y + sin z, which was to be proven.  Translating back into the previous problem (0 ≤ x,y,z ≤ 540°; x+y+z = 540°), the maximum occurs when x=y=60° and z=420°; translating into the original problem, we have proven the upper bound, and equality with the upper bound occurs when A=B=20° and C = 140°.


A convex polygon has $n$ sides. Each vertex is joined to a point $P$ not in the same plane. If $A, B, C$ are adjacent vertices of the polygon take the angle between the planes $PAB$ and $PBC$. The sum of the $n$ such angles equals the sum of the $n$ angles in the polygon. Show that $n=3$.

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


Show that for any positive real $x$, $[nx]\ge \sum_{1}^{n}\left(\frac{[kx]}{k}\right)$

First of all we write $[kx]=kx-\{kx\}$. So, we need to prove that
$\sum_{1}^{n}\left(\frac{\{kx\}}{k}\right)\geq \{nx\}.$
Let's denote $a_k=\{kx\}$. It is easy to see that $a_k+a_m \geq a_{k+m}$. We need to prove
$\sum_{1}^{n}\left(\frac{a_k}{k}\right)\geq a_n.$
We will prove it by induction by $n$. The base is obvious, so we need to make a step.
Let's take $m$ such that $\frac{a_m}{m}$ is minimal. If $m=n$ then our inequality is obvious. So, $m<n$. Then, by induction, $\sum_{1}^{n-m}\left(\frac{a_k}{k}\right)\geq a_{n-m}$ and $\sum_{n-m+1}^{n}\left(\frac{a_k}{k}\right)\geq m\cdot \frac{a_m}{m}=a_m$. Now we can add these two inequalities and get


In a party with $1982$ people, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else?

Solution:
We induct on $n$ to prove that in a party with $n$ people, there must be at least $(n-3)$ people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people $A, B, C$, who do not know each other.)
Base case: $n = 4$ is obvious.
Inductive step: Suppose in a party with $k$ people (with $k \ge 4$), at least $(k-3)$ people know everyone else. Consider a party with $(k+1)$ people. Take $k$ of the people (leaving another person, $A$, out) and apply the inductive step to conclude that at least $(k-3)$ people know everyone else in the $k$-person group, $G$.
Now suppose that everyone in the group $G$ knows each other. Then take $3$ of these people and $A$ to deduce that $A$ knows a person $B \in G$, which means $B$ knows everyone else. Then apply the inductive step on the remaining $k$ people (excluding $B$) to find $(k-3)$ people out of them that know everyone else (including $B$, of course). Then these $(k-3)$ people and $B$, which enumerate $(k-2)$ people, know everyone else.
Suppose that there exist two people $B, C \in G$ who do not know each other. Because $k-3 \ge 1$, there exist at least one person in $G$, person $D$, who knows everyone else in $G$. Now, take $A, B, C, D$ and observe that because $B, C$ do not know each other, either $A$ or $D$ knows everyone else of $A, B, C, D$ (by the problem condition), so in particular $A$ and $D$ know each other. Then apply the inductive step on the remaining $k$ people (excluding $D$) to find $(k-3)$ people out of them that know everyone else (including $D$, of course). Then these $(k-3)$ people and $D$, which enumerate $(k-2)$ people, know everyone else.
This completes the inductive step and thus the proof of this stronger result, which easily implies that at least $1982 - 3 = \boxed{1979}$ people know everyone else.