I have an $n \times n$ sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let $b(n)$ be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants $c$ and $d$ such that
for all $n > 0$.

Solution:
The upper bound requires an example of a set of $\frac{1}{5}n^2 + dn$ blocks whose removal makes it impossible to remove any further blocks. It suffices to show that we can tile the plane by tiles containing one block for every five stamps such that no more blocks can be chosen. Two such tilings are shown below with one tile outlined in heavy lines. Given an $n\times n$ section of the tiling take all blocks lying entirely within that section and add as many additional blocks as possible. If the basic tile is contained in an $(m + 1)\times (m + 1)$ square, then the $n\times n$ section is covered by tiles contained in a concentric $(n + 2m)\times (n + 2m)$ square. Hence there are at most $\frac{1}{5}(n + 2m)^2$ blocks entirely within the section. For an $n\times n$ section of the tiling, there are at most $4n$ blocks which lie partially in and partially out of that section (hence these blocks contain at most $8n$ stamps in the $n\times n$ square) and each of the additional blocks must contain one of these stamps. Thus there are at most $8n$ additional blocks. Thus there are at most

blocks total.
The lower bound requires an argument. Suppose that we have a set of $b(n)$ blocks whose removal makes removing any further blocks impossible.

There are $2n(n - 2)$ potential blocks of three consecutive stamps in a row or column. Each of these must meet at least one of the $b(n)$ blocks removed. Conversely, each of the $b(n)$ blocks removed meets at most 14 of these potential blocks (5 oriented the same way, including itself, and 9 oriented the orthogonal way). Therefore $14b(n)\geq 2n(n - 2)$ or

Call a stamp used if it belongs to one of the $b(n)$ removed blocks. Consider the $(n - 2)^2$ five-stamp crosses centered at each stamp not on an edge of the sheet. Each cross must contain two used stamps. (One stamp not in the center is not enough to prevent another block from being torn out, and it is impossible to use one stamp in the center and use no other stamps in the cross.) In addition, each block not lying along an edge of the sheet lies entirely inside one cross, which thus contains three used stamps. There are at most $4n/3$ of the $b(n)$ blocks lying along the edges, hence there are at least $b(n) - 4n/3$ crosses containing three used stamps.
Now count the number of pairs of a used stamp and a cross containing that stamp, in two ways. First counting block by block, we get $3b(n)$ used stamps, and each used stamp is contained in at most five crosses (exactly five if it is not on an edge), for a total of at most $15b(n)$ pairs. Next, counting cross by cross, each of the $(n - 2)^2$ crosses contains at least two used stamps and we have at least $b(n) - 4n/3$ crosses containing three used stamps, for a total of at least $2(n - 2)^2 + b(n) - 4n/3$ pairs. Therefore

or

Call a stamp used if it belongs to one of the $b(n)$ removed blocks. Count the number of pairs consisting of a used stamp and an adjacent unused stamp, in two ways.
There are at least $(n - 2)^2 - 3b(n)$ unused stamps which are not on an edge. Since no more blocks can be torn out, either the stamp to the left or right and either the stamp or below such an unused stamp must be used. Thus we have at least $2n^2 - 8n - 6b(n)$ such pairs.
Each block removed is adjacent to at most eight other stamps. However these eight stamps contain two blocks of three consecutive stamps. Hence at most six of these eight stamps can be unused. Thus each of the $b(n)$ blocks removed is involved in at most six pairs. Thus there are at most $6b(n)$ pairs.
Combining these we have

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


(Titu Andreescu)
Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

We proceed by induction.  For our base case, $n=1$, we have the number 5.  Now, suppose that there exists some number $a \cdot 5^{n-1}$ with $n-1$ digits, all of which are odd.  It is then sufficient to prove that there exists an odd digit $k$ such that $k\cdot 10^{n-1} + a \cdot 5^{n-1} = 5^{n-1}(k \cdot 2^{n-1} + a)$ is divisible by $5^n$.  This is equivalent to proving that there exists an odd digit $k$ such that $k \cdot 2^{n-1} + a$ is divisible by 5, which is true when $k \equiv -3^{n-1}a \pmod{5}$.  Since there is an odd digit in each of the residue classes mod 5, $k$ exists and the induction is complete.

First, we note that there are $5^n$ $n$ digit numbers with only odd digits.  Now, we will prove that none of these numbers have the same residue mod $5^n$, and therefore one of them must be 0 mod $5^n$.
Proof by contradiction:
Assume we have two distinct numbers $A_1A_2A_3...A_n$ and $B_1B_2B_3...B_n$ with only odd digits that leave the same residue mod $5^n$.  Then, subtracting the larger from the smaller would yield a new number that is a multiple of $5^n$ and has only even digits.  We could then halve all of the digits in that number to get a second multiple of $5^n$ with at most n digits that only uses the digits 0 through 4.
Lemma: Every multiple of $5^n$ with n digits or less has a 5 as one of its digits.
All numbers of this type can be written as $k5^n$.  Then, let $k$ have $x$ factors of $2$ in it.  ($x<n$, or else our number would have more than n digits).  So, we have $k5^n=a2^x5^n=a*10^x*5^{n-x}$ for some odd a.  Now $a*10^x*5^{n-x}$ is an odd multiple of 5  ($a5^{n-x}$)  with x zeroes after it, and all multiples of 5 end in 5.  Therefore, $a*10^x*5^{n-x}$ always contains a 5 as its $(x+1)^{st}$ digit, and we have proven our lemma.
By our lemma, our number with only the digits 0 through 4 cannot be a multiple of $5^n$, and so we have reached a contradiction.  QED
Note:  Not only does this prove the desired claim that there exists such a number, but it also proves that there is exactly one such number.

$5^n \pmod {10} \equiv 5$.
$2^k 5^n \pmod {10^{k +1} } \equiv  10^k 5^{n-k} \equiv 5 \cdot 10^k$.
For any $n$, we can construct a $a = 5^n \cdot \sum_{0 \leq i < n}{2^{x_i}}$:
$x_0 = 1$
$a_i = 5^n \sum_{0 \leq j \leq i}{2^{x_j}}$
$x_{i} = \frac{a_{i-1}}{10^{i}} + 1 \pmod 2$. (This makes the $10^{i}$ place of $a_{i}$ odd, without changing the the smaller place digits).
$a = a_{n-1} = 5^n \cdot  \sum_{0 \leq j < n}{2^{x_j}}$ ,  with digits in place $10^i$ odd, for $0 \leq i<n$.
Since $\sum_{0 \leq j < n}{2^{x_j}}  < 2^n$,  $a < 5^n 2^n = 10^n$.
By construction, the digits in all the places up through  $10^{n-1}$ are odd, and since $a<10^n$, there are no other digits.
In fact, if $A_m = a$ that solves the case $n=m$,  then $A_{m+1} \mod 10^ m \equiv A_m$.
Note that in some cases (like $n=5$) , both of $x_{n-1} \in \{0,1\}$ yield distinct numbers $a-5\cdot10^{n-1}$ and $a$ with all odd digits.
$a-5\cdot10^{n-1}$ has $n-1<n$ digits, and so $x_{n-1}=1$ is needed for padding.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


A convex polygon $\mathcal{P}$ in the plane is dissected into smaller convex polygons by drawing all of its diagonals. The lengths of all sides and all diagonals of the polygon $\mathcal{P}$ are rational numbers. Prove that the lengths of all sides of all polygons in the dissection are also rational numbers.

Solution:
When $\mathcal{P}$ is a triangle, the problem is trivial.  Otherwise, it is sufficient to prove that any two diagonals of the polygon cut each other into rational lengths.  Let two diagonals which intersect at a point $P$ within the polygon be $AC$ and $BD$.  Since $ABCD$ is a convex quadrilateral with sides and diagonals of rational length, we consider it in isolation.
By the Law of Cosines, $\cos BAC = \frac{AB^2 + CA^2 - BC^2}{2AB \cdot CA}$, which is rational.  Similarly, $\cos CAD$ is rational, as well as $\cos BAD = \cos (BAC + CAD) = \cos BAC \cos CAD - \sin BAC \sin CAD$.  It follows that $\sin BAC \sin CAD$ is rational.  Since $\sin^2 CAD = 1 - \cos^2 CAD$ is rational, this means that $\frac{\sin BAC \sin CAD}{\sin^2 CAD} = \frac{\sin BAC}{\sin CAD} = \frac{\sin BAP}{\sin PAD}$ is rational.  This implies that $\frac{ AB \sin BAP}{ AD \sin PAD} = \frac{\frac{1}{2} AB \cdot AP \sin BAP}{\frac{1}{2} AP \cdot AD \sin PAD} = \frac{[BAP]}{[PAD]} = \frac{BP}{PD}$ is rational.  Define $r$ to be equal to $\frac{BP}{PD}$. We know that $\frac{BP}{PD}$ is rational; hence $r$ is rational. We also have $(1+r)PD = (1+\frac{BP}{PD} )PD = PD + BP = BD$, which is, of course, rational.  It follows that $BP$ and $PD$ both have rational length, as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $n \neq 0$. For every sequence of integers
satisfying $0 \le a_i \le i$, for $i=0,\dots,n$, define another sequence
by setting $t(a_i)$ to be the number of  terms in the sequence $A$ that precede the term $a_i$ and are different from $a_i$. Show that, starting from any sequence $A$ as above, fewer than $n$ applications of the transformation $t$ lead to a sequence $B$ such that $t(B) = B$.

Solution:
Consider some sequence $C = c_0, \ldots, c_n$ as the image of $A$ after $t$ has been applied some finite number of times.
Lemma 1.  If $t(c_k) = c_k = j$, then ${} c_j = \cdots = c_{j+i} = \cdots = c_k = j$ ($0 \le i \le k-j$).
Proof. Since the $j$ terms $c_0, \ldots, c_{j-1}$ are all less than $j$, no other terms that precede $c_{k}$ can be unequal to $c_k$.  The lemma follows.
Lemma 2. If $t(c_k) = c_k = j$, then $t^2(c_k) = t(c_k)$ (where $f^2(x) = f(f(x))$).
Proof.  Since only $i$ terms precede the term $c_i$, we will have $t^m(c_i) \le i$, for any integer $m$.  This means that we will always have $t^m (c_0), \ldots, t^m (c_{j-1}) < j$.  This means that $c_j = t(c_j) = \cdots = c_k = t(c_k)$, and the lemma follows by iteration.
Thus we may regard a term $c_k$ as stable if $t(c_k) = c_k$.  We will call a sequence stable if all of its terms are stable.
Lemma 3.  If $c_k =j$ is not stable, then $t(c_k) > c_k$.
Proof. We have $c_0, \ldots, c_{j-1} < j$, so we always have $t(c_k) \ge c_k$.  Equality implies that $c_k$ is stable.
We will now prove the problem by induction.  For the base case, $n=1$, we have either 0,0 or 0,1, both of which are stable.  Now, suppose that $t^{n-2}(a_0), \ldots, t^{n-2}(a_{n-1})$ are stable.  We must then have $t^{n-2}(a_n) \in \{ n-2, n-1, n\}$.  If $t^{n-2}(a_n) = n$, then it is already stable.  If $t^{n-2}(a_n) = n-1$, then either it is already stable or $t^{n-1}(a_n) = n$, which is stable.  If $t^{n-2}(a_n) = t^{n-2}(a_{n-1})$, then $t^{n-2}(a_n)$ must already be stable.  The only possibilities remaining are $t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) = n-1$ and $t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) < n-2$.  In the first case, we must have $t^{n-1}(a_n)$ equal to $n-1$ or $n$, both of which will make it stable.  In the second case, we must have $t^{n-2}(a_{n-2}) = t^{n-2}(a_{n-1}) < n-2$, giving us $t^{n-1}(a_n) = n$, which will make it stable.  Thus the induction is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $ABC$ be a triangle. A circle passing through $A$ and $B$ intersects segments $AC$ and $BC$ at $D$ and $E$, respectively. Lines $AB$ and $DE$ intersect at $F$, while lines $BD$ and $CF$ intersect at $M$. Prove that $MF = MC$ if and only if $MB\cdot MD = MC^2$.

Extend segment $DM$ through $M$ to $G$ such that $FG\parallel CD$.

Then $MF = MC$ if and only if quadrilateral $CDFG$ is a parallelogram, or, $FD\parallel CG$. Hence $MC = MF$ if and only if $\angle GCD = \angle FDA$, that is, $\angle FDA + \angle CGF = 180^\circ$.
Because quadrilateral $ABED$ is cyclic, $\angle FDA = \angle ABE$. It follows that $MC = MF$ if and only if

that is, quadrilateral $CBFG$ is cyclic, which is equivalent to

Because $\angle DMC = \angle CMB$, $\angle CBM = \angle DCM$ if and only if triangles $BCM$ and $CDM$ are similar, that is

or $MB\cdot MD = MC^2$.

We first assume that $MB\cdot MD = MC^2$. Because $\frac{MC}{MD} = \frac{MB}{MC}$ and $\angle CMD = \angle BMC$, triangles $CMD$ and $BMC$ are similar. Consequently, $\angle MCD = \angle MBC$. This exact condition can also be visualized through power of M with respect to the circumcircle of triangle $BDC$ and getting the angle condition from the alternate segment theorem.

