This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 181

2018 Romania Team Selection Tests, 2
Tags: combinatorics , string , 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.

1987 IMO Longlists, 53
Tags: arithmetic sequence , combinatorics , probabilistic method , coloring , extremal combinatorics
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]

2018 Peru IMO TST, 6
Tags: string , sorting , distance , extremal combinatorics , radius , combinatorics
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.

1997 Pre-Preparation Course Examination, 1
Tags: additive combinatorics , additive number theory , extremal combinatorics , subset , combinatorics
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.$

2001 IMO, 3
Tags: matrix , combinatorics , ramsey theory , extremal combinatorics
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.

2007 IMO Shortlist, 7
Tags: combinatorics , set systems , extremal combinatorics
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]

1978 IMO Longlists, 30
Tags: graph theory , ramsey theory , combinatorics , extremal graph theory , extremal combinatorics
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.

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.

2005 IMO Shortlist, 8
Tags: diagonal , combinatorics , extremal combinatorics , coloring , polygon
Suppose we have a $n$-gon. Some $n-3$ diagonals are coloured black and some other $n-3$ diagonals are coloured red (a side is not a diagonal), so that no two diagonals of the same colour can intersect strictly inside the polygon, although they can share a vertex. Find the maximum number of intersection points between diagonals coloured differently strictly inside the polygon, in terms of $n$. [i]Proposed by Alexander Ivanov, Bulgaria[/i]

2017 Estonia Team Selection Test, 12
Tags: combinatorics , extremal combinatorics
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.

2009 Germany Team Selection Test, 1
Tags: geometry , rectangle , combinatorial geometry , extremal combinatorics , combinatorics
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]

1999 IMO, 3
Tags: combinatorics , extremal combinatorics , matrix
Let $n$ be an even positive integer. We say that two different cells of a $n \times n$ board are [b]neighboring[/b] if they have a common side. Find the minimal number of cells on the $n \times n$ board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.

1986 IMO Shortlist, 9
Tags: graph theory , combinatorics , 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$?

1988 IMO Shortlist, 20
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.

2014 Contests, 3
Tags: induction , inequalities , graph theory , extremal combinatorics , 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]

2001 IMO Shortlist, 8
Tags: matrix , combinatorics , ramsey theory , extremal combinatorics
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.

2008 IMO Shortlist, 3
Tags: combinatorics , extremal combinatorics , point set , bezout s identity , pigeonhole principle , geometry
In the coordinate plane consider the set $ S$ of all points with integer coordinates. For a positive integer $ k$, two distinct points $A$, $ B\in S$ will be called $ k$-[i]friends[/i] if there is a point $ C\in S$ such that the area of the triangle $ ABC$ is equal to $ k$. A set $ T\subset S$ will be called $ k$-[i]clique[/i] if every two points in $ T$ are $ k$-friends. Find the least positive integer $ k$ for which there exits a $ k$-clique with more than 200 elements. [i]Proposed by Jorge Tipe, Peru[/i]

1991 IMO Shortlist, 12
Tags: combinatorics , extremal combinatorics , set systems , relatively prime
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.

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

2010 Contests, 3
Tags: induction , geometry , trigonometry , combinatorics , extremal combinatorics , marvio
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$.

2000 IMO Shortlist, 4
Tags: combinatorics , extremal combinatorics , 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.

1969 IMO Longlists, 60
Tags: extremal combinatorics , point set , combinatorial geometry , geometry
$(SWE 3)$ Find the natural number $n$ with the following properties: $(1)$ Let $S = \{P_1, P_2, \cdots\}$ be an arbitrary finite set of points in the plane, and $r_j$ the distance from $P_j$ to the origin $O.$ We assign to each $P_j$ the closed disk $D_j$ with center $P_j$ and radius $r_j$. Then some $n$ of these disks contain all points of $S.$ $(2)$ $n$ is the smallest integer with the above property.

2008 IMO Shortlist, 1
Tags: geometry , rectangle , combinatorics , combinatorial geometry , extremal combinatorics
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]

1998 USAMO, 4
Tags: rectangle , floor function , induction , combinatorics , extremal combinatorics
A computer screen shows a $98 \times 98$ chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button: as a result, the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.