1. Let $ABC$ be an acute-angled triangle with $AB\neq AC$. The circle with diameter $BC$ intersects the sides $AB$ and $AC$ at $M$ and $N$ respectively. Denote by $O$ the midpoint of the side $BC$. The bisectors of the angles $\angle BAC$ and $\angle MON$ intersect at $R$. Prove that the circumcircles of the triangles $BMR$ and $CNR$ have a common point lying on the side $BC$.

Click for solution I needed 10 minutes to sort the trash out of the configuration. After that everything was trivial. If T is the point of intersection of the circumcircles of triangles BMR and CNR, then we must show that T lies on BC, i. e. that we have < BTR + < CTR = $180^{\circ}$. Since BMRT is a cyclic quadrilateral, we have < BTR = $180^{\circ}$ - < BMR, so < BTR = < AMR. Similarly < CTR = < ANR. So we have to show that < AMR + < ANR = $180^{\circ}$, or, in other words, we must prove that the quadrilateral AMRN is cyclic. Well, the points M and N lie on the circle with diameter BC, and the center of this circle is obviously the midpoint O of BC. Thus, MO = NO, so that the triangle MON is isosceles, and hence the line OR, being the angle bisector of the angle MON, coincides with the perpendicular bisector of the segment MN. Hence, the point R lies on the perpendicular bisector of the segment MN. In other words, the point R is the point of intersection of the perpendicular bisector of the segment MN with the angle bisector of the angle MAN. But a well-known fact states that the perpendicular bisector of a side of a triangle meets the angle bisector of the opposite angle at a point on the circumcircle of the triangle. Hence, the point R lies on the circumcircle of triangle MAN, and therefore, the quadrilateral AMRN is cyclic. Darij

Let $\Gamma$ be a circle and let $d$ be a line such that $\Gamma$ and $d$ have no common points. Further, let $AB$ be a diameter of the circle $\Gamma$; assume that this diameter $AB$ is perpendicular to the line $d$, and the point $B$ is nearer to the line $d$ than the point $A$. Let $C$ be an arbitrary point on the circle $\Gamma$, different from the points $A$ and $B$. Let $D$ be the point of intersection of the lines $AC$ and $d$. One of the two tangents from the point $D$ to the circle $\Gamma$ touches this circle $\Gamma$ at a point $E$; hereby, we assume that the points $B$ and $E$ lie in the same halfplane with respect to the line $AC$. Denote by $F$ the point of intersection of the lines $BE$ and $d$. Let the line $AF$ intersect the circle $\Gamma$ at a point $G$, different from $A$. Prove that the reflection of the point $G$ in the line $AB$ lies on the line $CF$.

Let $O$ be the circumcenter of an acute-angled triangle $ABC$ with ${\angle B<\angle C}$. The line $AO$ meets the side $BC$ at $D$. The circumcenters of the triangles $ABD$ and $ACD$ are $E$ and $F$, respectively. Extend the sides $BA$ and $CA$ beyond $A$, and choose on the respective extensions points $G$ and $H$ such that ${AG=AC}$ and ${AH=AB}$. Prove that the quadrilateral $EFGH$ is a rectangle if and only if ${\angle ACB-\angle ABC=60^{\circ }}$. Proposed by Hojoo Lee, Korea

In a convex quadrilateral $ABCD$, the diagonal $BD$ bisects neither the angle $ABC$ nor the angle $CDA$. The point $P$ lies inside $ABCD$ and satisfies \[\angle PBC=\angle DBA\quad\text{and}\quad \angle PDC=\angle BDA.\] Prove that $ABCD$ is a cyclic quadrilateral if and only if $AP=CP$.

Click for solution I needed over two hours for the solution, even though it is not so hard. Let $P_1$, $P_2$, $P_3$, $P_4$ be the orthogonal projections of the point P on the lines AB, BC, CD, DA, and let $Q_1$, $Q_2$, $Q_3$, $Q_4$ be the reflections of P in these lines, or, equivalently, the reflections of P in the points $P_1$, $P_2$, $P_3$, $P_4$. From < PBC = < DBA, you see that the line BD is the reflection of the line BP in the angle bisector of the angle ABC. Now you use the following (quite easy) lemma: If X is a point in the plane of an angle VUW, and V' and W' are the reflections of X in the lines UV and UW, then the perpendicular bisector of the line V'W' is the reflection of the line UX in the angle bisector of the angle VUW. Now, apply this lemma to the angle ABC and the point P, whose reflections in the lines BA and BC are $Q_1$ and $Q_2$, respectively, and you see that the perpendicular bisector of the line $Q_1 Q_2$ is the line BD. Hence, the points $Q_1$ and $Q_2$ are symmetric to each other with respect to the line BD. Similarly, the points $Q_4$ and $Q_3$ are symmetric to each other with respect to the line BD, too. Hence, since symmetry is a congruence transformation , we have $Q_1 Q_4 = Q_2 Q_3$. Now, since $Q_1$ and $Q_4$ are the reflections of P in $P_1$ and $P_4$, the points $P_1$ and $P_4$ are the midpoints of the segments $PQ_1$ and $PQ_4$, and thus $P_1 P_4 = \frac12 Q_1 Q_4$. Similarly $P_2 P_3 = \frac12 Q_2 Q_3$. Now, from $Q_1 Q_4 = Q_2 Q_3$, it follows that $P_1 P_4 = P_2 P_3$. Since $\measuredangle AP_4 P = 90^{\circ}$ and $\measuredangle AP_1 P = 90^{\circ}$, the points $P_4$ and $P_1$ lie on the circle with diameter AP. In other words, the circumcircle of triangle $AP_4 P_1$ has the segment AP as diameter. Therefore, by the Extended Law of Sines, we have $P_1 P_4 = AP \cdot \sin \measuredangle P_1 A P_4 = AP \cdot \sin A$, where A = < DAB and C = < BCD are two opposite angles of our quadrilateral. Similarly, $P_2 P_3 = CP \cdot \sin C$. Since $P_1 P_4 = P_2 P_3$, we conclude that AP = CP holds if and only if sin A = sin C. Now, sin A = sin C means either A = C, or A + C = $180^{\circ}$. In the case of A + C = $180^{\circ}$, the quadrilateral ABCD is cyclic, and we are happy. Remains to show that the case A = C cannot occur. In fact, a simple angle chase shows that in this case, we have < BPD = $180^{\circ}$, so that the point P (if it exists) lies on the diagonal BD, and from < PBC = < DBA we conclude that the diagonal BD bisects the angle ABC. This contradicts the assumption of the problem. Hence, AP = CP holds if and only if the quadrilateral ABCD is cyclic. Peter has another solution, applying the sine law one thousand times (later he admitted it were just four times or something like this ). Darij

