Olympiad problems

1987 IMO Longlists, 28

In a chess tournament there are $n \geq 5$ players, and they have already played $\left[ \frac{n^2}{4} \right] +2$ games (each pair have played each other at most once). [b](a)[/b] Prove that there are five players $a, b, c, d, e$ for which the pairs $ab, ac, bc, ad, ae, de$ have already played. [b](b)[/b] Is the statement also valid for the $\left[ \frac{n^2}{4} \right] +1$ games played? Make the proof by induction over $n.$

2002 Iran MO (3rd Round), 17

Tags: analytic geometry , combinatorics proposed , combinatorics

Find the smallest natural number $n$ that the following statement holds : Let $A$ be a finite subset of $\mathbb R^{2}$. For each $n$ points in $A$ there are two lines including these $n$ points. All of the points lie on two lines.

2008 International Zhautykov Olympiad, 3

Tags: combinatorics proposed , combinatorics

Let $ A \equal{} \{(a_1,\dots,a_8)|a_i\in\mathbb{N}$ , $ 1\leq a_i\leq i \plus{} 1$ for each $ i \equal{} 1,2\dots,8\}$.A subset $ X\subset A$ is called sparse if for each two distinct elements $ (a_1,\dots,a_8)$,$ (b_1,\dots,b_8)\in X$,there exist at least three indices $ i$,such that $ a_i\neq b_i$. Find the maximal possible number of elements in a sparse subset of set $ A$.

2012 Paraguay Mathematical Olympiad, 2

Tags: combinatorics proposed , combinatorics

The [i]traveler ant[/i] is walking over several chess boards. He only walks vertically and horizontally through the squares of the boards and does not pass two or more times over the same square of a board. a) In a $4$x$4$ board, from which squares can he begin his travel so that he can pass through all the squares of the board? b) In a $5$x$5$ board, from which squares can he begin his travel so that he can pass through all the squares of the board? c) In a $n$x$n$ board, from which squares can he begin his travel so that he can pass through all the squares of the board?

2005 ISI B.Stat Entrance Exam, 10

Tags: combinatorics proposed , combinatorics

Let $ABC$ be a triangle. Take $n$ point lying on the side $AB$ (different from $A$ and $B$) and connect all of them by straight lines to the vertex $C$. Similarly, take $n$ points on the side $AC$ and connect them to $B$. Into how many regions is the triangle $ABC$ partitioned by these lines? Further, take $n$ points on the side $BC$ also and join them with $A$. Assume that no three straight lines meet at a point other than $A,B$ and $C$. Into how many regions is the triangle $ABC$ partitioned now?

2012 All-Russian Olympiad, 1

Tags: combinatorics proposed , combinatorics

$101$ wise men stand in a circle. Each of them either thinks that the Earth orbits Jupiter or that Jupiter orbits the Earth. Once a minute, all the wise men express their opinion at the same time. Right after that, every wise man who stands between two people with a different opinion from him changes his opinion himself. The rest do not change. Prove that at one point they will all stop changing opinions.

2016 Bulgaria JBMO TST, 4

Tags: combinatorics proposed , combinatorics

Given is equilateral triangle $ABC$ with side length $n \geq 3$. It is divided into $n^2$ identical small equilateral triangles with side length $1$. On every vertex of the triangles there is a number. In a move we can choose a rhombus and add or subtract $1$ from all $4$ numbers on the vertices of the rhombus. Let point $D$ have coordinates $(3,2)$ where $3$ is the number of the row and $2$ is the position on it from left to right. On the vertices $A,B,C,D$ there are $1$'s and on the other vertices there are $0$'s. Is it possible, after some operations, all the numbers to become equal?

2011 Federal Competition For Advanced Students, Part 2, 1

Tags: geometry , geometric transformation , combinatorics proposed , combinatorics

Every brick has $5$ holes in a line. The holes can be filled with bolts (fitting in one hole) and braces (fitting into two neighboring holes). No hole may remain free. One puts $n$ of these bricks in a line to form a pattern from left to right. In this line no two braces and no three bolts may be adjacent. How many different such patterns can be produced with $n$ bricks?

1995 Baltic Way, 14

Tags: geometry , geometric transformation , reflection , combinatorics proposed , combinatorics

There are $n$ fleas on an infinite sheet of triangulated paper. Initially the fleas are in different small triangles, all of which are inside some equilateral triangle consisting of $n^2$ small triangles. Once a second each flea jumps from its original triangle to one of the three small triangles having a common vertex but no common side with it. For which natural numbers $n$ does there exist an initial configuration such that after a finite number of jumps all the $n$ fleas can meet in a single small triangle?

2024 Polish MO Finals, 2

Tags: combinatorics , combinatorics proposed , combinatorial geometry , game

Let $n$ be a positive integer. Bolek draws $2n$ points in the plane, no two of them defining a vertical or a horizontal line. Then Lolek draws for each of these $2n$ points two rays emanating from them, one of them vertically and the other one horizontally. Lolek wants to maximize the number of regions in which these rays divide the plane. Determine the largest number $k$ such that Lolek can obtain at least $k$ regions independent of the points chosen by Bolek.

2005 International Zhautykov Olympiad, 3

Tags: rotation , combinatorics proposed , combinatorics

Let $ A$ be a set of $ 2n$ points on the plane such that no three points are collinear. Prove that for any distinct two points $ a,b\in A$ there exists a line that partitions $ A$ into two subsets each containing $ n$ points and such that $ a,b$ lie on different sides of the line.

