Olympiad problems

1989 China Team Selection Test, 3

$1989$ equal circles are arbitrarily placed on the table without overlap. What is the least number of colors are needed such that all the circles can be painted with any two tangential circles colored differently.

2010 All-Russian Olympiad Regional Round, 9.2

Tags: inequalities , combinatorics unsolved , combinatorics

This problem is given by my teacher. :wink: [size=120]Seven skiers numbered 1,2,3,4,5,6,7 set out in turn at the starting point,each one slides the same distance at a constant speed. During this period,everyone just had two "beyond" experience.(going beyond one skier or be went beyond by another skier is called a "beyond" experience). When the race ended,we would decide the rank according to the order that skiers reached the ending. Prove that:there are two different rank at most.[/size]

2008 Finnish National High School Mathematics Competition, 5

Tags: combinatorics unsolved , combinatorics

The closed line segment $I$ is covered by finitely many closed line segments. Show that one can choose a subfamily $S$ of the family of line segments having the properties: (1) the chosen line segments are disjoint, (2) the sum of the lengths of the line segments of S is more than half of the length of $I.$ Show that the claim does not hold any more if the line segment $I$ is replaced by a circle and other occurences of the compound word ''line segment" by the word ''circular arc".

2010 Vietnam Team Selection Test, 2

Tags: induction , algorithm , graph theory , combinatorics unsolved , combinatorics

We have $n$ countries. Each country have $m$ persons who live in that country ($n>m>1$). We divide $m \cdot n$ persons into $n$ groups each with $m$ members such that there don't exist two persons in any groups who come from one country. Prove that one can choose $n$ people into one class such that they come from different groups and different countries.

2003 Indonesia MO, 4

Tags: linear algebra , matrix , combinatorics unsolved , combinatorics

Given a $19 \times 19$ matrix where each component is either $1$ or $-1$. Let $b_i$ be the product of all components in the $i$-th row, and $k_i$ be the product of all components in the $i$-th column, for all $1 \le i \le 19$. Prove that for any such matrix, $b_1 + k_1 + b_2 + k_2 + \cdots + b_{19} + k_{19} \neq 0$.

2013 ELMO Shortlist, 2

Tags: induction , logarithms , strong induction , combinatorics unsolved , combinatorics

Let $n$ be a fixed positive integer. Initially, $n$ 1's are written on a blackboard. Every minute, David picks two numbers $x$ and $y$ written on the blackboard, erases them, and writes the number $(x+y)^4$ on the blackboard. Show that after $n-1$ minutes, the number written on the blackboard is at least $2^{\frac{4n^2-4}{3}}$. [i]Proposed by Calvin Deng[/i]

2007 Olympic Revenge, 6

Tags: combinatorics unsolved , combinatorics

[i]Mediovagio[/i] is a computer game that consists in a $3 \times 3$ table in which each of the nine cells has a integer number from $1$ to $n$. When one clicks a cell, the numbers in the clicked cell and in the cells that share an edge with it are increased by $1$ and the sum is evaluated${}\bmod n$. Determine the values of $n$ for which it's possible, with a finite number of clicks, obtain any combination of numbers from an given initial combination. EDIT: I corrected the statement.

2003 Turkey MO (2nd round), 1

Tags: induction , combinatorics unsolved , combinatorics

$ n\geq 2$ cars are participating in a rally. The cars leave the start line at different times and arrive at the finish line at different times. During the entire rally each car takes over any other car at most once , the number of cars taken over by each car is different and each car is taken over by the same number of cars. Find all possible values of $ n$

2004 All-Russian Olympiad, 2

Tags: induction , combinatorics unsolved , combinatorics

In the cabinet 2004 telephones are located; each two of these telephones are connected by a cable, which is colored in one of four colors. From each color there is one cable at least. Can one always select several telephones in such a way that among their pairwise cable connections exactly 3 different colors occur?

2008 Turkey MO (2nd round), 3

Tags: function , combinatorics unsolved , combinatorics

There is a connected network with $ 2008$ computers, in which any of the two cycles don't have any common vertex. A hacker and a administrator are playing a game in this network. On the $ 1st$ move hacker selects one computer and hacks it, on the $ 2nd$ move administrator selects another computer and protects it. Then on every $ 2k\plus{}1th$ move hacker hacks one more computer(if he can) which wasn't protected by the administrator and is directly connected (with an edge) to a computer which was hacked by the hacker before and on every $ 2k\plus{}2th$ move administrator protects one more computer(if he can) which wasn't hacked by the hacker and is directly connected (with an edge) to a computer which was protected by the administrator before for every $ k>0$. If both of them can't make move, the game ends. Determine the maximum number of computers which the hacker can guarantee to hack at the end of the game.

2008 Tuymaada Olympiad, 7

Tags: combinatorics unsolved , combinatorics

A set $ X$ of positive integers is called [i]nice[/i] if for each pair $ a$, $ b\in X$ exactly one of the numbers $ a \plus{} b$ and $ |a \minus{} b|$ belongs to $ X$ (the numbers $ a$ and $ b$ may be equal). Determine the number of nice sets containing the number 2008. [i]Author: Fedor Petrov[/i]

2007 Tournament Of Towns, 5

Tags: function , induction , combinatorics unsolved , combinatorics