Let $A_1A_2A_3\ldots A_n$ be a regular $n$-gon. Let $B_1$ and $B_{n-1}$ be the midpoints of its sides $A_1A_2$ and $A_{n-1}A_n$. Also, for every $i\in\left\{2,3,4,\ldots ,n-2\right\}$. Let $S$ be the point of intersection of the lines $A_1A_{i+1}$ and $A_nA_i$, and let $B_i$ be the point of intersection of the angle bisector bisector of the angle $\measuredangle A_iSA_{i+1}$ with the segment $A_iA_{i+1}$. Prove that $\sum_{i=1}^{n-1} \measuredangle A_1B_iA_n=180^{\circ}$. Proposed by Dusan Dukic, Serbia and Montenegro

Click for solution Using lemma, This can be proved easily $lemma$. Let $XAB$ be a triangle such that $XA=XB$. $D, C$ be points on $XA, XB$ respectly such that $DC \parallel AB$. and $S= AC \cap BD$ . and $N$ be the intersection of the bisector of $\angle CSB$ and $BC$. Finally, $M$ be the mid point of $BC$. Then $D, N, M, A$ are on one circle. $pf)$ Let $AN \cap CD = E$, $DM\cap AB = F$. And the length of $DC=p$. It can be easily shown that $BF=CE=p$. so $EF\parallel XB$. Therefore, $\angle EAF=\angle FDE$. and from $\angle CAB=\angle BDC$, We get $\angle CAN = \angle MDB$. cuz $\angle CAD= \angle DBC$, $\angle NAD = \angle DMN$. so lemma is proved. Now, Let $C_i$ be the mid points of $A_i A_{i+1}$. Using lemma, We get $\angle A_1 C_i A_n = \angle A_1 B_i A_n$. With using similarity, We can concentrate angles into $B_1$. So, the sum of angles is $180$. $Q.E.D.$

Let $P$ be a convex polygon. Prove that there exists a convex hexagon that is contained in $P$ and whose area is at least $\frac34$ of the area of the polygon $P$. Alternative version. Let $P$ be a convex polygon with $n\geq 6$ vertices. Prove that there exists a convex hexagon with a) vertices on the sides of the polygon (or) b) vertices among the vertices of the polygon such that the area of the hexagon is at least $\frac{3}{4}$ of the area of the polygon. Proposed by Ben Green and Edward Crane, United Kingdom

