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

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

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

Let $\, a_1, a_2, a_3, \ldots \,$ be a sequence of positive real numbers satisfying $\, \sum_{j=1}^n a_j \geq \sqrt{n} \,$ for all $\, n \geq 1$. Prove that, for all $\, n \geq 1, \,$ \[ \sum_{j=1}^n a_j^2 > \frac{1}{4} \left( 1 + \frac{1}{2} + \cdots + \frac{1}{n} \right). \]

Click for solution Karamata again... Define a sequence $\left(b_n\right)_{n\in\mathbb{N}}$ by $b_k=\sqrt{k}-\sqrt{k-1}$ for every k. Since $b_k=\sqrt{k}-\sqrt{k-1}=\frac{\left(\sqrt{k}+\sqrt{k-1}\right)\left(\sqrt{k}-\sqrt{k-1}\right)}{\sqrt{k}+\sqrt{k-1}}$ $=\frac{k-\left(k-1\right)}{\sqrt{k}+\sqrt{k-1}}=\frac{1}{\sqrt{k}+\sqrt{k-1}}$, it is clear that this sequence $\left(b_n\right)$ is decreasing (since, when k increases, both $\sqrt{k}$ and $\sqrt{k-1}$ increase, so that $\sqrt{k}+\sqrt{k-1}$ increases, and thus $b_k=\frac{1}{\sqrt{k}+\sqrt{k-1}}$ decreases). Hence, for every index k with $1\leq k\leq n$, the numbers $b_1$, $b_2$, ..., $b_k$ are the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Hence, the sum $\sum_{j=1}^k b_j$ is the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Since $\sum_{j=1}^k b_j=\sum_{j=1}^k\left(\sqrt{j}-\sqrt{j-1}\right)=\sqrt{k}-\sqrt{0}=\sqrt{k}$, we thus can state: The sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$ is $\sqrt{k}$. For the numbers $a_1$, $a_2$, ..., $a_n$, we don't know how they are arranged, and we can only say that the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum $\sum_{j=1}^k a_j$ (in fact, this is obvious: the sum of the k greatest numbers is greater or equal to the sum of just some k numbers). So altogether, for every index k with $1\leq k\leq n$, we have: - The sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum $\sum_{j=1}^k a_j$. - By the condition of the problem, $\sum_{j=1}^k a_j \geq \sqrt{k}$. - The number $\sqrt{k}$ is the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Combining this, we see that for every index k with $1\leq k\leq n$, the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Now, we have the following fact: Karamata theorem for "pseudo-majorizing" number arrays: Let $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ be 2n numbers from an interval $\mathcal{I}$ such that for every index k with $1\leq k\leq n$, the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$ (but we don't require equality for k = n, i. e. we don't necessarily have $a_1+a_2+...+a_n=b_1+b_2+...+b_n$, but we only need $a_1+a_2+...+a_n\geq b_1+b_2+...+b_n$). Also, let f be a function which is convex and monotonically increasing on the interval $\mathcal{I}$. Then, $\sum_{j=1}^n f\left(a_j\right)\geq\sum_{j=1}^n f\left(b_j\right)$. This theorem can be easily deduced from the actual Karamata theorem. Now, applying this theorem to our numbers $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$, with the interval $\mathcal{I}=\mathbb{R}^+$ and the function $f\left(t\right)=t^2$ which is convex and monotonically increasing on $\mathbb{R}^+$, we get $\sum_{j=1}^n a_j^2\geq\sum_{j=1}^n b_j^2=\sum_{j=1}^n\left(\frac{1}{\sqrt{j}+\sqrt{j-1}}\right)^2>\sum_{j=1}^n\left(\frac{1}{\sqrt{j}+\sqrt{j}}\right)^2=\sum_{j=1}^n\left(\frac{1}{2\sqrt{j}}\right)^2$ $=\sum_{j=1}^n\frac{1}{4j}=\frac14\sum_{j=1}^n\frac{1}{j}$, and the problem is solved. EDIT: I just saw the same problem in a slightly different version being posted at http://www.artofproblemsolving.com/Forum/viewtopic.php?t=21262 . Darij

Let $\, |U|, \, \sigma(U) \,$ and $\, \pi(U) \,$ denote the number of elements, the sum, and the product, respectively, of a finite set $\, U \,$ of positive integers. (If $\, U \,$ is the empty set, $\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1$.) Let $\, S \,$ be a finite set of positive integers. As usual, let $\, \binom{n}{k} \,$ denote $\, n! \over k! \, (n-k)!$. Prove that \[ \sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S) \] for all integers $\, m \geq \sigma(S)$.

These problems are copyright $\copyright$ Mathematical Association of America.