USAMO Practice Session April 26, 2001

1. (Bulgaria, 1997) Two ordered $n$-tuples $(a_1, \dots, a_n)$ and $(b_1, \dots, b_n)$ are separated if each $n$-tuple consists of $n$ distinct elements of $\{1, \dots, n+1\}$, and there exist indices $i \neq j$ such that $a_i = b_j$. Find the maximum number of $n$-tuples such that any two of them are separated.
2. (China, 1997) Let $a_1, a_2, \dots$ be nonnegative real numbers such that
   $$a_{n+m} \leq a_n + a_m \qquad(m,n \in \mathbb{N}).$$
   Prove that
   $$a_n \leq ma_1 + \left( \frac{n}{m} - 1 \right) a_m$$
   for all $n \geq m$.
3. (Czech/Slovak, 1997) Show that there exists an increasing sequence $\{a_n\}_{n=1}^\infty$ of natural numbers such that for any $k \geq 0$, the sequence $\{k+a_n\}$ contains only finitely many primes.
4. (Iran, 1997) Suppose $w_1, \dots, w_k$ are distinct real numbers with nonzero sum. Prove that there exist integers $n_1, \dots, n_k$ such that $n_1w_1 + \cdots + n_kw_k > 0$, but for any permutation $\sigma$ of $\{1, \dots, n\}$ besides the identity permutation, we have $n_1 w_{\sigma(1)} + \cdots + n_k w_{\sigma(k)} < 0$.
5. (Iran, 1997) Suppose $f: \mathbb{R}^+ \to \mathbb{R}^+$ is a decreasing function such that for all $x,y \in \mathbb{R}^+$,
   $$f(x+y) + f(f(x)+f(y)) = f(f(x+f(y)) + f(y+f(x))).$$
   Prove that $f(f(x)) = x$.
6. (Romania, 1997) Let $P$ be the set of points in the plane and $D$ the set of lines in the plane. Determine whether there exists a bijective function $f: P \to D$ such that for any three collinear points $A,B,C$, the lines $f(A), f(B), f(C)$ are either parallel or concurrent.
7. (Russia, 1997) On an $m \times n$ checkerboard, where $m$ and $n$ are odd integers, are placed $1 \times 2$ dominoes so as to exactly cover all of the squares of the board except one corner square. It is permitted to slide a domino towards the empty square, thus exposing another square. Show that by a sequence of moves, any corner square of the board can be uncovered.
8. (South Korea, 1997) In an acute triangle $ABC$ with $AB \neq AC$, let $V$ be the intersection of the angle bisector of $A$ with $BC$, and let $D$ be the foot of the perpendicular from $A$ to $BC$. If $E$ and $F$ are the intersections of the circumcircle of $AVD$ with $CA$ and $AB$, respectively, show that the lines $AD$, $BE$, $CF$ are concurrent.
9. (Taiwan, 1997) Let $k = 2^{2^n}+1$ for some positive integer $n$. Show that $k$ is a prime if and only if $k$ divides $3^{(k-1)/2}+1$.
10. (Turkey, 1997) In a soccer league, when a player moves from a team $X$ with $x$ players to a team $y$ with $Y$ players, the federation receives $y-x$ million dollars from $Y$ if $y \geq x$, but pays $x-y$ million dollars to $X$ if $x>y$. There is no limit to the number of times a player may move during a season. The league consists of 18 teams, each of which begins a certain season with 20 players. At the end of the season, 12 teams end up with 20 players, while the other 6 end up with $16, 16, 21, 22, 22, 23$ players, respectively. What is the maximum amout the federation could have earned during the season?