Click for solution This is a more geometric approach. Take any two parallel lines of support $s,t$ touching $\mathcal{P}$ at $S,T$. The segment $ST$ partitions $\mathcal{P }$ into two convex polygons $\mathcal{P}^{\prime}$ and $\mathcal{P} ^{\prime\prime}$. Let $K,L$ be points on the boundary of $\mathcal{P}$ such that the segment $KL$ is parallel to $ST$ and has length $ST/2$. We claim that the trapezoid $SKLT$ has area at least $3/4$ the area of $\mathcal{P} ^{\prime}$. This yields the result because the same argument, applied to $\mathcal{P}^{\prime\prime}$, produces another trapezoid, of area at least $3/4$ the area of $\mathcal{P}^{\prime\prime}$. Combining the two trapezoids, we obtain a hexagon as needed. Draw the lines of support of $\mathcal{P}$ through $K$ and $L$, and let them intersect at $Z$. We assume for definiteness that $K$ is closer to the line $s$ than $L$. Let $ZK$ meet $s$ at $X$, let $ZL$ meet $t$ at $Y$, and let the line through $Z$, parallel to $ST$, meet $s$ and $t$ at $A$ and $B$, respectively. Clearly $\mathcal{P}^{\prime }$ is contained in the pentagon $SXZYT$, (which may reduce to a triangle or a quadrilateral), so it suffices to show that \[ \lbrack SKLT]\geq \frac{3}{4}[SXZYT].\ \ \ \ \ \mathbf{(1)} \] Denote ${AZ=a}$, ${BZ=b}$, and let the distances from the points $K$, $X$, $Y$, $S$ to the line $AB$ be $k$, $x$, $y$, $s$. Taking $U$, $V$ on $AB$ so that ${s\parallel KU\parallel LV\parallel t}$, we obtain \[ \frac{a+b}{2}=KL=UZ+ZV=\frac{ak}{x}+\frac{bk}{y}.\ \ \ \ \ \mathbf{(2)} \] The areas we are about to compare are expressed by \[ \lbrack SKLT]=\frac{3}{4}(a+b)(s-k), \] \[ \quad \lbrack SXZYT]=[SABT]-[AXZ]-[BYZ]=(a+b)s-\frac{ax}{2}-\frac{by}{2}, \] so the claimed inequality (1) comes down to \[ ax+by-2(a+b)k\geq 0.\ \ \ \ \ \mathbf{(3)} \] On computing $k$ from (2) and plugging into (3), a short calculation shows that the left-hand side of (3) is equal to ${ab(x-y)^{2}(ay+bx)^{-1}}$, which is nonnegative. [Moderator edit: This is the second proposed solution of this problem, avaliable at http://www.mathlinks.ro/Forum/viewtopic.php?t=15622 .]

For a given triangle $ ABC$, let $ X$ be a variable point on the line $ BC$ such that $ C$ lies between $ B$ and $ X$ and the incircles of the triangles $ ABX$ and $ ACX$ intersect at two distinct points $ P$ and $ Q.$ Prove that the line $ PQ$ passes through a point independent of $ X$.

Click for solution The problem follows nicely by a "lemma" proposed by Virgil Nicula here: http://www.mathlinks.ro/Forum/viewtopic.php?t=132338 Now, returning to the problem: Let the incircles of $\triangle{ABX}$ and $\triangle{ACX}$ touch $BX$ at $D$ and $F$, respectively, and let them touch $AX$ at $E$ and $G$, respectively. Clearly, $DE \| FG$. If the line $PQ$ intersects $BX$ and $AX$ at $M$ and $N$, respectively, then $MD^{2}= MP\cdot MQ = MF^{2}$, i.e., $MD = MF$ and analogously $NE = NG$. It follows that $PQ \| DE$ and $FG$ and equidistant from them. The midpoints of $AB, AC$, and $AX$ lie on the same line $m$, parallel to $BC$. Applying the "lemma" to $\triangle{ABX}$, we conclude that $DE$ passes through the common point $U$ of $m$ and the bisector of $\angle{ABX}$. Analogously, $FG$ passes through the common point $V$ of $m$ and the bisector of $\angle{ACX}$. Therefore $PQ$ passes through the midpoint $W$ of the line segment $UV$ . Since $U, V$ do not depend on $X$, neither does $W$.

Given a cyclic quadrilateral $ABCD$, let $M$ be the midpoint of the side $CD$, and let $N$ be a point on the circumcircle of triangle $ABM$. Assume that the point $N$ is different from the point $M$ and satisfies $\frac{AN}{BN}=\frac{AM}{BM}$. Prove that the points $E$, $F$, $N$ are collinear, where $E=AC\cap BD$ and $F=BC\cap DA$. Proposed by Dusan Dukic, Serbia and Montenegro

Click for solution I like the problem very much . Let $P$ be the second point of intersection between $CD$ and the circle $(ABM)$, and let $G=AB\cap CD$. A very simple computation, based on the fact that $GD\cdot GC=GA\cdot GB=GM\cdot GP$ and $M$ is the midpoint of $CD$ will show that $P$ is, in fact, the harmonic conjugate of $C,D$ art $G$, so it belongs to $EF$. $ANBM$ is a harmonic quadrilateral, so $(PA,PB;PN,PM)=-1$, and since $PM=PG$, so $(PA,PB;PE,PM)=-1$ as well, we get $PE=PN$, as desired.

Let $\tau(n)$ denote the number of positive divisors of the positive integer $n$. Prove that there exist infinitely many positive integers $a$ such that the equation $ \tau(an)=n $ does not have a positive integer solution $n$.

The function $f$ from the set $\mathbb{N}$ of positive integers into itself is defined by the equality \[f(n)=\sum_{k=1}^{n} \gcd(k,n),\qquad n\in \mathbb{N}.\] a) Prove that $f(mn)=f(m)f(n)$ for every two relatively prime ${m,n\in\mathbb{N}}$. b) Prove that for each $a\in\mathbb{N}$ the equation $f(x)=ax$ has a solution. c) Find all ${a\in\mathbb{N}}$ such that the equation $f(x)=ax$ has a unique solution.

Click for solution You can prove the multiplicativity easily by the chinese remainder theorem: Let $x,y$ be coprime. Then $\gcd(z,xy) = \gcd(z,x)\gcd(z,y) = \gcd(z \mod x,x)\gcd(z \mod y,y)$, and so $\gcd(r(a,b),xy))=\gcd(a,x)\gcd(b,y)$ (here $r(a,b)$ denotes the smallest natural number that fulfills $r(a,b) \equiv a \mod x,r(a,b) \equiv b \mod y$) Since in $f(xy)=\gcd(1,xy)+...+\gcd(xy,xy)$ and in $f(x)f(y) = (\gcd(1,x)+...+\gcd(x,x))(\gcd(1,y)+...+\gcd(y,y)) =$ $= \gcd(r(1,1),xy) + \gcd(r(1,2),xy) + \gcd(r(1,3),xy) + ... + \gcd(r(1,y),xy) + \gcd(r(2,1),xy) + ... + \gcd(r(x,y),xy)$ every residue class $\mod xy$ (on the left side of the $\gcd$) occurs exactly one time, so they are identical. Now use senouy's formula to get $f(2^{2n})=(n+1)\cdot 2^{2n}$, so a) is solved Now $f(p^n)$ is only divisible by $p^n$ iff $p|n$ and then ($n=pk$) you get $\frac{f(p^n)}{p^n}=(p-1)k+1$ So if $n=sq$ with an odd prime factor $q$, set $r:=\frac{q-1}{2}$ and you will get $f(2^{2(s-1)}3^{3r})=n 2^{2(s-1)}3^{3r}$, so there are at least two solutions. Let be $n=2^s$ now. For an odd prime $p$ also $f(p^k)$ is odd, so if $d$ is odd, by multiplicativity also $f(d)$ is odd. Assume $f(2^id)=2^s \cdot 2^i d$, where $d$ is odd. Then by the formula for powers of primes and multiplicativity you get $2^{i-1}(i+2) f(d) = 2^s \cdot 2^i d \implies (i+2) f(d) = 2^{s+1} d$, but since $f(d)$ is odd, you need that $i+2 = 2^{s+1} m$ with some (odd) $m$. But this gives $m f(d) =d$, which is because of $f(x)>x$ for all $x>1$ only possible if $m=d=1$, so there is only one solution for this case. So also b) is solved.

