Let $A_1$ be the center of the square inscribed in acute triangle $ABC$ with two vertices of the square on side $BC$. Thus one of the two remaining vertices of the square is on side $AB$ and the other is on $AC$. Points $B_1,\ C_1$ are defined in a similar way for inscribed squares with two vertices on sides $AC$ and $AB$, respectively. Prove that lines $AA_1,\ BB_1,\ CC_1$ are concurrent.

Click for solution Here is my solution: Let X, Y, Z be the centers of the squares BCTU, CAVW, ABSR constructed on the segments BC, CA, AB and pointing into the exterior of triangle ABC. The square inscribed in triangle ABC with two vertices on BC, one on AB and one on AC is homothetic to the square constructed on the segment BC into the exterior of triangle ABC, the center of homothety being A; hence, the centers $A_1$ and X of these two squares are collinear with A, i. e. the line $AA_1$ coincides with the line AX. Similarly, the line $BB_1$ coincides with BY, and the line $CC_1$ coincides with CZ. Hence, instead of proving that the lines $AA_1$, $BB_1$, $CC_1$ concur, it will be enough to show that the lines AX, BY, CZ concur. Well, why do the lines AX, BY, CZ concur? There are several proofs of this fact; here is the most elementary of them: I will show that the lines AX, BY, CZ are perpendicular to the lines YZ, ZX, XY, respectively; then, it will follow that AX, BY, CZ are the altitudes of triangle XYZ and hence concur. Why are the lines AX, BY, CZ perpendicular to YZ, ZX, XY? Well, the spiral dilatation with center B, rotation angle 45 and dilatation factor $\sqrt2$ maps C to T and Z to A. Hence, the segment TA is the image of the segment CZ, so that < (CZ; TA) = 45 (where < (k; l) denotes the directed angle between two lines k and l). The spiral dilatation with center C, rotation angle 45 and dilatation factor $\frac{1}{\sqrt2}$ maps T to X and A to Y. Hence, the segment XY is the image of the segment TA, so that < (TA; XY) = 45, and < (CZ; XY) = < (CZ; TA) + < (TA; XY) = 45 + 45 = 90, so that CZ is perpendicular to XY. Similarly, AX is perpendicular to YZ and BY is perpendicular to ZX, and we are done. [By the way, the same approach using spiral dilatations shows that AX = YZ, BY = ZX and CZ = XY.] Darij

Consider an acute-angled triangle $ABC$. Let $P$ be the foot of the altitude of triangle $ABC$ issuing from the vertex $A$, and let $O$ be the circumcenter of triangle $ABC$. Assume that $\angle C \geq \angle B+30^{\circ}$. Prove that $\angle A+\angle COP < 90^{\circ}$.

Let $ABC$ be a triangle with centroid $G$. Determine, with proof, the position of the point $P$ in the plane of $ABC$ such that $AP{\cdot}AG + BP{\cdot}BG + CP{\cdot}CG$ is a minimum, and express this minimum value in terms of the side lengths of $ABC$.