Because quadrilateral $ABED$ is cyclic, $\angle DAE = \angle DBE$. Hence

implying that $AE\parallel CF$, so $\angle AEF = \angle CFE$. Because quadrilateral $ABED$ is cyclic, $\angle ABD = \angle AED$. Hence

Because $\angle FBM = \angle DFM$ and $\angle FMB = \angle DMF$, triangles $BFM$ and $FDM$ are similar. Consequently, $\frac{FM}{DM} = \frac{BM}{FM}$, or $FM^2 = BM\cdot DM = CM^2$. Therefore $MC^2 = MB\cdot MD$ implies $MC = MF$.
Now we assume that $MC = MF$. Applying Ceva's Theorem to triangle $BCF$ and cevians $BM, CA, FE$ gives

implying that $\frac{BA}{AF} = \frac{BE}{EC}$, so $AE\parallel CF$.
Consequently, $\angle DCM = \angle DAE$. Because quadrilateral $ABED$ is cyclic, $\angle DAE = \angle DBE$. Hence

Because $\angle CBM = \angle DCM$ and $\angle CMB = \angle DMC$, triangles $BCM$ and $CDM$ are similar. Consequently, $\frac{CM}{DM} = \frac{BM}{CM}$, or $CM^2 = BM\cdot DM$.
Combining the above, we conclude that $MF = MC$ if and only if $MB\cdot MD = MC^2$.

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$ be positive real numbers. Prove that

Note that

Setting $x = a$ and $y = b + c$ yields

Thus, we have

and its analogous forms. Thus, the desired inequality is equivalent to

Because $(b + c)^2\leq 2(b^2 + c^2)$, we have $2a^2 + (b + c)^2\leq 2(a^2 + b^2 + c^2)$ and its analogous forms. It suffices to show that

or,

Multiplying this out the left-hand side of the last inequality gives $3(a^2 + b^2 + c^2) - 2(ab + bc + ca)$. Therefore the inequality $(*)$ is equivalent to $2[a^2 + b^2 + c^2 - (ab + bc + ca)]\geq 0$, which is evident because

Equality holds when $a = b = c$.

Given a function $f$ of three variables, define the cyclic sum

We first convert the inequality into

Splitting the 5 among the three terms yields the equivalent form

The numerator of the term shown factors as $(2a - x)(2a - 5x)$, where $x = b + c$. We will show that

Indeed, $(3)$ is equivalent to

which reduces to

evident. We proved that

hence $(2)$ follows. Equality holds if and only if $2a = b + c, 2b = c + a, 2c = a + b$, i.e., when $a = b = c$.

Given a function $f$ of $n$ variables, we define the symmetric sum

where $\sigma$ runs over all permutations of $1, \ldots, n$ (for a total of $n!$ terms).
We combine the terms in the desired inequality over a common denominator and use symmetric sum notation to simplify the algebra. The numerator of the difference between the two sides is

Recalling Schur's Inequality, we have

or

Hence,

and by repeated AM-GM inequality,

and

Adding these three inequalities yields the desired result.

Since, the inequality is homogeneous we may assume that $a+b+c=1$ and $0<a,b, c<1$.
The first time on the LHS is the inequality will be:

Note that equality holds when $a=b=c=1/3$.
A simple sketch of $f(x)$ on $[0,1]$ shows that the curve lies below the tangent line at $1/3$.
Which has the equation of the form $y=\frac{12x+4}{3}$.
So we claim that
Upon clearing the denominators, it is equivalent to:
Note that since the curve and the line intersect at $1/3, 3a-1$ would be a factor.

Adding the similar inequalities for $b$ and $c$ gives:

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


At the vertices of a regular hexagon are written six nonnegative integers whose sum is 2003. Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number 0 appears at all six vertices.

Solution: Assume the original numbers are $a,b,c,d,e,f$. Since $a+b+c+d+e+f$ is odd, either $a+c+e$ or $b+d+f$ must be odd. WLOG let $a+c+e$ be odd and $a\ge c\ge e \ge 0$.


(Titu Andreescu) Let $ABCD$ be a quadrilateral circumscribed about a circle, whose interior and exterior angles are at least 60 degrees. Prove that

When does equality hold?

It suffices to show that  because the other side of the inequality follows by symmetry. By Pitot's Theorem, we have $AB-AD=BC-CD$. WLOG, let $AB \geq AD$. Then we have that $BC \geq CD$, so we must show $BC^3-CD^3 \leq 3(AB^3-AD^3)$. If $AB=AD$, we are done. Therefore, we will assume for the rest of the proof that $AB>AD$, $BC>CD$.
Then we would like to show that
By the Law of Cosines, we have that  where $-1 \leq k_1, k_2 \leq 1$ (this is because $60^{\circ} \leq \angle BAD,\angle BCD \leq 120^{\circ}$). Therefore,  Then we wish to show that  and we are done. $\blacksquare$

By a well-known property of tangential quadrilaterals, the sum of the two pairs of opposite sides are equal; hence $a + c = b + d \Rightarrow a - b = d - c \Rightarrow |a - b| = |d - c|$ Now we factor the desired expression into $\frac {|d - c|(c^2 + d^2 + cd)}{3} \le|a - b|(a^2 + b^2 + ab)\le 3|d - c|(c^2 + d^2 + cd)$. Temporarily discarding the case where $a = b$ and $c = d$, we can divide through by the $|a - b| = |d - c|$ to get the simplified expression $(c^2 + d^2 + cd)/3\le a^2 + b^2 + ab\le 3(c^2 + d^2 + cd)$.
Now, draw diagonal $BD$. By the law of cosines, $c^2 + d^2 + 2cd\cos A = BD$. Since each of the interior and exterior angles of the quadrilateral is at least 60 degrees, we have that $A\in [60^{\circ},120^{\circ}]$. Cosine is monotonically decreasing on this interval, so by setting $A$ at the extreme values, we see that $c^2 + d^2 - cd\le BD^2 \le c^2 + d^2 + cd$. Applying the law of cosines analogously to $a$ and $b$, we see that $a^2 + b^2 - ab\le BD^2 \le a^2 + b^2 + ab$; we hence have $c^2 + d^2 - cd\le BD^2 \le a^2 + b^2 + ab$ and $a^2 + b^2 - ab\le BD^2 \le c^2 + d^2 + cd$.
We wrap up first by considering the second inequality. Because $c^2 + d^2 - cd\le BD^2 \le a^2 + b^2 + ab$, $\text{RHS}\ge 3(a^2 + b^2 - ab)$. This latter expression is of course greater than or equal to $a^2 + b^2 + ab$ because the inequality can be rearranged to $2(a - b)^2\ge 0$, which is always true. Multiply the first inequality by $3$ and we see that it is simply the second inequality with the variables swapped; hence by symmetry it is true as well.
Equality occurs when $a = b$ and $c = d$, or when $ABCD$ is a kite.


(Kiran Kedlaya) Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties:
(a) For $i = 1, \dots, n$, $a_i \in S$.
(b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$.
(c) For any integers $x,y \in S$, if $x + y \in S$, then $x - y \in S$.
Prove that $S$ must be equal to the set of all integers.

Solution:
Suppose $a_i$ has only one element; then for the greatest common divisor to be 1, $1$ has to be the sole element. Then $1$ is in $S$ by (a), $0$ is in $S$ by (b), $0 + 1 = 1\in S\Rightarrow 0 - 1 = - 1\in S$ by (c), and we can apply (c) analogously to get that $n\cdot 1 \in S$ for integers $n$ and hence $S$ is the set of all integers, as desired.
Lemma: If $x,y\in a_i$, then $ax + by\in S$ for integers $a,b$.
Proof: Assume $a_i$ has at least two elements; $x$ and $y$. By (b), $x - y$ is in $S$, and by the application of (c) above, we get that $n(x - y)$ for integers $n$ is in $S$. Then apply (c) to $n(x - y)$ and $ny$ or $nx$ to get that $ax + by\in S$ for all $a,b\in \mathbb{Z}$.
Now let the terms be $a_1,a_2,\ldots,a_{n}$. By applying our lemma many times, all numbers in  the form $\sum c_1a_1$ for a sequence of integers $c_i$ are attainable if the sequence is of a length which is a power of 2. If not, we "pad" the sequence with many copies of an existing element of the sequence until it does have a length which is a power of 2 - it is apparent that this will not change $S$.
By Schur's theorem (a generalization of the more well-known Chicken McNugget theorem), every integer greater than some integer $n$ is attainable, and hence there are two members of $S$ in the form $\sum c_1a_1$ which are consecutive integers. Furthermore, because such numbers are closed under addition, their sum is in $S$, and hence so is their difference; $1$. Thus, by the argument at the beginning at this proof, $S$ is the set of all integers, as desired.


(Ricky Liu) For what values of $k > 0$ is it possible to dissect a $1 \times k$ rectangle into two similar, but incongruent, polygons?

Solution:
We will show that a dissection satisfying the requirements of the problem is possible if and only if $k\neq 1$.
We first show by contradiction that such a dissection is not possible when $k = 1$. Assume that we have such a dissection. The common boundary of the two dissecting polygons must be a single broken line connecting two points on the boundary of the square (otherwise either the square is subdivided in more than two pieces or one of the polygons is inside the other). The two dissecting polygons must have the same number of vertices. They share all the vertices on the common boundary, so they have to use the same number of corners of the square as their own vertices. Therefore, the common boundary must connect two opposite sides of the square (otherwise one of the polygons will contain at least three corners of the square, while the other at most two). However, this means that each of the dissecting polygons must use an entire side of the square as one of its sides, and thus each polygon has a side of length 1. A side of longest length in one of the polygons is either a side on the common boundary or, if all those sides have length less than 1, it is a side of the square. But this is also true of the polygon, which means that the longest side length in the two polygons is the same. This is impossible since they are similar but not congruent, so we have a contradiction.
We now construct a dissection satisfying the requirements of the problem when $k\neq 1$. Notice that we may assume that $k > 1$, because a $1\times k$ rectangle is similar to a $1\times\frac{1}{k}$ rectangle.
We first construct a dissection of an appropriate chosen rectangle (denoted by $ABCD$ below) into two similar noncongruent polygons. The construct depends on two parameters ($n$ and $r$ below). By appropriate choice of these parameters we show that the constructed rectangle can be made similar to a $1\times k$ rectangle, for any $k > 1$. The construction follows.
Let $r > 1$ be a real number. For any positive integer $n$, consider the following sequence of $2n + 2$ points:

and so on, until

Define a rectangle $ABCD$ by

The sides of the $(2n+2)$-gon $A_1A_2\ldots A_{2n+1}B$ have lengths

and the sides of the $(2n+2)$-gon $A_0A_1A_2\ldots A_{2n}D$ have lengths

respectively. These two polygons dissect the rectangle $ABCD$ and, apart from orientation, it is clear that they are similar but noncongruent, with coefficient of similarity $r > 1$. The rectangle $ABCD$ and its dissection are thus constructed.
The rectangle $ABCD$ is similar to a rectangle of size $1\times f_n(r)$, where

It remains to show that $f_n(r)$ can have any value $k > 1$ for appropriate choices of $n$ and $r$. Choose $n$ sufficiently large so that $1 + \frac{1}{n} < k$. Since

and $f_n(r)$ is a continuous function for positive $r$, there exists an $r$ such that $1 < r < k$ and $f_n(r) = k$, so we are done.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Melanie Wood)
Alice and Bob play a game on a 6 by 6 grid.  On his or her turn, a player chooses a rational number not yet appearing on the grid and writes it in an empty square of the grid.  Alice goes first and then the players alternate.  When all squares have numbers written in them, in each row, the square with the greatest number is colored black.  Alice wins if she can then draw a line from the top of the grid to the bottom of the grid that stays in black squares, and Bob wins if she can't.  (If two squares share a vertex, Alice can draw a line from on to the other that stays in those two squares.)  Find, with proof, a winning strategy for one of the players.

Before the game, Bob may select three useless squares per row.  He may then move according to the following rules:
Bob can always do this because there are an even number of squares in each row.
In this way, Bob can prevent any useless square from being colored black at the end.  Then it will be sufficient for Bob to make the squares (1,1), (2,1), (2,2), (3,2), (3,3), (4,3), (4,4), (5,4), (5,5), (6,5), (6,6) useless, where $(m,n)$ is the square in the $m$th column and $n$th row.  Thus Bob can always win.
Note that it is not necessary for Bob to move first; even if he moves second, he will always be able to ensure that at least two squares per row of his choosing are not colored black.

Bob may move according to the following rules:
In this way, there will be 2 columns in between the black squares in rows 1 and 2, so they cannot possibly touch, which means that Bob will win.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Titu Andreescu)
Let $a$, $b$, and $c$ be positive real numbers.  Prove that