Find all functions $ f: \mathbb{N^{*}}\to \mathbb{N^{*}}$ satisfying \[ \left(f^{2}\left(m\right)+f\left(n\right)\right) \mid \left(m^{2}+n\right)^{2}\] for any two positive integers $ m$ and $ n$. Remark. The abbreviation $ \mathbb{N^{*}}$ stands for the set of all positive integers: $ \mathbb{N^{*}}=\left\{1,2,3,...\right\}$. By $ f^{2}\left(m\right)$, we mean $ \left(f\left(m\right)\right)^{2}$ (and not $ f\left(f\left(m\right)\right)$). Proposed by Mohsen Jamali, Iran

Click for solution Ok, let's solve it : We know that $f^2(1)+f(1)$ divides $4$ and is greater than $1$, so that it is $2$ or $4$. Solving the quadratic equations in $f(1)$ we easily find that $f(1)=1.$ It follows that for each prime $p$ the number $1+f(p-1)$ divides $p^2$ and is greater than $1$ so that it is $p$ or $p^2$. Suppose that for some prime $p$ we have $f(p-1)+1 = p^2.$ Then $p^4-2p^2+2 = (p^2-1)^2 + 1 = f^2(p-1)+f(1)$ divides $((p-1)^2+1)^2 = p^4-4p^3 + 8p^2 - 8p +4$. But it is easy to verify that for $p \geq 2$ we have $p^4-4p^3 + 8p^2 - 8p +4 <2(p^4-2p^2+2)$, from which we deduce that we must have $p^4-4p^3 + 8p^2 - 8p +4 = p^4 - 2p^2 + 2$, that is $2p^3-5p^2+4p-1=0$. Thus $p$ divides $1$ which is absurd. Then, for all prime $p$, we have $f(p-1)+1=p$ that is $f(p-1)=p-1.$ Now, for all positive integer $n$ and all prime $p$, we deduce that $f(n)+(p-1)^2$ divides $((p-1)^2+n)^2 = ((p-1)^2+f(n))((p-1)^2 + 2n - f(n)) + (f(n) - n)^2$. Thus $\frac {(f(n)-n)^2} {f(n) + (p-1)^2}$ is an integer. Note that this integer is clearly non-negative. Choosing $p$ sufficientely large, the corresponding integer is less than $1$, so that it is $0$. Thus $f(n) = n$. Conversely, $f(n)=n$ is clearly a solution of the problem. Pierre.

Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$. Proposed by Jaroslaw Wroblewski, Poland

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity. Find all positive integers $n$ such that $n$ has a multiple which is alternating.

Click for solution not really nice, but anyway not too hard, if one doesn't forget something at the end. ok, it are all numbers not divisible by 20. actually, it is clear that there is no alternating multiple of them since the last two digits are always even. so, let's first do powers of 2 and 5. in both cases start with the number 25252525...2525 for 5 with "enough" digits(or 101010...1010 for 2). in the k-th step, change the k-th digit such that the new number is divisible by $2^{k+1}$(respectively $5^{k+1}$) if the number is not divisible by that term before(where even digits stay even and odd digits stay odd). if inductively follows that this is actually possible, so we get a alternating number which is divisible by $2^n$(respectively $5^n$) and has an odd digit at the end. now, take a power of 2 times an odd number not divisible by 5. take the alternating number divisible by the power of 2 several times to get by fermat a number divisible by the number we want to. now, take (10 times a) power of 5 times an odd number not divisible by 5. take the number divisible by to the power of 5 several times to get a number divisible by the power of 5 times the odd number not divisible by 5. add a 0 at the end if the number is divisible by 10. so, we have everything since numbers divisible by 20 have no alternating multiple. i hope the main argument gets clear. Peter

Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. Proposed by John Murray, Ireland

