Olympiad problems

2011 Mongolia Team Selection Test, 3

Let $G$ be a graph, not containing $K_4$ as a subgraph and $|V(G)|=3k$ (I interpret this to be the number of vertices is divisible by 3). What is the maximum number of triangles in $G$?

1988 China Team Selection Test, 4

Tags: modular arithmetic , floor function , combinatorics unsolved , combinatorics

Let $k \in \mathbb{N},$ $S_k = \{(a, b) | a, b = 1, 2, \ldots, k \}.$ Any two elements $(a, b)$, $(c, d)$ $\in S_k$ are called "undistinguishing" in $S_k$ if $a - c \equiv 0$ or $\pm 1 \pmod{k}$ and $b - d \equiv 0$ or $\pm 1 \pmod{k}$; otherwise, we call them "distinguishing". For example, $(1, 1)$ and $(2, 5)$ are undistinguishing in $S_5$. Considering the subset $A$ of $S_k$ such that the elements of $A$ are pairwise distinguishing. Let $r_k$ be the maximum possible number of elements of $A$. (i) Find $r_5$. (ii) Find $r_7$. (iii) Find $r_k$ for $k \in \mathbb{N}$.

2006 Estonia Math Open Senior Contests, 6

Tags: rotation , pigeonhole principle , geometry , geometric transformation , combinatorics unsolved , combinatorics

Kati cut two equal regular $ n\minus{}gons$ out of paper. To the vertices of both $ n\minus{}gons$, she wrote the numbers 1 to $ n$ in some order. Then she stabbed a needle through the centres of these $ n\minus{}gons$ so that they could be rotated with respect to each other. Kati noticed that there is a position where the numbers at each pair of aligned vertices are different. Prove that the $ n\minus{}gons$ can be rotated to a position where at least two pairs of aligned vertices contain equal numbers.

2005 Rioplatense Mathematical Olympiad, Level 3, 3

Tags: integration , combinatorics unsolved , combinatorics

Let $k$ be a positive integer. Show that for all $n>k$ there exist convex figures $F_{1},\ldots, F_{n}$ and $F$ such that there doesn't exist a subset of $k$ elements from $F_{1},..., F_{n}$ and $F$ is covered for this elements, but $F$ is covered for every subset of $k+1$ elements from $F_{1}, F_{2},....., F_{n}$.

2010 Malaysia National Olympiad, 2

Tags: induction , combinatorics unsolved , combinatorics

A student wrote down the following sequence of numbers : the first number is 1, the second number is 2, and after that, each number is obtained by adding together all the previous numbers. Determine the 12th number in the sequence.

2010 Contests, 3

Tags: geometry , rectangle , combinatorics unsolved , combinatorics

We call a rectangle of the size $1 \times 2$ a domino. Rectangle of the $2 \times 3$ removing two opposite (under center of rectangle) corners we call tetramino. These figures can be rotated. It requires to tile rectangle of size $2008 \times 2010$ by using dominoes and tetraminoes. What is the minimal number of dominoes should be used?

1994 Vietnam Team Selection Test, 3

Tags: calculus , derivative , function , combinatorics unsolved , combinatorics

Calculate \[T = \sum \frac{1}{n_1! \cdot n_2! \cdot \cdots n_{1994}! \cdot (n_2 + 2 \cdot n_3 + 3 \cdot n_4 + \ldots + 1993 \cdot n_{1994})!}\] where the sum is taken over all 1994-tuples of the numbers $n_1, n_2, \ldots, n_{1994} \in \mathbb{N} \cup \{0\}$ satisfying $n_1 + 2 \cdot n_2 + 3 \cdot n_3 + \ldots + 1994 \cdot n_{1994} = 1994.$

1996 China Team Selection Test, 3

Tags: combinatorics unsolved , combinatorics

Let $ M \equal{} \lbrace 2, 3, 4, \ldots\, 1000 \rbrace$. Find the smallest $ n \in \mathbb{N}$ such that any $ n$-element subset of $ M$ contains 3 pairwise disjoint 4-element subsets $ S, T, U$ such that [b]I.[/b] For any 2 elements in $ S$, the larger number is a multiple of the smaller number. The same applies for $ T$ and $ U$. [b]II.[/b] For any $ s \in S$ and $ t \in T$, $ (s,t) \equal{} 1$. [b]III.[/b] For any $ s \in S$ and $ u \in U$, $ (s,u) > 1$.

2009 Germany Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

In Skinien there 2009 towns where each of them is connected with exactly 1004 other town by a highway. Prove that starting in an arbitrary town one can make a round trip along the highways such that each town is passed exactly once and finally one returns to its starting point.

2003 All-Russian Olympiad, 4

Tags: symmetry , ceiling function , geometry , rectangle , combinatorics unsolved , combinatorics

Find the greatest natural number $N$ such that, for any arrangement of the numbers $1, 2, \ldots, 400$ in a chessboard $20 \times 20$, there exist two numbers in the same row or column, which differ by at least $N.$

2010 USA Team Selection Test, 6

Tags: number theory , greatest common divisor , combinatorics unsolved , combinatorics

Let $T$ be a finite set of positive integers greater than 1. A subset $S$ of $T$ is called [i]good[/i] if for every $t \in T$ there exists some $s \in S$ with $\gcd(s, t) > 1$. Prove that the number of good subsets of $T$ is odd.