Click for solution The minimum of the expression $AP\cdot AG+BP\cdot BG+CP\cdot CG$ is achieved when P coincides with the centroid G of triangle ABC, and this minimum equals $AG^2+BG^2+CG^2=\frac13 \left( a^2+b^2+c^2\right) $. Proof. Using vectors and their scalar products, we have $UV\cdot UW\geq \overrightarrow{UV}\cdot \overrightarrow{UW}$ for any three points U, V and W, and equality holds if and only if the point W lies on the ray UV. Thus, $AP\cdot AG+BP\cdot BG+CP\cdot CG\geq \overrightarrow{AP}\cdot \overrightarrow{AG}+\overrightarrow{BP}\cdot \overrightarrow{BG}+\overrightarrow{CP}\cdot \overrightarrow{CG}$, with equality holding if and only if the point G lies on the ray AP, on the ray BP and on the ray CP simultaneously, i. e. if and only if the point P coincides with the point G. Now, $\overrightarrow{AP}\cdot \overrightarrow{AG}+\overrightarrow{BP}\cdot \overrightarrow{BG}+\overrightarrow{CP}\cdot \overrightarrow{CG}$ $=\left( \overrightarrow{AG}+\overrightarrow{GP}\right) \cdot \overrightarrow{AG}+\left( \overrightarrow{BG}+\overrightarrow{GP}\right) \cdot \overrightarrow{BG}+\left( \overrightarrow{CG}+\overrightarrow{GP}\right) \cdot \overrightarrow{CG}$ $=\left( \overrightarrow{AG}^2+\overrightarrow{BG}^2+\overrightarrow{CG}^2\right) +\overrightarrow{GP}\cdot \left( \overrightarrow{AG}+\overrightarrow{BG}+\overrightarrow{CG}\right) $. Now, since the point G is the centroid of triangle ABC, we have $\overrightarrow{AG}+\overrightarrow{BG}+\overrightarrow{CG}=\overrightarrow{0}$, and thus $\overrightarrow{AP}\cdot \overrightarrow{AG}+\overrightarrow{BP}\cdot \overrightarrow{BG}+\overrightarrow{CP}\cdot \overrightarrow{CG}=\left( \overrightarrow{AG}^2+\overrightarrow{BG}^2+\overrightarrow{CG}^2\right) +\overrightarrow{GP}\cdot \overrightarrow{0}$ $=\overrightarrow{AG}^2+\overrightarrow{BG}^2+\overrightarrow{CG}^2=AG^2+BG^2+CG^2$. After the well-known formula for the median lengths in a triangle, the length $m_a$ of the median of triangle ABC issuing from the vertex A satisfies the equation $4m_a^2=2b^2+2c^2-a^2$. Since the point G is the centroid of triangle ABC and thus divides all medians in the ratio 2 : 1, we have $AG=\frac23 m_a$, and thus $AG^2=\left( \frac23 m_a\right) ^2=\frac{4m_a^2}{9}=\frac{2b^2+2c^2-a^2}{9}$. Similarly, $BG^2=\frac{2c^2+2a^2-b^2}{9}$; $CG^2=\frac{2a^2+2b^2-c^2}{9}$, and thus $AG^2+BG^2+CG^2=\frac{2b^2+2c^2-a^2}{9}+\frac{2c^2+2a^2-b^2}{9}+\frac{2a^2+2b^2-c^2}{9}=\frac13 \left( a^2+b^2+c^2\right) $. Hence, we have $\overrightarrow{AP}\cdot \overrightarrow{AG}+\overrightarrow{BP}\cdot \overrightarrow{BG}+\overrightarrow{CP}\cdot \overrightarrow{CG}=\frac13 \left( a^2+b^2+c^2\right) $. Now, since $AP\cdot AG+BP\cdot BG+CP\cdot CG\geq \overrightarrow{AP}\cdot \overrightarrow{AG}+\overrightarrow{BP}\cdot \overrightarrow{BG}+\overrightarrow{CP}\cdot \overrightarrow{CG}$, it follows that $AP\cdot AG+BP\cdot BG+CP\cdot CG\geq \frac13 \left( a^2+b^2+c^2\right) $, with equality if and only if the point P coincides with the point G. In other words, the minimum of the expression $AP\cdot AG+BP\cdot BG+CP\cdot CG$ is achieved for P = G and equals $\frac13 \left( a^2+b^2+c^2\right) $. Proof complete. Darij

Let $M$ be a point in the interior of triangle $ABC$. Let $A'$ lie on $BC$ with $MA'$ perpendicular to $BC$. Define $B'$ on $CA$ and $C'$ on $AB$ similarly. Define \[ p(M) = \frac{MA' \cdot MB' \cdot MC'}{MA \cdot MB \cdot MC}. \] Determine, with proof, the location of $M$ such that $p(M)$ is maximal. Let $\mu(ABC)$ denote this maximum value. For which triangles $ABC$ is the value of $\mu(ABC)$ maximal?

Let $ABC$ be an acute triangle. Let $DAC,EAB$, and $FBC$ be isosceles triangles exterior to $ABC$, with $DA=DC, EA=EB$, and $FB=FC$, such that \[ \angle ADC = 2\angle BAC, \quad \angle BEA= 2 \angle ABC, \quad \angle CFB = 2 \angle ACB. \]Let $D'$ be the intersection of lines $DB$ and $EF$, let $E'$ be the intersection of $EC$ and $DF$, and let $F'$ be the intersection of $FA$ and $DE$. Find, with proof, the value of the sum \[ \frac{DB}{DD'}+\frac{EC}{EE'}+\frac{FA}{FF'}. \]

