Olympiad problems

1985 IMO Longlists, 69

Tags: combinatorics

Let $A$ and $B$ be two finite disjoint sets of points in the plane such that no three distinct points in $A \cup B$ are collinear. Assume that at least one of the sets $A, B$ contains at least five points. Show that there exists a triangle all of whose vertices are contained in $A$ or in $B$ that does not contain in its interior any point from the other set.

2015 May Olympiad, 5

Tags: combinatorics , geometry

If you have $65$ points in a plane, we will make the lines that passes by any two points in this plane and we obtain exactly $2015$ distinct lines, prove that least $4$ points are collinears!!

1956 Putnam, B5

Tags: combinatorics , graph theory , turan s theorem

Show that a graph with 2n points and $n^2 + 1$ edges necessarily contains a 3-cycle, but that we can find a graph with 2n points and $n^2$ edges without a 3-cycle. please prove it without induction .

2008 Thailand Mathematical Olympiad, 5

Tags: combinatorics

Students in a class consisting of $m$ boys and $n$ girls line up. Over all possible ways of lining up, compute the average number of pairs of two boys or two girls who are next to each other.

2017 Harvard-MIT Mathematics Tournament, 3

Tags: combinatorics

A polyhedron has $7n$ faces. Show that there exist $n + 1$ of the polyhedron's faces that all have the same number of edges.

1999 Federal Competition For Advanced Students, Part 2, 1

Tags: combinatorics

Ninety-nine points are given on one of the diagonals of a unit square. Prove that there is at most one vertex of the square such that the average squared distance from a given point to the vertex is less than or equal to $1/2$.

2009 Hong kong National Olympiad, 2

Tags: combinatorics

there are $n$ points on the plane,any two vertex are connected by an edge of red,yellow or green,and any triangle with vertex in the graph contains exactly $2$ colours.prove that $n<13$

2000 All-Russian Olympiad, 4

Tags: combinatorics

Some pairs of cities in a certain country are connected by roads, at least three roads going out of each city. Prove that there exists a round path consisting of roads whose number is not divisible by $3$.

2019 Portugal MO, 6

Tags: combinatorics

A metro network with $n \ge 2$ stations, where each station is connected to each of the others by a one-way line, is said to be [i]dispersed [/i]i f there are two stations $A$ and $B$ such that it is not possible to go from $A$ to $B$ through is from the network. If a network is [i]dispersed[/i], but it is possible to choose a station $A$ and reverse the direction of all lines to and from $A$ so that the new network is no longer dispersed, the network is said to be [i]correctable[/i]. Indicates all integers $n$ for which there is a network with $n$ stations, [i]dispersed [/i]and not [i]correctable[/i].

2020 DMO Stage 1, 4.

Tags: combinatorics

[b]Q.[/b] We paint the numbers $1,2,3,4,5$ with red or blue. Prove that the equation $x+y=z$ have a monocolor solution (that is, all the 3 unknown there are the same color . It not needed that $x, y, z$ must be different!) [i]Proposed by TuZo[/i]

2011 IFYM, Sozopol, 1

Tags: combinatorics , table , numbers in a table

In the cells of a square table $n$ x $n$ the numbers $1,2,...,n^2$ are written in an arbitrary way. Prove that there exist two adjacent cells, for which the difference between the numbers written in them is no lesser than $n$.

1991 Brazil National Olympiad, 1

Tags: combinatorics

At a party every woman dances with at least one man, and no man dances with every woman. Show that there are men M and M' and women W and W' such that M dances with W, M' dances with W', but M does not dance with W', and M' does not dance with W.

2023 Ukraine National Mathematical Olympiad, 9.8

Tags: graph , combinatorics

What is the largest possible number of edges in a graph on $2n$ nodes, if there exists exactly one way to split its nodes into $n$ pairs so that the nodes from each pair are connected by an edge? [i]Proposed by Anton Trygub[/i]

Kvant 2019, M2551

Tags: combinatorics

The vertices of a convex polygon with $n\geqslant 4$ sides are coloured with black and white. A diagonal is called [i]multicoloured[/i] if its vertices have different colours. A colouring of the vertices is [i]good[/i] if the polygon can be partitioned into triangles by using only multicoloured diagonals which do not intersect in the interior of the polygon. Find the number of good colourings. [i]Proposed by S. Berlov[/i]

2007 Kyiv Mathematical Festival, 5

Tags: combinatorics

The vertices of 100-gon (i.e., polygon with 100 sides) are colored alternately white or black. One of the vertices contains a checker. Two players in turn do two things: move the checker into other vertice along the side of 100-gon and then erase some side. The game ends when it is impossible to move the checker. At the end of the game if the checker is in the white vertice then the first player wins. Otherwise the second player wins. Does any of the players have winning strategy? If yes, then who? [i]Remark.[/i] The answer may depend on initial position of the checker.

