Let $ABCD$ be a cyclic quadrilateral. Let $P$, $Q$, $R$ be the feet of the perpendiculars from $D$ to the lines $BC$, $CA$, $AB$, respectively. Show that $PQ=QR$ if and only if the bisectors of $\angle ABC$ and $\angle ADC$ are concurrent with $AC$.

Click for solution in two cyclic quadrilatrals APRD & DRCQ ,AD & CD are diameters respectively and we have: RQ/sin(<RCQ)=CD/2 or RQ/sin(<BCA)=CD/2 PR/sin(<PAR)=AD/2 or PR/sin(<BAC)=AD/2 By dividing: CD/AD= sin(<BAC)/sin(<BCA)=BC/AB Since CD/AD=BC/AB thus bisectors of <CBA and <ADC intersect AC in the same poin. S.Ebadollahi

Three distinct points $A$, $B$, and $C$ are fixed on a line in this order. Let $\Gamma$ be a circle passing through $A$ and $C$ whose center does not lie on the line $AC$. Denote by $P$ the intersection of the tangents to $\Gamma$ at $A$ and $C$. Suppose $\Gamma$ meets the segment $PB$ at $Q$. Prove that the intersection of the bisector of $\angle AQC$ and the line $AC$ does not depend on the choice of $\Gamma$.

Click for solution It's indeed simple: In triangle $AQC$ $QB$ is the symmedian, so $\frac{BA}{BC}=\frac{QA^2}{QC^2}$ and it's fixed, so $\frac{QA}{QC}$ must also be fixed, and we're done.

Let $ABC$ be a triangle and let $P$ be a point in its interior. Denote by $D$, $E$, $F$ the feet of the perpendiculars from $P$ to the lines $BC$, $CA$, $AB$, respectively. Suppose that \[AP^2 + PD^2 = BP^2 + PE^2 = CP^2 + PF^2.\]Denote by $I_A$, $I_B$, $I_C$ the excenters of the triangle $ABC$. Prove that $P$ is the circumcenter of the triangle $I_AI_BI_C$. Proposed by C.R. Pranesachar, India

Click for solution This is also from the ISL. We have $PA^2+PD^2=PD^2+PE^2+EA^2=PB^2+PE^2=PD^2+PE^2+BD^2$ $\Rightarrow AE=BD$. In the same way we show that $CE=BF,\ AF=CD$, so we can see that $D, E, F$ are the projections of $I_a,I_b,I_c$ on $BC,CA,AB$ respectively. The conclusion follows.

Let $\Gamma_1$, $\Gamma_2$, $\Gamma_3$, $\Gamma_4$ be distinct circles such that $\Gamma_1$, $\Gamma_3$ are externally tangent at $P$, and $\Gamma_2$, $\Gamma_4$ are externally tangent at the same point $P$. Suppose that $\Gamma_1$ and $\Gamma_2$; $\Gamma_2$ and $\Gamma_3$; $\Gamma_3$ and $\Gamma_4$; $\Gamma_4$ and $\Gamma_1$ meet at $A$, $B$, $C$, $D$, respectively, and that all these points are different from $P$. Prove that \[ \frac{AB\cdot BC}{AD\cdot DC}=\frac{PB^2}{PD^2}. \]

Click for solution vinoth_90_2004 wrote: Let $ A_1$, $ A_2$, $ A_3$ and $ A_4$ be four circles such that the circles $ A_1$ and $ A_3$ are tangent at a point $ P$, and the circles $ A_2$ and $ A_4$ are also tangent at the same point $ P$. Suppose that the circles $ A_1$ and $ A_2$ meet at a point $ T_1$, the circles $ A_2$ and $ A_3$ meet at a point $ T_2$, the circles $ A_3$ and $ A_4$ meet at a point $ T_3$, and the circles $ A_4$ and $ A_1$ meet at a point $ T_4$, such that all these four points $ T_1$, $ T_2$, $ T_3$, $ T_4$ are distinct from $ P$. Prove: $ \frac {\overline{T_1T_2}\cdot\overline{T_2T_3}}{\overline{T_1T_4}\cdot\overline{T_3T_4}} = \frac {\overline{PT_2}^2}{\overline{PT_4}^2}$ (where $ \overline{ab}$, of course, means the distance between points $ a$ and $ b$). Good old inversion.. . Consider the inversion of pole $ P$ and any power we want and it should yield a pretty nice and neat solution. Let $ F'$ be the image the figure $ F$ by the inversion (no matter what $ F$ is: circle, line, point etc.). We have $ \frac {T_{1}T_{2}}{T_{1}'T_{2}'} = \frac {PT_{2}}{PT_{1}'}$ and the analogous relations. From all of that we find $ \frac {T_{1}T_{2}\cdot T_{3}T_{2}}{T_{1}T_{4}\cdot T_{3}T_{4}} = \frac {T_{1}'T_{2}'\cdot T_{3}'T_{2}'}{T_{1}'T_{4}'\cdot T_{3}'T_{4}'}\cdot \frac {PT_{2}^{2}}{PT_{4}^{2}} = \frac {PT_{2}^{2}}{PT_{4}^{2}}$ because $ A_{1}'\parallel A_{3}',\ A_{2}'\parallel A_{4}'$, so $ T_{1}'T_{2}'T_{3}'T_{4}'$ is a parallelogram, so $ T_{1}'T_{2}' = T_{3}'T_{4}',\ T_{3}'T_{2}' = T_{1}'T_{4}'$.