Click for solution You are right, Grobber's solution is incorrect. He probably got confused by the asymmetric notations (this also happened to me when I saw the problem first). However, the problem is still quite easy: In the following, $\left|P_1P_2P_3\right|$ will mean the (non-directed) area of a triangle $P_1P_2P_3$. Let d be the circle with center D and radius DA = DC. This circle d clearly passes through the points A and C. Similarly, we have a circle e with center E and radius EA = EB, which passes through the points A and B, and a circle f with center F and radius FB = FC, which passes through the points B and C. Let the two circles d and e intersect at a point S (apart from A). In the circle e, the angle < BEA is the central angle of the chord AB, while the angle < ASB is the obtuse chordal angle over this chord; hence, $\measuredangle BEA=2\cdot\left(180^{\circ}-\measuredangle ASB\right)$. Comparing this with $\measuredangle BEA=2\cdot\measuredangle ABC$, we get < ABC = 180° - < ASB, so that < ASB = 180° - < ABC. Similarly, we find < ASC = 180° - < BAC, since the point S lies on the circle d. Hence, < BSC = 360° - < ASB - < ASC = 360° - (180° - < ABC) - (180° - < BAC) = < ABC + < BAC = 180° - < ACB (by the sum of angles in triangle ABC). Thus, < ACB = 180° - < BSC. Hence, $\measuredangle CFB=2\cdot\measuredangle ACB$ becomes $\measuredangle CFB=2\cdot\left(180^{\circ}-\measuredangle BSC\right)$. Now, since the points B and C lie on the circle f, and the angle < CFB is the central angle of the chord BC in this circle, this equation yields that < BSC is the obtuse chordal angle over the chord BC in this circle f; thus, the point S lies on the circle f. Hence, the point S lies on all three circles d, e, f. The points B and S, being the two common points of the circles e and f, must be symmetric to each other with respect to the line EF joining the centers E and F of these circles; hence, the triangles BEF and SEF are congruent, so that | BEF | = | SEF |. The two triangles DD'E and BD'E have a common altitude from the vertex E; thus, their areas are proportional to their bases DD' and BD'. In other words, $\frac{\left|DD^{\prime}E\right|}{\left|BD^{\prime}E\right|}=\frac{DD^{\prime}}{BD^{\prime}}$. In other words, $BD^{\prime}\cdot\left|DD^{\prime}E\right|=DD^{\prime}\cdot\left|BD^{\prime}E\right|$. Similarly, $BD^{\prime}\cdot\left|DD^{\prime}F\right|=DD^{\prime}\cdot\left|BD^{\prime}F\right|$. Hence, $BD^{\prime}\cdot\left|DEF\right|=BD^{\prime}\cdot\left(\left|DD^{\prime}E\right|+\left|DD^{\prime}F\right|\right)=BD^{\prime}\cdot\left|DD^{\prime}E\right|+BD^{\prime}\cdot\left|DD^{\prime}F\right|$ $=DD^{\prime}\cdot\left|BD^{\prime}E\right|+DD^{\prime}\cdot\left|BD^{\prime}F\right|=DD^{\prime}\cdot\left(\left|BD^{\prime}E\right|+\left|BD^{\prime}F\right|\right)=DD^{\prime}\cdot\left|BEF\right|$ $=DD^{\prime}\cdot\left|SEF\right|$, so that $\frac{BD^{\prime}}{DD^{\prime}}=\frac{\left|SEF\right|}{\left|DEF\right|}$. Hence, $\frac{DB}{DD^{\prime}}=\frac{DD^{\prime}+BD^{\prime}}{DD^{\prime}}=1+\frac{BD^{\prime}}{DD^{\prime}}=1+\frac{\left|SEF\right|}{\left|DEF\right|}$. Similarly, $\frac{EC}{EE^{\prime}}=1+\frac{\left|SFD\right|}{\left|DEF\right|}$; $\frac{FA}{FF^{\prime}}=1+\frac{\left|SDE\right|}{\left|DEF\right|}$. Thus, $\frac{DB}{DD^{\prime}}+\frac{EC}{EE^{\prime}}+\frac{FA}{FF^{\prime}}=\left(1+\frac{\left|SEF\right|}{\left|DEF\right|}\right)+\left(1+\frac{\left|SFD\right|}{\left|DEF\right|}\right)+\left(1+\frac{\left|SDE\right|}{\left|DEF\right|}\right)$ $=3+\frac{\left|SEF\right|+\left|SFD\right|+\left|SDE\right|}{\left|DEF\right|}=3+\frac{\left|DEF\right|}{\left|DEF\right|}=3+1=4$. And the problem is solved. Darij