Click for solution Case 1: n odd Let $n=p_1^{a_1}\ldots p_k^{a_k}$, where $p_i$ are distinct odd primes. Then $P_n=\prod_{S\subseteq [k]}\alpha_S$, where for $S\subseteq[k],\ \alpha_S$ is congurent to $1\pmod{p_i^{a_i}},\ \forall i\in S$, and congruent to $-1\pmod{p_j^{a_j}},\ \forall j\in[k]\setminus S$ ($[k]$ is just a compact notation for $\{1,2,\ldots,k\}$). Since for each $i\in[k]$, there are $2^{k-1}$ subsets $S\subseteq[k]$ for which $\alpha_S\equiv-1\pmod{p_i^{a_i}}$, it means that $P_n\equiv (-1)^{2^{k-1}}\pmod {p_i^{a_i}},\ \forall i$, and thus $P_n\equiv(-1)^{2^{k-1}}\pmod n$. In other words, if $n$ is odd, the answer is $1$ if $n$ has at least $2$ prime divisors, and $-1$ if it's a prime power. Case 2: n even, but not a power of $2$ Let $n=2^ap_1^{a_1}\ldots p_k^{a_k}$, and let $\tilde n=\frac n{2^n}$. The possibilities for $x\pmod{\tilde n}$ are those from the preceding paragraph, while those for $2^a$ are $x\equiv 1\pmod 2$ if $a=1$, $x\equiv \pm1\pmod 4$ if $a=2$, and $x\equiv \pm 1,2^{a-1}\pm 1\pmod{2^a}$. Since $\pm 1,2^{a-1}\pm 1$ give $1\pmod{2^a}$ when squared, and each situation appears $2^k$ times, so an even number of times (since $k\ge 1$), it means that $P_n\equiv 1\pmod{2^a}$, no matter what $a$ is. When $a\ge 2$, each residue $\pmod{\tilde n}$ appears an even number of times, so $P_n\equiv 1\pmod n$ whenever $n=2^ap_1^{a_1}\ldots p_k^{a_k},\ k\ge 1,a\ge 2$. When $a=1$, $P_n$ gives $-1\pmod{\tilde n}$ if $k=1$, and $1\pmod{\tilde n}$ if $k\ge 2$, so $P_n\equiv -1\pmod n$ if $k=1$, and $1\pmod n$ if $k\ge 2$. Case 3: n is a power of $2$ If $n=2$, then the answer is $1$, if $n=4$ it's $-1$, and if $n=2^a,a\ge 3$, then we have $P_n\equiv 1\cdot(-1)\cdot(2^{a-1}-1)\cdot(2^{a-1}+1)\pmod{2^a}$, so $P_n\equiv 1\pmod n$. I hope it's Ok.

Let $p$ be an odd prime and $n$ a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length $p^{n}$. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by $p^{n+1}$. Proposed by Alexander Ivanov, Bulgaria

Click for solution there seems to be one here who wants to solve it... i didn't really want to post the solution i found in oberwolfach because it's so long... but here it goes: Consider the 8 given points as the vertices of a $K_8$ and color an edge $AB$ in color 1 if $AB^2$ is not divisible by $p$, in color 2 if $AB^2$ is divisible by $p$, but not by $p^{n+1}$ and in color 3 if $AB^2$ is divisible by $p^{n+1}$. If the statement is wrong, there is no triangle of color (3,3,3). Let $A,B$ be two of the 8 points, let $O$ be the center of the circle and let $R=\frac{p^n}2$. We know by the cosine theorem that $AB^2=2R^2(1-\cos \gamma)$ where $\gamma=\sphericalangle AOB$. Therefore $\cos \gamma$ is a rational number which has at most $p^{2n}$ in the denominator. Now, add an additional point $C$ and let $\alpha=\sphericalangle BOC, \beta=\sphericalangle COA$. We know that $2\cos \alpha \cos \beta \cos \gamma=1-\cos ^2 \alpha - \cos ^2 \beta - \cos ^2 \gamma$. Therefore $v_p(\cos \alpha) + v_p(\cos \beta) + v_p(\cos \gamma) \geq 2\min \{ v_p(\cos \alpha), v_p(\cos \beta), v_p(\cos \gamma) \}$ (here $v_p(x)$ denotes the $p$-adic valuation; it is clear that $v_p(\cos \alpha) \leq 0$). Wlog assume that $v_p(\cos \alpha)$ is minimal. then we know that $v_p(\cos \beta) + v_p(\cos \gamma)\geq v_p(\cos \alpha)$; if $v_p(\cos \beta),v_p(\cos \gamma) > v_p(\cos \alpha)$ we even have equality. This shows that triangles of color (1,1,1), (1,1,2), (2,2,2) and (1,3,3) may not exist. If there were no triangles of color (1,1,3), every triangle would contain an edge of color 2 and an edge of color 1 or 3 - this is impossible as there has to be in conclusion a triangle consisting only of color 2 or only of color 1 or 3(this was true even in any 6-element subset of the 8 points); therefore we have a triangle $ABC$ of color (1,1,3). Then wlog we have $v_p(\cos \alpha)=v_p(\cos \beta)=-2n$; it follows that $v_p(\cos \gamma)=0$, therefore $\cos \gamma$ is an integer. it may not be 1; therefore it is 0 or -1; but 0 is not possible since in that case we had $AB^2=\frac{p^{2n}}2$ which is not an integer. Therefore $AB$ is a diameter; summing up, all triangles of color (1,1,3) include a diameter. From now on, fix a diameter $AB$ and $C$ such that $AC$ and $BC$ have color 1. If for all $D,E\neq A,B$ we had that $DE$ is of color 2 or 3, there would necessarily be a triangle of color (2,2,2) or color (3,3,3), contradiction. Therefore we have some $DE$ of color 1. If, say $D=C$, then $ACE$ is of color (1,1,*), therefore of color (1,1,3), which means that AE is a diameter and it follows that $E=B$, contradiction; analogously for $E=C$. To finish, consider the cyclic quadrilateral $ACDE$. By the ptolemaus theorem, we know that $\pm AC\cdot DE \pm AE\cdot CD \pm AD\cdot CE=0$ with suitably chosen signs. This implies $(- AC^2\cdot DE^2 + AE^2\cdot CD^2 + AD^2\cdot CE^2)^2=4AD^2\cdot AE^2\cdot CD^2\cdot CE^2$. Now, look at both sides $\mod p$ to get a contradiction(remember that we just showed that $v_p(CD^2)>0, v_p(CE^2)>0$; but we know that $v_p(AC^2\cdot DE^2)=0$ and $v_p(AD^2\cdot CD^2)>0$ as the triangle $ACD$ may not be of color (1,1,1)). QED