Let $ABC$ be an isosceles triangle with $AC=BC$, whose incentre is $I$. Let $P$ be a point on the circumcircle of the triangle $AIB$ lying inside the triangle $ABC$. The lines through $P$ parallel to $CA$ and $CB$ meet $AB$ at $D$ and $E$, respectively. The line through $P$ parallel to $AB$ meets $CA$ and $CB$ at $F$ and $G$, respectively. Prove that the lines $DF$ and $EG$ intersect on the circumcircle of the triangle $ABC$. Proposed by Hojoo Lee

Each pair of opposite sides of a convex hexagon has the following property: the distance between their midpoints is equal to $\dfrac{\sqrt{3}}{2}$ times the sum of their lengths. Prove that all the angles of the hexagon are equal.

Click for solution Let a1,..,a6 by radius-vectors of hexagon vertices. We have abs((a1+a2)-(a4+a5))/2=sqrt(3/4)*(abs(a1-a2)+abs(a4-a5))>= sqrt(3/4)*abs(a1+a5-a2-a4). Take the square, ans sum up three such inequalities. Then simplify. We get 0>=(a1+a3+a5-a2-a4-a6)^2. So, a1+a3+a5=a2+a4+a6 and above inequalities were equalities, so opposite sides are parallel. From a1+a3+a5=a2+a4+a6 we have (projecting to the perpendicular to a1a2) that a6 and a3 are equidistant from the line a1a2. Then consider the triangle formed by continuations of sides a1a2, a3a4, a5a6. The hexagon is gotten from the triangle by cutting small similar to big and equal to each other triangles near vertives. We get for this triangle, that each of its medians equals sqrt(3/4)*respective side. The rest is easy (one of the ways is the formula for the length of the median).

Let $ABC$ be a triangle with semiperimeter $s$ and inradius $r$. The semicircles with diameters $BC$, $CA$, $AB$ are drawn on the outside of the triangle $ABC$. The circle tangent to all of these three semicircles has radius $t$. Prove that \[\frac{s}{2}<t\le\frac{s}{2}+\left(1-\frac{\sqrt{3}}{2}\right)r. \] Alternative formulation. In a triangle $ABC$, construct circles with diameters $BC$, $CA$, and $AB$, respectively. Construct a circle $w$ externally tangent to these three circles. Let the radius of this circle $w$ be $t$. Prove: $\frac{s}{2}<t\le\frac{s}{2}+\frac12\left(2-\sqrt3\right)r$, where $r$ is the inradius and $s$ is the semiperimeter of triangle $ABC$. Proposed by Dirk Laurie, South Africa

Let $m$ be a fixed integer greater than $1$. The sequence $x_0$, $x_1$, $x_2$, $\ldots$ is defined as follows: \[x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}&\text{if }i\geq m.\end{cases}\]Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ . Proposed by Marcin Kuczma, Poland

Click for solution consider the sequence mod 2004. it is equivalant to the following recurrence: x_0=1, x_1=2^1, x_2=2^2 ... x_2003=2^2003, x_n=x_n-1 ... + x_n-2004. so the recurrence is periodic. so the terms {1, 1, 2^1 ... 2^2003} occur again in that order somewhere on in the sequence. we can see that the 2004 terms before that are 1, followed by 2003 '0's. so we can have 2003 consecutive terms all divisible by 2004. We cannot have 2004 such terms, because if then all ensuing terms are divisible by 2004 - which then contradicts the periodicity of the recurrence mod 2004. And we are done.

Each positive integer $a$ undergoes the following procedure in order to obtain the number $d = d\left(a\right)$: (i) move the last digit of $a$ to the first position to obtain the numb er $b$; (ii) square $b$ to obtain the number $c$; (iii) move the first digit of $c$ to the end to obtain the number $d$. (All the numbers in the problem are considered to be represented in base $10$.) For example, for $a=2003$, we get $b=3200$, $c=10240000$, and $d = 02400001 = 2400001 = d(2003)$.) Find all numbers $a$ for which $d\left( a\right) =a^2$. Proposed by Zoran Sunic, USA

Determine all pairs of positive integers $(a,b)$ such that \[ \dfrac{a^2}{2ab^2-b^3+1} \] is a positive integer.

Click for solution First note that we must have 1=< 2ab^2-b^3+1=b^2(2a-b)+1 and so, 1<=b<=2a. Now, we'll prove that the pairs that solve this problem are (i) (a,b)=(n,1), (ii) (a,b)=(n,2n), and (iii) (a,b)=(8n^4-n,2n) where n is a positive Indeed, if b=1, we get the pairs in (i), while if b=2a we get the pairs in (ii). Now assume that 1<b<2a and set r=a^2/( 2ab^2-b^3+1) Then the quadratic equation (*) x^2-2xrb^2+r(b^3-1)=0 has two solution that are positive integers, since one of them is a and their product is r(b^3-1)>0. Evaluating the discriminant D we have D=4(r^2b^4-rb^3+r). Thus r^2b^4-rb^3+r=m^2 for some natural number and the above equation has solution rb^2+m and rb^2-m. Now note that m^2 = r^2b^4-rb^3+r > r^2b^4-2rb^3+b^2=(rb^2-b)^2, with rb^2-b>0. Hence, b>rb^2-m. However, since a^2> b^2(2a-b>=b^2, we have a>b. Therefore, a=rb^2+m > b and the other (also positve) root, say c, is c=rb^2-m < b. Furthermore, if 2c>b, then we have r=c^2/(b^2(2c-b)+1 <= c^2/b^2 <1, a contradiction. Thus b=2c and r=c^2. Since ac=r(b^3-1), we get a=c(b^3-1)=8c^4-c. It is easy to verify that if c>=1, then the integers b=2c and a=c(b^3-1) solve the problem, since a^2/(2ab^2-b^3+1) = c^2(b^3-1)^2 / [(b^3-1)(2cb^2-1)]=c^2. The proof is complete.

