Some Olympiad Problems

This page contains some interesting problems, mainly of combinatorial nature, from various Olympiads. I have included the problems which I found particularly interesting or hard or both. Solution to each problem can be seen by clicking on the link provided at the end of each problem. Any comments, clarifications and questions are welcome.

Problem. Prove that for any natural number $n$, the number $\binom{2n}{n}$ divides the least common multiple of $1.2, 3, \ldots, 2n$. [Solution]

Problem. (IMO 2001) Twenty one boys and twenty one girls took part in a mathematics competition. (1) Each contestant solved at most 6 problems. (2) For each girl and each boy at least one problem was solved by both of them. Prove that there was a problem solved by at least three boys and at least three girls. [Solution]

Problem. Let $f:\N\to \N$ be a bijection. Then show that there are natural numbers $a$ and $d$ such that $f(a) < f(a+d) < f(a+2d)$. [Solution]

Problem. Consider a sequence of N integers consisting of n distinct integers. Prove that if $N\geq 2^n$ then there is a consecutive block of integers whose product is a perfect square. [Solution]

Problem. A $6\times 6$ square is covered by $1\times 2$ dominoes without overlap. Prove that the square can be cut along a single line parallel to its sides so that none of the dominoes will be damaged. [Solution]

Problem. Let $A$ be a non-empty finite set and $P(A)$ be the power ser of $A$. Let $f:P(A)\to P(A)$ be an increasing function (meaning $X\subseq Y \implies f(X)\subseteq f(Y)$.) Prove that there is a $T$ in $P(A)$ such that $f(T) = T$. [Solution]

Problem. The set of all the natural numbers is partitioned into $n$ arithmetic progressions. Prove that there is at least one of these arithmetic progressions in which the first term is divisible by the common difference. Further show that if $r_1, \ldots, r_n$ are the common differences of these arithmetic progressions then $1/r_1 + \cdots + 1/r_n = 1$. [Solution]

Problem. Let $k$ be a positive integer and $n=2^{k-1}$. Prove that for any given set of $2n-1$ integers one can select $n$ integers such that their sum is divisible by $n$. [Solution]

Problem. Finitely many cards are placed in two stacks with more cards kept on the left stack than the right. Each card has one or more names written on it, although different cards may share some names. For each name we define a *shuffle* by moving every card that has name written on it to the opposite stack. Prove that it is possible to end with more cards in the right stack by picking up several distinct names and then doing in turn the shuffle corresponding to each name. [Solution]