Let $n \geq 3$ be an integer. Let $t_1$, $t_2$, ..., $t_n$ be positive real numbers such that \[n^2 + 1 > \left( t_1 + t_2 + \cdots + t_n \right) \left( \frac{1}{t_1} + \frac{1}{t_2} + \cdots + \frac{1}{t_n} \right).\] Show that $t_i$, $t_j$, $t_k$ are side lengths of a triangle for all $i$, $j$, $k$ with $1 \leq i < j < k \leq n$.

Click for solution solution by induction: the hardest part is to show that it works for n=3. so assume $t_1\geq t_2\geq t_3$. it is easy to see that the right is strictly increasing in $t_3$. so if we show that the reverse inequality holds for $t_1=t_2+t_3$, we are done. a quick calculation is enough to show that(it is too boring to post). but if we know is true for n-1, then let's do the following computation: $((t_1+...+t_{n-1})+t_n)(\frac{1}{t_1}+...+\frac{1}{t_{n-1}}+\frac{1}{t_n})\geq (t_1+...+t_{n-1})(\frac{1}{t_1}+...+\frac{1}{t_{n-1}})+2n-1$, by AM-GM and AM-HM. so we get the inequality reduces to that one for n-1 variables. Peter

Let $a_0$, $a_1$, $a_2$, ... be an infinite sequence of real numbers satisfying the equation $a_n=\left|a_{n+1}-a_{n+2}\right|$ for all $n\geq 0$, where $a_0$ and $a_1$ are two different positive reals. Can this sequence $a_0$, $a_1$, $a_2$, ... be bounded? Proposed by Mihai Bălună, Romania

Does there exist a function $s\colon \mathbb{Q} \rightarrow \{-1,1\}$ such that if $x$ and $y$ are distinct rational numbers satisfying ${xy=1}$ or ${x+y\in \{0,1\}}$, then ${s(x)s(y)=-1}$? Justify your answer. Proposed by Dan Brown, Canada

Click for solution Where did you find this problem? It is realy interesting. I believe the answer to be 'yes', and I think I have a way of constructing the function, but it's only verified empirically, and I haven't fixed my ideas well enough to provide a full proof. Here's what I thought we could do: It suffices to determine the function on the positive rationals, of course, so let's restrict our attention to those. Construct the Stern-Brocot tree step by step. At each step, to each leaf you attach a leaf to the left and a leaf to the right. Label the leaf to the left with $-1$ and the leaf to the right with $1$. It seems to work.

Find all polynomials $f$ with real coefficients such that for all reals $a,b,c$ such that $ab+bc+ca = 0$ we have the following relations \[ f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c). \]

Click for solution A reasonably clean solution: We want to find all polynomials f such that $f(a-b)+f(b-c)+f(c-a)=2f(a+b+c)$ whenever $ab+bc+ca=0$. Equivalently, $ab+bc+ca$ divides $f(a-b)+f(b-c)+f(c-a)-2f(a+b+c)$. Let $f(x)=r_nx^n+r_{n-1}x^{n-1}+...+r_0$ and $a'=ta,b'=tb,c'=tc$ Then $a'b'+b'c'+c'a'=0$ if $ab+bc+ca=0$ so $t^nr_n((a-b)^n+(b-c)^n+(c-a)^n-2(a+b+c)^n)+...+r_0(1+1+1-2)=0$ The functions of t $t^n,t^{n-1},...,1$ are linearly independent, so each coefficient $r_k((a-b)^k+(b-c)^k+(c-a)^k-2(a+b+c)^k)$ must be zero. This means that either $r_k=0$ or $ab+bc+ca$ divides $(a-b)^k+(b-c)^k+(c-a)^k-2(a+b+c)^k$ For $k=2$, $(a-b)^2+(b-c)^2+(c-a)^2-2(a+b+c)^2=-4(ab+bc+ca)$ For $k=4$, $(a-b)^4+(b-c)^4+(c-a)^4-2(a+b+c)^4= -6(ab+bc+ca)(2a^2+2b^2+2c^2+ab+bc+ca)$ Consider the case $a=2,b=2,c=-1$. Then $(-3)^k+(-3)^k=2*3^k$ This forces k to be even. Now take $a=6,b=3,c=-2$. This gives $3^k+5^k+(-8)^k=2*7^k$. Since $8^6>2*7^6$, $3^k+5^k+(-8)^k>2*7^k$ for all even $k>4$. By previous arguments, we must have $f(x)=dx^4+ex^2$

If $a$, $b$ ,$c$ are three positive real numbers such that $ab+bc+ca = 1$, prove that \[ \sqrt[3]{ \frac{1}{a} + 6b} + \sqrt[3]{\frac{1}{b} + 6c} + \sqrt[3]{\frac{1}{c} + 6a } \leq \frac{1}{abc}. \]

Find all functions $f:\mathbb{R} \to \mathbb{R}$ satisfying the equation \[ f(x^2+y^2+2f(xy)) = (f(x+y))^2. \] for all $x,y \in \mathbb{R}$.