Let $ b$ be an integer greater than $ 5$. For each positive integer $ n$, consider the number \[ x_n = \underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5, \] written in base $ b$. Prove that the following condition holds if and only if $ b = 10$: there exists a positive integer $ M$ such that for any integer $ n$ greater than $ M$, the number $ x_n$ is a perfect square. Proposed by Laurentiu Panaitopol, Romania

Click for solution I think I have a solution. Suppose b<>10. Also b<>2 By an easy observation, the problem reduces to (2b^n+b)^2+(b-2)(b-10)=(b-1)a_n^2 If b-1 is perfect square, then so is (2b^n+b)^2+(b-2)(b-10) so (b-2)(b-10)=0 which gives b=10. So b-1 is not perfect square Hence 2b^n+b, a_n are solutions to a generalised Pell equation. Let 2b^n+b=u_k, a_n=v_k,2b^(n+1)+b=u_l,a_(n+1)=v_l (where u_i,v_i are solutions to Pell's equation). It's well-known that u_l=pu_k+qv_k, for some p,q dependent of l-k. Since u_(k+1)/u_k tends to a constant, l-k and p,q will stabilise. Hence we get 2b^(n+1)+b=p(2b^n+b)+q(a_n) for FIXED p,q. Since a_n/(2b^n+b) tends to 1/sqrt(b-1), divinding by 2b^n+b and passing to limit we get b=p+q/sqrt(b-1) which is possible only if b-1 is perfect square. But we have already solved this case

An integer $n$ is said to be good if $|n|$ is not the square of an integer. Determine all integers $m$ with the following property: $m$ can be represented, in infinitely many ways, as a sum of three distinct good integers whose product is the square of an odd integer. Proposed by Hojoo Lee, Korea

Click for solution Excuse me. My previous solution is incorrect, because n<>4(n+6k² )-3(n+6k²)-3k². New solution. Consider following representations: (1) n=2(n+2k²)-(n+2k²)-2k² (2) n=4(n+3k²)-3(n+3k²)-3k² Let k be sufficiently large integer. It is clear 2k² and 3k² are good numbers. a) n=4l+1 then we use (1) where k is odd ==> (n+2k²)=3 (mod 4) and 2(n+2k²)=2 (mod 4). So addends are good numbers. b) n=4l+2 then we use (2) where k is even ==> (n+3k²)=2 (mod 4) and 3(n+3k²)=2 (mod 4). c) n=4l+3 then we use (1) where k is even ==> (n+2k²)=3 (mod 4) and 2(n+2k²)=2 (mod 4) d) n=4^rt then we apply 1), 2) or 3) for t and multiply addends by 4^r.

Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$.

Click for solution For p=2 take n=5. Let now p be odd. We have p^p-1=(p-1)(1+p+..+p^{p-1}}. The second bracket is odd and is not equal 1 modulo p^2. Then there exists its prime divisor q, which is odd and not of form k*p^2+1. Lets prove that q satisfies condition. If n^p=p (mod q), then (n^p)^p=p^p=1 (mod q), so n^{p^2}=1 (mod q). Since n^{q-1}=1 (mod q), we have n^gcd(q-1,p^2)=1 (mod q). But q-1 is not divisible by q^2, then gcd(q-1,p^2) is p or 1. so, n^p=1 (mod q) -- a contradiction, unless p-1 is divisible by q. But the 1+p+..+p^{p-1}=p (mod p-1), so coprime with p-1.

The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\]Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$. commentHi guys , Here is a nice problem: Let be given a sequence $a_n$ such that $a_0=2$ and $a_{n+1}=2a_n^2-1$ . Show that if $p$ is an odd prime such that $p|a_n$ then we have $p^2\equiv 1\pmod{2^{n+3}}$ Here are some futher question proposed by me :Prove or disprove that : 1) $gcd(n,a_n)=1$ 2) for every odd prime number $p$ we have $a_m\equiv \pm 1\pmod{p}$ where $m=\frac{p^2-1}{2^k}$ where $k=1$ or $2$ Thanks kiu si u Edited by Orl.

Click for solution Let $ T_n $ be the Chebychev polynomial of degree $ n $ which is defined for $ x $ in [-1,1] , by $T_n(x)=\cos\left(n\cdot \arccos{x}\right) $. In this case $ T_2(y)=2y^2-1 . $ Observe that \[ T_n\left(T_m(y)\right)=T_{nm}(y)=T_{m}\left(T_n(y)\right). \] In your case \[ a_{n+1}=T_2(a_n)= T_{2}\left(T_{2}(a_{n-1})\right)=T_{2^2}(a_{n-1})(x)=...=\] \[ =T_{2^j}(a_{n-j+1})=...=T_{2^{n+1}}(a_0)= ?? \] Note that another representation of $ T_n $ is $ T_n(t)=\frac{1}{2}\left( (t+\sqrt{t^2-1})^n+ (t-\sqrt{t^2-1})^n\right)\; ,\; t\in {\mathbb R}. $ However $ T_m(1)=1 .$ Therefore ... ? Perhaps help.

Let $p$ be a prime number and let $A$ be a set of positive integers that satisfies the following conditions: (i) the set of prime divisors of the elements in $A$ consists of $p-1$ elements; (ii) for any nonempty subset of $A$, the product of its elements is not a perfect $p$-th power. What is the largest possible number of elements in $A$ ?

