Olympiad problems

2001 Vietnam Team Selection Test, 2

Tags: analytic geometry , floor function , ceiling function , IMO Shortlist , combinatorics unsolved , combinatorics

Let an integer $n > 1$ be given. In the space with orthogonal coordinate system $Oxyz$ we denote by $T$ the set of all points $(x, y, z)$ with $x, y, z$ are integers, satisfying the condition: $1 \leq x, y, z \leq n$. We paint all the points of $T$ in such a way that: if the point $A(x_0, y_0, z_0)$ is painted then points $B(x_1, y_1, z_1)$ for which $x_1 \leq x_0, y_1 \leq y_0$ and $z_1 \leq z_0$ could not be painted. Find the maximal number of points that we can paint in such a way the above mentioned condition is satisfied.

2010 Tournament Of Towns, 2

Tags: combinatorics unsolved , combinatorics

At a circular track, $2n$ cyclists started from some point at the same time in the same direction with different constant speeds. If any two cyclists are at some point at the same time again, we say that they meet. No three or more of them have met at the same time. Prove that by the time every two cyclists have met at least once, each cyclist has had at least $n^2$ meetings.

2005 China Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

Given positive integer $n (n \geq 2)$, find the largest positive integer $\lambda$ satisfying : For $n$ bags, if every bag contains some balls whose weights are all integer powers of $2$ (the weights of balls in a bag may not be distinct), and the total weights of balls in every bag are equal, then there exists a weight among these balls such that the total number of balls with this weight is at least $\lambda$.

2001 India IMO Training Camp, 3

Tags: combinatorics unsolved , combinatorics

Each vertex of an $m\times n$ grid is colored blue, green or red in such a way that all the boundary vertices are red. We say that a unit square of the grid is properly colored if: $(i)$ all the three colors occur at the vertices of the square, and $(ii)$ one side of the square has the endpoints of the same color. Show that the number of properly colored squares is even.

2011 India IMO Training Camp, 3

Tags: combinatorics unsolved , combinatorics

A set of $n$ distinct integer weights $w_1,w_2,\ldots, w_n$ is said to be [i]balanced[/i] if after removing any one of weights, the remaining $(n-1)$ weights can be split into two subcollections (not necessarily with equal size)with equal sum. $a)$ Prove that if there exist [i]balanced[/i] sets of sizes $k,j$ then also a [i]balanced[/i] set of size $k+j-1$. $b)$ Prove that for all [i]odd[/i] $n\geq 7$ there exist a [i]balanced[/i] set of size $n$.

2019 Philippine TST, 1

Tags: combinatorics , flights , graph theory , combinatorics unsolved

Let $n$ and $\ell$ be integers such that $n \ge 3$ and $1 < \ell < n$. A country has $n$ cities. Between any two cities $A$ and $B$, either there is no flight from $A$ to $B$ and also none from $B$ to $A$, or there is a unique [i]two-way trip[/i] between them. A [i]two-way trip[/i] is a flight from $A$ to $B$ and a flight from $B$ to $A$. There exist two cities such that the least possible number of flights required to travel from one of them to the other is $\ell$. Find the maximum number of two-way trips among the $n$ cities.

1988 Irish Math Olympiad, 5

Tags: combinatorics unsolved , combinatorics

Problem: A person has seven friends and invites a different subset of three friends to dinner every night for one week (seven days). In how many ways can this be done so that all friends are invited at least once?

2014 Tuymaada Olympiad, 4

Tags: geometry , parallelogram , induction , combinatorics unsolved , combinatorics , Tuymaada