We first note that for positive $x$, $x^5 + 1 \ge x^3 + x^2$.  We may prove this in the following ways:
It thus becomes sufficient to prove that
We present two proofs of this inequality:
We get the desired inequality by taking $m_{1,1} = a^3$, $m_{2,2} = b^3$, $m_{3,3} = c^3$, and $m_{x,y} = 1$ when $x \neq y$. We have equality if and only if $a = b = c = 1$.
by Chebyshev's Inequality. By the Cauchy-Schwarz Inequality we have
Applying Chebyshev's and the Cauchy-Schwarz Inequalities each once more, we get
and
Multiplying the above four inequalities together yields
as desired, with equality if and only if $x = y = z = 1$.
By the AM-GM inequality, it is true that $a^3 + a^3b^3 + 1 \ge 3a^2b$, and so it is clear that
Additionally, again by AM-GM, it is true that $a^3b^3c^3 + a^3 + b^3 + c^3 + 1 + 1 \ge 6abc$, and so
as desired.

It is also possible to solve this inequality by expanding terms and applying brute force, either before or after proving that $x^5 - x^2 + 3 \ge x^3 + 2$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zuming Feng) A circle $\omega$ is inscribed in a quadrilateral $ABCD$.  Let $I$ be the center of $\omega$.  Suppose that
Prove that $ABCD$ is an isosceles trapezoid.

Solution:
Our proof is based on the following key Lemma.
Lemma: If a circle $\omega$, centered at $I$, is inscribed in a quadrilateral $ABCD$, then
Proof: Since circle $\omega$ is inscribed in $ABCD$, we get $m\angle DAI = m\angle IAB = a$, $m\angle ABI = m\angle IBC = b$, $m\angle BCI = m\angle ICD = c$, $m\angle CDI = m\angle IDA = d$, and $a + b + c + d = 180^\circ$. Construct a point $P$ outside of the quadrilateral such that $\triangle ABP$ is similar to $\triangle DCI$. We obtain

implying that the quadrilateral $PAIB$ is cyclic. By Ptolemy's Theorem, we have $AI\cdot BP + BI\cdot AP = AB\cdot IP$, or

Because $PAIB$ is cyclic, it is not difficult to see that, as indicated in the figure, $m\angle IPB = m\angle IAB = a$, $m\angle API = m\angle ABI = b$, $m\angle AIP = m\angle ABP = c$, and $m\angle PIB = m\angle PAB = d$. Note that $\triangle AIP$ and $\triangle ICB$ are similar, implying that

Substituting the above equalities into the identity $(2)$, we arrive at

or

Note also that $\triangle BIP$ and $\triangle IDA$ are similar, implying that $\frac{BP}{BI} = \frac{IA}{ID}$, or

Substituting the above identity back into $(3)$ gives the desired relation $(1)$, establishing the Lemma. $\blacksquare$
Now we prove our main result. By the Lemma and symmetry, we have

Adding the two identities $(1)$ and $(4)$ gives

By the AM-GM Inequality, we have $\frac{AI}{DI} + \frac{DI}{AI}\geq 2$. Thus,

where the equality holds if and only if $AI = DI$. Likewise, we have

where the equality holds if and only if $BI = CI$. Adding the last two identities gives

because $AD + BC = AB + CD$. (The latter equality is true because the circle $\omega$ is inscribed in the quadrilateral $ABCD$.)
By the given condition in the problem, all the equalities in the above discussion must hold, that is, $AI = DI$ and $BI = CI$. Consequently, we have $a = d$, $b = c$, and so $\angle DAB + \angle ABC = 2a + 2b = 180^\circ$, implying that $AD\parallel BC$. It is not difficult to see that $\triangle AIB$ and $\triangle DIC$ are congruent, implying that $AB = CD$. Thus, $ABCD$ is an isosceles trapezoid.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zuming Feng) Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

No such circular arrangement exists for $n=pq$, where $p$ and $q$ are distinct primes. In that case, the numbers to be arranged are $p$; $q$ and $pq$, and in any circular arrangement, $p$ and $q$ will be adjacent. We claim that the desired circular arrangement exists in all other cases. If $n=p^e$ where $e\ge2$, an arbitrary circular arrangement works. Henceforth we assume that $n$ has prime factorization $p^{e_1}_{1}p^{e_2}_{2}\cdots p^{e_k}_k$, where $p_1<p_2<\cdots<p_k$ and either $k>2$ or else $\max(e1,e2)>1$. To construct the desired circular arrangement of $D_n:=\lbrace d:d|n\ \text{and}\ d>1\rbrace$, start with the circular arrangement of $n,p_{1}p_{2},p_{2}p_{3}\ldots,p_{k-1}p_{k}$ as shown.

Then between $n$ and $p_{1}p_{2}$, place (in arbitrary order) all other members of $D_n$ that have $p_1$ as their smallest prime factor. Between $p_{1}p_{2}$ and $p_{2}p_{3}$, place all members of $D_n$ other than $p_{2}p_{3}$ that have $p_2$ as their smallest prime factor. Continue in this way, ending by placing $p_k,p^{2}_{k},\ldots,p^{e_k}_{k}$ between $p_{k-1}p_k$ and $n$. It is easy to see that each element of $D_n$ is placed exactly one time, and any two adjacent elements have a common prime factor. Hence this arrangement has the desired property.
Note. In graph theory terms, this construction yields a Hamiltonian cycle in the graph with vertex set $D_n$ in which two vertices form an edge if the two corresponding numbers have a common prime factor. The graphs below illustrate the construction for the special cases $n=p^{2}q$ and $n=pqr$.

The proof that no arrangement exists for $n=pq$, where $p,q$ are distinct primes follows from above. Apply induction to prove all other cases are possible
Base case:
Inductive step: Suppose the desired arrangement exists for a composite $n$, show the arrangement exists for $np^r$, where $p$ is a prime relatively prime to $n$ and $r$ is a positive integer
Let $a_1,a_2,\cdots,a_m$ be the arrangement of divisors of $n$, then $(a_i,a_{i+1})>1$ for $i=1,2,\cdots,m$, where $a_{m+1}=a_1$. The divisors of $np^r$ greater than 1 are of the form

The following sequence works

since all other divisors are divisible by $p$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Răzvan Gelca) Prove that the system

has no solutions in integers $x$, $y$, and $z$.

It suffices to show that there are no solutions to this system in the integers mod 19.  We note that $152 = 8 \cdot 19$, so $157 \equiv -147 \equiv 5 \pmod{19}$.  For reference, we construct a table of powers of five:

Evidently, the order of 5 is 9.  Hence 5 is the square of a multiplicative generator of the nonzero integers mod 19, so this table shows all nonzero squares mod 19, as well.
It follows that $147^{157} \equiv (-5)^{13} \equiv -5^4 \equiv 2$, and $157^{147} \equiv 5^3 \equiv -8$.  Thus we rewrite our system thus:

Adding these, we have

or

By Fermat's Little Theorem, the only possible values of $z^9$ are $\pm 1$ and 0, so the only possible values of $(x^3+y+1)^2$ are $-4,-5$, and $-6$.  But none of these are squares mod 19, a contradiction.  Therefore the system has no solutions in the integers mod 19.  Therefore the solution has no equation in the integers.  $\blacksquare$

Note that the given can be rewritten as
(1) $(x^3+y)(x^3+1) = (x^3+y)(x+1)(x^2-x+1) = 147^{157} = 7^{314}3^{152}$,
(2) $(x^3+y)(y+1)+z^9 = 157^{147} \rightarrow (x^3+y)(y+1) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$.
We can also see that
$x^2-x+1 = (x+1)^2-3(x+1)+3 \rightarrow \gcd(x+1, x^2-x+1) \le 3$.
Now we notice
$x^3+1 = 3^a7^b$
for some pair of non-negative integers $(a,b)$. We also note that
$x^2 \ge 2x$ when $|x| \ge 2 \rightarrow x^2-x+1 \ge x+1$
when $|x| \ge 2$. If $x = 1$ or $x = -1$ then examining (1) would yield $147^{157} \equiv 0 \pmod{2}$ which is a contradiction. If $x = 0$ then from (1) we can see that $y+1 = 147^{157}$, plugging this into 2 yields
(3) $(147^{157}-1)(147^{157}) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$, $146 | (147^{157}-1)$, $146 = 2*73$.
Noting that 73 is a prime number we see that it must divide at least 1 of the 2 factors on the right hand side of 3. Let us consider both cases.
$73 | (157^{49}-z^3) \rightarrow z^3 \equiv 11^{49} \pmod{73} \rightarrow (11^{49})^{24} \equiv 1 \pmod{73}$.
However
$(11^{49})^{24} \equiv 8 \pmod{73}$
Thus we can see that 73 cannot divide the first factor in the right hand side of (3). Let us consider the next case.
$73 | (157^{98}+157^{49}z^3+z^6) \rightarrow 11^{98}+11^{49}z^3+z^6 \equiv 0 \pmod{73}$.
However
$11^{98}+11^{49}z^3+z^6 \equiv z^6+47z^3+19 \equiv z^6-26z^3+19 \equiv (z^3-13)^2-150 \equiv (z^3-13)^2-4 \equiv (z^3-11)(z^3-15) \pmod{73}$.
It can be seen that 11 and 15 are not perfect cubes $\pmod{73}$ from the following.
$15^{24} \equiv 11^{24} \equiv 8 \not\equiv 1 \pmod{73}$
We can now see that $|x| \ge 2$. Furthermore, notice that if
$x+1 = \pm3^k7^j$
for a pair of positive integers $(j,k)$ means that
$|x^2-x+1| \le 3$
which cannot be true. We now know that
$x+1 = \pm3^k, \pm7^k \rightarrow x^2-x+1 = 3*7^m, 3^m$.
Suppose that
$x+1 = \pm7^k \rightarrow (x+1)^2-3(x+1)+3 = 3^m \rightarrow 7^{2k}\pm3*7^k+3  = 3^m \rightarrow 7^{2k} \equiv 0\pmod{3}$
which is a contradiction. Now suppose that
$x+1 = \pm3^k \rightarrow (x+1)^2-3(x+1)+3 = 3*7^m \rightarrow 3^{2k}\pm3^{k+1}+3 = 3*7^m \rightarrow 3^{2k-1}\pm3^{k}+1 = 7^m \rightarrow 3^k(3^{k-1}\pm1) = 7^m-1$.
We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation when $m > 0$ to obtain
$k \le 2+v_3(m) \le 2+log_3(m) \rightarrow 7^m-1 = 3^k(3^{k-1}\pm1)\le 3^{2+log_3(m)}(3^{1+log_3(m)}\pm1) = 9m(3m\pm1)$.
For $m > 2$ we can see that
$7^m-1 > 9m(3m\pm1)$
which is a contradiction. Therefore there only possible solution is when
$m = 0 \rightarrow k = 1 \rightarrow x = 2, m = 1 \rightarrow k = 1 \rightarrow x = -4, m = 2 \rightarrow$ no integer solutions for k.
Plugging this back into (1) and (2) yields
(4) $3^{155} | (x^3+y) \rightarrow 3^{155}| (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$.
In order for (4) to be true we must have 9 dividing at least 1 of the factors on the right hand side of the equation. Let us consider both cases.
$9 | 157^{49}-z^3 \rightarrow 157^{49}-z^3 \equiv 0 \pmod{9}$.
However,
$z^3 \equiv 0, 1, 8\pmod{9}, 157^{49}-z^3 \equiv 4-z^3 \not\equiv 0 \pmod{9}$.
We now consider the second case.
$9 | (z^6+157^{49}z^3+157^{98}) \rightarrow 157^{98}+157^{49}z^3+z^6\equiv 0\pmod{9}$.
However
$z^6+157^{49}z^3+157^{98} \equiv z^6+4z^3+7 \equiv (z^3+2)^2+3 \not\equiv 0\pmod{9}$
Therefore there are no solutions to the given system of diophantine equations. $\blacksquare$

We will show there is no solution to the system modulo 13. Add the two equations and add 1 to obtain

By Fermat's Theorem, $a^{12}\equiv 1\pmod{13}$ when $a$ is not a multiple of 13. Hence we compute $147^{157}\equiv 4^1\equiv 4\pmod{13}$ and $157^{147}\equiv 1^3\equiv 1\pmod{13}$. Thus

The cubes mod 13 are $0$, $\pm 1$, and $\pm 5$. Writing the first equation as

we see that there is no solution in case $x^3\equiv -1\pmod{13}$ and for $x^3$ congruent to $0, 1, 5, -5\pmod{13}$, correspondingly $x^3 + y$ must be congruent to $4, 2, 5, -1$. Hence

Also $z^9$ is a cube, hence $z^9$ must be $\text{0, 1, 5, 8, or 12}\pmod{13}$. It is easy to check that $6\pmod{13}$ is not obtained by adding one of $0, 9, 10, 12$ to one of $0, 1, 5, 8, 12$. Hence the system has no solutions in integers.
Note: This argument shows there is no solution even if $z^9$ is replaced by $z^3$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zuming Feng) Let $ABC$ be an acute-angled triangle, and let $P$ and $Q$ be two points on side $BC$. Construct point $C_1$ in such a way that convex quadrilateral $APBC_1$ is cyclic, $QC_1 \parallel CA$, and $C_1$ and $Q$ lie on opposite sides of line $AB$. Construct point $B_1$ in such a way that convex quadrilateral $APCB_1$ is cyclic, $QB_1 \parallel BA$, and $B_1$ and $Q$  lie on opposite sides of line $AC$.  Prove that points $B_1, C_1,P$, and $Q$ lie on a circle.

