(BLR) IMO1. An infinite square grid is colored in the chessboard pattern. For any pair of positive integers $m,n$ consider a right-angled triangle whose vertices are grid points and whose legs, of lengths $m$ and $n$, run along the lines of the grid. Let $S_b$ be the total area of the black part of the triangle and $S_w$ the total area of its white part. Define the function $f(m,n)=|S_b-S_w|$.
(a) Calculate $f(m,n)$ for all $m,n$ that have the same parity.
(b) Prove that $f(m,n)\le\frac12\max(m,n)$.
(c) Show that $f(m,n)$ is not bounded from above.
(CAN) Let $R_1,R_2,\ldots$ be the family of finite sequences of positive integers defined by the following rules: $R_1=(1)$, and if $R_{n-1}=(x_1,\ldots,x_s)$, then
$$R_n=(1,2,\ldots,x_1,1,2,\ldots,x_2,\ldots,1,2,\ldots,x_s,n).$$
For example, $R_2=(1,2)$, $R_3=(1,1,2,3)$, $R_4=(1,1,1,2,1,2,3,4)$. Prove that if $n>1$, then the $k$th term from the left in $R_n$ is equal to $1$ if and only if the $k$th term from the right in $R_n$ is different from $1$.
(GER) For each finite set $U$ of nonzero vectors in the plane we define $l(U)$ to be the length of the vector that is the sum of all vectors in $U$. Given a finite set $V$ of nonzero vectors in the plane, a subset $B$ of $V$ is said to be maximal if $l(B)$ is greater than or equal to $l(A)$ for each nonempty subset $A$ of $V$.
(a) Construct sets of $4$ and $5$ vectors that have $8$ and $10$ maximal subsets respectively.
(b) Show that for any set $V$ consisting of $n\ge1$ vectors, the number of maximal subsets is less than or equal to $2n$.
(IRN) IMO4. An $n\times n$ matrix with entries from $\{1,2,\ldots,2n-1\}$ is called a coveralls matrix if for each $i$ the union of the $i$th row and the $i$th column contains $2n-1$ distinct entries. Show that:
(a) There exist no coveralls matrices for $n=1997$.
(b) Coveralls matrices exist for infinitely many values of $n$.
(ROM) Let $ABCD$ be a regular tetrahedron and $M,N$ distinct points in the planes $ABC$ and $ADC$ respectively. Show that the segments $MN,BN,MD$ are the sides of a triangle.
(IRE) (a) Let $n$ be a positive integer. Prove that there exist distinct positive integers $x,y,z$ such that
$$x^{n-1}+y^n=z^{n+1}.$$
(b) Let $a,b,c$ be positive integers such that $a$ and $b$ are relatively prime and $c$ is relatively prime either to $a$ or to $b$. Prove that there exist infinitely many triples $(x,y,z)$ of distinct positive integers $x,y,z$ such that
$$x^a+y^b=z^c.$$
Original formulation: Let $a,b,c,n$ be positive integers such that $n$ is odd and $ac$ is relatively prime to $2b$. Prove that there exist distinct positive integers $x,y,z$ such that
(i) $x^a+y^b=z^c$, and
(ii) $xyz$ is relatively prime to $n$.
(RUS) Let $ABCDEF$ be a convex hexagon such that $AB=BC$, $CD=DE$, $EF=FA$. Prove that
$$\frac{BC}{BE}+\frac{DE}{DA}+\frac{FA}{FC}\ge\frac32.$$
When does equality occur?
(GBR) IMO2. Four different points $A,B,C,D$ are chosen on a circle $\Gamma$ such that the triangle $BCD$ is not right-angled. Prove that:
(a) The perpendicular bisectors of $AB$ and $AC$ meet the line $AD$ at certain points $W$ and $V$, respectively, and that the lines $CV$ and $BW$ meet at a certain point $T$.
(b) The length of one of the line segments $AD,BT,CT$ is the sum of the lengths of the other two.
Original formulation. In triangle $ABC$ the angle at $A$ is the smallest. A line through $A$ meets the circumcircle again at the point $U$ lying on the arc $BC$ opposite to $A$. The perpendicular bisectors of $CA$ and $AB$ meet $AU$ at $V$ and $W$, respectively, and the lines $CV,BW$ meet at $T$. Show that $AU=TB+TC$.
(USA) Let $A_1A_2A_3$ be a nonisosceles triangle with incenter $I$. Let $C_i$, $i=1,2,3$, be the smaller circle through $I$ tangent to $A_iA_{i+1}$ and $A_iA_{i+2}$ (the addition of indices being mod $3$). Let $B_i$, $i=1,2,3$, be the second point of intersection of $C_{i+1}$ and $C_{i+2}$. Prove that the circumcenters of the triangles $A_1B_1I,A_2B_2I,A_3B_3I$ are collinear.
(CZE) Find all positive integers $k$ for which the following statement is true:
If $F(x)$ is a polynomial with integer coefficients satisfying the condition
$$0\le F(c)\le k\quad\text{for each }c\in\{0,1,\ldots,k+1\},$$
then $F(0)=F(1)=\cdots=F(k+1)$.
(NET) Let $P(x)$ be a polynomial with real coefficients such that $P(x)>0$ for all $x\ge0$. Prove that there exists a positive integer $n$ such that $(1+x)^nP(x)$ is a polynomial with nonnegative coefficients.
(ITA) Let $p$ be a prime number and let $f(x)$ be a polynomial of degree $d$ with integer coefficients such that:
(i) $f(0)=0$, $f(1)=1$;
(ii) for every positive integer $n$, the remainder of the division of $f(n)$ by $p$ is either $0$ or $1$.
Prove that $d\ge p-1$.
(IND) In town $A$, there are $n$ girls and $n$ boys, and each girl knows each boy. In town $B$, there are $n$ girls $g_1,g_2,\ldots,g_n$ and $2n-1$ boys $b_1,b_2,\ldots,b_{2n-1}$. The girl $g_i$, $i=1,2,\ldots,n$, knows the boys $b_1,b_2,\ldots,b_{2i-1}$, and no others. For all $r=1,2,\ldots,n$, denote by $A(r),B(r)$ the number of different ways in which $r$ girls from town $A$, respectively town $B$, can dance with $r$ boys from their own town, forming $r$ pairs, each girl with a boy she knows. Prove that $A(r)=B(r)$ for each $r=1,2,\ldots,n$.
(IND) Let $b,m,n$ be positive integers such that $b>1$ and $m\ne n$. Prove that if $b^m-1$ and $b^n-1$ have the same prime divisors, then $b+1$ is a power of $2$.
(RUS) An infinite arithmetic progression whose terms are positive integers contains the square of an integer and the cube of an integer. Show that it contains the sixth power of an integer.
(BLR) In an acute-angled triangle $ABC$, let $AD,BE$ be altitudes and $AP,BQ$ internal bisectors. Denote by $I$ and $O$ the incenter and the circumcenter of the triangle, respectively. Prove that the points $D,E,I$ are collinear if and only if the points $P,Q,O$ are collinear.
(GBR) The altitudes through the vertices $A,B,C$ of an acute-angled triangle $ABC$ meet the opposite sides at $D,E,F$, respectively. The line through $D$ parallel to $EF$ meets the lines $AC$ and $AB$ at $Q$ and $R$, respectively. The line $EF$ meets $BC$ at $P$. Prove that the circumcircle of the triangle $PQR$ passes through the midpoint of $BC$.
(IRE) Let $a_1\ge\cdots\ge a_n\ge a_{n+1}=0$ be a sequence of real numbers. Prove that
$$\sqrt{\sum_{k=1}^n a_k}\le\sum_{k=1}^n\sqrt{k}(\sqrt{a_k}-\sqrt{a_{k+1}}).$$
(IRE) Let $D$ be an internal point on the side $BC$ of a triangle $ABC$. The line $AD$ meets the circumcircle of $ABC$ again at $X$. Let $P$ and $Q$ be the feet of the perpendiculars from $X$ to $AB$ and $AC$, respectively, and let $\gamma$ be the circle with diameter $XD$. Prove that the line $PQ$ is tangent to $\gamma$ if and only if $AB=AC$.