CMO 2008

$A B C D$ is a convex quadrilateral in which $A B$ is the longest side. Points $M$ and $N$ are located on sides $A B$ and $B C$ respectively, so that each of the segments $A N$ and $C M$ divides the quadrilateral into two parts of equal area. Prove that the segment $M N$ bisects the diagonal $B D$.

Determine all functions $f$ defined on the set of rationals that take rational values for which

$$f(2 f(x)+f(y))=2 x+y$$

for each $x$ and $y$.

Let $a, b, c$ be positive real numbers for which $a+b+c=1$. Prove that

$$\frac{a-b c}{a+b c}+\frac{b-c a}{b+c a}+\frac{c-a b}{c+a b} \leq \frac{3}{2} .$$

Find all functions $f$ defined on the natural numbers that take values among the natural numbers for which

$$(f(n))^{p} \equiv n \bmod f(p)$$

for all $n \in \mathbf{N}$ and all prime numbers $p$.

A self-avoiding rook walk on a chessboard (a rectangular grid of squares) is a path traced by a sequence of rook moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook's path is non-self-intersecting.

Let $R(m, n)$ be the number of self-avoiding rook walks on an $m \times n$ ( $m$ rows, $n$ columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, $R(m, 1)=1$ for all natural numbers $m ; R(2,2)=2 ; R(3,2)=4 ; R(3,3)=11$. Find a formula for $R(3, n)$ for each natural number $n$.