Let $B_1'$ be the second intersection of the line $C_1A$ with the circumcircle of $APC$, and let $Q'$ be the second intersection of the circumcircle of $B_1' C_1P$ and line $BC$.  It is enough to show that $B_1'=B_1$ and $Q' =Q$.  All our angles will be directed, and measured mod $\pi$.

Since points $C_1, P, Q', B_1'$ are concyclic and points $C_1, A,B_1'$ are collinear, it follows that

But since points $A, B_1', P, C$ are concyclic,

It follows that lines $AC$ and $C_1 Q'$ are parallel.  If we exchange $C$ with $B$ and $C_1$ with $B_1'$ in this argument, we see that lines $AB$ and $B_1' Q'$ are likewise parallel.
It follows that $Q'$ is the intersection of $BC$ and the line parallel to $AC$ and passing through $C_1$.  Hence $Q' = Q$.  Then $B_1'$ is the second intersection of the circumcircle of $APC$ and the line parallel to $AB$ passing through $Q$.  Hence $B_1' = B_1$, as desired.  $\blacksquare$
Motivation: One can notice that if you take such a $B_1'$ then $PQB_1'C_1$ is cyclic, and that similarly $PQB_1C_1'$ is also cyclic. One gets the intuition that only one such circle should exist where the other chord passes through A, and so sets up a ghost point for $Q$, which works. ~cocohearts

Lemma. $B_1, A, C_1$ are collinear.
Suppose they are not collinear. Let line $B_1 A$ intersect circle $ABP$ (i.e. the circumcircle of $ABP$) again at $C_2$ distinct from $C_1$. Because $\angle C_2 B_1 Q = \angle C_2 AB = \angle C_2 PB = 180^\circ - \angle C_2 PQ$, we have that $B_1 C_2 PQ$ is cyclic. Hence $\angle C_2 QP = \angle C_2 B_1 P = \angle P B_1 A = \angle C$, so $C_2 Q // AC$. Then $C_2$ must be the other intersection of the parallel to $AC$ through $Q$ with circle $ABP$. Then $C_2$ is on segment $C_1 Q$, so $C_2$ is contained in triangle $ABQ$. However, line $AB_1$ intersects this triangle only at point $A$ because $B_1$ lies on arc $AC$ not containing $P$ of circle $APC$, a contradiction. Hence, $B_1, A, C_1$ are collinear, as desired.
As a result, we have $\angle C_1 B_1 Q = \angle C_1 AB = \angle C_1 PB = 180^\circ - \angle C_1 PQ$, so $B_1 C_1 PQ$ is cyclic, as desired.

Due to the parallel lines, $m\angle C_1QB_1=m\angle A.$ Therefore, it suffices to prove that  Note that $m\angle BC_1A+m\angle AB_1C=180^{\circ}$ by the cyclic quadrilaterals. Now, the condition simplifies to proving $C_1,A,B_1$ collinear.
Use barycentric coordinates. Let  By the parallel lines,  for some $y',z'.$ As $A$ is a vertex of the reference triangle, we must prove that $q(1-q)=y'z'.$
Now we find the circumcircle of $\triangle APC.$ Let its equation be  Substituting in $A,C$ gives $u=w=0.$ Substituting in $P$ yields  Substituting in $B_1$ yields
Similarly, the circumcircle of $\triangle APB$ is  Now, we substitute $C_1$ into the equation

Let $k=a^2p-a^2q-b^2(1-q)+c^2q,$ and note that both $y',z'$ are negative. By the quadratic formula, we have

Multiplying these two, we have  as desired. $\blacksquare$
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Elgin Johnston) Legs $L_1, L_2, L_3, L_4$ of a square table each have  length $n$, where $n$ is a positive integer.  For how many ordered  4-tuples $(k_1, k_2, k_3, k_4)$ of nonnegative integers can we cut  a piece of length $k_i$ from the end of leg $L_i \; (i = 1,2,3,4)$ and still have a stable table?
(The table is stable if it can be placed so that  all four of the leg ends touch the floor. Note that a cut leg of length 0 is permitted.)

First flip the table upside down and observe the plane that the ends of the legs form. Let this plane be $ax+by+c=z$. Assume WLOG that the table is the square with endpoints $(0,0), (0,1), (1,0), (1,1)$ on the xy plane. Thus the lengths of the legs will be $c, c+b, c+a, c+a+b$ respectively. In other words $k_1+k_3=k_2+k_4=x$ for some $0 \le x \le 2n$.
For $0 \le x \le n$, it is easy to see that the number of stable tables is $(x+1)^2$.
For $n+1 \le x \le 2n$, we can biject the stable tables of $x$ to the stable of $2n-x$ by replacing all of the legs with the cut off portions.
So the total number of stable tables is $1^2+2^2+...+n^2+(n+1)^2+n^2+...+2^2+1^2 =$ $(1^2+2^2+...+(n+1)^2)+(1^2+2^2+...+n^2) =$ $\dfrac{(n+1)(n+2)(2n+3)}{6}+\dfrac{n(n+1)(2n+1)}{6}=\boxed{\dfrac{2n^3+6n^2+7n+3}{3}}$.

Let $C_i$ be the number of sets of cuts $\{k_1,k_2,k_3,k_4\}$ that result in the longest leg being of length $i$.  Then $C_i=C_{i-1}+x$, and we will evaluate $x$ to develop a recursion.  Note that if a set of cuts has non-zero cuts, then if that set is counted in $C_i$, subtract $1$ from each of the cuts to obtain a set of cuts that is counted in $C_{i-1}$.  For example, if $\{2,3,4,5\}$ was counted in $C_5$, then $\{1,2,3,4\}$ would have been counted in $C_4$ because subtracting the same length from each leg preserves the quality of the legs being coplanar, and there is a bijection.
Now we must evaluate those sets of cuts that don't fall in this bijection, which are clearly those where one leg is completely cut off.  After some simple geometric reasoning that I won't include here, we see that one corner has a leg of length of zero, and the opposite leg, called the initial leg, will have length $i$  If the remaining legs have length $y$ and $z$, then $(y,z)=(0,i),(1,i-1),...,(i-1,1),(i,0)$, so $i+1$ options.  The initial corner can be any of the four legs, but each of the four permutations of the set of cuts ${0,0,i,i}$ is repeated twice, so we have $4(i+1)-4=4i$ total additional sets of cuts.  We conclude that $C_i=C_{i-1}+4i$, and note that $C_0=1$.  Now we can create generating functions.  $F(x)=\sum_{i=0}^\infty C_ix^i$.  Also, $G(x)=\sum_{i=1}^\infty 4ix^i$. From the recursion, we have

This final equation is easy to analyze.  Simply use $G(x)$ as the first term of a geometric series with constant multiplier of $x$.  This gives $C_i=2i^2+2i+1$.  The total number of sets of cuts for a table of legs of length $n$ is the sum of all the $C_i$, $0\le i\le n$, from which we deduce the answer $\frac{2n^3 + 6n^2 +7n + 3}{3}$, or $\frac{(n+1)(2n^2 + 4n +3)}{3}$.

The problem's condition is that the ends of the legs must be coplanar. So the plane formed by legs $L_1$, $L_2$, and $L_3$ is the same as the plane formed by the legs $L_2$, $L_3$, and $L_4$ iff the problem's condition is met.
We now assign coordinates to the ends of the legs. Let the table be on the xy-plane such that $L_1$ is at $(0,0,k_1)$, $L_2$ is at $(s,0,k_2)$, $L_3$ is at $(0,s,k_3)$, and $L_4$ is at $(s,s,k_4)$, where $s$ is the side length of the table. (Note that we have turned the table over so that the top lies on the xy plane while the legs point in the +z direction - this does not affect the result.) A plane in 3-space has the equation form $Ax+By+Cz=1$. Plugging the coordinates of $L_1$, $L_2$, and $L_3$ into $Ax+By+Cz=1$, we eventually get $A_1=\dfrac{k_1-k_2}{sk_1}$, $B_1=\dfrac{k_1-k_3}{sk_1}$, $C_1=\dfrac{1}{k_1}$. Plugging the coordinates of $L_2$, $L_3$, and $L_4$ into $Ax+By+Cz=1$, we get $A_2=\dfrac{k_3-k_4}{s(k_2+k_3-k_4)}$, $B_2=\dfrac{k_2-k_4}{s(k_2+k_3-k_4)}$, $C_2=\dfrac{1}{k_2+k_3-k_4}$.
Since we need these to be coplanar, we set $A_1=A_2$, $B_1=B_2$, and $C_1=C_2$. (Notice that the $s$'s cancel.) From $A_1=A_2$, we get $(k_1-k_2)(k_2+k_3-k_4)=k_1(k_3-k_4)$ [1]. From $B_1=B_2$, we get $(k_1-k_3)(k_2+k_3-k_4)=k_1(k_2-k_4)$ [2]. From $C_1=C_2$, we get $k_1=k_2+k_3-k_4$ [3]. Notice that [1] and [2] can both be obtained directly from [3] and are therefore redundant. The only condition we have left to ensure that the ends of the legs are coplanar is $k_1+k_4=k_2+k_3$. Let $k_1+k_4=k_2+k_3=m$.
We proceed using casework by $m$. $m$ is an integer between $0$ and $2n$, inclusive. Furthermore, we note that $k_i$ range from $0$ to $n$, inclusive. For $m=0$, each of $(k_1,k_4)$ and $(k_2,k_3)$ have one choice, $(0,0)$. For $m=1$, they each have two choices, $(0,1)$ and $(1,0)$. And so on, until $m=n$, where they each have $n+1$ choices: $(0,n),(1,n-1),\cdots,(n-1,1),(n,0)$. When $m=n+1$, the restriction that $0\le k_i\le n$ takes effect: there are only $n$ choices for each ordered pair, which are $(1,n),(2,n-1),\cdots,(n-1,2),(n,1)$. And so on, until $m=2n$, where there is one choice for each ordered pair, $(n,n)$.
The number of possible 4-tuples $(k_1,k_2,k_3,k_4)$ is thus $1^2+2^2+...+n^2+(n+1)^2+n^2+...+2^2+1^2$, which is equivalent to $(1^2+2^2+...+(n+1)^2)+(1^2+2^2+...+n^2)$. Our final answer is $\dfrac{(n+1)(n+2)(2n+3)}{6}+\dfrac{n(n+1)(2n+1)}{6}=\boxed{\dfrac{2n^3+6n^2+7n+3}{3}}$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Kiran Kedlaya) Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side.
Prove that there exist at least two balancing lines.