Let $ABC$ be a triangle and $P$ an exterior point in the plane of the triangle. Suppose the lines $AP$, $BP$, $CP$ meet the sides $BC$, $CA$, $AB$ (or extensions thereof) in $D$, $E$, $F$, respectively. Suppose further that the areas of triangles $PBD$, $PCE$, $PAF$ are all equal. Prove that each of these areas is equal to the area of triangle $ABC$ itself.

Let $O$ be an interior point of acute triangle $ABC$. Let $A_1$ lie on $BC$ with $OA_1$ perpendicular to $BC$. Define $B_1$ on $CA$ and $C_1$ on $AB$ similarly. Prove that $O$ is the circumcenter of $ABC$ if and only if the perimeter of $A_1B_1C_1$ is not less than any one of the perimeters of $AB_1C_1, BC_1A_1$, and $CA_1B_1$.

Click for solution Let us denote by $p_{XYZ}$ the perimeter of a triangle $XYZ$. "$\Rightarrow$" If $O$ is the circumcenter of $\triangle{ABC}$, then $A_{1},B_{1}, C_{1}$ are the midpoints of the sides of the triangle, therefore $p_{A_{1}B_{1}C_{1}}=p_{AB_{1}C_{1}}= p_{A_{1}BC_{1}}= p_{A_{1}B_{1}C}$. "$\Leftarrow$" Assume WLOG, that $p_{A_{1}B_{1}C_{1}}$ is greater than $p_{AB_{1}C_{1}}$, $p_{A_{1}BC_{1}}$, $p_{A_{1}B_{1}C}$. And let $\alpha_{1}$, $\alpha_{2}$, $\beta_{1}$, $\beta_{2}$, $\gamma_{1}$, $\gamma_{2}$ be $\angle{B_{1}A_{1}C}$, $\angle{C_{1}A_{1}B}$, $\angle{C_{1}B_{1}A}$, $\angle{A_{1}B_{1}C}$, $\angle{A_{1}C_{1}B}$, $\angle{B_{1}C_{1}A}$. Now suppose $\gamma_{1}, \beta_{2}\geq \alpha$. If $A_{2}$ is the fourth vertex of the parallelogram $B_{1}AC_{1}A_{2}$, then these conditions imply that $A_{1}$ is in the interior or on the sides of $\triangle{B_{1}C_{1}A_{2}}$, therefore $p_{A_{1}B_{1}C_{1}}\leq p_{A_{2}B_{1}C_{1}}\leq p_{AB_{1}C_{1}}$. But, lets see that if one of the inequalitites $\gamma_{1}\geq \alpha$ and $\beta_{2}\geq \alpha$ is strict, then $p_{A_{1}B_{1}C_{1}}< p_{AB_{1}C_{1}}$, which contradicts our assumption. Therefore $\beta_{2}\geq \alpha$ implies $\gamma_{1}\leq \alpha$, and the analogues. $(\star)$ Now, because of the symmetry, we can suppose WLOG, that $\gamma_{1}\leq \alpha$, then since $\gamma_{1}+\alpha_{2}=180-\beta=\alpha+\gamma$, it follows that $\alpha_{2}\geq \gamma$. From $(\star)$ we deduce that $\beta_{1}\leq \gamma$, thus $\gamma_{2}\geq \beta$, $\alpha_{1}\leq \beta$, and $\beta_{2}\geq \alpha$. Now putting them all together, we obtain that: $\gamma_{1}\leq \alpha\leq \beta_{2}$, $\alpha_{1}\leq \beta\leq \gamma_{2}$, $\beta_{1}\leq \gamma\leq \alpha_{2}$. Now since $OA_{1}BC_{1}$ and $OB_{1}CA_{1}$ are cyclic quadrilaterals, we have that $\angle{A_{1}OB}=\gamma_{1}$ and $\angle{A_{1}OC}=\beta_{2}$. Thus $\frac{BO}{CO}=\frac{\cos{\beta_{2}}}{\cos{\gamma_{1}}}$, so $BO\leq CO$. Now in a similar way prove that $CO \leq AO$ and $AO \leq BO$. Thus $OA=OB=OC$, therefore $O$ is the circumcenter.