A $k\times \ell$ 'parallelogram' is drawn on a paper with hexagonal cells (it consists of $k$ horizontal rows of $\ell$ cells each). In this parallelogram a set of non-intersecting sides of hexagons is chosen; it divides all the vertices into pairs. Juniors) How many vertical sides can there be in this set? Seniors) How many ways are there to do that? [asy] size(120); defaultpen(linewidth(0.8)); path hex = dir(30)--dir(90)--dir(150)--dir(210)--dir(270)--dir(330)--cycle; for(int i=0;i<=3;i=i+1) { for(int j=0;j<=2;j=j+1) { real shiftx=j*sqrt(3)/2+i*sqrt(3),shifty=j*3/2; draw(shift(shiftx,shifty)*hex); } } [/asy] [i](T. Doslic)[/i]

2002 India IMO Training Camp, 2

Tags: combinatorics unsolved , combinatorics

Show that there is a set of $2002$ consecutive positive integers containing exactly $150$ primes. (You may use the fact that there are $168$ primes less than $1000$)

2005 China National Olympiad, 5

Tags: geometry , rectangle , combinatorial geometry , combinatorics unsolved , combinatorics

There are 5 points in a rectangle (including its boundary) with area 1, no three of them are in the same line. Find the minimum number of triangles with the area not more than $\frac 1{4}$, vertex of which are three of the five points.

2003 Turkey MO (2nd round), 3

Tags: combinatorics unsolved , combinatorics

An assignment of either a $ 0$ or a $ 1$ to each unit square of an $ m$x$ n$ chessboard is called $ fair$ if the total numbers of $ 0$s and $ 1$s are equal. A real number $ a$ is called $ beautiful$ if there are positive integers $ m,n$ and a fair assignment for the $ m$x$ n$ chessboard such that for each of the $ m$ rows and $ n$ columns , the percentage of $ 1$s on that row or column is not less than $ a$ or greater than $ 100\minus{}a$. Find the largest beautiful number.

1993 All-Russian Olympiad, 2

Tags: induction , combinatorics unsolved , combinatorics

The integers from $1$ to $1993$ are written in a line in some order. The following operation is performed with this line: if the first number is $k$ then the first $k$ numbers are rewritten in reverse order. Prove that after some finite number of these operations, the first number in the line of numbers will be $1$.

2003 All-Russian Olympiad, 3

Tags: combinatorics unsolved , combinatorics

There are $100$ cities in a country, some of them being joined by roads. Any four cities are connected to each other by at least two roads. Assume that there is no path passing through every city exactly once. Prove that there are two cities such that every other city is connected to at least one of them.

1988 Vietnam National Olympiad, 1

Tags: combinatorics unsolved , combinatorics

There are $ 1988$ birds in $ 994$ cages, two in each cage. Every day we change the arrangement of the birds so that no cage contains the same two birds as ever before. What is the greatest possible number of days we can keep doing so?

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]

2006 MOP Homework, 1

Tags: combinatorics unsolved , combinatorics

There are $2005$ players in a chess tournament played a game. Every pair of players played a game against each other. At the end of the tournament, it turned out that if two players $A$ and $B$ drew the game between them, then every other player either lost to $A$ or to $B$. Suppose that there are at least two draws in the tournament. Prove that all players can be lined up in a single file from left to right in the such a way that every play won the game against the person immediately to his right.

2004 Tournament Of Towns, 3

Tags: combinatorics unsolved , combinatorics

We have a number of towns, with bus routes between some of them (each bus route goes from a town to another town without any stops). It is known that you can get from any town to any other by bus (possibly changing buses several times). Mr. Ivanov bought one ticket for each of the bus routes (a ticket allows single travel in either direction, but not returning on the same route). Mr. Petrov bought n tickets for each of the bus routes. Both Ivanov and Petrov started at town A. Ivanov used up all his tickets without buying any new ones and finished his travel at town B. Petrov, after using some of his tickets, got stuck at town X: he can not leave it without buying a new ticket. Prove that X is either A or B.

2008 Nordic, 2

Tags: combinatorics unsolved , combinatorics

Assume that $n\ge 3$ people with different names sit around a round table. We call any unordered pair of them, say $M,N$, dominating if 1) they do not sit in adjacent seats 2) on one or both arcs connecting $M,N$ along the table, all people have names coming alphabetically after $M,N$. Determine the minimal number of dominating pairs.