Let $a_{ij}$ $i=1,2,3$; $j=1,2,3$ be real numbers such that $a_{ij}$ is positive for $i=j$ and negative for $i\neq j$. Prove the existence of positive real numbers $c_{1}$, $c_{2}$, $c_{3}$ such that the numbers \[a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3},\qquad a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3},\qquad a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3}\]are either all negative, all positive, or all zero. Proposed by Kiran Kedlaya, USA

Click for solution I don't know if this works or not, a lot of it is intuitive, but I think there might be some good ideas in there. First of all, if the vectors $\vec {u_i}=(a_{i1},\ a_{i2},\ a_{i3})$ are coplanar, then it's easy to show that all the three components of the non-zero solution of the system $a_{i1}c_i+a_{i2}c_2+a_{i3}c_3=0$ have the same sign. In this case we find positive $c_i$ s.t. all of those expressions are equal to $0$. We may thus assume that the three vectors are not coplanar (or, in other words, we may assume they're independent). We have to find three positive numbers $t_i$ s.t. all the components of the solution of the system $a_{i1}c_1+a_{i2}c_2+a_{i3}c_3=t_i$ have the same sign. In other words, we have to find positive $t_i$ s.t. the three determinants obtained from $\left |\begin{array}{ccc}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{array}\right |$ by replacing a column with $\left (\begin{array}{c}t_1\\ t_2\\ t_3\end{array} \right )$ have the same sign. This translates to the point $T(t_1,t_2,t_3)$ being on the interior of the trihedron determined by the lines $OP_1,OP_2,OP_3$, where $P_i(a_{1i},a_{2i},a_{3i}$. It really isn't hard to show that such a point $T$ exists (by "trihedron" I understand the figure formed by three lines in space, not three rays, as we usually understand). This is the part I'm not convinced about. It's related to the fact that the oriented volume of a tetrahedron which has $O$ as a vertex depends on the direction in which we consider the three vertices different from $O$ (clockwise/anticlockwise direction). Opinions?

Find all nondecreasing functions $f: \mathbb{R}\rightarrow\mathbb{R}$ such that (i) $f(0) = 0, f(1) = 1;$ (ii) $f(a) + f(b) = f(a)f(b) + f(a + b - ab)$ for all real numbers $a, b$ such that $a < 1 < b$. Proposed by A. Di Pisquale & D. Matthews, Australia

Click for solution Let's put down $a = -b$, then we have that $f(b^2) = f(b) + f(-b) - f(b)f(-b)$. If we need that f would be nondecreasing, it must be held that $f(b^2) >= f(b)$, so $f(-b)[1-f(b)] >= 0$ too. From that we have only two possibilities to discuss: CASE 1: $f(b) = 1$ and $f(-b) = 0$ (this implies that for each $a<0: f(a)=0$), then we can put down this into the formula (ii) from the task and obtain that $1 = f(a+b-ab)$. It can be easily seen that for each convenient $a, b$ we have $a+b-ab = x$ where $x$ can be each real number more than or equal $x$ because of the equation $(b-1)(1-a) = x-1$ has always a solution $b>=1$ for fixed $a, x$. So the function f generated in case 1 must satisfy (and it's enough): $ a<=0 ==> f(a) = 0,$ $0<a<1 ==> f: a ---> f(a)$, such that $0<f(a)>1$ and for each$0<a_1<a_2<1: f(a_1)<=f(a_2),$ $b>=1 ==> f(b) = 1,$ CASE 2: we have only $f(-b) = 0$ (this implies that for each $a<0: f(a)=0$), then we can put down this into the formula (ii) in which we only consider that $a<0$, then we obtain that $f(b) = f(a+b-ab)$. We can easily see that for each $a<=0$ and convenient $b: a+b-ab>=b$ and for each $b$ we can find any $a<0$ such that $a+b-ab = x$, where $x$ is fixed real number more or equal 1. This signifies that for each $b: f(b) =$ some constant $C>=1$. Now let's take remaining $0<a<1$. From formula (ii) $f(a) + C - f(a).C = C$, so $f(a).(1-C) = 0$. Now there are 2 possibilities: $C = 1$, then we obtain the same set of functions f as in case 1, or $C > 1$, then $f(a) = 0$ and we have another set of convenient function f: $ a<1 ==> f(a) = 0,$ $f(1)=1,$ $b>1 ==> f(b) = $some constant$ C > 1,$ I think that's all... It may contain some mistake, but I think that the inicial substitution $a = -b$ to obtain $f(b^2) = f(b) + f(-b) - f(b)f(-b)$ is good way to solve this problem...

Consider pairs of the sequences of positive real numbers \[a_1\geq a_2\geq a_3\geq\cdots,\qquad b_1\geq b_2\geq b_3\geq\cdots\]and the sums \[A_n = a_1 + \cdots + a_n,\quad B_n = b_1 + \cdots + b_n;\qquad n = 1,2,\ldots.\]For any pair define $c_n = \min\{a_i,b_i\}$ and $C_n = c_1 + \cdots + c_n$, $n=1,2,\ldots$. (1) Does there exist a pair $(a_i)_{i\geq 1}$, $(b_i)_{i\geq 1}$ such that the sequences $(A_n)_{n\geq 1}$ and $(B_n)_{n\geq 1}$ are unbounded while the sequence $(C_n)_{n\geq 1}$ is bounded? (2) Does the answer to question (1) change by assuming additionally that $b_i = 1/i$, $i=1,2,\ldots$? Justify your answer.

