Olympiad problems

2011 International Zhautykov Olympiad, 1

Find the maximum number of sets which simultaneously satisfy the following conditions: [b]i)[/b] any of the sets consists of $4$ elements, [b]ii)[/b] any two different sets have exactly $2$ common elements, [b]iii)[/b] no two elements are common to all the sets.

2000 Canada National Olympiad, 3

Tags: combinatorics unsolved , combinatorics

Let $A = (a_1, a_2, \cdots ,a_{2000})$ be a sequence of integers each lying in the interval $[-1000,1000]$. Suppose that the entries in A sum to $1$. Show that some nonempty subsequence of $A$ sums to zero.

2007 All-Russian Olympiad, 2

Tags: geometry , rectangle , combinatorics unsolved , combinatorics

The numbers $1,2,\ldots,100$ are written in the cells of a $10\times 10$ table, each number is written once. In one move, Nazar may interchange numbers in any two cells. Prove that he may get a table where the sum of the numbers in every two adjacent (by side) cells is composite after at most $35$ such moves. [i]N. Agakhanov[/i]

2007 APMO, 1

Tags: geometry , analytic geometry , vector , pigeonhole principle , modular arithmetic , combinatorics unsolved

Let $S$ be a set of $9$ distinct integers all of whose prime factors are at most $3.$ Prove that $S$ contains $3$ distinct integers such that their product is a perfect cube.

1994 All-Russian Olympiad Regional Round, 11.8

Tags: combinatorics unsolved , combinatorics

Points $ A_1,A_2, ... ,A_n$ inside a circle and points $ B_1,B_2,...,B_n$ on its boundary are positioned so that the segments $ A_1B_1,A_2B_2, ... ,A_nB_n$ do not intersect. A bug can go from point $ A_i$ to $ A_j$ if the segment $ A_iA_j$ does not intersect any segment $ A_kB_k$, $ k \neq i, j$. Prove that the bug can go from any point $ A_p$ to any point $ A_q$ in a finite number of steps.

2002 Switzerland Team Selection Test, 8

Tags: combinatorics unsolved , combinatorics

In a group of $n$ people, every weekend someone organizes a party in which he invites all of his acquaintances. Those who meet at a party become acquainted. After each of the $n$ people has organized a party, there still are two people not knowing each other. Show that these two will never get to know each other at such a party.

2014 Junior Balkan Team Selection Tests - Romania, 2

Tags: pigeonhole principle , symmetry , combinatorics unsolved , combinatorics

Let $x_1, x_2 \ldots , x_5$ be real numbers. Find the least positive integer $n$ with the following property: if some $n$ distinct sums of the form $x_p+x_q+x_r$ (with $1\le p<q<r\le 5$) are equal to $0$, then $x_1=x_2=\cdots=x_5=0$.

2003 Hungary-Israel Binational, 1

Tags: greatest common divisor , combinatorics unsolved , combinatorics

Two players play the following game. They alternately write divisors of $100!$ on the blackboard, not repeating any of the numbers written before. The player after whose move the greatest common divisor of the written numbers equals $1,$ loses the game. Which player has a winning strategy?

2009 Nordic, 4

Tags: combinatorics unsolved , combinatorics

$32$ competitors participate in a tournament. No two of them are equal and in a one against one match the better always wins. Show that the gold, silver, and bronze medal winners can be found in $39$ matches.

2000 Finnish National High School Mathematics Competition, 5

Tags: probability , combinatorics unsolved , combinatorics

Irja and Valtteri are tossing coins. They take turns, Irja starting. Each of them has a pebble which reside on opposite vertices of a square at the start. If a player gets heads, she or he moves her or his pebble on opposite vertex. Otherwise the player in turn moves her or his pebble to an adjacent vertex so that Irja proceeds in positive and Valtteri in negative direction. The winner is the one who can move his pebble to the vertex where opponent's pebble lies. What is the probability that Irja wins the game?

1997 China Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

Let $n$ be a natural number greater than 6. $X$ is a set such that $|X| = n$. $A_1, A_2, \ldots, A_m$ are distinct 5-element subsets of $X$. If $m > \frac{n(n - 1)(n - 2)(n - 3)(4n - 15)}{600}$, prove that there exists $A_{i_1}, A_{i_2}, \ldots, A_{i_6}$ $(1 \leq i_1 < i_2 < \cdots, i_6 \leq m)$, such that $\bigcup_{k = 1}^6 A_{i_k} = 6$.

1984 IMO Longlists, 68

Tags: combinatorics unsolved , combinatorics

In the Martian language every finite sequence of letters of the Latin alphabet letters is a word. The publisher “Martian Words” makes a collection of all words in many volumes. In the first volume there are only one-letter words, in the second, two-letter words, etc., and the numeration of the words in each of the volumes continues the numeration of the previous volume. Find the word whose numeration is equal to the sum of numerations of the words Prague, Olympiad, Mathematics.

2005 Hungary-Israel Binational, 2