Click for solution erdos wrote: Take $x=y=0$ and put $k=f(0)$ we get $f(2k)=k^2$ take $y=0$ we get $f(x^2+2k)=(f(x))^2=(f(-x))^2$ for all $x \in \mathbb R$ So for $x=k^2$ we get $f((-k)^2)=f(k^2)$ or $f((-k)^2)=-f(k^2)$ Suppose $f((-k)^2)=f(k^2)$, then take $x=y=k$ we get $f(2k^2+2f(k^2))=k^4$ now take $x=-y=k$ we get $f(2k^2+2f((-k)^2))=k^2$ so $k^4=k^2$ which means that $k \in \{0,-1,1\}$ we can check that $k=-1$ and $k=1$ are not possible cases. So $f(0)=0$ Take $y=0$ in the original functional equation we get $f(x^2)=(f(x))^2$ for all $x \in \mathbb R$ and this is has been solved before, we find that $f(x)=x$ for all $x \in \mathbb R$ Have I made a mistake somewhere ? for one thing, you're writing $ f((-k)^2) = f(k^2) $ or $ f((-k)^2) = -f(k^2) $ where you really mean $ f(-k^2) = f(k^2) $ or $ f(-k^2) = -f(k^2) $. and you're missing the case where $ f(-k^2) = -f(k^2) $

Let ${a_1,a_2,\dots,a_n}$ be positive real numbers, ${n>1}$. Denote by $g_n$ their geometric mean, and by $A_1,A_2,\dots,A_n$ the sequence of arithmetic means defined by \[ A_k=\frac{a_1+a_2+\cdots+a_k}{k},\qquad k=1,2,\dots,n. \] Let $G_n$ be the geometric mean of $A_1,A_2,\dots,A_n$. Prove the inequality \[ n \root n\of{\frac{G_n}{A_n}}+ \frac{g_n}{G_n}\le n+1 \] and establish the cases of equality. Proposed by Finbarr Holland, Ireland

Click for solution Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in $\LaTeX$. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions Bojan Basic wrote: Let \[m_k=\frac {A_{k-1}} {A_k}\] (suppose that $A_0=0$). Now it is obvious that \[\frac {a_k}{A_k}=\frac{kA_k-(k-1)A_{k-1}}{A_k}=k-(k-1)m_k\] We have: \[\sqrt[n]{\frac {G_n}{A_n}}=\sqrt[n^2]{m_2m_3^2\dots m_n^{n-1}}\] \[\frac {g_n}{G_n}=\sqrt[n]{\prod_{k=1}^n(k-(k-1)m_k)}\] Using AM-GM we obtain: \[n\sqrt[n^2]{1^{\frac{n(n+1)}2}m_2m_3^2\dots m_n^{n-1}}\leqslant \frac{\frac{n(n+1)} 2+\sum_{k=2}^n(k-1)m_k}n=\frac{n+1}2+\frac {\sum_{k=1}^n(k-1)m_k}n\] \[\sqrt[n]{\prod_{k=1}^n(k-(k-1)m_k)}\leqslant \frac{n+1} 2-\frac {\sum_{k=1}^n(k-1)m_k}n\] Summing the last two relations we get the desired inequality. Equality holds iff $a_1=a_2=\dots=a_n$.

There are $10001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There are a total of $k$ societies. Suppose that the following conditions hold: i.) Each pair of students are in exactly one club. ii.) For each student and each society, the student is in exactly one club of the society. iii.) Each club has an odd number of students. In addition, a club with ${2m+1}$ students ($m$ is a positive integer) is in exactly $m$ societies. Find all possible values of $k$. Proposed by Guihua Gong, Puerto Rico

Click for solution Easy: Suppose $A$ belongs to clubs $C_1,C_2...C_a$, then in these clubs A apears in $\sum|C_i|-1$ pairs, so we get this sum is equal to $10000$. and since every of these clubs is in $\frac{|C_i|-1}{2}$ societies, $A$ appears in $5000$ societies. Now every Society contains $10001$ students, so we easily get, counting edges in the bypartite graph formed by students and societies, and an edge if a student goes in that society that $k=5000$

Let ${n}$ and $k$ be positive integers. There are given ${n}$ circles in the plane. Every two of them intersect at two distinct points, and all points of intersection they determine are pairwise distinct (i. e. no three circles have a common point). No three circles have a point in common. Each intersection point must be colored with one of $n$ distinct colors so that each color is used at least once and exactly $k$ distinct colors occur on each circle. Find all values of $n\geq 2$ and $k$ for which such a coloring is possible. Proposed by Horst Sewerin, Germany

The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge). Proposed by Norman Do, Australia

Click for solution For context, the following is the original wording found in the first post of this thread. ~dj In a country there are $n>3$ cities. We can add a street between $2$ cities $A$ and $B$, iff there exist $2$ cities $X$ and $Y$ different from $A$ and $B$ such that there is no street between $A$ and $X$, $X$ and $Y$, and $Y$ and $B$. Find the biggest number of streets one can construct! I'll restate it, so that it's exactly like in ISL 2004 . We are given a complete graph on $n$ vertices, and the only allowed operation is to find a $4$-cycle, pick one of its edges, and delete it. The question is: what is the minimal number of edges we're left with? (the answer to the problem from the TST is then obtained from that one by subtracting it from $\frac{n(n-1)}2$) I think the answer (to the reworded question) is $n$: I'm sure constructing n example with $n$ edges is not a problem, so I'll focus on proving that it's the minimal value. First of all (even though we could skip this part and go straight to showing that the minimal number is $n$), it's obvious that an operation does not disconnect the graph, so the minimal number of edges left is $\ge n-1$. What we have to show is that it cannot be $n-1$, i.e. that we can't be left with a tree in the end. Assuming that in the end we're left with a tree, there must be a moment when we destroy the last odd cycle. This can only be done if the edge we remove in the respective operation belongs to the cycle. A quick look through all the cases should show that getting rid of all the odd cycles like this is impossible (the cases being: the odd cycle our edge is on and the $4$-cycle necessary for the operation share precisely one edge, the one we remove, or $2$ edges, or $3$, and, when they share $2$ edges, the two edges could be adjacent or opposite in the $4$-cycle, so there are $4$ cases in total, all of them easy to check). Is it Ok?

Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value. Proposed by Marcin Kuczma, Poland

