OIM 2009

Given a positive integer $n\geq 2$ , consider a set of $n$ islands arranged in a circle. Between every two neigboring islands two bridges are built as shown in the figure.

Starting at the island $X_1$ , in how many ways one can one can cross the $2n$ bridges so that no bridge is used more than once?

Attachments:

Let $C_1$ and $C_2$ be two congruent circles centered at $O_1$ and $O_2$ , which intersect at $A$ and $B$ . Take a point $P$ on the arc $AB$ of $C_2$ which is contained in $C_1$ . $AP$ meets $C_1$ at $C$ , $CB$ meets $C_2$ at $D$ and the bisector of $\angle CAD$ intersects $C_1$ and $C_2$ at $E$ and $L$ , respectively. Let $F$ be the symmetric point of $D$ with respect to the midpoint of $PE$ . Prove that there exists a point $X$ satisfying $\angle XFL = \angle XDC = 30^\circ$ and $CX = O_1O_2$ . Author: Arnoldo Aguilar (El Salvador)

Given a triangle $ABC$ of incenter $I$ , let $P$ be the intersection of the external bisector of angle $A$ and the circumcircle of $ABC$ , and $J$ the second intersection of $PI$ and the circumcircle of $ABC$ . Show that the circumcircles of triangles $JIB$ and $JIC$ are respectively tangent to $IC$ and $IB$ .

Consider the sequence $\{a_n\}_{n\geq1}$ defined as follows: $a_1 = 1$ , $a_{2k} = 1 + a_k$ and $a_{2k + 1} = \frac {1}{a_{2k}}$ for every $k\geq 1$ . Prove that every positive rational number appears on the sequence $\{a_n\}$ exactly once.

Six thousand points are marked on a circle, and they are colored using 10 colors in such a way that within every group of 100 consecutive points all the colors are used. Determine the least positive integer $k$ with the following property: In every coloring satisfying the condition above, it is possible to find a group of $k$ consecutive points in which all the colors are used.