Let $ABC$ be a triangle with $\angle BAC = 60^{\circ}$. Let $AP$ bisect $\angle BAC$ and let $BQ$ bisect $\angle ABC$, with $P$ on $BC$ and $Q$ on $AC$. If $AB + BP = AQ + QB$, what are the angles of the triangle?

Prove that there is no positive integer $n$ such that, for $k = 1,2,\ldots,9$, the leftmost digit (in decimal notation) of $(n+k)!$ equals $k$.

Click for solution Suppose that such an integer $n$ exists. for each $1\leq k\leq 9$, there exists an integer $p_{k}$ such that: $k.10^{p_{k}}\leq (n+k)! < (k+1).10^{p_{k}}$ By forming the quotient between two successive inequalities, we find that for each $2\leq k \leq 9$, $10^{p_{k}-p_{k-1}}<n+k<\frac{k+1}{k-1}10^{p_{k}-p_{k-1}}$ (1) As $\frac{k+1}{k-1}<10$ for each $2\leq k \leq 9$, we know that $p_{k}-p_{k-1}$ is a constant (i.e. does not depends on k). Assume $p_{k}-p_{k-1}=l$. Simply use (1) with $k=9$, and you will find: $%Error. "foreach" is a bad command. 1\leq k \leq 9, \ \ 10^{l}\leq n+k<1,25.10^{l}$(2) (by the way, this proves that if such an integer $n$ exists, we have $l\geq 2$ and $n+1\geq 100$) Now, from $(n+1)n!=(n+1)!<2.10^{p_{1}}$ and $(n+4)^{4}n!>(n+4)!\geq 4.10^{p_{4}}$ We get $\frac{(n+4)^{4}}{n+1}>2.10^{p_{4}-p_{1}}=2.10^{3l}$ if $l\geq 3$, then $n+1\geq 1000$ (using (2) ) so $\frac{n+1}{n+4}\geq \frac{1000}{1003}$ so: $(n+4)^{3}=\frac{(n+4)^{4}}{n+1}.\frac{n+1}{n+4}>\frac{1000}{1003}2.10^{3l}$ $n+4>\left(2\frac{1000}{1003}\right)^{1/3}.10^{l}>1,25.10^{l}$ which contradicts (2). Otherwise, $l=2$, and $\frac{(n+4)^{4}}{n+1}>2.10^{6}$ $n+1\geq 100$ (using (2) ) so $\frac{n+1}{n+4}\geq \frac{100}{103}$ so: $(n+4)^{3}=\frac{(n+4)^{4}}{n+1}.\frac{n+1}{n+4}>\frac{100}{103}2.10^{6}$ $n+4>\left(2\frac{100}{103}\right)^{1/3}.10^{2}>123$ so: $n+9>125$ which again contradicts (2).

Consider the system \begin{align*}x + y &= z + u,\\2xy & = zu.\end{align*}Find the greatest value of the real constant $m$ such that $m \leq x/y$ for any positive integer solution $(x,y,z,u)$ of the system, with $x \geq y$.

Let $ a_1 = 11^{11}, \, a_2 = 12^{12}, \, a_3 = 13^{13}$, and $ a_n = |a_{n - 1} - a_{n - 2}| + |a_{n - 2} - a_{n - 3}|, n \geq 4.$ Determine $ a_{14^{14}}$.

