Olympiad problems

2017 Estonia Team Selection Test, 12

Let $n \geq 3$ be a positive integer. Find the maximum number of diagonals in a regular $n$-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

2014 USA Team Selection Test, 3

Tags: induction , inequalities , combinatorics proposed , combinatorics , graph theory , Extremal combinatorics

Let $n$ be an even positive integer, and let $G$ be an $n$-vertex graph with exactly $\tfrac{n^2}{4}$ edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices $\{x,y\}$ is said to be [i]amicable[/i] if they have a common neighbor (there is a vertex $z$ such that $xz$ and $yz$ are both edges). Prove that $G$ has at least $2\textstyle\binom{n/2}{2}$ pairs of vertices which are amicable. [i]Zoltán Füredi (suggested by Po-Shen Loh)[/i]

1983 IMO Shortlist, 3

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.

2013 Moldova Team Selection Test, 4

Tags: IMO Shortlist , combinatorics , Extremal combinatorics , Doublecounting , Hi

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

1977 IMO, 2

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.

1990 IMO Shortlist, 22

Tags: graph theory , combinatorics , Extremal combinatorics , Extremal Graph Theory , IMO Shortlist

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.

1979 IMO Shortlist, 12

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

Let $R$ be a set of exactly $6$ elements. A set $F$ of subsets of $R$ is called an $S$-family over $R$ if and only if it satisfies the following three conditions: (i) For no two sets $X, Y$ in $F$ is $X \subseteq Y$ ; (ii) For any three sets $X, Y,Z$ in $F$, $X \cup Y \cup Z \neq R,$ (iii) $\bigcup_{X \in F} X = R$

2016 Indonesia TST, 3

Tags: combinatorics , Sets , Extremal combinatorics

Let $\{E_1, E_2, \dots, E_m\}$ be a collection of sets such that $E_i \subseteq X = \{1, 2, \dots, 100\}$, $E_i \neq X$, $i = 1, 2, \dots, m$. It is known that every two elements of $X$ is contained together in exactly one $E_i$ for some $i$. Determine the minimum value of $m$.

2024 ITAMO, 5

Tags: combinatorics , combinatorics proposed , grid combo , Extremal combinatorics

A [i]fortress[/i] is a finite collection of cells in an infinite square grid with the property that one can pass from any cell of the fortress to any other by a sequence of moves to a cell with a common boundary line (but it can have "holes"). The [i]walls[/i] of a fortress are the unit segments between cells belonging to the fortress and cells not belonging to the fortress. The [i]area[/i] $A$ of a fortress is the number of cells it consists of. The [i]perimeter[/i] $P$ is the total length of its walls. Each cell of the fortress can contain a [i]guard[/i] which can oversee the cells to the top, the bottom, the right and the left of this cell, up until the next wall (it also oversees its own cell). (a) Determine the smallest integer $k$ such that $k$ guards suffice to oversee all cells of any fortress of perimeter $P \le 2024$. (b) Determine the smallest integer $k$ such that $k$ guards suffice to oversee all cells of any fortress of area $A \le 2024$.

1985 IMO Shortlist, 8

Tags: combinatorics , combinatorial geometry , graph theory , Extremal combinatorics , Extremal Graph Theory , IMO Shortlist

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.

1987 IMO Shortlist, 17

Tags: arithmetic sequence , combinatorics , Probabilistic Method , Coloring , Extremal combinatorics , IMO Shortlist

Prove that there exists a four-coloring of the set $M = \{1, 2, \cdots, 1987\}$ such that any arithmetic progression with $10$ terms in the set $M$ is not monochromatic. [b][i]Alternative formulation[/i][/b] Let $M = \{1, 2, \cdots, 1987\}$. Prove that there is a function $f : M \to \{1, 2, 3, 4\}$ that is not constant on every set of $10$ terms from $M$ that form an arithmetic progression. [i]Proposed by Romania[/i]

1983 IMO Longlists, 50

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?

1987 IMO Shortlist, 11

Tags: combinatorics , partitions , counting , Extremal combinatorics , IMO Shortlist

Find the number of partitions of the set $\{1, 2, \cdots, n\}$ into three subsets $A_1,A_2,A_3$, some of which may be empty, such that the following conditions are satisfied: $(i)$ After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity. $(ii)$ If $A_1,A_2,A_3$ are all nonempty, then in exactly one of them the minimal number is even . [i]Proposed by Poland.[/i]

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.

