Olympiad problems

2004 Germany Team Selection Test, 2

Tags: geometry , combinatorial geometry , polygon , Extremal combinatorics , right angle , angles , IMO Shortlist

Let $n \geq 5$ be a given integer. Determine the greatest integer $k$ for which there exists a polygon with $n$ vertices (convex or not, with non-selfintersecting boundary) having $k$ internal right angles. [i]Proposed by Juozas Juvencijus Macys, Lithuania[/i]

2006 IMO Shortlist, 2

Tags: combinatorics , polygon , Extremal combinatorics , IMO , IMO 2006 , IMO Shortlist , Dusan Djukic

Let $P$ be a regular $2006$-gon. A diagonal is called [i]good[/i] if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$. The sides of $P$ are also called [i]good[/i]. Suppose $P$ has been dissected into triangles by $2003$ diagonals, no two of which have a common point in the interior of $P$. Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

1986 IMO, 3

Tags: graph theory , combinatorics , IMO , Coloring , Ramsey Theory , Extremal combinatorics , IMO 1986

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?

2018 Thailand TST, 1

Tags: combinatorics , IMO Shortlist , Strings , sorting , distance , Extremal combinatorics , radius

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with exactly $n$ occurrences of each of the letters $a, b,$ and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$ , there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.

1964 IMO, 4

Tags: combinatorics , Ramsey Theory , Coloring , graph theory , IMO , IMO 1964 , Extremal combinatorics

Seventeen people correspond by mail with one another-each one with all the rest. In their letters only three different topics are discussed. each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

2010 Germany Team Selection Test, 1

Tags: combinatorics , Extremal combinatorics , IMO Shortlist

For any integer $n\geq 2$, let $N(n)$ be the maxima number of triples $(a_i, b_i, c_i)$, $i=1, \ldots, N(n)$, consisting of nonnegative integers $a_i$, $b_i$ and $c_i$ such that the following two conditions are satisfied: [list][*] $a_i+b_i+c_i=n$ for all $i=1, \ldots, N(n)$, [*] If $i\neq j$ then $a_i\neq a_j$, $b_i\neq b_j$ and $c_i\neq c_j$[/list] Determine $N(n)$ for all $n\geq 2$. [i]Proposed by Dan Schwarz, Romania[/i]

2011 IMO Shortlist, 7

Tags: inequalities , combinatorics , IMO Shortlist , Extremal combinatorics

On a square table of $2011$ by $2011$ cells we place a finite number of napkins that each cover a square of $52$ by $52$ cells. In each cell we write the number of napkins covering it, and we record the maximal number $k$ of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value of $k$? [i]Proposed by Ilya Bogdanov and Rustem Zhenodarov, Russia[/i]

1966 IMO Longlists, 45

Tags: combinatorics , maximization , Extremal combinatorics , Combinatorics of words , IMO Shortlist , IMO Longlist

An alphabet consists of $n$ letters. What is the maximal length of a word if we know that any two consecutive letters $a,b$ of the word are different and that the word cannot be reduced to a word of the kind $abab$ with $a\neq b$ by removing letters.

1977 IMO Longlists, 57

Tags: linear algebra , algebra , Sequence , maximization , Extremal combinatorics , IMO , IMO 1977

In a finite sequence of real numbers the sum of any seven successive terms is negative and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.

2008 Germany Team Selection Test, 3

Tags: combinatorics , combinatorial geometry , polygon , Extremal combinatorics , IMO Shortlist

Given is a convex polygon $ P$ with $ n$ vertices. Triangle whose vertices lie on vertices of $ P$ is called [i]good [/i] if all its sides are unit length. Prove that there are at most $ \frac {2n}{3}$ [i]good[/i] triangles. [i]Author: Vyacheslav Yasinskiy, Ukraine[/i]

1983 IMO Shortlist, 14

Tags: arithmetic sequence , Extremal combinatorics , Ramsey Theory , Arithmetic Progression , IMO , IMO 1983 , combinatorics

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

2007 IMO Shortlist, 7

Tags: combinatorics , Set systems , Extremal combinatorics , IMO Shortlist

Let $ \alpha < \frac {3 \minus{} \sqrt {5}}{2}$ be a positive real number. Prove that there exist positive integers $ n$ and $ p > \alpha \cdot 2^n$ for which one can select $ 2 \cdot p$ pairwise distinct subsets $ S_1, \ldots, S_p, T_1, \ldots, T_p$ of the set $ \{1,2, \ldots, n\}$ such that $ S_i \cap T_j \neq \emptyset$ for all $ 1 \leq i,j \leq p$ [i]Author: Gerhard Wöginger, Austria[/i]