Solution:
Consider the convex hull of the the $2n$ points, or the points that would form the largest convex polygon. If the points in the convex hull contain both red and blue points, then there must be at least 2 edges of the graph of the convex hull such that the edge connects a blue and a red point. Drawing a line through those points would give a balancing line, as we have n-1 blue points and n-1 red points on one side, and 0 points on the other.
Therefore it suffices to show that there exist at least 2 balancing lines when the convex hull is colored all the same color.
Pick a random point on the convex hull, and without loss of generality we can say it is blue (if there are no red we can change all the colors, and end up with an equivalent setup). Consider a line going through it and not any other points. As we rotate the line clockwise, we encounter the red points in some order. Let the ith point encountered be $R_i$. Let $b_i$ and $r_i$ be the number of points encountered before $R_i$. Then $r_i=i-1$.
Define a sequence $f(i)=b_i-r_i$. Then $f(1)=b_i-(1-1)=b_i\geq0$
$f(n)=b_n-(n-1)=b_n-n+1\leq0$, because we can only encounter up to n-1 blue points.
Thus, $f(i)$ goes from negative to positive as $i$ goes from 1 to $n$. We can also see that $f(i)$ can only increase by one for each change in i, so we know $f(i)$ must be 0 for some value of $i$. Take the first $f(i)$ where $f(i) = 0$. Since $f(i-1)$ must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least $3>2$ balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Case 1 One can notice That if any blue and red point have not points on one of it's sides this mean the line between them is a balancing line (as on the other side we will have $n-1$ blue points and $n-1$ red).
Case 2: Now we consider the case in which all the points are inside a polygon with all vertices being one color (assume WLOG it's blue
Now consider a line that is pivoting at any vertex and rotating till reaching another vertex of the polygon (convex hull) passing through every point in side the polygon. and let $x$ be the number of red points.
minus the number of blue points on one side of the line.
In other words every time the line passes through a blue point $x$ will increase by $1$, and decrease by $1$ if it passes through a red point.
Firstly we have that $x=1$ and when the line reaches the other vertex of the polygon  it will be equal to $-1$.
So when $x$ will be equal to zero, we have a balancing line.
Now repeating this process on all the other vertices of the polygon (convex hull) then we will have balancing lines equal to the number of the vertices.


(Titu Andreescu, Gabriel Dospinescu) For $m$ a positive integer, let $s(m)$ be the sum of the digits of $m$. For $n\ge 2$, let $f(n)$ be the minimal $k$ for which there  exists a set $S$ of $n$ positive integers such that  $s\left(\sum_{x\in X} x\right) = k$ for any nonempty subset $X\subset S$.  Prove that there are constants $0 < C_1 < C_2$ with

Solution:
For the upper bound, let $p$ be the smallest integer such that $10^p\geq n(n+1)/2$ and let

The sum of any nonempty set of elements of $S$ will have the form $k(10^p - 1)$ for some $1\leq k\leq n(n+1)/2$. Write $k(10^p - 1) = [(k - 1)10^p] + [(10^p - 1) - (k - 1)]$. The second term gives the bottom $p$ digits of the sum and the first term gives at most $p$ top digits. Since the sum of a digit of the second term and the corresponding digit of $k - 1$ is always 9, the sum of the digits will be $9p$. Since $10^{p-1} < n(n+1)/2$, this example shows that

Since $n\geq 2$, $5(n + 1) < n^4$, and hence

For the lower bound, let $S$ be a set of $n\geq 2$ positive integers such that any nonempty $X\subset S$ has $s\left(\sum_{x\in X} x\right) = f(n)$. Since $s(m)$ is always congruent to $m$ modulo 9, $\sum_{x\in X} x\equiv f(n)\pmod{9}$ for all nonempty $X\subset S$. Hence every element of $S$ must be a multiple of 9 and $f(n)\geq 9$. Let $q$ be the largest positive integer such that $10^q - 1\leq n$. Lemma 1 below shows that there is a nonempty subset $X$ of $S$ with $\sum_{x\in X} x$ a multiple of $10^q - 1$, and hence Lemma 2 shows that $f(n)\geq 9q$.
Lemma 1. Any set of $m$ positive integers contains a nonempty subset whose sum is a multiple of $m$.
Proof. Suppose a set $T$ has no nonempty subset with sum divisible by $m$. Look at the possible sums mod $m$ of nonempty subsets of $T$. Adding a new element $a$ to $T$ will give at least one new sum mod $m$, namely the least multiple of $a$ which does not already occur. Therefore the set $T$ has at least $|T|$ distinct sums mod $m$ of nonempty subsets and $|T| < m$. $\blacksquare$
Lemma 2. Any positive multiple $M$ of $10^q - 1$ has $s(M)\geq 9q$.
Proof. Suppose on the contrary that $M$ is the smallest positive multiple of $10^q - 1$ with $s(M) < 9q$. Then $M\neq 10^q - 1$, hence $M > 10^q$. Suppose the most significant digit of $M$ is the $10^m$ digit, $m\geq q$. Then $N = M - 10^{m-q}(10^q - 1)$ is a smaller positive multiple of $10^q - 1$ and has $s(N)\leq s(M) < 9q$, a contradiction. $\blacksquare$
Finally, since $10^{q+1} > n$, we have $q + 1 > \log_{10} n$. Since $f(n)\geq 9q$ and $f(n)\geq 9$, we have

Weaker versions of Lemmas 1 and 2 are still sufficient to prove the desired type of lower bound.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Kiran Kedlaya) Let $p$ be a prime number and let $s$ be an integer with $0 < s < p$. Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and
if and only if $s$ is not a divisor of $p-1$.
Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of $x$.

We proceed by contradiction.  Assume that $s|(p-1)$.  Then for some positive integer $k$, $sk=p-1$.  The conditions given are equivalent to stating that $sm \bmod p < sn \bmod p< s\bmod p$.
Now consider the following array modulo p:

Obviously, there are $s$ rows and $k$ columns. The first entry of each row is simply $((r-1)k+1)s\mod p$.  Since we wish for $sm\mod p$ and $sn\mod p$ to both be in the first column, while also satisfying the given conditions, we can easily see that $sm$ must be in a row $m_r$ with $m_r>n_r$, where $n_r$ denotes the row $sn \mod p$ is in.  However, since the values of each entry decreases while $((r-1)k+1)s$ keeps increasing, we can see that the condition can never be satisfied and thus, $s\not|(p-1).$
To prove the other direction, let $sj+r=p-1$ for positive integers $j$ and $r$ with $j$ being the largest integer such that $sj<p-1$ and $r<s$. Since $s\not|(p-1)$, $1<s<p-1$.
Note that for $0<l<j$, $ls\ge s\mod p$.  Thus, the first integer multiplied by s modulo p that will be less than s is $j+1.$ $(j+1)s\equiv s-r-1\mod p$.  Since $\lbrace s,2s,\hdots,js,(j+1)s,\hdots,xs,\hdots,(p-1)s \rbrace$ is a complete residue system mod p with the exception of the 0 term, we can find an $x>j+1$ such that $xs \equiv s-1 \mod p$.
Thus, choose $m=j+1$ and $n=x$ to complete the proof.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Dick Gibbs) For a given positive integer $k$ find, in terms of $k$, the minimum value of $N$ for which there is a set of $2k+1$ distinct positive integers that has sum greater than $N$ but every subset of size $k$ has sum at most $N/2$.

Let one optimal set of integers be $\{a_1,\dots,a_{2k+1}\}$ with $a_1 > a_2 > \cdots > a_{2k+1} > 0$.
The two conditions can now be rewritten as $a_1+\cdots + a_k \leq N/2$ and $a_1+\cdots +a_{2k+1} > N$.
Subtracting, we get that $a_{k+1}+\cdots + a_{2k+1} > N/2$, and hence $a_{k+1}+\cdots + a_{2k+1} > a_1+\cdots + a_k$.
In words, the sum of the $k+1$ smallest numbers must exceed the sum of the $k$ largest ones.
Let $a_{k+1}=C$. As all the numbers are distinct integers, we must have $\forall i \in\{1,\dots,k\}:~ a_{k+1-i} \geq C+i$, and also $\forall i \in\{1,\dots,k\}:~ a_{k+1+i} \leq C-i$.
Thus we get that $a_1+\cdots + a_k \geq kC + \dfrac{k(k+1)}2$, and $a_{k+1}+\cdots + a_{2k+1} \leq (k+1)C - \dfrac{k(k+1)}2$.
As we want the second sum to be larger, clearly we must have $(k+1)C - \dfrac{k(k+1)}2 > kC + \dfrac{k(k+1)}2$.
This simplifies to $C > k(k+1)$.
Hence we get that:

On the other hand, for the set $\{ k^2+k+1+i ~|~ i\in\{-k,\dots,k\} \, \}$ the sum of the largest $k$ elements is exactly $k^3 + k^2 + k + \dfrac{k(k+1)}2$, and the sum of the entire set is $(k^2+k+1)(2k+1) = 2k^3 + 3k^2 + 3k + 1$, which is more than twice the sum of the largest set.
Hence the smallest possible $N$ is $\boxed{ N = 2k^3 + 3k^2 + 3k }$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Titu Andreescu, Gabriel Dospinescu) For integral $m$, let $p(m)$ be the greatest prime divisor of $m$. By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$. Find all polynomials $f$ with integer coefficients such that the sequence $\{ p(f(n^2))-2n) \}_{n \in \mathbb{Z} \ge 0}$ is bounded above. (In particular, this requires $f(n^2)\neq 0$ for $n\ge 0$.)

Let $f(x)$ be a non-constant polynomial in $x$ of degree $d$ with
integer coefficients, suppose further that no prime divides all the
coefficients of $f$ (otherwise consider the polynomial obtained by
dividing $f$ by the gcd of its coefficients). We further normalize
$f$ by multiplying by $-1$, if necessary, to ensure that the
leading coefficient (of $x^d$) is positive.
Let $g(n) = f(n^2)$, then $g(n)$ is a polynomial of degree $2$ or
more and $g(n) = g(-n)$. Let $g_1, \ldots, g_k$ be the factorization
of $g$ into irreducible factors with positive leading coefficients.
Such a factorization is unique. Let $d(g_i)$ denote the degree of
$g_i$. Since $g(-n) = g(n)$ the factors $g_i$ are either even
functions of $n$ or come in pairs $(g_i, h_i)$ with $g_i(-n) = (-1)^{d(g_i)} h_i(n)$.
Let $P(0) = \infty$, $P(\pm 1) = 1$. For any other integer $m$ let
$P(m)$ be the largest prime factor of $m$.
Suppose that for some finite constant $C$ and all $n \ge 0$ we have
$P(g(n)) - 2n < C$. Since the polynomials $g_i$ divide $g$, the
same must be true for each of the irreducible polynomials $g_i$.
A theorem of T. Nagell implies that if $d(g_i) \ge 2$ the ratio
$P(g_i(n))/n$ is unbounded for large values of $n$. Since in our case the $P(g_i(n))/n$ is asymptotically bounded above
by $2$ for large $n$, we conclude that all the irreducible
factors $g_i$ are linear. Since linear polynomials are not even
functions of $n$, they must occur in pairs $g_i(n) = a_in + b_i$,
$h_i(n) = a_in - b_i$. Without loss of generality, $b_i \ge 0$.
Since the coefficients of $f$ are relatively prime, so are $a_i$
and $b_i$, and since $P(0) = \infty$, neither polynomial can have
any non-negative integer roots, so $a_i > 1$ and thus $b_i > 0$.
On the other hand, by Dirichlet's theorem, $a_i \le 2$, since
otherwise the sequence $a_in + b_i$ would yield infinitely many
prime values with $P(g_i(n)) = a_in + b_i \ge 3n.$ So $a_i = 2$ and
therefore $b_i$ is a positive odd integer. Setting $b_i = 2c_i + 1$, clearly $P(g_i(n)) - 2n < 2c_i + 2$.  Since this holds for each
factor $g_i$, it is true for the product $g$ of all the factors
with the bound determined by the factor with the largest value of
$c_i$.
Therefore, for suitable non-negative integers $c_i$, $g(n)$ is a
product of polynomials of the form $4n^2 - (2c_i + 1)^2$.  Now,
since $g(n) = f(n^2)$, we conclude that $f(n)$ is a product of
linear factors of the form $4n - (2c_i + 1)^2$.
Since we restricted ourselves to non-constant polynomials with
relatively prime coefficients, we can now relax this condition and
admit a possibly empty list of linear factors as well as an arbitrary
non-zero integer multiple $M$. Thus for a suitable non-zero integer
$M$ and $k \ge 0$ non-negative integers $c_i$, we have:

The polynomial $f$ has the required properties if and only if

where $a_1, a_2, \ldots, a_k$ are odd positive integers and $c$ is a nonzero integer. It is straightforward to verify that polynomials given by $(*)$ have the required property. If $p$ is a prime divisor of $f(n^2)$ but not of $c$, then $p|(2n - a_j)$ or $p|(2n + a_j)$ for some $j\leq k$. Hence $p - 2n\leq \max\{a_1, a_2, \ldots, a_k\}$. The prime divisors of $c$ form a finite set and do not affect whether or not the given sequence is bounded above. The rest of the proof is devoted to showing that any $f$ for which $\{p(f(n^2)) - 2n\}_{n\geq 0}$ is bounded above is given by $(*)$.
Let $\mathbb{Z}[x]$ denote the set of all polynomials with integer coefficients. Given $f\in\mathbb{Z}[x]$, let $\mathcal{P}(f)$ denote the set of those primes that divide at least one of the numbers in the sequence $\{f(n)\}_{n\geq 0}$. The solution is based on the following lemma.
Lemma. If $f\in\mathbb{Z}[x]$ is a nonconstant polynomial then $\mathcal{P}(f)$ is infinite.
Proof. Repeated use will be made of the following basic fact: if $a$ and $b$ are distinct integers and $f\in\mathbb{Z}[x]$, then $a - b$ divides $f(a) - f(b)$. If $f(0) = 0$, then $p$ divides $f(p)$ for every prime $p$, so $\mathcal{P}(f)$ is infinite. If $f(0) = 1$, then every prime divisor $p$ of $f(n!)$ satisfies $p > n$. Otherwise $p$ divides $n!$, which in turn divides $f(n!) - f(0) = f(n!) - 1$. This yields $p|1$, which is false. Hence $f(0) = 1$ implies that $\mathcal{P}(f)$ is infinite. To complete the proof, set $g(x) = f(f(0)x)/f(0)$ and observe that $g\in\mathcal{Z}[x]$ and $g(0) = 1$. The preceding argument shows that $\mathcal{P}(g)$ is infinite, and it follows that $\mathcal{P}(f)$ is infinite. $\blacksquare$
Suppose $f\in\mathbb{Z}[x]$ is nonconstant and there exists a number $M$ such that $p(f(n^2)) - 2n\leq M$ for all $n\geq 0$. Application of the lemma to $f(x^2)$ shows that there is an infinite sequence of distinct primes $\{p_j\}$ and a corresponding infinite sequence of nonnegative integers $\{k_j\}$ such that $p_j|f(k_j)^2$ for all $j\geq 1$. Consider the sequence $\{r_j\}$ where $r_j = \min\{k_j\pmod{p_j}, p_j - k_j\pmod{p_j}\}$. Then $0\leq r_j\leq (p_j - 1)/2$ and $p_j|f(r_j)^2$. Hence $2r_j + 1\leq p_j\leq p(f(r_j^2))\leq M + 2r_j$, so $1\leq p_j - 2r_\leq M$ for all $j\geq 1$. It follows that there is an integer $a_1$ such that $1\leq a_1\leq M$ and $a_1 = p_j - 2r_j$ for infinitely many $j$. Let $m = \deg f$. Then $p_j|4^mf(((p_j - a_1)/2)^2)$ and $4^mf(((x - a_1)/2)^2)\in\mathbb{Z}[x]$. Consequently, $p_j|f((a_1/2)^2)$ for infinitely many $j$, which shows that $(a_1/2)^2$ is a zero of $f$. Since $f(n^2)\leq 0$ for $n\geq 0$, $a_1$ must be odd. Then $f(x) = (4x - a_1)^2g(x)$, where $g\in\mathbb{Z}[x]$. (See the note below.) Observe that $\{p(g(n^2)) - 2n\}_{n\geq 0}$ must be bounded above. If $g$ is constant, we are done. If $g$ is nonconstant, the argument can be repeated to show that $f$ is given by $(*)$.
Note. The step that gives $f(x) = (4x - a_1^2)g(x)$ where $g\in\mathbb{Z}[x]$ follows immediately using a lemma of Gauss. The use of such an advanced result can be avoided by first writing $f(x) = r(4x - a_1^2)g(x)$ where $r$ is rational and $g\in\mathbb{Z}[x]$. Then continuation gives $f(x) = c(4x - a_1^2)\cdots (4x - a_k^2)$ where $c$ is rational and the $a_i$ are odd. Consideration of the leading coefficient shows that the denominator of $c$ is $2^s$ for some $s\geq 0$ and consideration of the constant term shows that the denominator is odd. Hence $c$ is an integer.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Ricky Liu) Find all positive integers $n$ such that there are $k\ge 2$ positive rational numbers $a_1, a_2, \ldots, a_k$ satisfying $a_1 + a_2 + \cdots + a_k = a_1\cdot a_2\cdots a_k = n$.

