Olympiad problems

2010 ELMO Shortlist, 4

The numbers $1, 2, \ldots, n$ are written on a blackboard. Each minute, a student goes up to the board, chooses two numbers $x$ and $y$, erases them, and writes the number $2x+2y$ on the board. This continues until only one number remains. Prove that this number is at least $\frac{4}{9}n^3$. [i]Brian Hamrick.[/i]

2008 Bosnia and Herzegovina Junior BMO TST, 4

Tags: combinatorics proposed , combinatorics

On circle are $ 2008$ blue and $ 1$ red point(s) given. Are there more polygons which have a red point or those which dont have it??

2002 Iran MO (3rd Round), 11

Tags: geometry , combinatorics proposed , combinatorics

In an $m\times n$ table there is a policeman in cell $(1,1)$, and there is a thief in cell $(i,j)$. A move is going from a cell to a neighbor (each cell has at most four neighbors). Thief makes the first move, then the policeman moves and ... For which $(i,j)$ the policeman can catch the thief?

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]

2012 Middle European Mathematical Olympiad, 2

Tags: floor function , combinatorics proposed , combinatorics

Let $ N $ be a positive integer. A set $ S \subset \{ 1, 2, \cdots, N \} $ is called [i]allowed[/i] if it does not contain three distinct elements $ a, b, c $ such that $ a $ divides $ b $ and $ b $ divides $c$. Determine the largest possible number of elements in an allowed set $ S $.

2012 ELMO Shortlist, 7

Tags: combinatorics proposed , combinatorics

Consider a graph $G$ with $n$ vertices and at least $n^2/10$ edges. Suppose that each edge is colored in one of $c$ colors such that no two incident edges have the same color. Assume further that no cycles of size $10$ have the same set of colors. Prove that there is a constant $k$ such that $c$ is at least $kn^\frac{8}{5}$ for any $n$. [i]David Yang.[/i]

2005 Croatia National Olympiad, 4

Tags: combinatorics proposed , combinatorics

The vertices of a regular $2005$-gon are colored red, white and blue. Whenever two vertices of different colors stand next to each other, we are allowed to recolor them into the third color. (a) Prove that there exists a ﬁnite sequence of allowed recolorings after which all the vertices are of the same color. (b) Is that color uniquely determined by the initial coloring?

2015 International Zhautykov Olympiad, 1

Tags: geometry , analytic geometry , combinatorics proposed , combinatorics

Each point with integral coordinates in the plane is coloured white or blue. Prove that one can choose a colour so that for every positive integer $ n $ there exists a triangle of area $ n $ having its vertices of the chosen colour.

2002 Romania Team Selection Test, 4

Tags: induction , combinatorics proposed , combinatorics

At an international conference there are four official languages. Any two participants can speak in one of these languages. Show that at least $60\%$ of the participants can speak the same language. [i]Mihai Baluna[/i]

1992 Canada National Olympiad, 5

Tags: invariant , combinatorics proposed , combinatorics

A deck of $ 2n\plus{}1$ cards consists of a joker and, for each number between 1 and $ n$ inclusive, two cards marked with that number. The $ 2n\plus{}1$ cards are placed in a row, with the joker in the middle. For each $ k$ with $ 1 \leq k \leq n,$ the two cards numbered $ k$ have exactly $ k\minus{}1$ cards between them. Determine all the values of $ n$ not exceeding 10 for which this arrangement is possible. For which values of $ n$ is it impossible?

2014 Dutch IMO TST, 5

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

2009 India IMO Training Camp, 6

Tags: function , combinatorics proposed , combinatorics

Prove The Following identity: $ \sum_{j \equal{} 0}^n \left ({3n \plus{} 2 \minus{} j \choose j}2^j \minus{} {3n \plus{} 1 \minus{} j \choose j \minus{} 1}2^{j \minus{} 1}\right ) \equal{} 2^{3n}$. The Second term on left hand side is to be regarded zero for j=0.

1996 ITAMO, 6

Tags: combinatorics proposed , combinatorics

What is the minimum number of squares that is necessary to draw on a white sheet to obtain a square grid of side $n$?

2002 Junior Balkan Team Selection Tests - Romania, 1

Tags: geometry , combinatorics proposed , combinatorics

A square of side 1 is decomposed into 9 equal squares of sides 1/3 and the one in the center is painted in black. The remaining eight squares are analogously divided into nine squares each and the square in the center is painted in black. Prove that after 1000 steps the total area of black region exceeds 0.999[/b]