1991 IMO, 3

Tags: combinatorics , IMO , Extremal combinatorics , Set systems , relatively prime , imo 1991

Let $ S \equal{} \{1,2,3,\cdots ,280\}$. Find the smallest integer $ n$ such that each $ n$-element subset of $ S$ contains five numbers which are pairwise relatively prime.

2016 EGMO, 3

Tags: combinatorics , EGMO , EGMO 2016 , Coloring , Extremal combinatorics

Let $m$ be a positive integer. Consider a $4m\times 4m$ array of square unit cells. Two different cells are [i]related[/i] to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are colored blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

2004 China Team Selection Test, 2

Tags: matrix , combinatorics , IMO , Ramsey Theory , Extremal combinatorics , IMO 2001 , IMO Shortlist

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

1983 IMO Longlists, 6

Tags: geometry , Ramsey Theory , combinatorics , Extremal combinatorics , right triangle , IMO , IMO 1983

Let $ABC$ be an equilateral triangle and $\mathcal{E}$ the set of all points contained in the three segments $AB$, $BC$, and $CA$ (including $A$, $B$, and $C$). Determine whether, for every partition of $\mathcal{E}$ into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

2002 Kazakhstan National Olympiad, 3

Tags: modular arithmetic , combinatorics , Extremal combinatorics , maximization , IMO Shortlist

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$, such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$, find the greatest value of $m$.

2010 Belarus Team Selection Test, 7.2

Tags: combinatorics , Extremal combinatorics , IMO Shortlist

For any integer $n\geq 2$, let $N(n)$ be the maxima number of triples $(a_i, b_i, c_i)$, $i=1, \ldots, N(n)$, consisting of nonnegative integers $a_i$, $b_i$ and $c_i$ such that the following two conditions are satisfied: [list][*] $a_i+b_i+c_i=n$ for all $i=1, \ldots, N(n)$, [*] If $i\neq j$ then $a_i\neq a_j$, $b_i\neq b_j$ and $c_i\neq c_j$[/list] Determine $N(n)$ for all $n\geq 2$. [i]Proposed by Dan Schwarz, Romania[/i]

1992 IMO Longlists, 10

Tags: combinatorics , Ramsey Theory , graph theory , IMO , IMO 1992 , Coloring , Extremal combinatorics

Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

1990 IMO Longlists, 9

Tags: number theory , partition , Ramsey Theory , Coloring , Extremal combinatorics , IMO Shortlist , Hi

Assume that the set of all positive integers is decomposed into $ r$ (disjoint) subsets $ A_1 \cup A_2 \cup \ldots \cup A_r \equal{} \mathbb{N}.$ Prove that one of them, say $ A_i,$ has the following property: There exists a positive $ m$ such that for any $ k$ one can find numbers $ a_1, a_2, \ldots, a_k$ in $ A_i$ with $ 0 < a_{j \plus{} 1} \minus{} a_j \leq m,$ $ (1 \leq j \leq k \minus{} 1)$.

1986 IMO Shortlist, 9

Tags: graph theory , combinatorics , IMO , Coloring , Ramsey Theory , Extremal combinatorics , IMO 1986

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?

1983 IMO, 1

Tags: geometry , Ramsey Theory , combinatorics , Extremal combinatorics , right triangle , IMO , IMO 1983

Let $ABC$ be an equilateral triangle and $\mathcal{E}$ the set of all points contained in the three segments $AB$, $BC$, and $CA$ (including $A$, $B$, and $C$). Determine whether, for every partition of $\mathcal{E}$ into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

1997 Nordic, 1

Tags: combinatorics , maximization , triplets , Extremal combinatorics

Let $A$ be a set of seven positive numbers. Determine the maximal number of triples $(x, y, z)$ of elements of $A$ satisfying $x < y$ and $x + y = z$.

2012 IMO Shortlist, C3

Tags: combinatorics , matrix , Extremal combinatorics , IMO Shortlist

In a $999 \times 999$ square table some cells are white and the remaining ones are red. Let $T$ be the number of triples $(C_1,C_2,C_3)$ of cells, the first two in the same row and the last two in the same column, with $C_1,C_3$ white and $C_2$ red. Find the maximum value $T$ can attain. [i]Proposed by Merlijn Staps, The Netherlands[/i]

1983 IMO, 2

Tags: arithmetic sequence , Extremal combinatorics , Ramsey Theory , Arithmetic Progression , IMO , IMO 1983 , combinatorics

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?