The audience arranges $n$ coins in a row. The sequence of heads and tails is chosen arbitrarily. The audience also chooses a number between $1$ and $n$ inclusive. Then the assistant turns one of the coins over, and the magician is brought in to examine the resulting sequence. By an agreement with the assistant beforehand, the magician tries to determine the number chosen by the audience. [list][b](a)[/b] Prove that if this is possible for some $n$, then it is also possible for $2n$. [b](b)[/b] Determine all $n$ for which this is possible.[/list]

1999 Taiwan National Olympiad, 3

Tags: floor function , combinatorics unsolved , combinatorics

There are $1999$ people participating in an exhibition. Among any $50$ people there are two who don't know each other. Prove that there are $41$ people, each of whom knows at most $1958$ people.

2011 Tuymaada Olympiad, 1

Tags: combinatorics unsolved , combinatorics

Red, blue, and green children are arranged in a circle. When a teacher asked the red children that have a green neighbor to raise their hands, $20$ children raised their hands. When she asked the blue children that have a green neighbor to raise their hands, $25$ children raised their hands. Prove that some child that raised her hand had two green neighbors.

1989 IMO Longlists, 57

Tags: vector , combinatorics unsolved , combinatorics

Let $ v_1, v_2, \ldots, v_{1989}$ be a set of coplanar vectors with $ |v_r| \leq 1$ for $ 1 \leq r \leq 1989.$ Show that it is possible to find $ \epsilon_r$, $1 \leq r \leq 1989,$ each equal to $ \pm 1,$ such that \[ \left | \sum^{1989}_{r\equal{}1} \epsilon_r v_r \right | \leq \sqrt{3}.\]

1990 Vietnam National Olympiad, 2

Tags: combinatorics unsolved , combinatorics

At least $ n - 1$ numbers are removed from the set $\{1, 2, \ldots, 2n - 1\}$ according to the following rules: (i) If $ a$ is removed, so is $ 2a$; (ii) If $ a$ and $ b$ are removed, so is $ a \plus{} b$. Find the way of removing numbers such that the sum of the remaining numbers is maximum possible.

2005 MOP Homework, 4

Tags: calculus , derivative , algebra , polynomial , combinatorics unsolved , combinatorics

Consider an infinite array of integers. Assume that each integer is equal to the sum of the integers immediately above and immediately to the left. Assume that there exists a row $R_0$ such that all the number in the row are positive. Denote by $R_1$ the row below row $R_0$, by $R_2$ the row below row $R_1$, and so on. Show that for each positive integer $n$, row $R_n$ cannot contain more than $n$ zeros.

2003 France Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

$10$ cities are connected by one-way air routes in a way so that each city can be reached from any other by several connected flights. Let $n$ be the smallest number of flights needed for a tourist to visit every city and return to the starting city. Clearly $n$ depends on the flight schedule. Find the largest $n$ and the corresponding flight schedule.

2009 Romanian Masters In Mathematics, 2

Tags: analytic geometry , modular arithmetic , combinatorics unsolved , combinatorics , number theory , combinatorial geometry

A set $ S$ of points in space satisfies the property that all pairwise distances between points in $ S$ are distinct. Given that all points in $ S$ have integer coordinates $ (x,y,z)$ where $ 1 \leq x,y, z \leq n,$ show that the number of points in $ S$ is less than $ \min \Big((n \plus{} 2)\sqrt {\frac {n}{3}}, n \sqrt {6}\Big).$ [i]Dan Schwarz, Romania[/i]

2009 Mediterranean Mathematics Olympiad, 3

Tags: linear algebra , matrix , combinatorics unsolved , combinatorics

Decide whether the integers $1,2,\ldots,100$ can be arranged in the cells $C(i, j)$ of a $10\times10$ matrix (where $1\le i,j\le 10$), such that the following conditions are fullfiled: i) In every row, the entries add up to the same sum $S$. ii) In every column, the entries also add up to this sum $S$. iii) For every $k = 1, 2, \ldots, 10$ the ten entries $C(i, j)$ with $i-j\equiv k\bmod{10}$ add up to $S$. [i](Proposed by Gerhard Woeginger, Austria)[/i]

2014 Contests, 3

Tags: combinatorics unsolved , combinatorics

There are $ n$ students; each student knows exactly $d $ girl students and $d $ boy students ("knowing" is a symmetric relation). Find all pairs $ (n,d) $ of integers .

2004 All-Russian Olympiad, 3

Tags: combinatorics unsolved , combinatorics

The natural numbers from 1 to 100 are arranged on a circle with the characteristic that each number is either larger as their two neighbours or smaller than their two neighbours. A pair of neighbouring numbers is called "good", if you cancel such a pair, the above property remains still valid. What is the smallest possible number of good pairs?

2006 Hungary-Israel Binational, 2

Tags: combinatorics unsolved , combinatorics

A block of size $ a\times b\times c$ is composed of $ 1\times 1\times 2$ domino blocks. Assuming that each of the three possible directions of domino blocks occurs equally many times, what are the possible values of $ a$, $ b$, $ c$?

2015 Bangladesh Mathematical Olympiad, 4

Tags: national olympiad , graph theory , combinatorics unsolved , combinatorics

There are $36$ participants at a BdMO event. Some of the participants shook hands with each other. But no two participants shook hands with each other more than once. Each participant recorded the number of handshakes they made. It was found that no two participants with the same number of handshakes made, had shaken hands with each other. Find the maximum possible number of handshakes at the party with proof. (When two participants shake hands with each other, this will be counted as one handshake.)

2007 Tournament Of Towns, 5

Tags: combinatorics unsolved , 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]