1997 Pre-Preparation Course Examination, 1

Tags: combinatorics , Additive combinatorics , Additive Number Theory , Extremal combinatorics , Subsets , IMO Shortlist

Let $ k,m,n$ be integers such that $ 1 < n \leq m \minus{} 1 \leq k.$ Determine the maximum size of a subset $ S$ of the set $ \{1,2,3, \ldots, k\minus{}1,k\}$ such that no $ n$ distinct elements of $ S$ add up to $ m.$

2013 Taiwan TST Round 1, 4

Tags: IMO Shortlist , combinatorics , Extremal combinatorics , Doublecounting , Hi

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

1990 IMO Longlists, 4

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

Given $ n$ countries with three representatives each, $ m$ committees $ A(1),A(2), \ldots, A(m)$ are called a cycle if [i](i)[/i] each committee has $ n$ members, one from each country; [i](ii)[/i] no two committees have the same membership; [i](iii)[/i] for $ i \equal{} 1, 2, \ldots,m$, committee $ A(i)$ and committee $ A(i \plus{} 1)$ have no member in common, where $ A(m \plus{} 1)$ denotes $ A(1);$ [i](iv)[/i] if $ 1 < |i \minus{} j| < m \minus{} 1,$ then committees $ A(i)$ and $ A(j)$ have at least one member in common. Is it possible to have a cycle of 1990 committees with 11 countries?

1966 IMO Longlists, 43

Tags: combinatorics , Coloring , graph theory , Ramsey Theory , Extremal combinatorics , IMO Longlist , IMO Shortlist

Given $5$ points in a plane, no three of them being collinear. Each two of these $5$ points are joined with a segment, and every of these segments is painted either red or blue; assume that there is no triangle whose sides are segments of equal color. [b]a.)[/b] Show that: [i](1)[/i] Among the four segments originating at any of the $5$ points, two are red and two are blue. [i](2)[/i] The red segments form a closed way passing through all $5$ given points. (Similarly for the blue segments.) [b]b.)[/b] Give a plan how to paint the segments either red or blue in order to have the condition (no triangle with equally colored sides) satisfied.

2001 Czech-Polish-Slovak Match, 3

Tags: combinatorics , Extremal combinatorics , IMO Shortlist , graph theory , Chessboard

Let $ n$ and $ k$ be positive integers such that $ \frac{1}{2} n < k \leq \frac{2}{3} n.$ Find the least number $ m$ for which it is possible to place $ m$ pawns on $ m$ squares of an $ n \times n$ chessboard so that no column or row contains a block of $ k$ adjacent unoccupied squares.

1966 IMO Shortlist, 43

Tags: combinatorics , Coloring , graph theory , Ramsey Theory , Extremal combinatorics , IMO Longlist , IMO Shortlist

Given $5$ points in a plane, no three of them being collinear. Each two of these $5$ points are joined with a segment, and every of these segments is painted either red or blue; assume that there is no triangle whose sides are segments of equal color. [b]a.)[/b] Show that: [i](1)[/i] Among the four segments originating at any of the $5$ points, two are red and two are blue. [i](2)[/i] The red segments form a closed way passing through all $5$ given points. (Similarly for the blue segments.) [b]b.)[/b] Give a plan how to paint the segments either red or blue in order to have the condition (no triangle with equally colored sides) satisfied.

2017 Romania Team Selection Test, P3

Tags: combinatorics , IMO Shortlist , Extremal combinatorics , Hi

Let $n \geq 3$ be a positive integer. Find the maximum number of diagonals in a regular $n$-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

1979 IMO Longlists, 15

Tags: graph theory , number theory , maximization , Extremal Graph Theory , Extremal combinatorics , IMO Shortlist , IMO Longlist

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

1983 IMO Longlists, 1

Tags: combinatorics , Extremal combinatorics , Ramsey Theory , graph theory , Extremal Graph Theory , IMO Shortlist

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.

1988 IMO Shortlist, 14

Tags: linear algebra , matrix , combinatorics , Extremal combinatorics , IMO Shortlist

For what values of $ n$ does there exist an $ n \times n$ array of entries -1, 0 or 1 such that the $ 2 \cdot n$ sums obtained by summing the elements of the rows and the columns are all different?

2013 Germany Team Selection Test, 3

Tags: IMO Shortlist , combinatorics , Extremal combinatorics , Doublecounting , Hi

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