Click for solution I'm surprised this was a high school contest problem. For convenience, let the sequences be nonincreasing rather than strictly decreasing- we can always tweak them after the fact without changing the convergence of the series. (a) Yes. An example: Let $r_0=0$, $r_1=1$, $r_2=1+2^1$, $r_3=r_2+2^3$, ..., $r_{n+1}=r_n+2^{\frac{n(n+1)}{2}}$. Let $a_1=1$, $a_k=2^{-3}$ if $r_1<k \le r_3$, $a_k=2^{-m(2m+1)}$ if $r_{2m-1}< k \le r_{2m+1}$. Let $b_k=2^{-1}$ if $0<k \le r_2$, $b_k=2^{-m(2m-1)}$ if $r_{2m-2}< k \le r_{2m}$. Then $c_k=2^{-\frac{n(n+1)}{2}}$ if $r_{n-1}<k \le r_n$ and $\displaystyle \sum_{k=1}^{\infty}c_k = \sum_{j=0}^{\infty} \sum_{k=r_j+1}^{r_{j+1}} 2^{-\frac{(j+1)(j+2)}{2}} = \sum_{j=0}^{\infty} \sum_{k=r_j+1}^{r_{j+1}} 2^{-\frac{j(j+1)}{2}}\cdot 2^{-(j+1)} = \sum_{j=0}^{\infty} 2^{-(j+1)} = 1$ On the other hand $\displaystyle \sum_{k=1}^{r_{2n-1}}a_k > \sum_{j=0}^{n-1} \sum_{k=r_{2j}+1}^{r_{2j+1}}a_k = \sum_{j=0}^{n-1} \sum_{k=r_{2j}+1}^{r_{2j+1}}2^{-j(2j+1)} = \sum_{j=0}^{n-1} 1 = n$ and $\displaystyle \sum_{k=1}^{r_{2n}}b_k > \sum_{j=1}^n \sum_{k=r_{2j-1}+1}^{r_{2j}}b_k = \sum_{j=1}^{n} \sum_{k=r_{2j-1}+1}^{r_{2j}}2^{-j(2j-1)} = \sum_{j=1}^n 1 = n$ Each series $\sum_k a_k$ and $\sum_k b_k$ diverge, while $\sum_k \min(a_k,b_k)$ converges. (b)The answer changes: $\sum_k c_k$ must diverge. Case 1. Suppose that for all $k \ge N$, $a_k < \frac{1}{k}$. Then $\displaystyle \sum_{k=N}^{\infty} c_k = \sum_{k=N}^{\infty} a_k$ diverges by divergence of $\sum_k a_k$. Case 2. There exist infinitely many $m$ such that $a_m \ge \frac{1}{m}$ Let $m_n$ be an infinite sequence with $m_{n+1} \ge 2m_n$ and $a_{m_n} \ge \frac{1}{m_n}$ for all $n \ge 1$ (with $m_0=0$). Then $c_{m_n}=\frac{1}{m_n}$, so $\displaystyle \sum_{k=1}^{m_n} c_k = \sum_{j=0}^{n-1} \sum_{k=m_j+1}^{m_{j+1}} c_k \ge \sum_{j=0}^{n-1} \sum_{k=m_j+1}^{m_{j+1}} \frac{1}{m_{j+1}} \ge \sum_{j=0}^{n-1}\frac{m_{j+1}-m_j}{m_{j+1}} \ge \sum_{j=0}^{n-1} \frac{1}{2} = \frac{n}{2}$ and $\sum_k c_k$ diverges. These two case exhaust all possibilities, and we are done.

Let $n$ be a positive integer and let $x_1\le x_2\le\cdots\le x_n$ be real numbers. Prove that \[ \left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2\le\frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2. \] Show that the equality holds if and only if $x_1, \ldots, x_n$ is an arithmetic sequence.

Click for solution We can rewrite the given expression as \( \sum_i (2i-n-1)x_i \)^2 \leq (n^2 - 1)/3 \( n\sum x_i^2 - (\sum x_i )^2\). As the expression is translation invariant (obvious from the original form), we can assume that \sum x_i =0. The rest follows by Cauchy-Schwartz.

Let $\mathbb{R}^+$ be the set of all positive real numbers. Find all functions $f: \mathbb{R}^+ \to \mathbb{R}^+$ that satisfy the following conditions: - $f(xyz)+f(x)+f(y)+f(z)=f(\sqrt{xy})f(\sqrt{yz})f(\sqrt{zx})$ for all $x,y,z\in\mathbb{R}^+$; - $f(x)<f(y)$ for all $1\le x<y$. Proposed by Hojoo Lee, Korea