Let $p \geq 5$ be a prime number. Prove that there exists an integer $a$ with $1 \leq a \leq p-2$ such that neither $a^{p-1}-1$ nor $(a+1)^{p-1}-1$ is divisible by $p^2$.

Click for solution It's well-known that $P(x)=x^{p-1}-1$ has $p-1$ roots in $\mathbb Z_{p^2}$. Assume what we're trying to prove doesn't hold. In each pair $(1,2),(3,4),\ldots,(p-2,p-1)$ there's at least a root of $P$, so there are at least $\frac{p-1}2$ roots of $P$ among the first $p$ residues $\pmod{p^2}$. If $x$ is a root of $P$, then so is $-x$ (in $\mathbb Z_{p^2}$, of course), so there are at least $\frac{p-1}2$ other roots of $P$ among the last $p$ residues $\pmod{p^2}$. This means that the roots of $P$ lie in the intervals $(1,p)$ and $(p^2-p,p^2)$. However, we can clearly find roots which are not in these intervals, for example the product of two roots chosen from the pairs $(\frac{p-3}2,\frac{p-1}2),(\frac{p+1}2,\frac{p+3}2)$. Their product is $\ge \frac{(p-3)(p+1)}4$ and $\le \frac{(p-1)(p+3)}4$. For $p\ge 7$ this product is outside the two intervals mentioned above, and for $p=5$ we can check it manually (take $a=1$).

Let $a > b > c > d$ be positive integers and suppose that \[ ac + bd = (b+d+a-c)(b+d-a+c). \] Prove that $ab + cd$ is not prime.

Click for solution Solution by Iura: Lemma. If $ab=cd$ then there exist $m,n,p,q$ with $a=mn, b=pq, c=mp, d=nq$. Proof is obvious. Opening the brackets we get $a^2+c^2-ac=b^2+bd+d^2$ Multiplying by $4$ we get $(2a-c)^2+3c^2=(2b+d)^2+3d^2$ thus $3(c+d)(c-d)=(2b+d-2a+c)(2b+d+2a+c)$. Now using this Lemma we get either \[c+d=mn, c-d=pq, 2a+c-2b+d=3mp, 2b+d+2a+c=nq,\] or \[c+d=mn, c-d=pq, 2a+c-2b+d=mp, 2b+d+2a+c=3nq.\] For the first case, notice that $16(ab+cd)=(3p^2+n^2)(3m-q)(m+q)$, and it's easy to handle it now. The second case is analogous.

Is it possible to find $100$ positive integers not exceeding $25,000$, such that all pairwise sums of them are different?

Let $ T$ denote the set of all ordered triples $ (p,q,r)$ of nonnegative integers. Find all functions $ f: T \rightarrow \mathbb{R}$ satisfying \[ f(p,q,r) = \begin{cases} 0 & \text{if} \; pqr = 0, \\ 1 + \frac{1}{6}(f(p + 1,q - 1,r) + f(p - 1,q + 1,r) & \\ + f(p - 1,q,r + 1) + f(p + 1,q,r - 1) & \\ + f(p,q + 1,r - 1) + f(p,q - 1,r + 1)) & \text{otherwise} \end{cases} \] for all nonnegative integers $ p$, $ q$, $ r$.

Let $a_0, a_1, a_2, \ldots$ be an arbitrary infinite sequence of positive numbers. Show that the inequality $1 + a_n > a_{n-1} \sqrt[n]{2}$ holds for infinitely many positive integers $n$.

