Olympiad problems

1996 All-Russian Olympiad, 8

The numbers from 1 to 100 are written in an unknown order. One may ask about any 50 numbers and find out their relative order. What is the fewest questions needed to find the order of all 100 numbers? [i]S. Tokarev[/i]

2024 German National Olympiad, 3

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

At a party, $25$ elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves. Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.

2008 Czech-Polish-Slovak Match, 3

Tags: geometry , rectangle , combinatorics proposed , combinatorics

Find all triplets $(k, m, n)$ of positive integers having the following property: Square with side length $m$ can be divided into several rectangles of size $1\times k$ and a square with side length $n$.

2009 China Western Mathematical Olympiad, 2

Tags: combinatorics proposed , combinatorics

Given an integer $n\ge\ 3$, find the least positive integer $k$, such that there exists a set $A$ with $k$ elements, and $n$ distinct reals $x_{1},x_{2},\ldots,x_{n}$ such that $x_{1}+x_{2}, x_{2}+x_{3},\ldots, x_{n-1}+x_{n}, x_{n}+x_{1}$ all belong to $A$.

Oliforum Contest IV 2013, 3

Tags: combinatorics proposed , combinatorics , Contest 8

Given an integer $n$ greater than $1$, suppose $x_1,x_2,\ldots,x_n$ are integers such that none of them is divisible by $n$, and neither their sum. Prove that there exists atleast $n-1$ non-empty subsets $\mathcal I\subseteq \{1,\ldots, n\}$ such that $\sum_{i\in\mathcal I}x_i$ is divisible by $n$

2007 China Team Selection Test, 3

Tags: function , induction , combinatorics proposed , combinatorics

Let $ n$ be positive integer, $ A,B\subseteq[0,n]$ are sets of integers satisfying $ \mid A\mid \plus{} \mid B\mid\ge n \plus{} 2.$ Prove that there exist $ a\in A, b\in B$ such that $ a \plus{} b$ is a power of $ 2.$

2011 Pre-Preparation Course Examination, 4

Tags: combinatorics proposed , combinatorics

A star $K_{1,3}$ is called a paw. suppose that $G$ is a graph without any induced paws. prove that $\chi(G)\le(\omega(G))^2$. (15 points)

2010 ELMO Shortlist, 3

Tags: modular arithmetic , algorithm , combinatorics proposed , combinatorics , Elmo

2010 MOPpers are assigned numbers 1 through 2010. Each one is given a red slip and a blue slip of paper. Two positive integers, A and B, each less than or equal to 2010 are chosen. On the red slip of paper, each MOPper writes the remainder when the product of A and his or her number is divided by 2011. On the blue slip of paper, he or she writes the remainder when the product of B and his or her number is divided by 2011. The MOPpers may then perform either of the following two operations: [list] [*] Each MOPper gives his or her red slip to the MOPper whose number is written on his or her blue slip. [*] Each MOPper gives his or her blue slip to the MOPper whose number is written on his or her red slip.[/list] Show that it is always possible to perform some number of these operations such that each MOPper is holding a red slip with his or her number written on it. [i]Brian Hamrick.[/i]

2011 China Second Round Olympiad, 4

Tags: linear algebra , matrix , combinatorics proposed , combinatorics

Let $A$ be a $3 \times 9$ matrix. All elements of $A$ are positive integers. We call an $m\times n$ submatrix of $A$ "ox" if the sum of its elements is divisible by $10$, and we call an element of $A$ "carboxylic" if it is not an element of any "ox" submatrix. Find the largest possible number of "carboxylic" elements in $A$.

1979 IMO Longlists, 16

Tags: combinatorics proposed , combinatorics

Let $Q$ be a square with side length $6$. Find the smallest integer $n$ such that in $Q$ there exists a set $S$ of $n$ points with the property that any square with side $1$ completely contained in $Q$ contains in its interior at least one point from $S$.

2011 ELMO Shortlist, 5

Tags: logarithms , algorithm , combinatorics proposed , combinatorics

Prove there exists a constant $c$ (independent of $n$) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where a) $f(n)=n\ln{n}$; b) $f(n)=n$. [i]David Yang.[/i]

2013 China Team Selection Test, 3

Tags: analytic geometry , geometry , combinatorics proposed , combinatorics

A point $(x,y)$ is a [i]lattice point[/i] if $x,y\in\Bbb Z$. Let $E=\{(x,y):x,y\in\Bbb Z\}$. In the coordinate plane, $P$ and $Q$ are both sets of points in and on the boundary of a convex polygon with vertices on lattice points. Let $T=P\cap Q$. Prove that if $T\ne\emptyset$ and $T\cap E=\emptyset$, then $T$ is a non-degenerate convex quadrilateral region.

2010 Contests, 3

Tags: combinatorics proposed , combinatorics , Set systems , Projective plane

In an exam every question is solved by exactly four students, every pair of questions is solved by exactly one student, and none of the students solved all of the questions. Find the maximum possible number of questions in this exam.

2003 Baltic Way, 11

Tags: combinatorics proposed , combinatorics

Is it possible to select $1000$ points in the plane so that $6000$ pairwise distances between them are equal?

1995 Baltic Way, 13

Tags: combinatorics proposed , combinatorics