Click for solution It can't be that hard. The desired answer is indeed $f_m(x)=x^m+\frac{1}{x^m}$ , for any $m>0$. It is easy to check that it satisfies our equation. I think I have an "ugly solution" for this. Fix some $t>1$ as given and $f(t)=t^m+\frac{1}{t^m}=r>2$ , $r$-given (from this it follows some $m$). We can express $f(t^2)=f^2(t)-2$ , $f(t^3)=f^3(t)-3f(t)$ , ... and generally $f(t^n)=P_n(f(t))$, for any integer $n>0$ , where $P_n$ are polynomials ($n$-even, $P_n$-even ; while $n$-odd, $P_n$-odd and coefficients in $P_n$ are only function of $n$ - I computed them recursively and they have an "ugly" form in my oppinion). Hence $f(t^n)$ just follows uniquely determined from the given $f(t)$ - anyway i don't need those coefficients in explicitely form, since my goal is to show that $r=P_n(x)$ has only one solution greater than $2$, $x>2$ for $r>2$ - it results by induction this important fact in the proof; here it is used the increasing condition. The equation $f(t)=P_n(f(t^{1/n}))$ has an unique solution for $f(t^{1/n})>2$ uniquely determined by that initial value $f(t)=r>2$. So for any rational $p/q>0$ I can compute uniquely $f(t^{p/q})$ from $f(t^p)$ which come from $f(t)$, then my function is well-determined for any rational $x=t^{p/q}>1$ as $f(x)$ starting from that $f(t)=r>2$, then it follows by extension for any real $x>1$, using again increasing condition! Since $f(x)=f(\frac{1}{x})$ we get the only possible answer $f_m(x)=x^m+\frac{1}{x^m}$ , $f_m: \mathbb{R}^+ \longrightarrow \mathbb{R}^+$ for any $m>0$. I hope that some other "good looking" proof exists.

Let $n$ be a positive integer and let $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ be two sequences of positive real numbers. Suppose $(z_2,\ldots,z_{2n})$ is a sequence of positive real numbers such that $z_{i+j}^2 \geq x_iy_j$ for all $1\le i,j \leq n$. Let $M=\max\{z_2,\ldots,z_{2n}\}$. Prove that \[ \left( \frac{M+z_2+\dots+z_{2n}}{2n} \right)^2 \ge \left( \frac{x_1+\dots+x_n}{n} \right) \left( \frac{y_1+\dots+y_n}{n} \right). \] commentEdited by Orl. Proposed by Reid Barton, USA

Click for solution The official solution is this (im just copying from the booklet ): and its really nice: Let X = max (x1,x2 ... x(n)), and Y = max (y1,y2 ... y(n)). By replacing with x(i)'=x(i)/X, and y(i)'=y(i)/Y and z(i) by z(i)'=z(i)/sqrt XY, we may assume X=Y=1. Now we prove the following: M + z2 + ... + z(2n) >= x1 + x2 ... + x(n) + y1 + y2 ... + y(n) ... (*) from which the result follows with am-gm. to prove (*) we will show that for any r>=0, the number of terms greater than r on the left hand side is at leas the number of such terms on the right-hand side. Then the k-th largest term on the left hand side is greater than or equal to the number of such terms on the right hand side for each k proving (*) (really wierd ..). If r>=1 then there are no terms greater than r on the right-hand side. So suppose r<1. Let A = {1<=i<=n|x(i) > r}, a = |A|, B = {1<=i<=n|y(i) > r}, b = |B|. Since max { x1, x2, ... x(n)} = max {y1, y2 ... y(n)} = 1, both a and b are at least 1. Now x(i) > r and y(j) > r implies z(i+j) >= sqrt (x(i)*y(j)) > r, so C = {2 <= i <= 2n | z(i) > r} is at least as large as A+B = {x+y | x in A, y in B}. However we know |A+B| >= |A| + |B| - 1 because if A={i1,i2 .. i(a)}, i1<i2 .. <i(a) and B ={j1,j2 .. j(b)}, j1<j2 ... <j(b) then the a+b-1 numbers i1+j1, i1+j2 ... i1+jb, i2+jb, ... i(a) + j(b) are all distinct and belong to A+B. Hence |C| >= a+b-1. In particular |C| >= 1 so z(k) > r for some k. Then M>r, so the left hand side of (*) has at least a+b terms greater than r. Since a+b is the number of terms greater than r on the right hand side we have proven (*).

Let $A$ be a $101$-element subset of the set $S=\{1,2,\ldots,1000000\}$. Prove that there exist numbers $t_1$, $t_2, \ldots, t_{100}$ in $S$ such that the sets \[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \] are pairwise disjoint.

Click for solution Assume that we have already found t_1, t_2, ..., t_k (k<=99) and are searching for t_{k+1}. We can not take t_{k+1} only of form t_i+a_j-a_l, where 1<=i<=k and a_j and a_l are elements of A. So, we have k*101*100 forbidden values of t_{k+1}, which correspond to a_j<>a_l, and k forbidden values which correspond to a_j=a_l. So, at most 99*101*100+99=1000000-1 forbidden values, and at least 1 admissible.