2014 ELMO Shortlist, 5

Tags: function , combinatorics proposed , combinatorics

Let $n$ be a positive integer. For any $k$, denote by $a_k$ the number of permutations of $\{1,2,\dots,n\}$ with exactly $k$ disjoint cycles. (For example, if $n=3$ then $a_2=3$ since $(1)(23)$, $(2)(31)$, $(3)(12)$ are the only such permutations.) Evaluate \[ a_n n^n + a_{n-1} n^{n-1} + \dots + a_1 n. \][i]Proposed by Sammy Luo[/i]

2008 Junior Balkan Team Selection Tests - Moldova, 12

Tags: combinatorics proposed , combinatorics

Natural nonzero numder, which consists of $ m$ digits, is called hiperprime, if its any segment, which consists $ 1,2,...,m$ digits is prime (for example $ 53$ is hiperprime, because numbers $ 53,3,5$ are prime). Find all hiperprime numbers.

2012 Iran MO (3rd Round), 1

Tags: combinatorics proposed , combinatorics

Prove that for each coloring of the points inside or on the boundary of a square with $1391$ colors, there exists a monochromatic regular hexagon.

2005 CentroAmerican, 4

Tags: geometry , geometric transformation , reflection , rectangle , combinatorics proposed , combinatorics

Two players, Red and Blue, play in alternating turns on a 10x10 board. Blue goes first. In his turn, a player picks a row or column (not chosen by any player yet) and color all its squares with his own color. If any of these squares was already colored, the new color substitutes the old one. The game ends after 20 turns, when all rows and column were chosen. Red wins if the number of red squares in the board exceeds at least by 10 the number of blue squares; otherwise Blue wins. Determine which player has a winning strategy and describe this strategy.

2007 Tournament Of Towns, 4

Tags: combinatorics proposed , combinatorics

Each cell of a $29 \times 29$ table contains one of the integers $1, 2, 3, \ldots , 29$, and each of these integers appears $29$ times. The sum of all the numbers above the main diagonal is equal to three times the sum of all the numbers below this diagonal. Determine the number in the central cell of the table.

2011 All-Russian Olympiad, 3

Tags: combinatorics proposed , combinatorics , graph theory

The graph $G$ is not $3$-coloured. Prove that $G$ can be divided into two graphs $M$ and $N$ such that $M$ is not $2$-coloured and $N$ is not $1$-coloured. [i]V. Dolnikov[/i]

2009 Poland - Second Round, 2

Tags: combinatorics proposed , combinatorics

Find all integer numbers $n\ge 4$ which satisfy the following condition: from every $n$ different $3$-element subsets of $n$-element set it is possible to choose $2$ subsets, which have exactly one element in common.

2006 Cono Sur Olympiad, 4

Tags: combinatorics proposed , combinatorics

Daniel writes over a board, from top to down, a list of positive integer numbers less or equal to 10. Next to each number of Daniel's list, Martin writes the number of times exists this number into the Daniel's list making a list with the same length. If we read the Martin's list from down to top, we get the same list of numbers that Daniel wrote from top to down. Find the greatest length of the Daniel's list can have.

1998 Turkey MO (2nd round), 3

Tags: Ramsey Theory , combinatorics proposed , combinatorics

The points of a circle are colored by three colors. Prove that there exist infinitely many isosceles triangles inscribed in the circle whose vertices are of the same color.

2007 Middle European Mathematical Olympiad, 2

Tags: combinatorics proposed , combinatorics

For a set $ P$ of five points in the plane, no three of them being collinear, let $ s(P)$ be the numbers of acute triangles formed by vertices in $ P$. Find the maximum value of $ s(P)$ over all such sets $ P$.

2002 Tournament Of Towns, 7

Tags: ceiling function , combinatorics proposed , combinatorics

[list] [*] A power grid with the shape of a $3\times 3$ lattice with $16$ nodes (vertices of the lattice) joined by wires (along the sides of squares. It may have happened that some of the wires have burned out. In one test technician can choose any two nodes and check if electrical current circulates between them (i.e there is a chain of intact wires joining the chosen nodes) . Technicial knows that current will circulate from any node to another node. What is the least number of tests required to demonstrate this? [*] Previous problem for the grid of $5\times 5$ lattice.[/list]

2011 ELMO Shortlist, 2

Tags: induction , combinatorics proposed , combinatorics , Directed graphs , graph theory , Coloring

A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to. [i]David Yang.[/i] [hide="Stronger Version"]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492100]here[/url].[/hide]

2001 Balkan MO, 4

Tags: geometry , 3D geometry , analytic geometry , combinatorics proposed , combinatorics

A cube side 3 is divided into 27 unit cubes. The unit cubes are arbitrarily labeled 1 to 27 (each cube is given a different number). A move consists of swapping the cube labeled 27 with one of its 6 neighbours. Is it possible to find a finite sequence of moves at the end of which cube 27 is in its original position, but cube $n$ has moved to the position originally occupied by $27-n$ (for each $n = 1, 2, \ldots , 26$)?

2016 SGMO, Q6

Tags: combinatorics , combinatorics proposed , function

Let $f_1,f_2,\ldots $ be a sequence of non-increasing functions from the naturals to the naturals. Show there exists $i < j$ such that $$f_i(n) \leq f_j(n) \text{ for all } n \in \mathbb{N}.$$