Olympiad problems

1998 Baltic Way, 18

Determine all positive integers $n$ for which there exists a set $S$ with the following properties: (i) $S$ consists of $n$ positive integers, all smaller than $2^{n-1}$; (ii) for any two distinct subsets $A$ and $B$ of $S$, the sum of the elements of $A$ is different from the sum of the elements of $B$.

2010 Contests, 3

Tags: combinatorics proposed , combinatorics

On each day, more than half of the inhabitants of Évora eats [i]sericaia[/i] as dessert. Show that there is a group of 10 inhabitants of Évora such that, on each of the last 2010 days, at least one of the inhabitants ate [i]sericaia[/i] as dessert.

2010 Mediterranean Mathematics Olympiad, 4

Tags: modular arithmetic , algebra , polynomial , linear algebra , matrix , combinatorics proposed , combinatorics

Let $p$ be a positive integer, $p>1.$ Find the number of $m\times n$ matrices with entries in the set $\left\{ 1,2,\dots,p\right\} $ and such that the sum of elements on each row and each column is not divisible by $p.$

1989 Polish MO Finals, 1

Tags: modular arithmetic , combinatorics proposed , combinatorics

An even number of politicians are sitting at a round table. After a break, they come back and sit down again in arbitrary places. Show that there must be two people with the same number of people sitting between them as before the break.. [b]Additional problem:[/b] Solve the problem when the number of people is in a form $6k+3$.

2004 Iran MO (3rd Round), 5

Tags: function , combinatorics proposed , combinatorics

assume that k,n are two positive integer $k\leq n$count the number of permutation $\{\ 1,\dots ,n\}\ $ st for any $1\leq i,j\leq k$and any positive integer m we have $f^m(i)\neq j$ ($f^m$ meas iterarte function,)

2014 Brazil National Olympiad, 5

Tags: geometry , rectangle , combinatorics proposed , combinatorics

There is an integer in each cell of a $2m\times 2n$ table. We define the following operation: choose three cells forming an L-tromino (namely, a cell $C$ and two other cells sharing a side with $C$, one being horizontal and the other being vertical) and sum $1$ to each integer in the three chosen cells. Find a necessary and sufficient condition, in terms of $m$, $n$ and the initial numbers on the table, for which there exists a sequence of operations that makes all the numbers on the table equal.

2001 Tuymaada Olympiad, 1

Tags: inequalities , combinatorics proposed , combinatorics

Ten volleyball teams played a tournament; every two teams met exactly once. The winner of the play gets 1 point, the loser gets 0 (there are no draws in volleyball). If the team that scored $n$-th has $x_{n}$ points ($n=1, \dots, 10$), prove that $x_{1}+2x_{2}+\dots+10x_{10}\geq 165$. [i]Proposed by D. Teryoshin[/i]

2003 Tournament Of Towns, 7

Tags: combinatorics proposed , combinatorics

A square is triangulated in such way that no three vertices are collinear. For every vertex (including vertices of the square) the number of sides issuing from it is counted. Can it happen that all these numbers are even?

2011 Kosovo National Mathematical Olympiad, 5

Tags: combinatorics proposed , combinatorics

Let $n>1$ be an integer and $S_n$ the set of all permutations $\pi : \{1,2,\cdots,n \} \to \{1,2,\cdots,n \}$ where $\pi$ is bijective function. For every permutation $\pi \in S_n$ we define: \[ F(\pi)= \sum_{k=1}^n |k-\pi(k)| \ \ \text{and} \ \ M_{n}=\frac{1}{n!}\sum_{\pi \in S_n} F(\pi) \] where $M_n$ is taken with all permutations $\pi \in S_n$. Calculate the sum $M_n$.

2013 Macedonia National Olympiad, 2

Tags: induction , combinatorics proposed , combinatorics

$ 2^n $ coins are given to a couple of kids. Interchange of the coins occurs when some of the kids has at least half of all the coins. Then from the coins of one of those kids to the all other kids are given that much coins as the kid already had. In case when all the coins are at one kid there is no possibility for interchange. What is the greatest possible number of consecutive interchanges? ($ n $ is natural number)

2012 China Team Selection Test, 1

Tags: algorithm , induction , combinatorics proposed , combinatorics

In a simple graph $G$, we call $t$ pairwise adjacent vertices a $t$[i]-clique[/i]. If a vertex is connected with all other vertices in the graph, we call it a [i]central[/i] vertex. Given are two integers $n,k$ such that $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$. Let $G$ be a graph on $n$ vertices such that [b](1)[/b] $G$ does not contain a $(k+1)$-[i]clique[/i]; [b](2)[/b] if we add an arbitrary edge to $G$, that creates a $(k+1)$-[i]clique[/i]. Find the least possible number of [i]central[/i] vertices in $G$.

2010 Hong kong National Olympiad, 2

Tags: inequalities , combinatorics proposed , combinatorics

Let $n$ be a positive integer. Find the number of sequences $x_{1},x_{2},\ldots x_{2n-1},x_{2n}$, where $x_{i}\in\{-1,1\}$ for each $i$, satisfying the following condition: for any integer $k$ and $m$ such that $1\le k\le m\le n$ then the following inequality holds \[\left|\sum_{i=2k-1}^{2m}x_{i}\right|\le\ 2\]

1998 Hungary-Israel Binational, 3

Tags: combinatorics proposed , combinatorics