Click for solution Assume, as before, that for $n\ge n_0$ what we want to show doesn't hold anymore. We have $a_{n+k}\le S_k=a_n2^{H_{n+k}-H_n}-2^{H_{n+k}-H_{n+1}}-\ldots-2^{H_{n+k}-H_{n+k-1}}-1$, where $H_n=1+\frac 12+\ldots+\frac 1n$. Let's fix $n$ and make $k\to\infty$. It would be enough to show that $S_k\to-\infty$ to obtain a contradiction. Clearly, $2^{H_{n+k}-H_n}\to\infty$ as $k\to\infty$, so it's enough to show that $\frac{2^{H_{n+k}-H_{n+1}}+\ldots+2^{H_{n+k}-H_{n+k-1}}+1}{2^{H_{n+k}-H_n}}\to\infty$ as $k\to\infty$ (remember, $n$ is fixed). We can multiply that fraction by $2^{H_n}$, which is constant, to get a nicer expression. We can also add the constant term $2^{-H_1}+\ldots+2^{-H_n}$, to get, in the end, $\sum_{t\ge 1} 2^{-H_t}=\infty\ (*)$ (this is what we want to prove). Since $\sum_{t\ge 1}2^{-\ln t}=\sum_{t\ge 1}\frac 1{t^{\ln 2}}=\infty$, we can use Cesaro-Stolz to prove $(*)$. It looks rather nasty. Does it work?

Let $x_1,x_2,\ldots,x_n$ be arbitrary real numbers. Prove the inequality \[ \frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2 + x_2^2} + \cdots + \frac{x_n}{1 + x_1^2 + \cdots + x_n^2} < \sqrt{n}. \]

Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$, satisfying \[ f(xy)(f(x) - f(y)) = (x-y)f(x)f(y) \] for all $x,y$.

Click for solution Assume $f(1)=0$. Take $y=1$. We get $f^2(x)=0,\ \forall x$, so $f(x)=0,\ \forall x$. This is a solution, so we can take it out of the way: assume $f(1)\ne 0$. $y=1\Rightarrow f(x)[f(x)-f(1)]=(x-1)f(x)f(1)$. We either have $f(x)=0$ or $f(x)=f(1)x$, so for every $x$, $f(x)\in\{0,f(1)x\}$. In particular, $f(0)=0$. Assume $f(y)=0$. We get $f(x)f(xy)=0,\ \forall x$. This means that $f(a),f(b)\ne 0\Rightarrow f(\frac ab)\ne 0\ (*)$ ($\frac ab$ is defined because $f(b)\ne 0\Rightarrow b\ne 0$). Assume now that $x\ne y$ and $f(x),f(y)\ne 0$. We get $f(x)=f(1)x,\ f(y)=f(1)y$, and after replacing everything we get $f(xy)=f(1)xy\ne 0$, so $x\ne y,\ f(x),f(y)\ne 0\Rightarrow f(xy)\ne 0\ (**)$. Assume now $f(x)\ne 0$. From $(*)$ we get $f(\frac 1x)\ne 0$, and after applying $(*)$ again to $a=x,b=\frac 1x$ we get $f(x^2)\ne 0\ (***)$. We can now see that $(**),(***)$ combine to $f(x),f(y)\ne 0\Rightarrow f(xy)\ne 0\ (\#)$. Let $G=\{x\in\mathbb R|f(x)\ne 0\}$. $(*)$ and $(\#)$ simply say that $(G,\ \cdot)$ is a subgroup of $(\mathbb R^{*},\ \cdot)$. Conversely, let $G$ be a subgroup of the multiplicative group $\mathbb R^*$. Take $f(x)=\{\begin{array}{c}f(1)x,\ x\in G\\0,\ x\not \in G\end{array}$. It's easy to check the condition $f(xy)[f(x)-f(y)]=(x-y)f(x)f(y)$.

Find all positive integers $a_1, a_2, \ldots, a_n$ such that \[ \frac{99}{100} = \frac{a_0}{a_1} + \frac{a_1}{a_2} + \cdots + \frac{a_{n-1}}{a_n}, \] where $a_0 = 1$ and $(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k - 1)$ for $k = 1,2,\ldots,n-1$.

Prove that for all positive real numbers $a,b,c$, \[ \frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}} \geq 1. \]

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$, such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$, find the greatest value of $m$.

