Olympiad problems

1978 IMO Shortlist, 10

An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.

2009 Germany Team Selection Test, 1

Tags: combinatorial geometry , rectangle , extremal combinatorics , combinatorics , geometry

In the plane we consider rectangles whose sides are parallel to the coordinate axes and have positive length. Such a rectangle will be called a [i]box[/i]. Two boxes [i]intersect[/i] if they have a common point in their interior or on their boundary. Find the largest $ n$ for which there exist $ n$ boxes $ B_1$, $ \ldots$, $ B_n$ such that $ B_i$ and $ B_j$ intersect if and only if $ i\not\equiv j\pm 1\pmod n$. [i]Proposed by Gerhard Woeginger, Netherlands[/i]

1979 IMO Shortlist, 5

Tags: graph theory , maximization , extremal graph theory , extremal combinatorics , number theory

Let $n \geq 2$ be an integer. Find the maximal cardinality of a set $M$ of pairs $(j, k)$ of integers, $1 \leq j < k \leq n$, with the following property: If $(j, k) \in M$, then $(k,m) \not \in M$ for any $m.$

2012 IMO Shortlist, C2

Tags: combinatorics , double counting , extremal combinatorics

Let $n \geq 1$ be an integer. What is the maximum number of disjoint pairs of elements of the set $\{ 1,2,\ldots , n \}$ such that the sums of the different pairs are different integers not exceeding $n$?

2010 Germany Team Selection Test, 1

Tags: combinatorics , extremal combinatorics

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]

1995 IMO Shortlist, 5

Tags: graph theory , extremal combinatorics , combinatorics

At a meeting of $ 12k$ people, each person exchanges greetings with exactly $ 3k\plus{}6$ others. For any two people, the number who exchange greetings with both is the same. How many people are at the meeting?

2017 Baltic Way, 3

Tags: algebra , fibonacci , additive number theory , extremal combinatorics

Positive integers $x_1,...,x_m$ (not necessarily distinct) are written on a blackboard. It is known that each of the numbers $F_1,...,F_{2018}$ can be represented as a sum of one or more of the numbers on the blackboard. What is the smallest possible value of $m$? (Here $F_1,...,F_{2018}$ are the first $2018$ Fibonacci numbers: $F_1=F_2=1, F_{k+1}=F_k+F_{k-1}$ for $k>1$.)

2022 Cyprus TST, 4

Tags: combinatorics , extremal combinatorics

Let \[M=\{1, 2, 3, \ldots, 2022\}\] Determine the least positive integer $k$, such that for every $k$ subsets of $M$ with the cardinality of each subset equal to $3$, there are two of these subsets with exactly one common element.

2007 IMO Shortlist, 8

Tags: combinatorics , polygon , extremal combinatorics , combinatorial geometry

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, 1

Tags: combinatorics , extremal combinatorics , ramsey theory , graph theory , extremal graph theory

The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

2010 Contests, 3

Tags: trigonometry , induction , combinatorics , extremal combinatorics , marvio , geometry

A strip of width $w$ is the set of all points which lie on, or between, two parallel lines distance $w$ apart. Let $S$ be a set of $n$ ($n \ge 3$) points on the plane such that any three different points of $S$ can be covered by a strip of width $1$. Prove that $S$ can be covered by a strip of width $2$.

2005 Germany Team Selection Test, 3

Tags: linear algebra , matrix , combinatorics , extremal combinatorics

For an ${n\times n}$ matrix $A$, let $X_{i}$ be the set of entries in row $i$, and $Y_{j}$ the set of entries in column $j$, ${1\leq i,j\leq n}$. We say that $A$ is [i]golden[/i] if ${X_{1},\dots ,X_{n},Y_{1},\dots ,Y_{n}}$ are distinct sets. Find the least integer $n$ such that there exists a ${2004\times 2004}$ golden matrix with entries in the set ${\{1,2,\dots ,n\}}$.

2016 EGMO, 3

Tags: combinatorics , 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.

1988 IMO Longlists, 54

Tags: combinatorics , partition , coloring , extremal combinatorics , ramsey theory

Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct numbers such that the product of two of them equals the third.

1967 IMO Longlists, 51

Tags: combinatorics , extremal combinatorics , counting

A subset $S$ of the set of integers 0 - 99 is said to have property $A$ if it is impossible to fill a crossword-puzzle with 2 rows and 2 columns with numbers in $S$ (0 is written as 00, 1 as 01, and so on). Determine the maximal number of elements in the set $S$ with the property $A.$

1990 IMO Longlists, 78

Tags: graph theory , combinatorics , extremal combinatorics , extremal graph theory

Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.

2008 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory , divisibility , extremal combinatorics , additive combinatorics

Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$ [i]Author: Gerhard Wöginger, Netherlands[/i]

1983 IMO Shortlist, 14

Tags: combinatorics , arithmetic sequence , extremal combinatorics , ramsey theory , arithmetic progression

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?

2013 International Zhautykov Olympiad, 3

Tags: combinatorics , rectangle , square , extremal combinatorics , covering , square grid

A $10 \times 10$ table consists of $100$ unit cells. A [i]block[/i] is a $2 \times 2$ square consisting of $4$ unit cells of the table. A set $C$ of $n$ blocks covers the table (i.e. each cell of the table is covered by some block of $C$ ) but no $n -1$ blocks of $C$ cover the table. Find the largest possible value of $n$.

1986 IMO, 3

Tags: combinatorics , graph theory , coloring , ramsey theory , extremal combinatorics

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

1990 IMO, 2

Tags: combinatorics , graph theory , extremal combinatorics , coloring

Let $ n \geq 3$ and consider a set $ E$ of $ 2n \minus{} 1$ distinct points on a circle. Suppose that exactly $ k$ of these points are to be colored black. Such a coloring is [b]good[/b] if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $ n$ points from $ E$. Find the smallest value of $ k$ so that every such coloring of $ k$ points of $ E$ is good.

1989 IMO Longlists, 89

Tags: combinatorics , graph theory , extremal graph theory , extremal combinatorics

155 birds $ P_1, \ldots, P_{155}$ are sitting down on the boundary of a circle $ C.$ Two birds $ P_i, P_j$ are mutually visible if the angle at centre $ m(\cdot)$ of their positions $ m(P_iP_j) \leq 10^{\circ}.$ Find the smallest number of mutually visible pairs of birds, i.e. minimal set of pairs $ \{x,y\}$ of mutually visible pairs of birds with $ x,y \in \{P_1, \ldots, P_{155}\}.$ One assumes that a position (point) on $ C$ can be occupied simultaneously by several birds, e.g. all possible birds.

1985 IMO Longlists, 84

Tags: combinatorial geometry , combinatorics , graph theory , extremal combinatorics , extremal graph theory

Let $A$ be a set of $n$ points in the space. From the family of all segments with endpoints in $A$, $q$ segments have been selected and colored yellow. Suppose that all yellow segments are of different length. Prove that there exists a polygonal line composed of $m$ yellow segments, where $m \geq \frac{2q}{n}$, arranged in order of increasing length.

2018 India IMO Training Camp, 1

Tags: combinatorics , sorting , distance , extremal combinatorics , radius , string

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.

1990 IMO Shortlist, 3

Tags: graph theory , combinatorics , extremal combinatorics , coloring

Let $ n \geq 3$ and consider a set $ E$ of $ 2n \minus{} 1$ distinct points on a circle. Suppose that exactly $ k$ of these points are to be colored black. Such a coloring is [b]good[/b] if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $ n$ points from $ E$. Find the smallest value of $ k$ so that every such coloring of $ k$ points of $ E$ is good.