Let $ n$ be a positive integer. We consider the set $ P$ of all partitions of $ n$ into a sum of positive integers (the order is irrelevant). For every partition $ \alpha$, let $ a_{k}(\alpha)$ be the number of summands in $ \alpha$ that are equal to $ k, k = 1,2,...,n.$ Prove that $ \sum_{\alpha\in P}\frac{1}{1^{a_{1}(\alpha)}a_{1}(\alpha)!\cdot 2^{a_{2}(\alpha)}a_{2}(\alpha)!...n^{a_{n}(\alpha)}a_{n}(\alpha)!}=1.$

1999 Baltic Way, 7

Tags: combinatorics proposed , combinatorics

Two squares on an $8\times 8$ chessboard are called adjacent if they have a common edge or common corner. Is it possible for a king to begin in some square and visit all squares exactly once in such a way that all moves except the first are made into squares adjacent to an even number of squares already visited?

1972 Bundeswettbewerb Mathematik, 1

Tags: combinatorics proposed , combinatorics

Given an infinity chess board and a knight on it. On how many different fields the knight can be after $n$ steps¿

1999 Romania Team Selection Test, 15

Tags: combinatorics proposed , combinatorics

The participants to an international conference are native and foreign scientist. Each native scientist sends a message to a foreign scientist and each foreign scientist sends a message to a native scientist. There are native scientists who did not receive a message. Prove that there exists a set $S$ of native scientists such that the outer $S$ scientists are exactly those who received messages from those foreign scientists who did not receive messages from scientists belonging to $S$. [i]Radu Niculescu[/i]

1999 Federal Competition For Advanced Students, Part 2, 3

Tags: Online Math Open , symmetry , combinatorics proposed , combinatorics

Two players $A$ and $B$ play the following game. An even number of cells are placed on a circle. $A$ begins and $A$ and $B$ play alternately, where each move consists of choosing a free cell and writing either $O$ or $M$ in it. The player after whose move the word $OMO$ (OMO = [i]Osterreichische Mathematik Olympiade[/i]) occurs for the first time in three successive cells wins the game. If no such word occurs, then the game is a draw. Prove that if player $B$ plays correctly, then player $A$ cannot win.

2010 Iran MO (3rd Round), 6

Tags: combinatorics proposed , combinatorics

Suppose that $X$ is a set with $n$ elements and $\mathcal F\subseteq X^{(k)}$ and $X_1,X_2,...,X_s$ is a partition of $X$. We know that for every $A,B\in \mathcal F$ and every $1\le j\le s$, $E=B\cap (\bigcup_{i=1}^{j}X_i)\neq A\cap (\bigcup_{i=1}^{j} X_i)=F$ shows that none of $E,F$ contains the other one. Prove that \[|\mathcal F|\le \max_{\sum\limits_{i=1}^{S}w_i=k}\prod_{j=1}^{s}\binom{|X_j|}{w_j}\] (15 points) Exam time was 5 hours and 20 minutes.

2006 Iran Team Selection Test, 1

Tags: algebra , polynomial , combinatorial geometry , IMO Shortlist , Ring Theory , combinatorics proposed , combinatorics

We have $n$ points in the plane, no three on a line. We call $k$ of them good if they form a convex polygon and there is no other point in the convex polygon. Suppose that for a fixed $k$ the number of $k$ good points is $c_k$. Show that the following sum is independent of the structure of points and only depends on $n$ : \[ \sum_{i=3}^n (-1)^i c_i \]

1999 Iran MO (2nd round), 3

Tags: combinatorics proposed , combinatorics

We have a $100\times100$ garden and we’ve plant $10000$ trees in the $1\times1$ squares (exactly one in each.). Find the maximum number of trees that we can cut such that on the segment between each two cut trees, there exists at least one uncut tree.

2004 Polish MO Finals, 3

Tags: inequalities , combinatorics proposed , combinatorics

On a tournament with $ n \ge 3$ participants, every two participants played exactly one match and there were no draws. A three-element set of participants is called a [i]draw-triple[/i] if they can be enumerated so that the ﬁrst defeated the second, the second defeated the third, and the third defeated the ﬁrst. Determine the largest possible number of draw-triples on such a tournament.

1993 IberoAmerican, 2

Tags: geometry , parallelogram , rotation , geometric transformation , reflection , combinatorics proposed , combinatorics

Show that for every convex polygon whose area is less than or equal to $1$, there exists a parallelogram with area $2$ containing the polygon.

2010 Korea National Olympiad, 3

Tags: combinatorics proposed , combinatorics

There are $ 2000 $ people, and some of them have called each other. Two people can call each other at most $1$ time. For any two groups of three people $ A$ and $ B $ which $ A \cap B = \emptyset $, there exist one person from each of $A$ and $B$ that haven't called each other. Prove that the number of two people called each other is less than $ 201000 $.

2009 Vietnam National Olympiad, 5

Tags: combinatorics proposed , combinatorics

Let $ S \equal{}\{1,2,3, \ldots, 2n\}$ ($ n \in \mathbb{Z}^\plus{}$). Ddetermine the number of subsets $ T$ of $ S$ such that there are no 2 element in $ T$ $ a,b$ such that $ |a\minus{}b|\equal{}\{1,n\}$

2005 Canada National Olympiad, 3

Tags: geometry , circumcircle , combinatorics proposed , combinatorics

Let $S$ be a set of $n\ge 3$ points in the interior of a circle. $a)$ Show that there are three distinct points $a,b,c\in S$ and three distinct points $A,B,C$ on the circle such that $a$ is (strictly) closer to $A$ than any other point in $S$, $b$ is closer to $B$ than any other point in $S$ and $c$ is closer to $C$ than any other point in $S$. $b)$ Show that for no value of $n$ can four such points in $S$ (and corresponding points on the circle) be guaranteed.