Consider the following two person game. A number of pebbles are situated on the table. Two players make their moves alternately. A move consists of taking off the table $x$ pebbles where $x$ is the square of any positive integer. The player who is unable to make a move loses. Prove that there are infinitely many initial situations in which the second player can win no matter how his opponent plays.

2012 APMO, 2

Tags: rectangle , combinatorics proposed , combinatorics

Into each box of a $ 2012 \times 2012 $ square grid, a real number greater than or equal to $ 0 $ and less than or equal to $ 1 $ is inserted. Consider splitting the grid into $2$ non-empty rectangles consisting of boxes of the grid by drawing a line parallel either to the horizontal or the vertical side of the grid. Suppose that for at least one of the resulting rectangles the sum of the numbers in the boxes within the rectangle is less than or equal to $ 1 $, no matter how the grid is split into $2$ such rectangles. Determine the maximum possible value for the sum of all the $ 2012 \times 2012 $ numbers inserted into the boxes.

2014 Kyiv Mathematical Festival, 3a

Tags: combinatorics proposed , combinatorics , Kyiv mathematical festival

a) There are 8 teams in a Quidditch tournament. Each team plays every other team once without draws. Prove that there exist teams $A,B,C,D$ such that pairs of teams $A,B$ and $C,D$ won the same number of games in total. b) There are 25 teams in a Quidditch tournament. Each team plays every other team once without draws. Prove that there exist teams $A,B,C,D,E,F$ such that pairs of teams $A,B,$ $~$ $C,D$ and $E,F$ won the same number of games in total.

2002 Tournament Of Towns, 2

Tags: geometry , rectangle , combinatorics proposed , combinatorics

A game is played on a $23\times 23$ board. The first player controls two white chips which start in the bottom left and top right corners. The second player controls two black ones which start in bottom right and top left corners. The players move alternately. In each move, a player moves one of the chips under control to a square which shares a side with the square the chip is currently in. The first player wins if he can bring the white chips to squares which share a side with each other. Can the second player prevent the first player from winning?

1998 Iran MO (3rd Round), 4

Tags: combinatorics , combinatorics proposed

Let be given $r_1,r_2,\ldots,r_n \in \mathbb R$. Show that there exists a subset $I$ of $\{1,2,\ldots,n \}$ which which has one or two elements in common with the sets $\{i,i + 1,i + 2\} , (1 \leq i \leq n- 2)$ such that \[\left| {\mathop \sum \limits_{i \in I} {r_i}} \right| \geqslant \frac{1}{6}\mathop \sum \limits_{i = 1}^n \left| {{r_i}} \right|.\]

2007 Italy TST, 2

Tags: modular arithmetic , combinatorics proposed , combinatorics

In a competition, there were $2n+1$ teams. Every team plays exatly once against every other team. Every match finishes with the victory of one of the teams. We call cyclical a 3-subset of team ${ A,B,C }$ if $A$ won against $B$, $B$ won against $C$ , $C$ won against $A$. (a) Find the minimum of cyclical 3-subset (depending on $n$); (b) Find the maximum of cyclical 3-subset (depending on $n$).

2007 Iran MO (2nd Round), 3

Tags: analytic geometry , combinatorics proposed , combinatorics

In a city, there are some buildings. We say the building $A$ is dominant to the building $B$ if the line that connects upside of $A$ to upside of $B$ makes an angle more than $45^{\circ}$ with earth. We want to make a building in a given location. Suppose none of the buildings are dominant to each other. Prove that we can make the building with a height such that again, none of the buildings are dominant to each other. (Suppose the city as a horizontal plain and each building as a perpendicular line to the plain.)

2014 Greece National Olympiad, 3

Tags: Euler , modular arithmetic , combinatorial geometry , combinatorics proposed , combinatorics , Discrete intermediate value theorem

For even positive integer $n$ we put all numbers $1,2,...,n^2$ into the squares of an $n\times n$ chessboard (each number appears once and only once). Let $S_1$ be the sum of the numbers put in the black squares and $S_2$ be the sum of the numbers put in the white squares. Find all $n$ such that we can achieve $\frac{S_1}{S_2}=\frac{39}{64}.$

2007 International Zhautykov Olympiad, 1

Tags: combinatorics proposed , combinatorics

There are given $111$ coins and a $n\times n$ table divided into unit cells. This coins are placed inside the unit cells (one unit cell may contain one coin, many coins, or may be empty), such that the difference between the number of coins from two neighbouring cells (that have a common edge) is $1$. Find the maximal $n$ for this to be possible.

2012 Iran MO (3rd Round), 2

Tags: combinatorics proposed , combinatorics

Suppose $s,k,t\in \mathbb N$. We've colored each natural number with one of the $k$ colors, such that each color is used infinitely many times. We want to choose a subset $\mathcal A$ of $\mathbb N$ such that it has $t$ disjoint monochromatic $s$-element subsets. What is the minimum number of elements of $A$? [i]Proposed by Navid Adham[/i]

2001 Austrian-Polish Competition, 9

Tags: combinatorics proposed , combinatorics

Let $A$ be a set with $2n$ elements, and let $A_1, A_2...,A_m$ be subsets of $A$e ach one with n elements. Find the greatest possible m, such that it is possible to select these $m$ subsets in such a way that the intersection of any 3 of them has at most one element.