Tags: combinatorics unsolved , combinatorics

Let $f$ be an increasing mapping from the family of subsets of a given ﬁnite set $H$ into itself, i.e. such that for every $X \subseteq Y\subseteq H$ we have $f (X )\subseteq f (Y )\subseteq H .$ Prove that there exists a subset $H_{0}$ of $H$ such that $f (H_{0}) = H_{0}.$

1987 Federal Competition For Advanced Students, P2, 2

Tags: combinatorics unsolved , combinatorics

Find the number of all sequences $ (x_1,...,x_n)$ of letters $ a,b,c$ that satisfy $ x_1\equal{}x_n\equal{}a$ and $ x_i \not\equal{} x_{i\plus{}1}$ for $ 1 \le i \le n\minus{}1.$

1991 China Team Selection Test, 3

Tags: invariant , induction , combinatorial geometry , combinatorics unsolved , combinatorics

$5$ points are given in the plane, any three non-collinear and any four non-concyclic. If three points determine a circle that has one of the remaining points inside it and the other one outside it, then the circle is said to be [i]good[/i]. Let the number of good circles be $n$; find all possible values of $n$.

1991 China National Olympiad, 6

Tags: combinatorics unsolved , combinatorics

A football is covered by some polygonal pieces of leather which are sewed up by three different colors threads. It features as follows: i) any edge of a polygonal piece of leather is sewed up with an equal-length edge of another polygonal piece of leather by a certain color thread; ii) each node on the ball is vertex to exactly three polygons, and the three threads joint at the node are of different colors. Show that we can assign to each node on the ball a complex number (not equal to $1$), such that the product of the numbers assigned to the vertices of any polygonal face is equal to $1$.

1995 Taiwan National Olympiad, 2

Tags: combinatorics unsolved , combinatorics

Given a sequence of eight integers $x_{1},x_{2},...,x_{8}$ in a single operation one replaces these numbers with $|x_{1}-x_{2}|,|x_{2}-x_{3}|,...,|x_{8}-x_{1}|$. Find all the eight-term sequences of integers which reduce to a sequence with all the terms equal after finitely many single operations.

2006 Finnish National High School Mathematics Competition, 5

Tags: combinatorics unsolved , combinatorics

The game of Nelipe is played on a $16\times16$-grid as follows: The two players write in turn numbers $1, 2,..., 16$ in different squares. The numbers on each row, column, and in every one of the 16 smaller squares have to be different. The loser is the one who is not able to write a number. Which one of the players wins, if both play with an optimal strategy?

1993 All-Russian Olympiad Regional Round, 11.8

Tags: ceiling function , inequalities , combinatorics unsolved , combinatorics

There are $ 1993$ towns in a country, and at least $ 93$ roads going out of each town. It's known that every town can be reached from any other town. Prove that this can always be done with no more than $ 62$ transfers.

1996 Hungary-Israel Binational, 3

Tags: combinatorics unsolved , combinatorics

A given convex polyhedron has no vertex which belongs to exactly 3 edges. Prove that the number of faces of the polyhedron that are triangles, is at least 8.

2004 Poland - Second Round, 3

Tags: induction , combinatorics unsolved , combinatorics

There are $ n\geq 5$ people in a party. Assume that among any three of them some two know each other. Show that one can select at least $ \frac{n}{2}$ people and arrange them at a round table so that each person sits between two of his/her acquaintances.

1994 China Team Selection Test, 2

Tags: function , ratio , arithmetic sequence , algebra , system of equations , combinatorics unsolved , combinatorics

An $n$ by $n$ grid, where every square contains a number, is called an $n$-code if the numbers in every row and column form an arithmetic progression. If it is sufficient to know the numbers in certain squares of an $n$-code to obtain the numbers in the entire grid, call these squares a key. [b]a.) [/b]Find the smallest $s \in \mathbb{N}$ such that any $s$ squares in an $n-$code $(n \geq 4)$ form a key. [b]b.)[/b] Find the smallest $t \in \mathbb{N}$ such that any $t$ squares along the diagonals of an $n$-code $(n \geq 4)$ form a key.

2006 MOP Homework, 5

Tags: combinatorics unsolved , combinatorics

Find all pairs of positive integers (m, n) for which it is possible to paint each unit square of an m*n chessboard either black or white in such way that, for any unit square of the board, the number of unit squares which are painted the same color as that square and which have at least one common vertex with it (including the square itself) is even.

2010 Contests, 3

Tags: combinatorics unsolved , combinatorics

Adam has RM2010 in his bank account. He donates RM10 to charity every day. His first donation is on Monday. On what day will he donate his last RM10?

2004 Switzerland Team Selection Test, 9

Tags: induction , combinatorics unsolved , combinatorics

Let $A_{1}, ..., A_{n}$ be different subsets of an $n$-element set $X$. Show that there exists $x\in X$ such that the sets $A_{1}-\{x\}, A_{2}-\{x\}, ..., A_{n}-\{x\}$ are all different.