In the plane the points with integer coordinates are the vertices of unit squares. The squares are coloured alternately black and white (as on a chessboard). For any pair of positive integers $ m$ and $ n$, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $ m$ and $ n$, lie along edges of the squares. Let $ S_1$ be the total area of the black part of the triangle and $ S_2$ be the total area of the white part. Let $ f(m,n) = | S_1 - S_2 |$. a) Calculate $ f(m,n)$ for all positive integers $ m$ and $ n$ which are either both even or both odd. b) Prove that $ f(m,n) \leq \frac 12 \max \{m,n \}$ for all $ m$ and $ n$. c) Show that there is no constant $ C\in\mathbb{R}$ such that $ f(m,n) < C$ for all $ m$ and $ n$.

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.

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 \geq 1$ vectors the number of maximal subsets is less than or equal to $ 2n.$

An $ n \times n$ matrix whose entries come from the set $ S = \{1, 2, \ldots , 2n - 1\}$ is called a silver matrix if, for each $ i = 1, 2, \ldots , n$, the $ i$-th row and the $ i$-th column together contain all elements of $ S$. Show that: (a) there is no silver matrix for $ n = 1997$; (b) silver matrices exist for infinitely many values of $ n$.

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.

(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.\]

The lengths of the sides of a convex hexagon $ ABCDEF$ satisfy $ AB = BC$, $ CD = DE$, $ EF = FA$. Prove that: \[ \frac {BC}{BE} + \frac {DE}{DA} + \frac {FA}{FC} \geq \frac {3}{2}. \]

It is known that $ \angle BAC$ is the smallest angle in the triangle $ ABC$. The points $ B$ and $ C$ divide the circumcircle of the triangle into two arcs. Let $ U$ be an interior point of the arc between $ B$ and $ C$ which does not contain $ A$. The perpendicular bisectors of $ AB$ and $ AC$ meet the line $ AU$ at $ V$ and $ W$, respectively. The lines $ BV$ and $ CW$ meet at $ T$. Show that $ AU = TB + TC$. Alternative formulation: 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,$ and $ CT$ is the sum of the lengths of the other two.

Click for solution I note $x=m(\widehat {BAU}),y=m(\widehat {CAU})$. Thus, $m(\widehat {BTC})=2(x+y)=2A$ and $\frac{TB}{\sin (C-y)}=\frac{TC}{\sin (B-x)}=\frac{a}{\sin 2A}=\frac{R}{\cos A}\Longrightarrow$ $TB+TC=\frac{R}{\cos A}\cdot [\sin (B-x)+\sin (C-y)]=$ $=2R\cdot \cos \frac{B-C-x+y}{2}=2R\sin (C+x)=AU.$

Let $ A_1A_2A_3$ be a non-isosceles 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 circumcentres of the triangles $ A_1 B_1I,A_2B_2I,A_3B_3I$ are collinear.

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 \leq F(c) \leq k$ for each $ c\in \{0,1,\ldots,k + 1\}$, then $ F(0) = F(1) = \ldots = F(k + 1)$.

Let $ P(x)$ be a polynomial with real coefficients such that $ P(x) > 0$ for all $ x \geq 0.$ Prove that there exists a positive integer n such that $ (1 + x)^n \cdot P(x)$ is a polynomial with nonnegative coefficients.

Let $ p$ be a prime number and $ f$ an integer polynomial of degree $ d$ such that $ f(0) = 0,f(1) = 1$ and $ f(n)$ is congruent to $ 0$ or $ 1$ modulo $ p$ for every integer $ n$. Prove that $ d\geq p - 1$.

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.$

Let $ b, m, n$ be positive integers such that $ b > 1$ and $ m \neq n.$ Prove that if $ b^m - 1$ and $ b^n - 1$ have the same prime divisors, then $ b + 1$ is a power of 2.

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.

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 circumcentre of the triangle, respectively. Prove that the points $ D, E,$ and $ I$ are collinear if and only if the points $ P, Q,$ and $ O$ are collinear.

Find all pairs $ (a,b)$ of positive integers that satisfy the equation: $ a^{b^2} = b^a$.

