Olympiad problems

2009 Germany Team Selection Test, 2

Tracy has been baking a rectangular cake whose surface is dissected by grid lines in square fields. The number of rows is $ 2^n$ and the number of columns is $ 2^{n \plus{} 1}$ where $ n \geq 1, n \in \mathbb{N}.$ Now she covers the fields with strawberries such that each row has at least $ 2n \plus{} 2$ of them. Show that there four pairwise distinct strawberries $ A,B,C$ and $ D$ which satisfy those three conditions: (a) Strawberries $ A$ and $ B$ lie in the same row and $ A$ further left than $ B.$ Similarly $ D$ lies in the same row as $ C$ but further left. (b) Strawberries $ B$ and $ C$ lie in the same column. (c) Strawberries $ A$ lies further up and further left than $ D.$

1988 IMO Longlists, 68

Tags: geometry , geometric transformation , rotation , graph theory , combinatorics unsolved , combinatorics

In a group of $n$ people, each one knows exactly three others. They are seated around a table. We say that the seating is $perfect$ if everyone knows the two sitting by their sides. Show that, if there is a perfect seating $S$ for the group, then there is always another perfect seating which cannot be obtained from $S$ by rotation or reflection.

2010 Contests, 4

Tags: abstract algebra , induction , combinatorics unsolved , combinatorics

Each vertex of a finite graph can be coloured either black or white. Initially all vertices are black. We are allowed to pick a vertex $P$ and change the colour of $P$ and all of its neighbours. Is it possible to change the colour of every vertex from black to white by a sequence of operations of this type? Note: A finite graph consists of a finite set of vertices and a finite set of edges between vertices. If there is an edge between vertex $A$ and vertex $B,$ then $A$ and $B$ are neighbours of each other.

1996 India National Olympiad, 4

Tags: combinatorics unsolved , combinatorics

Let $X$ be a set containing $n$ elements. Find the number of ordered triples $(A,B, C)$ of subsets of $X$ such that $A$ is a subset of $B$ and $B$ is a proper subset of $C$.

1990 China National Olympiad, 6

Tags: combinatorics unsolved , combinatorics

A convex $n$-gon and its $n-3$ diagonals which have no common point inside the polygon form a [i]subdivision graph[/i]. Show that if and only if $3|n$, there exists a [i]subdivision graph [/i]that can be drawn in one closed stroke. (i.e. start from a certain vertex, get through every edges and diagonals exactly one time, finally back to the starting vertex.)

2010 Malaysia National Olympiad, 3

Tags: combinatorics unsolved , combinatorics

Let $N=\overline{abc}$ be a three-digit number. It is known that we can construct an isoceles triangle with $a,b$ and $c$ as the length of sides. Determine how many possible three-digit number $N$ there are. ($N=\overline{abc}$ means that $a,b$ and $c$ are digits of $N$, and not $N=a\times b\times c$.)

1999 South africa National Olympiad, 6

Tags: combinatorics unsolved , combinatorics

You are at a point $(a,b)$ and you need to reach another point $(c,d)$. Both points are below the line $x = y$ and have integer coordinates. You can move in steps of length 1, either upwards of to the right, but you may not move to a point on the line $x = y$. How many different paths are there?

2014 Greece Team Selection Test, 4

Tags: binomial coefficients , combinatorics unsolved , combinatorics

Square $ABCD$ is divided into $n^2$ equal small squares by lines parallel to its sides.A spider starts from $A$ and moving only rightward or upwards,tries to reach $C$.Every "movement" of the spider consists of $k$ steps rightward and $m$ steps upwards or $m$ steps rightward and $k$ steps upwards(it can follow any possible order for the steps of each "movement").The spider completes $l$ "movements" and afterwards it moves without limitation (it still moves rightwards and upwards only).If $n=m\cdot l$,find the number of the possible paths the spider can follow to reach $C$.Note that $n,m,k,l\in \mathbb{N^{*}}$ with $k<m$.

2004 Tournament Of Towns, 5

