Let $B$ be a point on a circle $S_1$, and let $A$ be a point distinct from $B$ on the tangent at $B$ to $S_1$. Let $C$ be a point not on $S_1$ such that the line segment $AC$ meets $S_1$ at two distinct points. Let $S_2$ be the circle touching $AC$ at $C$ and touching $S_1$ at a point $D$ on the opposite side of $AC$ from $B$. Prove that the circumcentre of triangle $BCD$ lies on the circumcircle of triangle $ABC$.

Click for solution I. for one, distinctly remember posting two or three of these on the forum, but what the heck! They're nice problems; we can solve them all over again. I remember giving an inversive proof, but I can't find it anymore, so here's another one: Let $M$ be the circumcenter of $BCD$. We have $\angle BMC=2\angle BDC$, and we want to show that $\angle BMC=\angle BAC$, so it's equivalent to showing that $\angle BAC=2\angle BDC$. Let $C'$ be the intersection of $DC$ with $S_1$. The tangent through $C'$ to $S_1$ is parallel to $AC$ because $C'$ is the image $C$ through the homothety centered at $D$ which turns $S_2$ into $S_1$. Now let $T$ be the intersection of the tangents to $S_1$ through $B,C'$. We now have $\angle BAC=\pi-\angle BTC'=2\angle TC'B=2\angle BDC'=2\angle BDC$, Q.E.D.

Let $ABC$ be a triangle for which there exists an interior point $F$ such that $\angle AFB=\angle BFC=\angle CFA$. Let the lines $BF$ and $CF$ meet the sides $AC$ and $AB$ at $D$ and $E$ respectively. Prove that \[ AB+AC\geq4DE. \]

Click for solution I saw this problem these days and I was pretty sure it was an ISL problem. Lets take the equilateral triangles $ ACP$ and $ ABQ$ on the exterior of the triangle $ ABC$. We have that $ \angle{APC} + \angle{AFC} = 180$, therefore the points $ A,P,F,C$ are concyclic. But $ \angle{AFP} = \angle{ACP} = 60 = \angle{AFD}$, so $ D \in (FP)$. Analoguosly we have that $ E \in (FQ)$. Now observe that $ \frac {FP}{FD} = 1 + \frac {DP}{FD} = 1 + \frac {[APC]}{[AFC]}\geq 4$, and the equality occurs when $ F$ is the midpoint of $ \widehat{AC}$. Therefore $ FD \leq \frac {1}{4}FP$, and $ FE \leq \frac {1}{4}FQ$. So, by taking it metrical, we have that: $ DE = \sqrt {FD^{2} + FE^{2} + FD \cdot FE}\leq \frac {1}{4}\cdot \sqrt {FP^{2} + FQ^{2} + FP \cdot FQ} = \frac {1}{4}PQ$ But $ PQ \leq AP + AQ = AB + AC$, and thus the problem is solved.

The circle $S$ has centre $O$, and $BC$ is a diameter of $S$. Let $A$ be a point of $S$ such that $\angle AOB<120{{}^\circ}$. Let $D$ be the midpoint of the arc $AB$ which does not contain $C$. The line through $O$ parallel to $DA$ meets the line $AC$ at $I$. The perpendicular bisector of $OA$ meets $S$ at $E$ and at $F$. Prove that $I$ is the incentre of the triangle $CEF.$