Click for solution I think I got this... hopefully... We find the solutions (1, 1), (27, 3), and (16, 2), and we claim that no others exist. First of all, a and b must have the same ratios of prime factors, so one must divide the other. Note also that if b = xa, x > 1, then $a^{x^2a^2} = (xa)^a \implies a^{x^2a} = xa \implies a^{x^2a - 1} = x$ Since x > 1, $a \ge 2$. If x = 2, then $a^{2^2a-1} \ge 2^{2 \cdot 2^2-1} = 2^7 > 2$. Then we can show easily by induction that if x > 2, $a^{x^2a-1} > x$. We now deal with the case $a \ge b$. If $a = b$, $a^{a^2} = a^a \implies a = 1$ gives us the solution (1, 1). Let $a = kb, k > 1$. $(kb)^{b^2} = b^{kb}$ $k^{b^2} = b^{kb-b^2}$ $k^b = b^{k-b}$ Note that $k-b > 0 \implies k > b \implies b | k$. Let $k = mb$. $(mb)^b = b^{(m-1)b}$ $mb = b^{m-1}$ $m = b^{m-2}$ Now test cases m = 1, 2, 3, 4. It turns out that m = 3, b = 3 works, giving us the solution (27, 3), and m = 4, b = 2 works, giving us the solution (16, 2). If m = 5, since $b \ge 2$, we have $b^{5-2} \ge 8 > 5$. From there on, it is easy to see by induction that $b^{m-2} > m$, so no other solutions exist.

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.$

Let $ a_1\geq \cdots \geq a_n \geq a_{n + 1} = 0$ be real numbers. Show that \[ \sqrt {\sum_{k = 1}^n a_k} \leq \sum_{k = 1}^n \sqrt k (\sqrt {a_k} - \sqrt {a_{k + 1}}). \] Proposed by Romania

Let $ ABC$ be a triangle. $ D$ is a point on the side $ (BC)$. The line $ AD$ meets the circumcircle again at $ X$. $ P$ is the foot of the perpendicular from $ X$ to $ AB$, and $ Q$ is the foot of the perpendicular from $ X$ to $ AC$. Show that the line $ PQ$ is a tangent to the circle on diameter $ XD$ if and only if $ AB = AC$.

Let $ x_1$, $ x_2$, $ \ldots$, $ x_n$ be real numbers satisfying the conditions: \[ \left\{\begin{array}{cccc} |x_1 + x_2 + \cdots + x_n | & = & 1 & \ \\ |x_i| & \leq & \displaystyle \frac {n + 1}{2} & \ \textrm{ for }i = 1, 2, \ldots , n. \end{array} \right. \] Show that there exists a permutation $ y_1$, $ y_2$, $ \ldots$, $ y_n$ of $ x_1$, $ x_2$, $ \ldots$, $ x_n$ such that \[ | y_1 + 2 y_2 + \cdots + n y_n | \leq \frac {n + 1}{2}. \]

Does there exist functions $ f,g: \mathbb{R}\to\mathbb{R}$ such that $ f(g(x)) = x^2$ and $ g(f(x)) = x^k$ for all real numbers $ x$ a) if $ k = 3$? b) if $ k = 4$?

Let $ ABCD$ be a convex quadrilateral. The diagonals $ AC$ and $ BD$ intersect at $ K$. Show that $ ABCD$ is cyclic if and only if $ AK \sin A + CK \sin C = BK \sin B + DK \sin D$.

For each positive integer $ n$, let $ f(n)$ denote the number of ways of representing $ n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $ f(4) = 4$, because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1. Prove that, for any integer $ n \geq 3$ we have $ 2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}$.

Let $ X,Y,Z$ be the midpoints of the small arcs $ BC,CA,AB$ respectively (arcs of the circumcircle of $ ABC$). $ M$ is an arbitrary point on $ BC$, and the parallels through $ M$ to the internal bisectors of $ \angle B,\angle C$ cut the external bisectors of $ \angle C,\angle B$ in $ N,P$ respectively. Show that $ XM,YN,ZP$ concur.

For every integer $ n \geq 2$ determine the minimum value that the sum $ \sum^n_{i=0} a_i$ can take for nonnegative numbers $ a_0, a_1, \ldots, a_n$ satisfying the condition $ a_0 = 1,$ $ a_i \leq a_{i+1} + a_{i+2}$ for $ i = 0, \ldots, n - 2.$