Click for solution I think it's $667^3$. $667^3$ can be achieved by taking $667$ $1$'s, followed by $667$ $2$'s, followed by $667$ $3$'s. Let's now prove that it's the maximum we can achieve. Break the sequence into maximal subsequences which are also arthimetic progressions of common difference $1$. Two such progressions don't intersect, so they don't interfere (we can't have $3$-element progressions with elements from two different such subsequences). Assume we have such a subsequence $a_{n_1},\ldots,a_{n_t}$. This contributes $t-2$ to $m$, so we can change the first $\lfloor\frac t3 \rfloor$ numbers into the same number (say $1$), then the next $\lfloor\frac t3\rfloor$ numbers into $2$, and the remeining numbers into $3$. This new sey contributes $\lfloor\frac t3 \rfloor^2(t-2\lfloor\frac t3 \rfloor)$ to $m$, and this is clearly $>t-2$. We do this for all subsequences of the form considered above, until we get, in the end, some $1$'s, some $2$'s, and some $3$'s. Furthermore, if we have $2$ followed by $1$ (or $3$ followed by $2$ or $1$), we can interchange these two and we increase $m$, so after performing all operations of this sort we get $a_i=1,\ \forall i\in\overline{1,a},\ a_i=2,\ \forall i\in\overline{a+1,a+b},\ a_i=3,\ \forall i\in\overline{a+b+1,a+b+c=2001}$. In this case $m=abc$, with $a+b+c=2001$, and after applying $AM-GM$ we find $m=abc\le \left(\frac{2001}3\right)^3=667^3$, Q.E.D.

Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$, define $S(a) = \sum_{i=1}^n c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$.

Define a $ k$-clique to be a set of $ k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

A set of three nonnegative integers $\{x,y,z\}$ with $x < y < z$ is called historic if $\{z-y,y-x\} = \{1776,2001\}$. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

Find all finite sequences $(x_0, x_1, \ldots,x_n)$ such that for every $j$, $0 \leq j \leq n$, $x_j$ equals the number of times $j$ appears in the sequence.

For a positive integer $n$ define a sequence of zeros and ones to be balanced if it contains $n$ zeros and $n$ ones. Two balanced sequences $a$ and $b$ are neighbors if you can move one of the $2n$ symbols of $a$ to another position to form $b$. For instance, when $n = 4$, the balanced sequences $01101001$ and $00110101$ are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set $S$ of at most $\frac{1}{n+1} \binom{2n}{n}$ balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in $S$.

A pile of $n$ pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column which contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a final configuration. For each $n$, show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration in terms of $n$. IMO ShortList 2001, combinatorics problem 7, alternative

Click for solution 1) First of all, we need to show that we do eventually have to stop. This is clear because each time we move a pebble goes to the right, and we can't go arbitrarily far to the right, because each pebble (except for those on the first column) has another pebble immediately to its left, so we would need infinitely many pebbles. This shows that there always is a final configuration. 2) Another thing we notice is that a final configuration consists of columns of decreasing length (from left to right). This is because before and after each move, this property is clearly conserved. Moreover, the difference between a column and its right neighbour is $0$ or $1$, because otherwise we would be able to continue moving the pebbles. 3) In a final configuration we can't have three consecutive columns of equal lengths. This is true because if we look at the last move performed on one of the three columns, then we see that no matter how we make that move, before we make it we need two consecutive columns s.t. the one on the left has fewer pebbles than the one on the right, and this is impossible. In fact, this shows that we never have three equal consecutive columns (not just in final configurations). 4) In a final configuration we can't have two different pairs of equal consecutive columns. Consider two such pairs $c_1,c_2$ and $c_1',c_2'$, s.t. $c_1'$ is to the right of $c_2$, which don't have any other such pairs between them. Since this is a final config, the columns between $c_2$ and $c_1'$ inclusive form a decreasing arithmetic progression with common difference $-1$. We can now retrace the steps until we get two pairs of equal columns which are adjacent and which differ in length by $1$, and this is clearly impossible (consider, for example, $3,3,2,2$; no matter how we try to obtain this, we can't avoid either two consecutive solumns s.t. the one on the left is shorter, or three equal consecutive columns, and we have examined these situations before). These conditions show that the final configuration is unique, because each $n$ has only one decomposition as a sum of different numbers except, maybe, for a pair, and this decomposition is obtained as follows: assume we have $T_{k-1}=\frac{(k-1)k}2<n\le \frac{k(k+1)}2=T_k$. Then we write $n$ as $1+2+\ldots+(k-1)+n-T_{k-1}$. These are also the lengths of the columns.

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.