Tags: combinatorics unsolved , combinatorics

Two 10-digit integers are called neighbours if they diﬀer in exactly one digit (for example, integers $1234567890$ and $1234507890$ are neighbours). Find the maximal number of elements in the set of 10-digit integers with no two integers being neighbours.

1988 IMO Longlists, 75

Tags: modular arithmetic , combinatorics unsolved , combinatorics

Let $S$ be an infinite set of integers containing zero, and such that the distances between successive number never exceed a given fixed number. Consider the following procedure: Given a set $X$ of integers we construct a new set consisting of all numbers $x \pm s,$ where $x$ belongs to $X$ and s belongs to $S.$ Starting from $S_0 = \{0\}$ we successively construct sets $S_1, S_2, S_3, \ldots$ using this procedure. Show that after a finite number of steps we do not obtain any new sets, i.e. $S_k = S_{k_0}$ for $k \geq k_0.$

2014 Contests, 1

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

Is it possible to place the numbers $0,1,2,\dots,9$ on a circle so that the sum of any three consecutive numbers is a) 13, b) 14, c) 15?

2012 Kyrgyzstan National Olympiad, 6

Tags: invariant , modular arithmetic , induction , algorithm , combinatorics unsolved , combinatorics

The numbers $ 1, 2,\ldots, 50 $ are written on a blackboard. Each minute any two numbers are erased and their positive difference is written instead. At the end one number remains. Which values can take this number?

2012 Mexico National Olympiad, 5

Tags: combinatorics unsolved , combinatorics

Some frogs, some red and some others green, are going to move in an $11 \times 11$ grid, according to the following rules. If a frog is located, say, on the square marked with # in the following diagram, then [list] [*]If it is red, it can jump to any square marked with an x. [*]if it is green, it can jump to any square marked with an o.[/list] \[\begin{tabular}{| p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | l} \hline &&&&&&\\ \hline &&x&&o&&\\ \hline &o&&&&x&\\ \hline &&&\small{\#}&&&\\ \hline &x&&&&o&\\ \hline &&o&&x&&\\ \hline &&&&&&\\ \hline \end{tabular} \] We say 2 frogs (of any color) can meet at a square if both can get to the same square in one or more jumps, not neccesarily with the same amount of jumps. [list=a] [*]Prove if 6 frogs are placed, then there exist at least 2 that can meet at a square. [*]For which values of $k$ is it possible to place one green and one red frog such that they can meet at exactly $k$ squares?[/list]

2009 Ukraine National Mathematical Olympiad, 3

Tags: combinatorics unsolved , combinatorics

Given a $n \times n$ square board. Two players by turn remove some side of unit square if this side is not a bound of $n \times n$ square board. The player lose if after his move $n \times n$ square board became broken into two parts. Who has a winning strategy?

2011 Middle European Mathematical Olympiad, 3

Tags: combinatorics unsolved , combinatorics

For an integer $n \geq 3$, let $\mathcal M$ be the set $\{(x, y) | x, y \in \mathbb Z, 1 \leq x \leq n, 1 \leq y \leq n\}$ of points in the plane. What is the maximum possible number of points in a subset $S \subseteq \mathcal M$ which does not contain three distinct points being the vertices of a right triangle?

2010 Tournament Of Towns, 4

Tags: induction , combinatorics unsolved , combinatorics

$5000$ movie fans gathered at a convention. Each participant had watched at least one movie. The participants should be split into discussion groups of two kinds. In each group of the first kind, the members would discuss a movie they all watched. In each group of the second kind, each member would tell about the movie that no one else in this group had watched. Prove that the chairman can always split the participants into exactly 100 groups. (A group consisting of one person is allowed; in this case this person submits a report).

2002 Indonesia MO, 2

Tags: probability , combinatorics unsolved , combinatorics

Five dice are rolled. The product of the faces are then computed. Which result has a larger probability of occurring; $180$ or $144$?

2022 Grosman Mathematical Olympiad, P6