First, consider composite numbers.  We can then factor $n$ into $p_1p_2.$  It is easy to see that $p_1+p_2\le n$, and thus, we can add $(n-p_1-p_2)$ 1s in order to achieve a sum and product of $n$.  For $p_1+p_2=n$, which is only possible in one case, $n=4$, we consider $p_1=p_2=2$.
Secondly, let $n$ be a prime.  Then we can find the following procedure: Let $a_1=\frac{n}{2}, a_2=4, a_3=\frac{1}{2}$ and let the rest of the $a_k$ be 1.  The only numbers we now need to check are those such that $\frac{n}{2}+4+\frac{1}{2}>n\Longrightarrow n<9$.  Thus, we need to check for $n=1,2,3,5,7$.  One is included because it is neither prime nor composite.
For $n=1$, consider $a_1a_2\hdots a_k=1$.  Then by AM-GM, $a_1+a_2+\hdots+a_k\ge k\sqrt[k]{1}>1$ for $k\ge 2$.  Thus, $n=1$ is impossible.
If $n=2$, once again consider $a_1a_2\hdots a_k=2$.  Similar to the above, $a_1+a_2+\hdots\ge k\sqrt[k]{2}>2$ for $k\ge 2$ since $\sqrt[k]{2}>1$ and $k>2$. Obviously, $n=2$ is then impossible.
If $n=3$, let $a_1a_2\hdots a_k=3$.  Again, $a_1+a_2+\hdots\ge k\sqrt[k]{3}>3$.  This is obvious for $k\ge 3$.  Now consider $k=2$.  Then $2\sqrt{3}\approx 3.4$ is obviously greater than $3$.  Thus, $n=3$ is impossible.
If $n=5$, proceed as above and consider $k=2$.  Then $a_1+a_2=5$ and $a_1a_2=5$.  However, we then come to the quadratic $a_1^2-5a_1+5=0 \Longrightarrow a_1=\frac{5\pm\sqrt{5}}{2}$, which is not rational.  For $k=3$ and $k=4$ we note that $\sqrt[3]{5}>\frac{5}{3}$ and $\sqrt[4]{5}>\frac{5}{4}$.  This is trivial to prove.  If $k\ge 5$, it is obviously impossible, and thus $n=5$ does not work.
The last case, where $n=7$, is possible using the following three numbers.  $a_1=\frac{9}{2}, a_2=\frac{4}{3}, a_3=\frac{7}{6}$ shows that $n=7$ is possible.
Hence, $n$ can be any positive integer greater than $3$ with the exclusion of $5$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zoran Sunik) A mathematical frog jumps along the number line. The frog starts at 1, and jumps according to the following rule: if the frog is at integer $n$, then it can jump either to $n+1$ or to $n+2^{m_n+1}$ where $2^{m_n}$ is the largest power of 2 that is a factor of $n$. Show that if $k\ge 2$ is a positive integer and $i$ is a nonnegative integer, then the minimum number of jumps needed to reach $2^i k$ is greater than the minimum number of jumps needed to reach $2^i$.

For $i\geq 0$ and $k\geq 1$, let $x_{i,k}$ denote the minimum number of jumps needed to reach the integer $n_{i,k} = 2^i k$. We must prove that

for all $i\geq 0$ and $k\geq 2$. We prove this using the method of descent.
First note that $(1)$ holds for $i = 0$ and all $k\geq 2$, because it takes 0 jumps to reach the starting value $n_{0,1} = 1$, and at least one jump to reach $n_{0,k} = k\geq 2$. Now assume that $(1)$ is not true for all choices of $i$ and $k$. Let $i_0$ be the minimal value of $i$ for which $(1)$ fails for some $k$, let $k_0$ be the minimal value of $k > 1$ for which $x_{i_0,k}\leq x_{i_0,1}$. Then it must be the case that $i_0\geq 1$ and $k_0\geq 2$.
Let $J_{i_0,k_0}$ be a shortest sequence of $x_{i_0,k_0} + 1$ integers that the frog occupies in jumping from 1 to $2^{i_0} k_0$. The length of each jump, that is, the difference between consecutive integers in $J_{i_0,k_0}$, is either 1 or a positive integer power of 2. The sequence $J_{i_0,k_0}$ cannot contain $2^{t_0}$ because it takes more jumps to reach $2^{t_0} k_0$ than it does to reach $2^{t_0}$. Let $2^{M+1}$, $M\geq 0$ be the length of the longest jump made in generating $J_{i_0,k_0}$. Such a jump can only be made from a number that is divisible by $2^M$ (and by no higher power of 2). Thus we must have $M < i_0$, since otherwise a number divisible by $2^{i_0}$ is visited before $2^{i_0} k_0$ is reached, contradicting the definition of $k_0$.
Let $2^{m+1}$ be the length of the jump when the frog jumps over $2^{i_0}$. If this jump starts at $2^m(2t - 1)$ for some positive integer $t$, then it will end at $2^m(2t - 1) + 2^{m+1} = 2^m(2t + 1)$. Since it goes over $2^{i_0}$ we see $2^m(2t - 1) < 2^{i_0} < 2^m(2t + 1)$ or $(2^{i_0-m} - 1)/2 < t < (2^{i_0-m} + 1)/2$. Thus $t = 2^{i_0-m-1}$ and the jump over $2^{i_0}$ is from $2^m(2^{i_0-m} - 1) = 2^{i_0} - 2^m$ to $2^m(2^{i_0-m}+1) = 2^{i_0} + 2^m$.
Considering the jumps that generate $J_{i_0,k_0}$, let $N_1$ be the number of jumps from 1 to $2^{i_0} + 2^m$, and let $N_2$ be the number of jumps from $2^{i_0} + 2^m$ to $2^{i_0}k$. By definition of $i_0$, it follows that $2^m$ can be reached from 1 in less than $N_1$ jumps. On the other hand, because $m < i_0$, the number $2^{i_0}(k_0 - 1)$ can be reached from $2^m$ in exactly $N_2$ jumps by using the same jump length sequence as in jumping from $2^m + 2^{i_0}$ to $2^{i_0} k_0 = 2^{i_0}(k_0 - 1) + 2^{i_0}$. The key point here is that the shift by $2^{i_0}$ does not affect any of divisibility conditions needed to make jumps of the same length. In particular, with the exception of the last entry, $2^{i_0} k_0$, all of the elements of $J_{i_0,k_0}$ are of the form $2^p(2t + 1)$ with $p < i_0$, again because of the definition of $k_0$. Because $2^p(2t + 1) - 2^{i_0} = 2^p(2t - 2^{i_0-p} + 1)$ and the number $2t + 2^{i_0-p} + 1$ is odd, a jump of size $2^{p+1}$ can be made from $2^p(2t + 1) - 2^{i_0}$ just as it can be made from $2^p(2t + 1)$.
Thus the frog can reach $2^m$ from 1 in less than $N_1$ jumps, and can then reach $2^{i_0}(k_0 - 1)$ from $2^m$ in $N_2$ jumps. Hence the frog can reach $2^{i_0}(k_0 - 1)$ from 1 in less than $N_1 + N_2$ jumps, that is, in fewer jumps than needed to get to $2^{i_0} k_0$ and hence in fewer jumps than required to get to $2^{i_0}$. This contradicts the definition of $k_0$.

Suppose $x_0 = 1, x_1, \ldots, x_t = 2^i k$ are the integers visited by the frog on his trip from 1 to $2^i k$, $k\geq 2$. Let $s_j = x_j - x_{j-1}$ be the jump sizes. Define a reduced path $y_j$ inductively by

Say a jump $s_j$ is deleted in the second case. We will show that the distinct integers among the $y_j$ give a shorter path from 1 to $2^i$. Clearly $y_j\leq 2^i$ for all $j$. Suppose $2^i - 2^{r+1} < y_j\leq 2^i - 2^r$ for some $0\leq r\leq i - 1$. Then every deleted jump before $y_j$ must have length greater than $2^r$, hence must be a multiple of $2^{r+1}$. Thus $y_j\equiv x_j\pmod{2^{r+1}}$. If $y_{j+1} > y_j$, then either $s_{j+1} = 1$ (in which case this is a valid jump) or $s_{j+1}/2 = 2^m$ is the exact power of 2 dividing $x_j$. In the second case, since $2^r\geq s_{j+1} > 2^m$, the congruence says $2^m$ is also the exact power of 2 dividing $y_j$, thus again this is a valid jump. Thus the distinct $y_j$ form a valid path for the frog. If $j = t$ the congruence gives $y_t\equiv x_t\equiv 0\pmod{2^{r+1}}$, but this is impossible for $2^i - 2^{r+1} < y_t\leq 2^i - 2^r$. Hence we see $y_t = 2^i$, that is, the reduced path ends at $2^i$. Finally since the reduced path ends at $2^i < 2^i k$ at least one jump must have been deleted and it is strictly shorter than the original path.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zuming Feng, Zhonghao Ye) Let $ABCD$ be a quadrilateral, and let $E$ and $F$ be points on sides $AD$ and $BC$, respectively, such that $AE/ED = BF/FC$.  Ray $FE$ meets rays $BA$ and $CD$ at $S$ and $T$ respectively. Prove that the circumcircles of triangles $SAE$, $SBF$, $TCF$, and $TDE$ pass through a common point.

Let the intersection of the circumcircles of $SAE$ and $SBF$ be $X$, and let the intersection of the circumcircles of $TCF$ and $TDE$ be $Y$.
$BXF=BSF=AXE$ because $BSF$ tends both arcs $AE$ and $BF$.
$BFX=XSB=XEA$ because $XSB$ tends both arcs $XA$ and $XB$.
Thus, $XAE\sim XBF$ by AA similarity, and $X$ is the center of spiral similarity for $A,E,B,$ and $F$.
$FYC=FTC=EYD$ because $FTC$ tends both arcs $ED$ and $FC$.
$FCY=FTY=EDY$ because $FTY$ tends both arcs $YF$ and $YE$.
Thus, $YED\sim YFC$ by AA similarity, and $Y$ is the center of spiral similarity for $E,D,F,$ and $C$.
From the similarity, we have that $XE/XF=AE/BF$. But we are given $ED/AE=CF/BF$, so multiplying the 2 equations together gets us $ED/FC=XE/XF$. $DEX,CFX$ are the supplements of $AEX, BFX$, which are congruent, so $DEX=CFX$, and so $XED\sim XFC$ by SAS similarity, and so $X$ is also the center of spiral similarity for $E,D,F,$ and $C$. Thus, $X$ and $Y$ are the same point, which all the circumcircles pass through, and so the statement is true.

We will give a solution using complex coordinates. The first step is the following lemma.
Lemma. Suppose $s$ and $t$ are real numbers and $x$, $y$ and $z$ are complex. The circle in the complex plane passing through $x$, $x + ty$ and $x + (s + t)z$ also passes through the point $x + syz/(y - z)$, independent of $t$.
Proof. Four points $z_1$, $z_2$, $z_3$ and $z_4$ in the complex plane lie on a circle if and only if the cross-ratio

is real. Since we compute

the given points are on a circle. $\blacksquare$
Lay down complex coordinates with $S = 0$ and $E$ and $F$ on the positive real axis. Then there are real $r_1$, $r_2$ and $R$ with $B = r_1A$, $F = r_2E$ and $D = E + R(A - E)$ and hence $AE/ED = BF/FC$ gives

The line $CD$ consists of all points of the form $sC + (1 - s)D$ for real $s$. Since $T$ lies on this line and has zero imaginary part, we see from $\text{Im}(sC + (1 - s)D) = (sr_1R + (1 - s)R)\text{Im}(A)$ that it corresponds to $s = -1/(r_1 - 1)$. Thus