2009 South africa National Olympiad, 5

Tags: invariant , absolute value , combinatorics unsolved , combinatorics

A game is played on a board with an infinite row of holes labelled $0, 1, 2, \dots$. Initially, $2009$ pebbles are put into hole $1$; the other holes are left empty. Now steps are performed according to the following scheme: (i) At each step, two pebbles are removed from one of the holes (if possible), and one pebble is put into each of the neighbouring holes. (ii) No pebbles are ever removed from hole $0$. (iii) The game ends if there is no hole with a positive label that contains at least two pebbles. Show that the game always terminates, and that the number of pebbles in hole $0$ at the end of the game is independent of the specific sequence of steps. Determine this number.

1991 China Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

For $i = 1,2, \ldots, 1991$, we choose $n_i$ points and write number $i$ on them (each point has only written one number on it). A set of chords are drawn such that: (i) They are pairwise non-intersecting. (ii) The endpoints of each chord have distinct numbers. If for all possible assignments of numbers the operation can always be done, find the necessary and sufficient condition the numbers $n_1, n_2, \ldots, n_{1991}$ must satisfy for this to be possible.

1994 China National Olympiad, 2

Tags: pigeonhole principle , combinatorics unsolved , combinatorics

There are $m$ pieces of candy held in $n$ trays($n,m\ge 4$). An [i]operation[/i] is defined as follow: take out one piece of candy from any two trays respectively, then put them in a third tray. Determine, with proof, if we can move all candies to a single tray by finite [i]operations[/i].

2011 China Girls Math Olympiad, 4

Tags: probability , expected value , combinatorics unsolved , combinatorics

A tennis tournament has $n>2$ players and any two players play one game against each other (ties are not allowed). After the game these players can be arranged in a circle, such that for any three players $A,B,C$, if $A,B$ are adjacent on the circle, then at least one of $A,B$ won against $C$. Find all possible values for $n$.

1998 Vietnam Team Selection Test, 3

Tags: combinatorics unsolved , combinatorics

In a conference there are $n \geq 10$ people. It is known that: [b]I.[/b] Each person knows at least $\left[\frac{n+2}{3}\right]$ other people. [b]II.[/b] For each pair of person $A$ and $B$ who don't know each other, there exist some people $A(1), A(2), \ldots, A(k)$ such that $A$ knows $A(1)$, $A(i)$ knows $A(i+1)$ and $A(k)$ knows $B$. [b]III.[/b] There doesn't exist a Hamilton path. Prove that: We can divide those people into 2 groups: $A$ group has a Hamilton cycle, and the other contains of people who don't know each other.

2008 Turkey Team Selection Test, 6

Tags: combinatorics unsolved , combinatorics

There are $ n$ voters and $ m$ candidates. Every voter makes a certain arrangement list of all candidates (there is one person in every place $ 1,2,...m$) and votes for the first $ k$ people in his/her list. The candidates with most votes are selected and say them winners. A poll profile is all of this $ n$ lists. If $ a$ is a candidate, $ R$ and $ R'$ are two poll profiles. $ R'$ is $ a\minus{}good$ for $ R$ if and only if for every voter; the people which in a worse position than $ a$ in $ R$ is also in a worse position than $ a$ in $ R'$. We say positive integer $ k$ is monotone if and only if for every $ R$ poll profile and every winner $ a$ for $ R$ poll profile is also a winner for all $ a\minus{}good$ $ R'$ poll profiles. Prove that $ k$ is monotone if and only if $ k>\frac{m(n\minus{}1)}{n}$.

2002 Italy TST, 2

Tags: floor function , combinatorics unsolved , combinatorics

On a soccer tournament with $n\ge 3$ teams taking part, several matches are played in such a way that among any three teams, some two play a match. $(a)$ If $n=7$, find the smallest number of matches that must be played. $(b)$ Find the smallest number of matches in terms of $n$.