Tags: combinatorics , Coloring , combinatorics unsolved

In the following image is a beehive lattice of hexagons. Each cell is colored in one of three colors Red, Blue, or Green (denoted by the letters $R, B, G$). The frame is colored according to the instructions in the image, and the rest of the hexagons are colored however one wants. Is there necessarily a point where three hexagons of different colors meet?

1997 Irish Math Olympiad, 5

Tags: combinatorics unsolved , combinatorics

Let $ p$ be an odd prime number and $ n$ a natural number. Then $ n$ is called $ p\minus{}partitionable$ if $ T\equal{}\{1,2,...,n \}$ can be partitioned into (disjoint) subsets $ T_1,T_2,...,T_p$ with equal sums of elements. For example, $ 6$ is $ 3$-partitionable since we can take $ T_1\equal{}\{ 1,6 \}$, $ T_2\equal{}\{ 2,5 \}$ and $ T_3\equal{}\{ 3,4 \}$. $ (a)$ Suppose that $ n$ is $ p$-partitionable. Prove that $ p$ divides $ n$ or $ n\plus{}1$. $ (b)$ Suppose that $ n$ is divisible by $ 2p$. Prove that $ n$ is $ p$-partitionable.

2014 Iran MO (3rd Round), 2

Tags: combinatorics unsolved , combinatorics

Consider a flat field on which there exist a valley in the form of an infinite strip with arbitrary width $\omega$. There exist a polyhedron of diameter $d$(Diameter in a polyhedron is the maximum distance from the points on the polyhedron) is in one side and a pit of diameter $d$ on the other side of the valley. We want to roll the polyhedron and put it into the pit such that the polyhedron and the field always meet each other in one point at least while rolling (If the polyhedron and the field meet each other in one point at least then the polyhedron would not fall into the valley). For crossing over the bridge, we have built a rectangular bridge with a width of $\frac{d}{10}$ over the bridge. Prove that we can always put the polyhedron into the pit considering the mentioned conditions. (You will earn a good score if you prove the decision for $\omega = 0$).

2019 IFYM, Sozopol, 3

Tags: combinatorics , combinatorics unsolved , algorithm

There are 365 cards with 365 different numbers. Each step, we can choose 3 cards $a_{i},a_{j},a_{k}$ and we know the order of them (examble: $a_{i}<a_{j}<a_{k}$). With 2000 steps, can we order 365 cards from smallest to biggest??

2006 Turkey MO (2nd round), 2

Tags: ratio , graph theory , combinatorics unsolved , combinatorics

There are $2006$ students and $14$ teachers in a school. Each student knows at least one teacher (knowing is a symmetric relation). Suppose that, for each pair of a student and a teacher who know each other, the ratio of the number of the students whom the teacher knows to that of the teachers whom the student knows is at least $t.$ Find the maximum possible value of $t.$

1998 IberoAmerican, 2

Tags: combinatorics unsolved , combinatorics

Find the maximal possible value of $n$ such that there exist points $P_1,P_2,P_3,\ldots,P_n$ in the plane and real numbers $r_1,r_2,\ldots,r_n$ such that the distance between any two different points $P_i$ and $P_j$ is $r_i+r_j$.

1988 IMO Longlists, 32

Tags: geometry , 3D geometry , sphere , combinatorics unsolved , combinatorics

$n$ points are given on the surface of a sphere. Show that the surface can be divided into $n$ congruent regions such that each of them contains exactly one of the given points.

1993 Vietnam National Olympiad, 2

Tags: combinatorics unsolved , combinatorics

$1993$ points are arranged in a circle. At time $0$ each point is arbitrarily labeled $+1$ or $-1$. At times $n = 1, 2, 3, ...$ the vertices are relabeled. At time $n$ a vertex is given the label $+1$ if its two neighbours had the same label at time $n-1$, and it is given the label $-1$ if its two neighbours had different labels at time $n-1$. Show that for some time $n > 1$ the labeling will be the same as at time $1.$