Apply the lemma with $x = E$, $y = A - E$, $z = (r_2 - r_1)E/(r_1 - 1)$, and $s = (r_2 - 1)(r_1 - r_2)$. Setting $t = 1$ gives

and setting $t = R$ gives

Therefore the circumcircles to $SAE$ and $TDE$ meet at

This last expression is invariant under simultaneously interchanging $A$ and $B$ and interchanging $E$ and $F$. Therefore it is also the intersection of the circumcircles of $SBF$ and $TCF$.

Let $M$ be the Miquel point of $ABCD$; then $M$ is the center of the spiral similarity that takes $AD$ to $BC$. Because $\frac{AE}{ED} = \frac{BF}{FC}$, the same spiral similarity also takes $E$ to $F$, so $M$ is the center of the spiral similarity that maps $AE$ to $BF$ and $ED$ to $FC$. Then it is obvious that the circumcircles of $SAE$, $SBF$, $TCF$, and $TDE$ pass through $M$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Sam Vandervelde) Let $n$ be a positive integer.  Define a sequence by setting $a_1 = n$ and, for each $k>1$, letting $a_k$ be the unique integer in the range $0 \le a_k \le k-1$ for which $a_1 + a_2 + \cdots + a_k$ is divisible by $k$.  For instance, when $n=9$ the obtained sequence is $9, 1, 2, 0, 3, 3, 3, \ldots$.  Prove that for any $n$ the sequence $a_1, a_2, a_3, \ldots$ eventually becomes constant.

Let $S_k = a_1 + a_2 + \cdots + a_k$ and $b_k = \frac{S_k}{k}$. Thus, because $S_{k+1} = S_k + a_{k+1}$,

$\frac{k}{k+1} < 1$, and by definition, $\frac{a_{k+1}}{k+1} < 1$. Thus, $b_{k+1} < b_k + 1$. Also, both $b_k$ and $b_{k+1}$ are integers, so $b_{k+1} \le b_k$. As the $b_k$'s form a non-increasing sequence of positive integers, they must eventually become constant.
Therefore, $b_k = b_{k+1}$ for some sufficiently large value of $k$. Then $a_{k+1} = S_{k+1} - S_k = b_k(k + 1) - b_k(k) = b_k$, so eventually the sequence $a_k$ becomes constant.

Let $a_1 = n$. Since $a_k\leq k - 1$, we have that

Since $a_1 + a_2 + \cdots + a_n = nk$ for some integer $k$, we can keep adding $k$ to satisfy the conditions, provided that $k\leq n$. This is true since $k\leq\frac{n + 1}{2}\leq n$, so the sequence must eventually become constant.

Define $S_k = a_1 + a_2 + \cdots + a_k$, and $b_k = \frac{S_k}{k}$. By the problem hypothesis, $b_k$ is an integer valued sequence.
Lemma: There exists a $k$ such that $b_k < k$.
Proof: Choose any $k$ such that $k^2 + 3k - 2 > 2n$. Then

as desired.
End Lemma
Let $k$ be the smallest $k$ such that $b_k < k$. Then $b_k = m < k$, and $S_k = km$. To make $b_{k+1}$ an integer, $S_{k+1} = S_k + a_{k+1}$ must be divisible by $k+1$. Thus, because $km + m$ is divisible by $k+1$, $a_{k+1} \equiv m \pmod{k+1}$, and, because $0 \le a_{k+1} < k$, $a_{k+1} = m$. Then $b_{k+1} = \frac{(k+1)m}{k+1} = m$ as well. Repeating the same process using $k+1$ instead of $k$ gives $a_{k+2} = m$, and an easy induction can prove that for all $N > k+1$, $a_N = m$. Thus, $a_k$ becomes a constant function for arbitrarily large values of $k$.

For $k\geq 1$, let

We claim that for some $m$ we have $s_m = m(m - 1)$. To this end, consider the sequence which computes the differences between $s_k$ and $k(k - 1)$, i.e., whose $k$-th term is $s_k - k(k - 1)$. Note that the first term of this sequence is positive (it is equal to $n$) and that its terms are strictly decreasing since

Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that $s_k > k(k - 1)$ and $s_{k+1} < (k + 1)k$. Since $s_k$ and $s_{k+1}$ are divisible by $k$ and $k + 1$, respectively, we can tighten the above inequalities to $s_k\geq k^2$ and $s_{k+1}\leq (k + 1)(k - 1) = k^2 - 1$. But this would imply that $s_k > s_{k+1}$, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.
Let $m$ be a positive integer such that $s_m = m(m - 1)$. We claim that

This follows from the fact that the sequence $a_1, a_2, a_3, \ldots$ is uniquely determined and choosing $a_{m+i} = m - 1$, for $i\geq 1$, satisfies the range condition

and yields

First, we may make an observation and say that for $n \equiv p (mod k)$, $\sum_{m=2}^{k} a_m \equiv k-p (mod k)$ must occur for the whole sum to be divisible by $k$. Thus, the following is apparent:

Then, we may make another observation that when $n=k$, the sum also has to be divisible by n. We may then explore when n=k:

and

Then,

Also,
 for $s \ge 1$. This is because:

This must be true since $r(n+1)$ will be divisible by $n+1$ and $k=n+1$, we may then generalize this to all $r(n+s), s \in \mathbb{Z}, s \ge 1$

Thus, we may say that the sequence $a_1,a_2,...a_k$ must converge to some integer value $r \le n$ when $k \ge n + 1$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Gregory Galperin) A square grid on the Euclidean plane consists of all points $(m,n)$, where $m$ and $n$ are integers.  Is it possible to cover all grid points by an infinite family of discs with non-overlapping interiors if each disc in the family has radius at least 5?

Lemma. Among 3 tangent circles with radius greater than or equal to 5, one can always fit a circle with radius greater than $\frac{1}{\sqrt{2}}$ between those 3 circles.
Proof. Descartes' Circle Theorem states that if $a$ is the curvature of a circle ($a=\frac 1{r}$, positive for externally tangent, negative for internally tangent), then we have that

Solving for $a$, we get

Take the positive root, as the negative root corresponds to internally tangent circle.
Now clearly, we have $b+c+d \le \frac 35$, and $bc+cd+db\le \frac 3{25}$.
Summing/square root/multiplying appropriately shows that $a \le \frac{3 + 2 \sqrt{3}}5$. Incidently, $\frac{3 + 2\sqrt{3}}5 < \sqrt{2}$, so $a< \sqrt{2}$, $r > \frac 1{\sqrt{2}}$, as desired. $\blacksquare$
For sake of contradiction, assume that we have a satisfactory placement of circles. Consider 3 circles, $p,\ q,\ r$ where there are no circles in between. By Appolonius' problem, there exists a circle $t$ tangent to $p,\ q,\ r$ externally that is between those 3 circles. Clearly, if we move $p,\ q,\ r$ together, $t$ must decrease in radius. Hence it is sufficient to consider 3 tangent circles. By lemma 1, there is always a circle of radius greater than $\frac{1}{\sqrt{2}}$ that lies between $p,\ q,\ r$. However, any circle with $r>\frac 1{\sqrt{2}}$ must contain a lattice point. (Consider placing an unit square parallel to the gridlines in the circle.) That is a contradiction. Hence no such tiling exists.

It is not possible. The proof is by contradiction. Suppose that such a covering family $\mathcal{F}$ exists. Let $D(P,\rho)$ denote the disc with center $P$ and radius $\rho$. Start with an arbitrary disc $D(O,r)$ that does not overlap any member of $\mathcal{F}$. Then $D(O,r)$ covers no grid point. Take the disc $D(O,r)$ to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then $D(O,r)$ is tangent to at least three discs in $\mathcal{F}$. Observe that there must be two of the three tangent discs, say $D(A,a)$ and $D(B,b)$ such that $\angle AOB\leq 120^\circ$. By the Law of Cosines applied to triangle $ABO$,

which yields

and thus

Note that $r < 1/\sqrt{2}$ because $D(O,r)$ covers no grid point, and $(a - 3r)(b - 3r)\geq (5 - 3r)^2$ because each disc in $\mathcal{F}$ has radius at least 5. Hence $2\sqrt{3}r\geq 5 - 3r$, which gives $5\leq (3 + 2\sqrt{3})r < (3 + 2\sqrt{3})/\sqrt{2}$ and thus $5\sqrt{2} < 3 + 2\sqrt{3}$. Squaring both sides of this inequality yields $50 < 21 + 12\sqrt{3} < 21 + 12\cdot 2 = 45$. This contradiction completes the proof.
Remark: The above argument shows that no covering family exists where each disc has radius greater than $(3 + 2\sqrt{3})/\sqrt{2}\approx 4.571$. In the other direction, there exists a covering family in which each disc has radius $\sqrt{13}/2\approx 1.802$. Take discs with this radius centered at points of the form $\left(2m + 4n + \frac{1}{2}, 3m + \frac{1}{2}\right)$, where $m$ and $n$ are integers. Then any grid point is with $\sqrt{13}/2$ of one of the centers and the distance between any two centers is at least $\sqrt{13}$. The extremal radius of a covering family is unknown.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(András Gyárfás) Let $S$ be a set containing $n^2+n-1$ elements, for some positive integer $n$.  Suppose that the $n$-element subsets of $S$ are partitioned into two classes.  Prove that there are at least $n$ pairwise disjoint sets in the same class.

Claim: If we have instead $k(n+1)-1$ elements, then we must have k disjoint subsets in a class.
We proceed by Induction
Base Case: $k=1$ is trivial.
Case 1: If there exists an $n+1$ element subset $X$ s.t. $X$ has 2 n-element subsets in different classes.
Consider the $(k-1)(n+1)-1$ elements that are not in $X$, from the Induction hypothesis, we have $k-1$ disjoint subsets in one of the classes. Those $k-1$ subsets paired with a subset of $X$ in the same class forms $k$ disjoint subsets of size n.
Case 2: All $n+1$ element subsets have all of their n-element subsets in one class.
Look at any 2 n-element subsets $a_1$ and $a_p$. Then we can create a path $a_1,a_2,...,a_p$ s.t. any 2 consecutive terms belong to the same n+1-element subset.(i.e. we change 1 element each time.) Thus, $a_1$ and $a_p$ are in the same class and we see that all subsets are in one class. Obviously we can find $k$ disjoint subsets of size n.
The question is asking for the case when $k=n$ which we have proved.

Call an $n+1$-element subset of $S$ separable if it has a subset in each class of the partition. We recursively build a set $Q$ of disjoint separable subsets of $S$: begin with $Q$ empty and at each step if there is a separable subset which is disjoint from all sets in $Q$ add that set to $Q$. The process terminates when every separable subset intersects a set in $Q$. Let $T$ be the set of elements in $S$ which are not in any set in $Q$. We claim that one class contains every $n$-element subset of $T$.
Suppose that $a_1, a_2, \ldots a_k$ are elements of $T$. Denote by $A_i$ the set $\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}$. Note that for each $i$, $A_i \cup A_{i+1}$ is not separable, so that $A_i$ and $A_{i+1}$ are in the same class. But then $A_i$ is in the same class for each $1 \leq i \leq k - n + 1$ — in particular, $A_1$ and $A_{k-n+1}$ are in the same class. But for any two sets we may construct such a sequence with $A_1$ equal to one and $A_{k-n+1}$ equal to the other.
We are now ready to construct our $n$ disjoint sets. Suppose that $|Q| = q$. Then $|T| = (n+1)(n-q) - 1 \geq n(n-q)$, so we may select $n - q$ disjoint $n$-element subsets of $T$. Then for each of the $q$ sets in $Q$, we may select a subset which is in the same class as all the subsets of $T$, for a total of $n$ disjoint sets.

In order to apply induction, we generalize the result to be proved so that it reads as follows:
Proposition. If the $n$-element subsets of a set $S$ with $(n + 1)m - 1$ elements are partitioned into two classes, then there are at least $m$ pairwise disjoint sets in the same class.
Proof. Fix $n$ and proceed by induction on $m$. The case of $m = 1$ is trivial. Assume $m > 1$ and that the proposition is true for $m - 1$. Let $\mathcal{P}$ be the partition of the $n$-element subsets into two classes. If all the $n$-element subsets belong to the same class, the result is obvious. Otherwise select two $n$-element subsets $A$ and $B$ from different classes so that their intersection has maximal size. It is easy to see that $|A\cap B| = n - 1$. (If $|A\cap B| = k < n - 1$, then build $C$ from $B$ by replacing some element not in $A\cap B$ with an element of $A$ not already in $B$. Then $|A\cap C| = k + 1$ and $|B\cap C| = n - 1$ and either $A$ and $C$ or $B$ and $C$ are in different classes.) Removing $A\cup B$ from $S$, there are $(n + 1)(m - 1) - 1$ elements left. On this set the partition induced by $\mathcal{P}$ has, by the inductive hypothesis, $m - 1$ pairwise disjoint sets in the same class. Adding either $A$ or $B$ as appropriate gives $m$ pairwise disjoint sets in the same class. $\blacksquare$
Remark: The value $n^2 + n - 1$ is sharp. A set $S$ with $n^2 + n - 2$ elements can be split into a set $A$ with $n^2 - 1$ elements and a set $B$ of $n - 1$ elements. Let one class consist of all $n$-element subsets of $A$ and the other consist of all $n$-element subsets that intersect $B$. Then neither class contains $n$ pairwise disjoint sets.

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