Click for solution Triangles $AOE,AOF$ are equilateral because $AE=OE=OA,\ AF=OF=OA$. The condition $\angle AOB<120^{\circ}\iff \angle AOC>60^{\circ}$ simply means that $F$ (assume $F$ is on the same side of $OA$ as $C$) lies on the arc $AC$ which doesn't contain $E$, so $CA$ is the internal bisector of $\angle ECF$ because $A$ is the midpoint of the arc $EF$ (without the condition, $AC$ would be the external bisector). This means that $J$ lies on the bisector of $\angle ECF$. On the other hand, we have $AD\|OJ$ and $OD\|AJ$ because they're both $\perp AB$, so $J$ is the reflection of $D$ in the midpoint of $OA$. This means $\angle EJF=\angle EDF=120^{\circ}$, and since $\angle ECF=\frac{\angle EOF}2=60^{\circ}$ and $J$ lies on the internal bisector of $\angle ECF$, it means that $J$ is the incenter (the only other position on $AC$ from which $EF$ is seen under an angle of $120^{\circ}$ is $A$, and it's clear that $J\ne A$).

Circles $S_1$ and $S_2$ intersect at points $P$ and $Q$. Distinct points $A_1$ and $B_1$ (not at $P$ or $Q$) are selected on $S_1$. The lines $A_1P$ and $B_1P$ meet $S_2$ again at $A_2$ and $B_2$ respectively, and the lines $A_1B_1$ and $A_2B_2$ meet at $C$. Prove that, as $A_1$ and $B_1$ vary, the circumcentres of triangles $A_1A_2C$ all lie on one fixed circle.

Click for solution A quick angle chase reveals that $CA_1QA_2$ is cyclic, meaning that we can forget about the $B_i$'s: we're looking for the locus of the circumcenter of $A_1A_2Q$. Since $\angle PA_iQ$ are constant angles, it means that the triangles $A_1A_2Q$ are all similar, and this means that the triangles $A_1QO$ are all similar, where $O$ is the circumcenter of $A_1A_2Q$. This means that the locus of $O$ is the image of $S_1$ through the spiral similarity of center $Q$ which turns $A_1$ into $O$. In other words, this locus is a circle, Q.E.D. Comment: it can be shown fairly easily now, by choosing particular positions of $A_1$, the the circle is, in fact, the circumcircle of $QO_1O_2$, where $O_i$ is the center of $S_i$.

For any set $S$ of five points in the plane, no three of which are collinear, let $M(S)$ and $m(S)$ denote the greatest and smallest areas, respectively, of triangles determined by three points from $S$. What is the minimum possible value of $M(S)/m(S)$ ?

Click for solution I think it's achieved for the regular pentagon, so it's $\phi=\frac{1+\sqrt 5}2$. First of all, let's notice that if it's not a convex pentagon, then we have a point inside a triangle, so that point is inside a triangle formed by the centroid and two vertices of the triangle, so the ratio would be at least $3>\phi$. This means that the pentagons which reach the minimal value are convex. Furthermore, it's easy to see that, since the pentagon is convex, the triangle with the minimal area is formed by three consecutive vertices, while the one with the largest area is formed by three vertices which are not consecutive. Assume our pentagon is $ABCDE$, and the triangle with minimal area is $BAE$. Since we can apply an affine transformation which maps $A,B,E$ to three consecutive vertices of a regular pentagon and this transformation preserves the ratios of areas, we may assume there is a regular pentagon $ABC'D'E$. Take $X$ s.t. $C'X\|BD',\ D'X\|EC'$. Since $S(C'AE)\le S(CAE),\ S(D'AB)\le S(DAB)$, and given the convexity of $ABCDE$, at least one of $C,D$ lies inside $C'XD'$ (just draw a picture to see why). Assume it's $D$. We can move $C,D$ along lines parallel to $BD$ s.t. the area of $BCD$ increases, and this time $C,D$ lie on the union of the two segments math=inline]$XC'$[/math, math=inline]$XD'$[/math. It's easy now to see that we can enlarge the area of $BDC$ even more by moving $C,D$ s.t. they reach positions $C',D'$, but this means that the initial area of $BCD$ was smaller that that of $BAE$, and this is a contradiction, so the minimal ratio is reached for regular pentagons. I know the argument is a bit murky, but it's not that hard to see why it works if you draw a picture.

Let $n\geq3$ be a positive integer. Let $C_1,C_2,C_3,\ldots,C_n$ be unit circles in the plane, with centres $O_1,O_2,O_3,\ldots,O_n$ respectively. If no line meets more than two of the circles, prove that \[ \sum\limits^{}_{1\leq i<j\leq n}{1\over O_iO_j}\leq{(n-1)\pi\over 4}. \]

The incircle $ \Omega$ of the acute-angled triangle $ ABC$ is tangent to its side $ BC$ at a point $ K$. Let $ AD$ be an altitude of triangle $ ABC$, and let $ M$ be the midpoint of the segment $ AD$. If $ N$ is the common point of the circle $ \Omega$ and the line $ KM$ (distinct from $ K$), then prove that the incircle $ \Omega$ and the circumcircle of triangle $ BCN$ are tangent to each other at the point $ N$.

Click for solution I don't like this solution, but I couldn't find a better one this late at night (or this early in the morning; it's 4:15 AM here ). Let $S=KA\cap \Omega$, and let $T$ be the antipode of $K$ on $\Omega$. Let $X,Y$ be the touch points between $\Omega$ and $CA,AB$ respectively. The line $AD$ is parallel to $KT$ and is cut into two equal parts by $KS,KN,KD$, so $(KT,KN;KS,KD)=-1$. This means that the quadrilateral $KTSN$ is harmonic, so the tangents to $\Omega$ through $K,S$ meet on $NT$. On the other hand, the tangents to $\Omega$ through the points $X,Y$ meet on $KS$, so $KXSY$ is also harmonic, meaning that the tangents to $\Omega$ through $K,S$ meet on $XY$. From these it follows that $BC,XY,TN$ are concurrent. If $P=XY\cap BC$, it's well-known that $(B,C;K,P)=-1$, and since $\angle KNP=\angle KNT=\frac{\pi}2$, it means that $N$ lies on an Apollonius circle, so $NK$ is the bisector of $\angle BNC$. From here the conclusion follows, because if $B'=NB\cap \Omega,\ C'=NC\cap \Omega$, we get $B'C'\|BC$, so there's a homothety of center $N$ which maps $\Omega$ to the circumcircle of $BNC$.

Let two circles $S_{1}$ and $S_{2}$ meet at the points $A$ and $B$. A line through $A$ meets $S_{1}$ again at $C$ and $S_{2}$ again at $D$. Let $M$, $N$, $K$ be three points on the line segments $CD$, $BC$, $BD$ respectively, with $MN$ parallel to $BD$ and $MK$ parallel to $BC$. Let $E$ and $F$ be points on those arcs $BC$ of $S_{1}$ and $BD$ of $S_{2}$ respectively that do not contain $A$. Given that $EN$ is perpendicular to $BC$ and $FK$ is perpendicular to $BD$ prove that $\angle EMF=90^{\circ}$.

Click for solution Let $G=NE\cap S_1,\ X=NE\cap MK,\ Y=KF\cap MN$. The quadrilateral $XNKY$ is ccylic because $\angle MXN=\angle MYK=\frac \pi 2$, so $\angle MNE=\angle FKM\ (*)$. If we show that the triangles $MNE,FKM$ are similar, then we would have $\angle NMK=\pi-\angle YMK=\frac \pi 2+\angle MKY=\frac \pi 2+\angle NME+\angle KMF$, which is exactly what we want. We thus need to show that $\frac{MN}{NE}=\frac{FK}{KM}\ (**)$, which, together with $(*)$, proves the similarity of $MNE,FKM$. $(**)\iff NE\cdot KF=BN\cdot BK\ (***)$, because $BN=MK,\ BK=MN$. Since all triangles $BCD$ are similar, no matter which line $CD$ we choose, there is a spiral similarity $\mathcal S$ cantered at $B$ which maps $D\to C$. $\mathcal S$ maps $BD\to BC$, so if $K'=\mathcal S(K)$, then $K'\in BC$ and $\frac{BK'}{K'C}=\frac{BK}{KC}=\frac{CN}{NB}$, meaning that $K'$ is the symmetric of $N$ wrt the perpendicular bisector of $BC$. We then have $NE\cdot NG=BN\cdot NC=BN\cdot BK'$, and this proves $(***)$ because $\frac{K'F'}{KF}=\frac{BK'}{BK}$ and $K'F'=NG$, so $\frac{NG}{KF}=\frac{BK'}{BK}$.

What is the smallest positive integer $t$ such that there exist integers $x_1,x_2,\ldots,x_t$ with \[x^3_1+x^3_2+\,\ldots\,+x^3_t=2002^{2002}\,?\]

Let $n\geq2$ be a positive integer, with divisors $1=d_1<d_2<\,\ldots<d_k=n$. Prove that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is always less than $n^2$, and determine when it is a divisor of $n^2$.

Click for solution $d_k = {n\over d_1}$ $d_{k-1} = {n\over d_2}$ $d_1 = {n\over d_k}$ So we can write it like this: $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$ The Maximum that can be is: ${{n^2}\over 1*2}+{{n^2}\over 2*3}+\,\ldots\,+{{n^2}\over (n-1)n}$ We can see that the sum starting with the form: ${m\over {m+1}}{n^2}$ We check what happens if we add the next term: ${m\over {m+1}}{n^2} + {1\over {(m+1)(m+2)}}{n^2} = {{(m+1)^2}\over {(m+1)(m+2)}}{n^2} = {{m+1}\over {m+2}}{n^2}$ From here is easy to define that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$ $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$ is a divisor of ${n^2}$ when $n$ is a prime number: $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = n$ if $n$ isn't a prime we have at least 3 divisors of $n$ We proved that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$ So if it's a divisor of ${n^2}$ the maximum that can be: ${{n^2}\over d_2}$ $d_1 = 1$ $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$=${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = {{n^2}\over d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} > {{n^2}\over d_2}$ We see from here that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is a divisor of ${n^2}$ only if $n$ is a prime!

Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors.

Click for solution Lemma 1: If $(a,b)=1$ and $a,b$ are odd, then $(2^a+1,2^b+1)=3$. Proof: Let $d=(2^a+1,2^b+1)$. $3|d$ and $d|(2^{2a}-1,2^{2b}-1)=2^{(2a,2b)}-1=2^2-1=3$, so $d=3$. $\blacksquare$ Lemma 2: If $3\not |a$ ($a$ is odd), then $9\not |2^a+1$. Proof: If $a=3k+1$ we have $2^a+1=2(2^{3k}+1)-1=9t-1$, and if $a=3k+2$ we have $2^a+1=4(2^{3k}+1)-3$. $\blacksquare$ Let $N=p_1\ldots p_n,\ N'=\frac N{p_n}$. For $n=1$, the result is easy to prove: $2^p+1$ has the divisors $1, 3, \frac{2^p+1}3, 2^p+1$. We have $3\ne \frac{2^p+1}3$ because $p>3$. We can now use induction. Assume we have shown it for $n-1$. This means that $2^{N'}+1$ has at least $4^{n-1}$ divisors. We have $2^{N'}+1|2^N+1,\ \frac{2^{p_n}+1}3|2^N+1$, and we can apply the lemmata for $a=p_n, b=N'$ to get $\frac{2^{p_n}+1}3\big|\frac{2^N+1}{2^{N'}+1}$. On the other hand, we clearly have $\left(\frac{2^{p_n}+1}3\right)^2<\frac{2^N+1}{2^{N'}+1}$, which means that $\frac{2^N+1}{2^{N'}+1}$ has at least four divisors $1=d_1,d_2,d_3,d_4$. For each $d|2^{N'}+1$, each of $d_id$ is a divisor of $2^N+1$, and all $d_id$ are different because $(d_i,d)=1$, hence the result: $2^N+1$ has at least $4\cdot 4^{n-1}=4^n$ divisors.

Is there a positive integer $m$ such that the equation \[ {1\over a}+{1\over b}+{1\over c}+{1\over abc}={m\over a+b+c} \] has infinitely many solutions in positive integers $a,b,c$?

Click for solution We take $m=12$. What follows is a standard argument: given a solution $(a,b,c)$ with $a\le b\le c$, we show that we can find a solution $(b,c,a')$ with $b\le c\le a'$. Start with $(a_0,b_0,c_0)=(1,1,1)$ (this is a solution of the equation). Let $P(n)$ be the property $a_n|b_nc_n+1, b_n|c_n+a_n, c_n|a_nb_n+1$ and let $Q(n)$ be the property $a_n\le b_n\le c_n$. Furthermore, let $R(n)$ be $(a_n,b_n)=(b_n,c_n)=(c_n,a_n)=1$. It’s clear that $P(0),Q(0),R(0)$ hold. Let’s now take $(a_1,b_1,c_1)=(b_0,c_0,\frac{b_0c_0+1}{a_0})$. $Q(1)$ holds because we already know $b_0\le c_0$ from $Q(0)$, and $b_1\le c_1$ because otherwise we would have $c_0a_0>b_0c_0+1$, which is false. $R(1)$ is equally easy to check. Let’s now prove $P(1)$: $c_1|a_1b_1+1$ because of the definition of $c_1$, $a_1|b_1c_1+1\iff a_0b_0|b_0c_0^2+c_0+a_0$, which is true because $a_0|b_0c_0+1,b_0|c_0+a_0,(a_0,b_0)=1$, and $b_1|c_1+a_1\iff c_0a_0|a_0b_0+b_0c_0+1$, which is true because $a_0|b_0c_0+1,c_0|a_0b_0+1,(c_0,a_0)=1$. We have thus shown that $P(1),Q(1),R(1)$ hold, and, in particular, we can define $(a_2,b_2,c_2)=(b_1,c_1,\frac{b_1c_1+1}{a_1})$, and so on. We use the exact same arguments to prove that $P(n),Q(n),R(n)$ are true, so we can define $(a_{n+1},b_{n+1},c_{n+1})=(b_n,c_n,\frac{b_nc_n+1}{a_n})$. On the other hand, a simple computation reveals that if $(a_n,b_n,c_n)$ is a solution, then so is $(a_{n+1},b_{n+1},c_{n+1})$, so we have found infinitely many solutions (that’s because the inequalities in $Q(n)$ become strict for $n\ge 2$, due to $R(n)$).

Let $m,n\geq2$ be positive integers, and let $a_1,a_2,\ldots ,a_n$ be integers, none of which is a multiple of $m^{n-1}$. Show that there exist integers $e_1,e_2,\ldots,e_n$, not all zero, with $\left|{\,e}_i\,\right|<m$ for all $i$, such that $e_1a_1+e_2a_2+\,\ldots\,+e_na_n$ is a multiple of $m^n$.

Find all pairs of positive integers $m,n\geq3$ for which there exist infinitely many positive integers $a$ such that \[ \frac{a^m+a-1}{a^n+a^2-1} \] is itself an integer. Laurentiu Panaitopol, Romania

Find all functions $f$ from the reals to the reals such that \[f\left(f(x)+y\right)=2x+f\left(f(y)-x\right)\] for all real $x,y$.

Click for solution Yay! My first (first) IMOSL solution! First we let $f(0) = \alpha$. $f(f(x)+y) = 2x + f(f(y)-x)$ $(1)$ Plugging in $x=0$ into (1): $f(y+\alpha) = f(f(y))$ $(2)$ Plugging in $x=f(y)$ into (1): $f(f(f(y))+y) = 2f(y) + f(f(y)-f(y)) \Rightarrow f(2y+\alpha) = 2f(y) + \alpha$ $(3)$ Now plugging in $y=-\alpha$ into (3): $f(-\alpha) = 2f(-\alpha) + \alpha \Rightarrow f(-\alpha) = -\alpha$ Plugging in $y=-\alpha$ into (2): $\alpha = f(f(-\alpha)) \Rightarrow \alpha = -\alpha \Rightarrow \alpha = 0$ So (2) can be rewritten as: $f(f(x)) = x$ $(4)$ Plugging in $y=0$ into (1): $f(f(x)) = 2x + f(-x) \Rightarrow f(-x) = -x$ Plugging in $x=-x$ for the last equation gives $f(x)=x$ for all $x$. It is easy to see that this function indeed satisfies the initial conditions given in the problem.

Let $a_1,a_2,\ldots$ be an infinite sequence of real numbers, for which there exists a real number $c$ with $0\leq a_i\leq c$ for all $i$, such that \[\left\lvert a_i-a_j \right\rvert\geq \frac{1}{i+j} \quad \text{for all }i,\ j \text{ with } i \neq j. \] Prove that $c\geq1$.

Click for solution Let $k$ be an arbitrary natural number. Let $\{m_1,m_2,\ldots{},m_k\}$ be a permutation of $\{1,2,\ldots{},k\}$ such that $a_{m_1} < a_{m_2} < \cdots{} < a_{m_k}$. Note that we can never have equality since $|a_{m_i} - a_{m_{i+1}}| \ge \frac{1}{m_i+m_{i+1}}$. Let $\overline{a_ia_j} = |a_i-a_j|$. By looking at the $a_i$ as a set of intervals on $[0,c]$, it makes sense that $\overline{a_{m_1}a_{m_k}} = \sum \limits_{i=1}^{k-1} \overline{a_{m_i}a_{m_{i+1}}}$. $\overline{a_{m_i}a_{m_k}} \ge \sum\limits_{i=1}^{k-1} \frac{1}{m_i+m_{i+1}}$. By the Arithmetic Mean Harmonic Mean Inequality, $\frac{(a_1+a_2) + (a_2+a_3) + \ldots{} + (m_{k-1}+m_k)}{k-1} \ge \frac{k-1}{\frac{1}{m_1+m_2} + \ldots{} + \frac{1}{m_{k-1}+m_k}}$. $(m_1+2m_2+\ldots{}+2m_{k-1}+2m_k)\left(\frac{1}{m_1+m_2} + \ldots{} + \frac{1}{m_{k-1}+m_k}\right) \ge (k-1)^2$. $(\overline{a_{m_1}a_{m_k}})(m_1+2m_2+\ldots{}+2m_{k-1}+m_k) \ge (k-1)^2$. The right term of the left-hand side is less than $2(m_1+m_2+\ldots{}+m_k)$: $2\overline{a_{m_1}a_{m_k}}(m_1+m_2+\ldots{}+m_k) > (k-1)^2$ Since $\{m_1,m_2,\ldots{},m_k\}$ is a permutation of $\{1,2,\ldots{},k\}$, $2\overline{a_{m_1}a_{m_k}} \cdot \frac{k(k+1)}{2} > (k-1)^2$. $\overline{a_{m_1}a_{m_k}} > \frac{(k-1)^2}{k(k+1)} = \frac{k-1}{k} \cdot \frac{k-1}{k+1} > \left(\frac{k-1}{k+1}\right)^2 = \left(1-\frac{2}{k+1}\right)^2$. If $\overline{a_{m_1}a_{m_k}} < 1$ for all $k \in \mathbb N$, we can easily find a $k$ such that $\left(1-\frac{2}{k+1}\right)^2 > \overline{a_{m_1}a_{m_k}}$, causing a contradiction. So $\overline{a_{m_1}a_{m_k}} \ge 1$ for some integers $m_1$, $m_k$. $|a_{m_1}-a_{m_k}| \ge 1$. Since both terms are positive, it is clear that at least one of them is greater than or equal to $1$. So $c \ge 1$, as desired.

Let $P$ be a cubic polynomial given by $P(x)=ax^3+bx^2+cx+d$, where $a,b,c,d$ are integers and $a\ne0$. Suppose that $xP(x)=yP(y)$ for infinitely many pairs $x,y$ of integers with $x\ne y$. Prove that the equation $P(x)=0$ has an integer root.

Find all functions $f$ from the reals to the reals such that \[ \left(f(x)+f(z)\right)\left(f(y)+f(t)\right)=f(xy-zt)+f(xt+yz) \] for all real $x,y,z,t$.

Let $n$ be a positive integer that is not a perfect cube. Define real numbers $a,b,c$ by \[a=\root3\of n\kern1.5pt,\qquad b={1\over a-[a]}\kern1pt,\qquad c={1\over b-[b]}\kern1.5pt,\] where $[x]$ denotes the integer part of $x$. Prove that there are infinitely many such integers $n$ with the property that there exist integers $r,s,t$, not all zero, such that $ra+sb+tc=0$.

Let $A$ be a non-empty set of positive integers. Suppose that there are positive integers $b_1,\ldots b_n$ and $c_1,\ldots,c_n$ such that - for each $i$ the set $b_iA+c_i=\left\{b_ia+c_i\colon a\in A\right\}$ is a subset of $A$, and - the sets $b_iA+c_i$ and $b_jA+c_j$ are disjoint whenever $i\ne j$ Prove that \[{1\over b_1}+\,\ldots\,+{1\over b_n}\leq1.\]

Let $n$ be a positive integer. Each point $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers with $x+y<n$, is coloured red or blue, subject to the following condition: if a point $(x,y)$ is red, then so are all points $(x',y')$ with $x'\leq x$ and $y'\leq y$. Let $A$ be the number of ways to choose $n$ blue points with distinct $x$-coordinates, and let $B$ be the number of ways to choose $n$ blue points with distinct $y$-coordinates. Prove that $A=B$.

Click for solution This was actually in the contest, wasn't it? It's kind of hard to put into words. The red points consists of a series of $n$ columns of decreasing height (I mean decreasing starting from left to right, and I don't mean strictly decreasing). The blue points consist of the completion of the red columns up to the border of the triangle having vertices $(0,0),(0,n-1),(n-1,0)$. At the same time, the blue and red sets can also be regarded as rows instead of columns. $A$ is simply the product of the lengths of all blue columns, while $B$ is the product of the lengths of all blue rows. If we show that the same numbers, with the same multiplicities, appear in the collections of a) blue column lengths and b) blue row lengths, then we are clearly done. Call this assertion $(*)$. The blue set can be regarded as the union of some maximal right triangles with the legs parallel to the axes of the plane (maximal in the sense that they aren't part of any other similar right triangles). The triangles are obtained as follows: from a point on the diagonal $x+y=n-1$ go down as far as you can without taking any red points. Now go to the right until you meet the diagonal again. The maximal triangles of this set are the ones we're looking for. We can now prove the assertion $(*)$ by induction on $n$. If there are points on the diagonal $x+y=n-1$ which are red, then it's easy to see that the number of blue columns of length $0$ is equal to the number of blue rows of length $0$, and we can look at the picture as the union of some smaller pictures (for smaller $n$'s), by breaking the diagonal where it has red points. We use the induction hypothesis on these smaller pictures. On the other hand, if no points on $x+y=n-1$ are red, then we can look at the points strictly below the diagonal $x+y=n-1$, and use the induction hypothesis on these. After we append the diagonal $x+y=n-1$ all lengths (of blue columns and rows) increase by $1$, so we have shown what we wanted: the number of blue columns of length $t$ is the same as the number of blue rows of length $t$ for all $0\le t\le n$. Watch out: I might have reversed "red" and "blue" in some places.

For $n$ an odd positive integer, the unit squares of an $n\times n$ chessboard are coloured alternately black and white, with the four corners coloured black. A it tromino is an $L$-shape formed by three connected unit squares. For which values of $n$ is it possible to cover all the black squares with non-overlapping trominos? When it is possible, what is the minimum number of trominos needed?

Let $n$ be a positive integer. A sequence of $n$ positive integers (not necessarily distinct) is called full if it satisfies the following condition: for each positive integer $k\geq2$, if the number $k$ appears in the sequence then so does the number $k-1$, and moreover the first occurrence of $k-1$ comes before the last occurrence of $k$. For each $n$, how many full sequences are there ?

Let $T$ be the set of ordered triples $(x,y,z)$, where $x,y,z$ are integers with $0\leq x,y,z\leq9$. Players $A$ and $B$ play the following guessing game. Player $A$ chooses a triple $(x,y,z)$ in $T$, and Player $B$ has to discover $A$'s triple in as few moves as possible. A move consists of the following: $B$ gives $A$ a triple $(a,b,c)$ in $T$, and $A$ replies by giving $B$ the number $\left|x+y-a-b\right |+\left|y+z-b-c\right|+\left|z+x-c-a\right|$. Find the minimum number of moves that $B$ needs to be sure of determining $A$'s triple.

Let $r\geq2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$, no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$.

Click for solution Just an idea. Let $A_{1},A_{2},...,A_{n} \in F$. There is $X \in F$ which is not a subset of $\bigcup_{i=1}^{n}{A_{i}}$ (since $F$ is infinite), so $X'=X-\bigcup_{i=1}^{n}{A_{i}}$ has at most $r-1$ elements and also has noneempty intersection with all $A_{i}$. So, I've proved that for all finite subfamilies $F' \subset F$, there is a set with $r-1$ elements which meets all elements in $F'$. Can you see a nice way to finish it from this point? I think I found one, but it's quite boring, so I won't post it now.

Let $n$ be an even positive integer. Show that there is a permutation $\left(x_{1},x_{2},\ldots,x_{n}\right)$ of $\left(1,\,2,\,\ldots,n\right)$ such that for every $i\in\left\{1,\ 2,\ ...,\ n\right\}$, the number $x_{i+1}$ is one of the numbers $2x_{i}$, $2x_{i}-1$, $2x_{i}-n$, $2x_{i}-n-1$. Hereby, we use the cyclic subscript convention, so that $x_{n+1}$ means $x_{1}$.

Click for solution This discussion might give some insight. Let's work in $\mathbb Z_n$, for simplicity. In this setting, we have $x_{i+1}\in\{2x_i,2x_i-1\}$. A mere adaptation of the solution posted there by alekk: construct a graph with $k$ vertices labeled $0,2,\ldots,2(k-1)=n-2$. We draw a directed edge from $2a$ to $2b$ iff $2b\equiv 2(2a-1)\pmod n$ or $2b\equiv 4a\pmod n$ (we allow loops, i.e. edges like $0\to 0$). The edge represents the residue $2a-1$ or $2a$, according to the situation. Each residue $\pmod n$ is represented by exactly one edge, so the problem is reduced to proving that the graph we have described is Eulerian, which is clear because each vertex has $2$ outgoing edges and $2$ incoming edges.

Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?