2004 Korea - Final Round, 1

Tags: combinatorics unsolved , combinatorics

On a circle there are $n$ points such that every point has a distinct number. Determine the number of ways of choosing $k$ points such that for any point there are at least 3 points between this point and the nearest point. (clockwise) ($n,k\geq 2$)

2012 Mexico National Olympiad, 4

Tags: inequalities , combinatorics unsolved , combinatorics

The following process is applied to each positive integer: the sum of its digits is subtracted from the number, and the result is divided by $9$. For example, the result of the process applied to $938$ is $102$, since $\frac{938-(9 + 3 + 8)}{9} = 102.$ Applying the process twice to $938$ the result is $11$, applied three times the result is $1$, and applying it four times the result is $0$. When the process is applied one or more times to an integer $n$, the result is eventually $0$. The number obtained before obtaining $0$ is called the [i]house[/i] of $n$. How many integers less than $26000$ share the same [i]house[/i] as $2012$?

1994 Baltic Way, 20

Tags: combinatorics unsolved , combinatorics

An equilateral triangle is divided into $9000000$ congruent equilateral triangles by lines parallel to its sides. Each vertex of the small triangles is coloured in one of three colours. Prove that there exist three points of the same colour being the vertices of a triangle with its sides parallel to the lines of the original triangle.

2004 All-Russian Olympiad, 3

Tags: induction , inequalities , combinatorics unsolved , combinatorics

In a country there are several cities; some of these cities are connected by airlines, so that an airline connects exactly two cities in each case and both flight directions are possible. Each airline belongs to one of $k$ flight companies; two airlines of the same flight company have always a common final point. Show that one can partition all cities in $k+2$ groups in such a way that two cities from exactly the same group are never connected by an airline with each other.

2005 All-Russian Olympiad, 4

Tags: algorithm , combinatorics unsolved , combinatorics

100 people from 25 countries, four from each countries, stay on a circle. Prove that one may partition them onto 4 groups in such way that neither no two countrymans, nor two neighbours will be in the same group.

2007 Finnish National High School Mathematics Competition, 4

Tags: combinatorics unsolved , combinatorics

The six offices of the city of Salavaara are to be connected to each other by a communication network which utilizes modern picotechnology. Each of the offices is to be connected to all the other ones by direct cable connections. Three operators compete to build the connections, and there is a separate competition for every connection. When the network is finished one notices that the worst has happened: the systems of the three operators are incompatible. So the city must reject connections built by two of the operators, and these are to be chosen so that the damage is minimized. What is the minimal number of offices which still can be connected to each other, possibly through intermediate offices, in the worst possible case.

2007 Kurschak Competition, 1

Tags: parameterization , combinatorics unsolved , combinatorics

We have placed $n>3$ cards around a circle, facing downwards. In one step we may perform the following operation with three consecutive cards. Calling the one on the center $B$, the two on the ends $A$ and $C$, we put card $C$ in the place of $A$, then move $A$ and $B$ to the places originally occupied by $B$ and $C$, respectively. Meanwhile, we flip the cards $A$ and $B$. Using a number of these steps, is it possible to move each card to its original place, but facing upwards?

2003 Tournament Of Towns, 5

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

A paper tetrahedron is cut along some of so that it can be developed onto the plane. Could it happen that this development cannot be placed on the plane in one layer?

2007 Canada National Olympiad, 1

Tags: combinatorics unsolved , combinatorics

What is the maximum number of non-overlapping $ 2\times 1$ dominoes that can be placed on a $ 8\times 9$ checkerboard if six of them are placed as shown? Each domino must be placed horizontally or vertically so as to cover two adjacent squares of the board.

1988 IMO Longlists, 33

Tags: geometry , rectangle , combinatorics unsolved , combinatorics

In a multiple choice test there were 4 questions and 3 possible answers for each question. A group of students was tested and it turned out that for any three of them there was a question which the three students answered differently. What is the maximum number of students tested?

1999 Mediterranean Mathematics Olympiad, 1

Tags: combinatorics unsolved , combinatorics

Do there exist a circle and an infinite set of points on it such that the distance between any two of the points is rational?

2006 Czech-Polish-Slovak Match, 2

Tags: invariant , modular arithmetic , arithmetic sequence , algebra , system of equations , IMO Shortlist , combinatorics unsolved

There are $n$ children around a round table. Erika is the oldest among them and she has $n$ candies, while no other child has any candy. Erika decided to distribute the candies according to the following rules. In every round, she chooses a child with at least two candies and the chosen child sends a candy to each of his/her two neighbors. (So in the first round Erika must choose herself). For which $n \ge 3$ is it possible to end the distribution after a finite number of rounds with every child having exactly one candy?

2000 South africa National Olympiad, 6

Tags: geometry , rectangle , combinatorics unsolved , combinatorics

Let $A_n$ be the number of ways to tile a $4 \times n$ rectangle using $2 \times 1$ tiles. Prove that $A_n$ is divisible by 2 if and only if $A_n$ is divisible by 3.

2011 Tuymaada Olympiad, 3

Tags: combinatorics unsolved , combinatorics

Written in each square of an infinite chessboard is the minimum number of moves needed for a knight to reach that square from a given square $O$. A square is called [i]singular[/i] if $100$ is written in it and $101$ is written in all four squares sharing a side with it. How many singular squares are there?