Let $D_1$, $D_2$, ..., $D_n$ be closed discs in the plane. (A closed disc is the region limited by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most $2003$ discs $D_i$. Prove that there exists a disc $D_k$ which intersects at most $7\cdot 2003 - 1 = 14020$ other discs $D_i$.

Click for solution Well, here is a solution of the problem: First, as an auxiliary result, we will solve the following problem, which is the Problem 4 of the German pre-TST 2004, written in December 2003 (the official solution is online at http://www.bundeswettbewerb-mathematik.de/imo/aufgaben/aufgaben.htm ): Auxiliary problem. In the plane, consider n circular disks $ K_1 $, $ K_2 $, ..., $ K_n $ with equal radius r. Assume that each point of the plane is contained in not more than 2003 of these circular disks. Show that each circular disk $ K_i $ intersects not more than 14020 other circular disks. Here's my original solution of this problem, i. e. the solution I gave during the TST (well... not exactly the solution I gave; I have corrected a little bagatelle mistake which even the proof-reader didn't notice ). In the following, disk will always mean closed circular disk ("closed" means that the points on the periphery of the circle belong the disk, too). If XY is a segment, then the disk with diameter XY will mean the disk corresponding to the circle with diameter XY. To cover a figure will mean covering it without gaps (but maybe with overlaps). First we prove: Lemma 1. For every positive number r, a disk of radius 2r can be covered by 7 disks of radius r. Proof. (See Fig. 1 below.) Let O be the center of a disk K with radius 2r, and let ABCDEF be a regular hexagon whose vertices lie on the periphery k of the disk K. Then, AB = BC = CD = DE = EF = FA = 2r (since it is well-known that the sidelength of a regular hexagon equals its circumradius). The disk with center O and radius r and the disks with diameters AB, BC, CD, DE, EF and FA will be called the little disks. The radii of these little disks are all r (in fact, this is clear for the disk with center O and radius r, and concerning the disks with diameters AB, BC, CD, DE, EF and FA, it follows from $ \frac{AB}{2}=\frac{BC}{2}=\frac{CD}{2}=\frac{DE}{2}=\frac{EF}{2}=\frac{FA}{2}=\frac{2r}{2}=r $). We will now show that these 7 little disks cover the disk K. This will clearly prove Lemma 1. Let P be a point inside the disk K; then we must show that this point P lies in one of our 7 little disks. Because of the rotational symmetry of the regular hexagon ABCDEF and because of the symmetrical construction of our disks, we can WLOG assume that the point P lies inside the circular sector AOB (including the arc AB of the circle k and the segments AO and BO). The triangle AOB is equilateral with sidelength AB = AO = BO = 2r; if A' and B' are the midpoints of the segments AO and BO, then $ OA^{\prime }=OB^{\prime }=\frac{2r}{2}=r $, so that these points A' and B' lie on the circle with center O and radius r. If the point P lies inside (or on the boundary) of triangle A'OB', then it follows that P lies inside the disk with center O and radius r, and the proof is done. Hence, it remains only to consider the case when the point P lies outside the triangle A'OB'. Since the triangle AOB is equilateral, symmetry yields $ BA^{\prime }\perp AO $, so that < AA'B = 90?. Similarly, < AB'B = 90?. Thus, the points A' and B' lie on the circle with diameter AB. Therefore, if the point P lies inside (or on the boundary) of the quadrilateral AA'B'B, then the point P lies inside the disk with diameter AB, and the proof is done again. So it remains to consider the case when the point P lies outside the triangle A'OB' and outside the quadrilateral AA'B'B. Then, the points P and O lie in different halfplanes with respect to the line AB. Then, since the point P lies inside the disk K, the angle < APB is greater or equal to the obtuse chordal angle of the chord AB in the circle k. But the obtuse chordal angle of the chord AB in the circle k equals 180? - the acute chordal angle of the chord AB; the acute chordal angle equals $ \frac12 $ times the central angle of the chord AB, and the central angle equals < AOB = 60? (since the triangle AOB is equilateral). Thus, the obtuse chordal angle of the chord AB is $ 180^{\circ }-\frac{1}{2}\cdot 60^{\circ }=180^{\circ }-30^{\circ }=150^{\circ } $. And thus, $ \measuredangle APB\geq 150^{\circ } $. Hence, also $ \measuredangle APB\geq 90^{\circ } $, and thus the point P lies inside the disk with diameter AB. So we are done again. Thus, every point P inside the disk K lies inside one of the 7 little disks. In other words, the 7 little disks cover the disk K. This proves Lemma 1. Now to the problem. The disk $ K_i $ intersects a disk $ K_j $ if and only if $ O_iO_j \leq r+r=2r $, where for every k, the point $ O_k $ is the center of the disk $ K_k $. Hence, the disk $ K_i $ intersects the disk $ K_j $ if and only if the point $ O_j $ lies inside the disk with center $ O_i $ and radius 2r. In this case, after Lemma 1, the point $ O_j $ must lie inside one of 7 certain disks with radius r which cover the disk with center $ O_i $ and radius 2r. But each of these 7 disks can contain at most 2003 different points $ O_k $, since else the center of this disk would have a distance $ \leq r $ to more than 2003 points $ O_k $ and thus, itself, would lie inside more than 2003 disks $ K_k $, what contradicts the problem hypothesis. Hence, the disk with center $ O_i $ and radius 2r contains at most $ 7 \cdot 2003 $ points $ O_k $, i. e. the disk $ K_i $ intersects at most $ 7 \cdot 2003 $ disks $ K_k $. Since one of these disks $ K_k $ is $ K_i $ itself (every disk intersects itself), it follows that the disk $ K_i $ intersects at most $ 7 \cdot 2003 - 1 = 14021 - 1 = 14020 $ other disks $ K_k $. And this for every i. This completes the solution of the auxiliary problem. Now, let's solve the actual problem: ISL 2003 problem C2. Let $ D_1 $, $ D_2 $, ..., $ D_n $ be closed discs in the plane. (A closed disc is the region limited by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most 2003 discs $ D_i $. Prove that there exists a disc $ D_k $ which intersects at most $ 7\cdot 2003 - 1 = 14020 $ other discs $ D_i $. Solution. This ISL problem can be reduced to the auxiliary problem as follows: Let $ O_1 $, $ O_2 $, ..., $ O_n $ be the centers and $ r_1 $, $ r_2 $, ..., $ r_n $ the radii of the discs $ D_1 $, $ D_2 $, ..., $ D_n $. Let $ r_u $ be the smallest radius among the radii $ r_1 $, $ r_2 $, ..., $ r_n $. Now, for every i, define a new disc $ K_i $ as follows: - Let $ K_u=D_u $. - If $ i\neq u $, then the disc $ K_i $ is defined as follows: Let the segment $ O_uO_i $ meet the periphery of the disc $ D_i $ at a point $ S_i $. Since the radius $ r_u $ is minimal, we have $ S_iO_i = r_i \geq r_u $, and hence we can find a point $ P_i $ on the segment $ S_iO_i $ such that $ S_iP_i=r_u $. Then, call $ K_i $ the disc with center $ P_i $ and radius $ r_u $. For every i, we have: (1) The disc $ K_i $ will completely lie inside the disc $ D_i $. (2) If the disc $ D_i $ intersects the disc $ D_u $, then the disc $ K_i $ intersects the disk $ D_u $, too. Proof of (1): This is trivial for i = u, and for $ i\neq u $, this is clear since the disk $ K_i $ touches the disc $ D_i $ at $ S_i $. Proof of (2): This is clear for i = u, and for $ i\neq u $, this follows from the simple observation that if the disc $ D_i $ intersects the disc $ D_u $, the point $ S_i $ lies inside the disc $ D_u $, and hence this point $ S_i $ is common to the discs $ D_u $ and $ K_i $. All discs $ K_1 $, $ K_2 $, ..., $ K_n $ have the same radius $ r_u $. Also, from the problem hypothesis we know that every point in the plaine is contained in at most 2003 discs $ D_i $; hence, after (1), we can conclude that every point in the plane is contained in at most 2003 discs $ K_i $. Thus, we can apply the problem I posted before, and see that every of the discs $ K_i $ intersects at most 14020 other discs $ K_j $. In particular, this is true for the disc $ K_u=D_u $. Thus, the disc $ D_u $ intersects at most 14020 other discs $ K_j $. Now, using (2), this implies that the disc $ D_u $ intersects at most 14020 other discs $ D_j $. And the ISL 2003 problem is solved. Darij

Let $n \geq 5$ be a given integer. Determine the greatest integer $k$ for which there exists a polygon with $n$ vertices (convex or not, with non-selfintersecting boundary) having $k$ internal right angles. Proposed by Juozas Juvencijus Macys, Lithuania

Let $x_1,\ldots, x_n$ and $y_1,\ldots, y_n$ be real numbers. Let $A = (a_{ij})_{1\leq i,j\leq n}$ be the matrix with entries \[a_{ij} = \begin{cases}1,&\text{if }x_i + y_j\geq 0;\\0,&\text{if }x_i + y_j < 0.\end{cases}\]Suppose that $B$ is an $n\times n$ matrix with entries $0$, $1$ such that the sum of the elements in each row and each column of $B$ is equal to the corresponding sum for the matrix $A$. Prove that $A=B$.

Click for solution Consider the matrix $A-B$. It has only $-1,0,1$ as elements, and we want to prove that it actually has only $0$. It also has the property that the sum of the elements on each line and each column is $0$. In $A$ we can't have $i\ne k,\ j\ne l$ s.t. $a_{ij},a_{kl}=1,\ a_{il},a_{kj}=0$ or vice-versa. Then in $A-B$ we can't have $i\ne k,\ j\ne l$ s.t. $a_{ij},a_{kl}=1,\ a_{il},a_{kj}\ne 1$ or vice-versa. [Moderator edit: Here and in the following, $a_{uv}$ doesn't necessarily denote the $\left(u,v\right)$-th entry of the matrix $A$, but rather the $\left(u,v\right)$-th entry of whatever matrix we are currently talking about.] Consider the line in $A-B$ with the maximal number of $1$'s. If this number is non-zero, then there must be some $-1$'s as well on this line (call it line $i$). Assume $a_{ij}=-1$. In this case there is a $k$ s.t. $a_{kj}=1$ (because the sum of all numbers on column $j$ is $0$). If for all $m$ for which $a_{im}=1$ we also have $a_{km}=1$ then on the line $k$ we have more $1$'s than on the line $i$, and that's a contradiction, so there must exist an $l$ s.t. $a_{il}=1$ and $a_{kl}\ne 1$. But if we look at the four elements $a_{ij}=-1\ne 1,a_{kl}\ne 1,a_{il}=a_{kj}=1$ we see that they contradict what we said in the first paragraph.

Every point with integer coordinates in the plane is the center of a disk with radius $1/1000$. (1) Prove that there exists an equilateral triangle whose vertices lie in different discs. (2) Prove that every equilateral triangle with vertices in different discs has side-length greater than $96$. Radu Gologan, Romania RemarkThe "> 96" in (b) can be strengthened to "> 124". By the way, part (a) of this problem is the place where I used the well-known "Dedekind" theorem.

Click for solution This is also from the ISL. I've only managed to solve (a), which is not at all tough. We just find a triangle with vertices (as complex numbers) of the form $2n,\ 2n\epsilon,\ 2n\epsilon^2$. Since $\epsilon=\frac{-1+\sqrt3}2$, it means that we can find an $n$ s.t. $2n\epsilon$ is inside a disk (by using the "famous Dedekind theorem" , otherwise known as Kronecker's thm). $2n\epsilon^2$ will, of course, be inside a disk as well, because $\epsilon^2$ is the symmetric of $\epsilon$ wrt the $Ox$ axis.

Let $f(k)$ be the number of integers $n$ satisfying the following conditions: (i) $0\leq n < 10^k$ so $n$ has exactly $k$ digits (in decimal notation), with leading zeroes allowed; (ii) the digits of $n$ can be permuted in such a way that they yield an integer divisible by $11$. Prove that $f(2m) = 10f(2m-1)$ for every positive integer $m$. Proposed by Dirk Laurie, South Africa