(Reid Barton) An animal with $n$ cells is a connected figure consisting of $n$ equal-sized square cells.${}^1$ The figure below shows an 8-cell animal.
A dinosaur is an animal with at least 2007 cells.  It is said to be primitive if its cells cannot be partitioned into two or more dinosaurs.  Find with proof the maximum number of cells in a primitive dinosaur.
${}^1$Animals are also called polyominoes.  They can be defined inductively.  Two cells are adjacent if they share a complete edge.  A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.

Let a $n$-dino denote an animal with $n$ or more cells.
We show by induction that an $n$-dino with $4n-2$ or more animal cells is not primitive. (Note: if it had more, we could just take off enough until it had $4n-2$, which would have a partition, and then add the cells back on.)
Base Case: If $n=1$, we have two cells, which are clearly not primitive.
Inductive Step: Assume any $4n-2$ cell animal can be partitioned into two or more $n$-dinos.
For a given $(4n+2)$-dino, take off any four cells (call them $w,\ x,\ y,\ z$) to get an animal with $4n-2$ cells.
This can be partitioned into two or more $n$-dinos, let's call them $A$ and $B$. This means that $A$ and $B$ are connected.
If both $A$ and $B$ are $(n+1)$-dinos or if $w,\ x,\ y,\ z$ don't all attach to one of them, then we're done.
So assume $A$ has $n$ cells and thus $B$ has at least $3n-2$ cells, and that $w,\ x,\ y,\ z$ are added to $B$. So $B$ has $3n+2$ cells total.
Let $C$ denote the cell of $B$ attached to $A$. There are $3n+1$ cells on $B$ besides $C$. Thus, of the three (or less) sides of $C$ not attached to $A$, one of them must have $n+1$ cells by the pigeonhole principle. It then follows that we can add $A$, $C$, and the other two sides together to get an $(n+1)$ dino, and the side of $C$ that has $n+1$ cells is also an $n+1$-dino, so we can partition the animal with $4n+2$ cells into two $(n+1)$-dinos and we're done.
Thus, our answer is $4(2007) - 3 = 8025$ cells.

For simplicity, let $k=2007$ and let $n$ be the number of squares. Let the centers of the squares be vertices, and connect any centers of adjacent squares with edges. Suppose we have some loops. Just remove an edge in the loop. We are still connected since you can go around the other way in the loop. Now we have no loops. Each vertex can have at most 4 edges coming out of it. For each point, assign it the quadruple: $(a,b,c,d)$ where $a$, $b$, $c$, $d$ are the numbers of vertices on each branch, WLOG $a\ge b\ge c\ge d$. Note $a+b+c+d=n-1$.
Claim: If $n=4k-2$, then we must be able to divide the animal into two dinosaurs.
Chose a vertex, $v$, for which $a$ is minimal (i.e. out of all maximal elements in a quadruple, choose the one with the least maximal element).  We have that $4a \ge a+b+c+d=4k-3$, so $a\ge k$. Hence we can just cut off that branch, that forms a dinosaur.
But suppose the remaining vertices do not make a dinosaur. Then we have $b+c+d+1\le k-1 \iff n-a\le k-1\iff a\ge 3k-1$. Now move to the first point on the branch at $a$. We have a new quadruple $p,\ q,\ r,\ b+c+d+1$) where $p+q+r=a-1\ge 3k-2$.
Now consider the maximal element of that quadruple. We already have $b+c+d+1\le k-1$. WLOG $p\ge q\ge r\ge 0$, then $3p\ge p+q+r=a-1\ge 3k-2\implies p\ge k$ so $p>k-1=b+c+d+1$, so $p$ is the maximal element of that quadruple.
Also $a-1=p+q+r\ge p+0+0$, so $p<a$. But that is a contradiction to the minimality of $a$. Therefore, we must have that $b+c+d+1\ge k$, so we have a partition of two dinosaurs.
Maximum: $n=4k-3$.
Consider a cross with each branch having $k-1$ verticies. Clearly if we take partition $k$ vertices, we remove the center, and we are not connected.
So $k=2007$: $4\cdot 2007-3=8025$.

Turn the dinosaur into a graph (cells are vertices, adjacent cells connected by an edge) and prove this result about graphs. A connected graph with $V$ vertices, where each vertex has degree less than or equal to $D$, can be partitioned into connected components of sizes at least $\frac{V-1}{D}$. So then in this special case, we have $D = 4$, and so $V = 2006 \times 4+1$ (a possible configuration of this size that works consists of a center and 4 lines of cells each of size 2006 connected to the center). We next throw out all the geometry of this situation, so that we have a completely unconstrained graph. If we prove the above-mentioned result, we can put the geometry back in later by taking the connected components that our partition gives us, then filling back all edges that have to be there due to adjacent cells. This won't change any of the problem constraints, so we can legitimately do this.
Going, now, to the case of arbitrary graphs, we WOP on the number of edges. If we can remove any edge and still have a connected graph, then we have found a smaller graph that does not obey our theorem, a contradiction due to the minimality imposed by WOP. Therefore, the only case we have to worry about is when the graph is a tree. If it's a tree, we can root the tree and consider the size of subtrees. Pick the root such that the size of the largest subtree is minimized. This minimum must be at least $\frac{V-1}{D}$, otherwise the sum of the size of the subtrees is smaller than the size of the graph, which is a contradiction. Also, it must be at most $\frac{V}{2}$, or else pick the subtree of size greater than $\frac{V}{2}$ and you have decreased the size of the largest subtree if you root from that vertex instead, so you have some subtree with size between $\frac{V-1}{D}$ and $\frac V2$. Cut the edge connecting the root to that subtree, and use that as your partition.
It is easy to see that these partitions satisfy the contention of our theorem, so we are done.

Let $s$ denote the minimum number of cells in a dinosaur; the number this year is $s = 2007$.
Claim: The maximum number of cells in a primitive dinosaur is $4(s - 1) + 1$.
First, a primitive dinosaur can contain up to $4(s - 1) + 1$ cells. To see this, consider a dinosaur in the form of a cross consisting of a central cell and four arms with $s - 1$ cells apiece. No connected figure with at least $s$ cells can be removed without disconnecting the dinosaur.
The proof that no dinosaur with at least $4(s - 1) + 2$ cells is primitive relies on the following result.
Lemma. Let $D$ be a dinosaur having at least $4(s - 1) + 2$ cells, and let $R$ (red) and $B$ (black) be two complementary animals in $D$, i.e. $R\cap B = \emptyset$ and $R\cup B = D$. Suppose $|R|\leq s - 1$. Then $R$ can be augmented to produce animals $\~{R}\subset R$ (Error compiling LaTeX. Unknown error_msg) and $\{B} = D\backslash\{R}$ (Error compiling LaTeX. Unknown error_msg) such that at least one of the following holds:
(i) $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) and $|\~{B}|\geq s$ (Error compiling LaTeX. Unknown error_msg),
(ii) $|\{R}| = |R| + 1$ (Error compiling LaTeX. Unknown error_msg),
(iii) $|R| < |\{R}|\leq s - 1$ (Error compiling LaTeX. Unknown error_msg).
Proof. If there is a black cell adjacent to $R$ that can be made red without disconnecting $B$, then (ii) holds. Otherwise, there is a black cell $c$ adjacent to $R$ whose removal disconnects $B$. Of the squares adjacent to $c$, at least one is red, and at least one is black, otherwise $B$ would be disconnected. Then there are at most three resulting components $\mathcal{C}_1, \mathcal{C}_2, \mathcal{C}_3$ of $B$ after the removal of $c$. Without loss of generality, $\mathcal{C}_3$ is the largest of the remaining components. (Note that $\mathcal{C}_1$ or $\mathcal{C}_2$ may be empty.) Now $\mathcal{C}_3$ has at least $\lceil (3s - 2)/3\rceil = s$ cells. Let $\{B} = \mathcal{C}_3$ (Error compiling LaTeX. Unknown error_msg). Then $|\{R}| = |R| + |\mathcal{C}_1| + |\mathcal{C}_2| + 1$ (Error compiling LaTeX. Unknown error_msg). If $|\{B}|\leq 3s - 2$ (Error compiling LaTeX. Unknown error_msg), then $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) and (i) holds. If $|\{B}|\geq 3s - 1$ (Error compiling LaTeX. Unknown error_msg) then either (ii) or (iii) holds, depending on whether $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) or not. $\blacksquare$
Starting with $|R| = 1$, repeatedly apply the Lemma. Because in alternatives (ii) and (iii) $|R|$ increases but remains less than $s$, alternative (i) eventually must occur. This shows that no dinosaur with at least $4(s - 1) + 2$ cells is primitive.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Titu Andreescu) Prove that for every nonnegative integer $n$, the number $7^{7^n}+1$ is the product of at least $2n+3$ (not necessarily distinct) primes.

The proof is by induction. The base is provided by the $n = 0$ case, where $7^{7^0} + 1 = 7^1 + 1 = 2^3$. To prove the inductive step, it suffices to show that if $x = 7^{2m - 1}$ for some positive integer $m$ then $(x^7 + 1)/(x + 1)$ is composite. As a consequence, $x^7 + 1$ has at least two more prime factors than does $x + 1$. To confirm that $(x^7 + 1)/(x + 1)$ is composite, observe that

Also each factor exceeds 1. It suffices to check the smaller one; $\sqrt{7x}\leq x$ gives

Hence $(x^7 + 1)/(x + 1)$ is composite and the proof is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Kiran Kedlaya, Sungyoon Kim) Let $ABC$ be an acute triangle with $\omega$, $\Omega$, and $R$ being its incircle, circumcircle, and circumradius, respectively.  Circle $\omega_A$ is tangent internally to $\Omega$ at $A$ and tangent externally to $\omega$.  Circle $\Omega_A$ is tangent internally to $\Omega$ at $A$ and tangent internally to $\omega$.  Let $P_A$ and $Q_A$ denote the centers of $\omega_A$ and $\Omega_A$, respectively.  Define points $P_B$, $Q_B$, $P_C$, $Q_C$ analogously.  Prove that

with equality if and only if triangle $ABC$ is equilateral.

Lemma.
Proof. Note $P_{A}$ and $Q_{A}$ lie on $AO$ since for a pair of tangent circles, the point of tangency and the two centers are collinear.
Let $\omega$ touch $BC$, $CA$, and $AB$ at $D$, $E$, and $F$, respectively. Note $AE=AF=s-a$. Consider an inversion, $\mathcal{I}$, centered at $A$, passing through $E$, $F$. Since $IE\perp AE$, $\omega$ is orthogonal to the inversion circle, so $\mathcal{I}(\omega)=\omega$. Consider $\mathcal{I}(\omega_{A})=\omega_{A}'$. Note that $\omega_{A}$ passes through $A$ and is tangent to $\omega_{A}$, hence $\omega_{A}'$ is a line that is tangent to $\omega$. Furthermore, $\omega_{A}'\perp AO$ because $\omega_{A}$ is symmetric about $OA$, so the inversion preserves that reflective symmetry. Since it is a line that is symmetric about $AO$, it must be perpendicular to $AO$. Likewise, $\mathcal{I}(\Omega_{A})=\Omega_{A}'$ is the other line tangent to $\omega$ and perpendicular to $AO$.
Let $\omega_{A} \cap AO=X$ and $\omega_{A}' \cap AO=X'$ (second intersection).
Let $\Omega_{A} \cap AO=Y$ and $\Omega_{A}' \cap AO=Y'$ (second intersection).
Evidently, $AX=2AP_{A}$ and $AY=2AQ_{A}$. We want:

by inversion. Note that $\omega_{A}' || \Omega_{A}'$, and they are tangent to $\omega$, so the distance between those lines is $2r=AX'-AY'$. Drop a perpendicular from $I$ to $AO$, touching at $H$. Then $AH=AI\cos\angle OAI=AI\cos\frac{1}{2}|\angle B-\angle C|$. Then $AX', AY' = AI\cos\frac{1}{2}|\angle B-\angle C|\pm r$. So $AX'\cdot AY' = AI^{2}\cos^{2}\frac{1}{2}|\angle B-\angle C|-r^{2}$.

Note that $\frac{AI}{r} = \frac{1}{\sin\frac{A}{2}}$. Applying the double angle formulas and $1-\cos\angle A=\frac{2(s-b)(s-c)}{bc}$, we get
End Lemma
The problem becomes:

which is true because $OI^{2}=R(R-2r)$, equality is when the circumcenter and incenter coincide. As before, $\angle OAI=\frac{1}{2}|\angle B-\angle C|=0$, so, by symmetry, $\angle A=\angle B=\angle C$. Hence the inequality is true iff $\triangle ABC$ is equilateral.
Comment: It is much easier to determine $AP_{A}$ by considering $\triangle IAP_{A}$. We have $AI$, $\angle IAO$, $IP_{A}=r+r(P_{A})$, and $AP_{A}=r(P_{A})$. However, the inversion is always nice to use. This also gives an easy construction for $w_{A}$ because the tangency point is collinear with the intersection of $w_{A}'$ and $w$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.