$A$ and $B$ play a game, given an integer $N$, $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$, but his number cannot be bigger than $N$. The player who writes $N$ wins. For which values of $N$ does $B$ win? Proposed by A. Slinko & S. Marshall, New Zealand

Click for solution If $N$ is odd $A$ wins. He first writes $1$, an odd number. If he writes an odd number $n$, both $n+1, 2n$ are even, so the number he gets is even and thus can make the +1 move, writing another odd number. Thus $B$ only writes even numbers and never $N$. Let $N=d_1d_2...d_k$ in binary, and suppose $N$ is even. Let $a_i=d_1d_2...d_{k-i+1}+1$. Partition the set ${1, 2, ..., N}$ into $S_1={N, N-1, ..., a_2}, S_2={a_2-1, ..., a_3}$, and so on. A move $n \rightarrow 2n$ always goes to the following subset. Now it is clear that if a player is the first to write a number in $S_1$, doing it by doubling the previous number, he wins (because he writes the even numbers from then on). If $X$ is the first to write a number in $S_2$, $Y$ will then jump to $S_1$ by a $n \rightarrow 2n$ move and win. So the first to write a number in $S_2$ loses. We have $S_2={d_1....d_{k-1}, ..., d_1...d_{k-2}+1}$. Clearly $d_1...d_{k-2}$ will be written, unless a player commits suicide, because the only way to skip it is to play a $n \rightarrow 2n$ move and that is losing. So for even $N$ the player who writes $d_1...d_{k-2}$ wins. Then the winner for the $d_1...d_k$ game is $A$ if $d_k=1$, and it is the same as for the $d_1...d_{k-2}$ game if $d_k=0$. If among $d_k, d_{k-2}, d_{k-4}$ and so on there's a $1$, the winner is $A$. If not, and if $k$ is even, the winner is the same as for $d_1d_2$, which is $A$ if $d_2=1$, and $B$ if $d_2=0$, by inspection. If $k$ is odd, the winner is either $A$ or the same as for $d_1d_2d_3$, which is always $A$ by inspection. We conclude that $B$ wins iff $N$ is the sum of distinct odd powers of 2.

For an ${n\times n}$ matrix $A$, let $X_{i}$ be the set of entries in row $i$, and $Y_{j}$ the set of entries in column $j$, ${1\leq i,j\leq n}$. We say that $A$ is golden if ${X_{1},\dots ,X_{n},Y_{1},\dots ,Y_{n}}$ are distinct sets. Find the least integer $n$ such that there exists a ${2004\times 2004}$ golden matrix with entries in the set ${\{1,2,\dots ,n\}}$.

Define a "hook" to be a figure made up of six unit squares as shown below in the picture, or any of the figures obtained by applying rotations and reflections to this figure. [asy][asy] unitsize(0.5 cm); draw((0,0)--(1,0)); draw((0,1)--(1,1)); draw((2,1)--(3,1)); draw((0,2)--(3,2)); draw((0,3)--(3,3)); draw((0,0)--(0,3)); draw((1,0)--(1,3)); draw((2,1)--(2,3)); draw((3,1)--(3,3)); [/asy][/asy] Determine all $ m\times n$ rectangles that can be covered without gaps and without overlaps with hooks such that - the rectangle is covered without gaps and without overlaps - no part of a hook covers area outside the rectangle.

Click for solution solution from Christian Sattler(Germany): first we define an involution on the hooks: send every hook to the one which includes the square where the hook goes around. it is clear that this is an involution, so the number of hooks is even. it immediately follows that 12 | mn. there are three cases(wlog 3 divides m): 3 divides m and 4 divides n(trivial since we can do 3x4-rectangles), 12 divides m, then n can be arbritarily, but not equal to 1,2 or 5(it is clear that n is not 1,2, and 5 is easy to exclude. in all other cases we may write n as linear combination of 3 and 4 with positive coefficients and we can use 3x4-rectangles again taking rows of 3x4-rectangles or 4x3-rectangles). so we are left with the case 6 | m and 2 | n. so look again at our involution: it shows that our hooks appear in pairs of the possible forms: either 3x4-rectangles or something similar to an S: .=== .=== ===. ===. now mark every second row. it is easy to see that there are always 6 out of the 12 squares of the S are marked, the same for horizontal 3x4-rectangles, but vertical 3x4-rectangles have either 4 or 8 squares marked, that shows that there's an even number of them. doing the same with columns, we get that the total number of 3x4-rectangles is even. now, look at the coloring of .==. =..= .==. =..= and periodic. it is easy to see that 6 out of 12 squares are marked at 3x4-rectangles, the S upright, the S turned by 90 degree and even distance to the left boundary of the rectangle, but 4 or 8 for an S turned by 90 degree with odd distance to the left boundary. this shows that there's an even number of them and by translating the coloring by 1 to the right and turning it all around, we get that the number of S is even as well. this shows that 24 is a divisor of mn, so we get one of the two other cases. i only found all solutions but couldn't prove that it are all. Peter

For a finite graph $G$, let $f(G)$ be the number of triangles and $g(G)$ the number of tetrahedra formed by edges of $G$. Find the least constant $c$ such that \[g(G)^3\le c\cdot f(G)^4\] for every graph $G$. Proposed by Marcin Kuczma, Poland