2007 Tournament Of Towns, 5

Tags: combinatorics

A triangular pie has the same shape as its box, except that they are mirror images of each other. We wish to cut the pie in two pieces which can t together in the box without turning either piece over. How can this be done if [list][b](a)[/b] one angle of the triangle is three times as big as another; [b](b)[/b] one angle of the triangle is obtuse and is twice as big as one of the acute angles?[/list]

2005 MOP Homework, 1

Tags: modular arithmetic , combinatorics

Let $X$ be a set with $n$ elements and $0 \le k \le n$. Let $a_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at least $k$ common components (where a common component of $f$ and g is an $x \in X$ such that $f(x) = g(x)$). Let $b_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at most $k$ common components. (a) Show that $a_{n,k} \cdot b_{n,k-1} \le n!$. (b) Let $p$ be prime, and find the exact value of $a_{p,2}$.

2014 Dutch IMO TST, 5

Tags: combinatorics

On each of the $2014^2$ squares of a $2014 \times 2014$-board a light bulb is put. Light bulbs can be either on or off. In the starting situation a number of the light bulbs is on. A move consists of choosing a row or column in which at least $1007$ light bulbs are on and changing the state of all $2014$ light bulbs in this row or column (from on to off or from off to on). Find the smallest non-negative integer $k$ such that from each starting situation there is a finite sequence of moves to a situation in which at most $k$ light bulbs are on.

2006 Moldova Team Selection Test, 4

Tags: combinatorics

Let $f(n)$ denote the number of permutations $(a_{1}, a_{2}, \ldots ,a_{n})$ of the set $\{1,2,\ldots,n\}$, which satisfy the conditions: $a_{1}=1$ and $|a_{i}-a_{i+1}|\leq2$, for any $i=1,2,\ldots,n-1$. Prove that $f(2006)$ is divisible by 3.

1994 All-Russian Olympiad, 4

Tags: combinatorics , combinatorial geometry

On a line are given $n$ blue and $n$ red points. Prove that the sum of distances between pairs of points of the same color does not exceed the sum of distances between pairs of points of different colors. (O. Musin)

2020 OMMock - Mexico National Olympiad Mock Exam, 5

Tags: combinatorics , game strategy

A ladder is a non-decreasing sequence $a_1, a_2, \dots, a_{2020}$ of non-negative integers. Diego and Pablo play by turns with the ladder $1, 2, \dots, 2020$, starting with Diego. In each turn, the player replaces an entry $a_i$ by $a_i'<a_i$, with the condition that the sequence remains a ladder. The player who gets $(0, 0, \dots, 0)$ wins. Who has a winning strategy? [i]Proposed by Violeta Hernández[/i]

1988 Tournament Of Towns, (181) 4

Tags: combinatorics , game , game strategy

There is a set of cards with numbers from $1$ to $30$ (which may be repeated) . Each student takes one such card. The teacher can perform the following operation: He reads a list of such numbers (possibly only one) and then asks the students to raise an arm if their number was in this list. How many times must he perform such an operation in order to determine the number on each student 's card? (Indicate the number of operations and prove that it is minimal . Note that there are not necessarily 30 students.)

2007 All-Russian Olympiad Regional Round, 8.5

Tags: counting , distinguishability , combinatorics

There are $ 11$ coins, which are indistinguishable by sight. Nevertheless, among them there are $ 10$ geniune coins ( of weight $ 20$ g each) and one counterfeit (of weight $ 21$ g). You have a two-pan scale which is blanced when the weight in the left-hand pan is twice as much as the weight in the right-hand one. Using this scale only, find the false coin by three weighings.

1949 Moscow Mathematical Olympiad, 162

Tags: geometric progression , algebra , geometric sequence , combinatorics

Given a set of $4n$ positive numbers such that any distinct choice of ordered foursomes of these numbers constitutes a geometric progression. Prove that at least $4$ numbers of the set are identical.

1997 Dutch Mathematical Olympiad, 4

Tags: octahedron , coloring , combinatorics , combinatorial geometry

We look at an octahedron, a regular octahedron, having painted one of the side surfaces red and the other seven surfaces blue. We throw the octahedron like a die. The surface that comes up is painted: if it is red it is painted blue and if it is blue it is painted red. Then we throw the octahedron again and paint it again according to the above rule. In total we throw the octahedron $10$ times. How many different octahedra can we get after finishing the $10$th time? [i]Two octahedra are different if they cannot be converted into each other by rotation.[/i]