2012 China Western Mathematical Olympiad, 3

Tags: combinatorics proposed , combinatorics

Let $n$ be a positive integer $\geq 2$ . Consider a $n$ by $n$ grid with all entries $1$. Define an operation on a square to be changing the signs of all squares adjacent to it but not the sign of its own. Find all $n$ such that it is possible after a finite sequence of operations to reach a $n$ by $n$ grid with all entries $-1$

1996 Iran MO (3rd Round), 4

Tags: combinatorics proposed , combinatorics

Show that there doesn't exist two infinite and separate sets $A,B$ of points such that [b](i)[/b] There are no three collinear points in $A \cup B$, [b](ii)[/b] The distance between every two points in $A \cup B$ is at least $1$, and [b](iii)[/b] There exists at least one point belonging to set $B$ in interior of each triangle which all of its vertices are chosen from the set $A$, and there exists at least one point belonging to set $A$ in interior of each triangle which all of its vertices are chosen from the set $B$.

1993 All-Russian Olympiad, 4

Tags: graph theory , combinatorics proposed , combinatorics

In a family album, there are ten photos. On each of them, three people are pictured: in the middle stands a man, to the right of him stands his brother, and to the left of him stands his son. What is the least possible total number of people pictured, if all ten of the people standing in the middle of the ten pictures are different.

1986 IMO Longlists, 10

Tags: probability , combinatorics proposed , combinatorics

A set of $n$ standard dice are shaken and randomly placed in a straight line. If $n < 2r$ and $r < s$, then the probability that there will be a string of at least $r$, but not more than $s$, consecutive $1$'s can be written as $\frac{P}{6^{s+2}}$. Find an explicit expression for $P$.

2014 Indonesia MO, 1

Tags: combinatorics proposed , combinatorics

Is it possible to fill a $3 \times 3$ grid with each of the numbers $1,2,\ldots,9$ once each such that the sum of any two numbers sharing a side is prime?

2012 ELMO Shortlist, 3

Tags: combinatorics proposed , combinatorics

Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\ldots,c_k\}$ ($k\ge1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$. [i]David Yang.[/i]

2006 Moldova MO 11-12, 8

Tags: induction , combinatorics proposed , combinatorics

Given an alfabet of $n$ letters. A sequence of letters such that between any 2 identical letters there are no 2 identical letters is called a [i]word[/i]. a) Find the maximal possible length of a [i]word[/i]. b) Find the number of the [i]words[/i] of maximal length.

2020 Baltic Way, 20

Tags: combinatorics , combinatorics proposed

Let $A$ and $B$ be sets of positive integers with $|A|\ge 2$ and $|B|\ge 2$. Let $S$ be a set consisting of $|A|+|B|-1$ numbers of the form $ab$ where $a\in A$ and $b\in B$. Prove that there exist pairwise distinct $x,y,z\in S$ such that $x$ is a divisor of $yz$.

2006 CentroAmerican, 5

Tags: combinatorics proposed , combinatorics

The [i]Olimpia[/i] country is formed by $n$ islands. The most populated one is called [i]Panacenter[/i], and every island has a different number of inhabitants. We want to build bridges between these islands, which we'll be able to travel in both directions, under the following conditions: a) No pair of islands is joined by more than one bridge. b) Using the bridges we can reach every island from Panacenter. c) If we want to travel from Panacenter to every other island, in such a way that we use each bridge at most once, the number of inhabitants of the islands we visit is strictly decreasing. Determine the number of ways we can build the bridges.

2018 Bundeswettbewerb Mathematik, 1

Tags: game , combinatorics , combinatorics proposed

Anja and Bernd take turns in removing stones from a heap, initially consisting of $n$ stones ($n \ge 2$). Anja begins, removing at least one but not all the stones. Afterwards, in each turn the player has to remove at least one stone and at most as many stones as removed in the preceding move. The player removing the last stone wins. Depending on the value of $n$, which player can ensure a win?

2010 All-Russian Olympiad, 2

Tags: combinatorics proposed , combinatorics

On an $n\times n$ chart, where $n \geq 4$, stand "$+$" signs in the cells of the main diagonal and "$-$" signs in all the other cells. You can change all the signs in one row or in one column, from $-$ to $+$ or from $+$ to $-$. Prove that you will always have $n$ or more $+$ signs after finitely many operations.