Olympiad problems

2008 District Olympiad, 3

In a school there are $ 10$ rooms. Each student from a room knows exactly one student from each one of the other $ 9$ rooms. Prove that the rooms have the same number of students (we suppose that if $ A$ knows $ B$ then $ B$ knows $ A$).

2011 Iran MO (3rd Round), 4

Tags: combinatorics proposed , combinatorics

We say the point $i$ in the permutation $\sigma$ [b]ongoing[/b] if for every $j<i$ we have $\sigma (j)<\sigma (i)$. [b]a)[/b] prove that the number of permutations of the set $\{1,....,n\}$ with exactly $r$ ongoing points is $s(n,r)$. [b]b)[/b] prove that the number of $n$-letter words with letters $\{a_1,....,a_k\},a_1<.....<a_k$. with exactly $r$ ongoing points is $\sum_{m}\dbinom{k}{m} S(n,m) s(m,r)$.

2008 China Team Selection Test, 2

Tags: combinatorics proposed , combinatorics

Prove that for arbitary integer $ n > 16$, there exists the set $ S$ that contains $ n$ positive integers and has the following property:if the subset $ A$ of $ S$ satisfies for arbitary $ a,a'\in A, a\neq a', a \plus{} a'\notin S$ holds, then $ |A|\leq4\sqrt n.$

2010 Contests, 3

Tags: combinatorics proposed , combinatorics

Given is the set $M_n=\{0, 1, 2, \ldots, n\}$ of nonnegative integers less than or equal to $n$. A subset $S$ of $M_n$ is called [i]outstanding[/i] if it is non-empty and for every natural number $k\in S$, there exists a $k$-element subset $T_k$ of $S$. Determine the number $a(n)$ of outstanding subsets of $M_n$. [i](41st Austrian Mathematical Olympiad, National Competition, part 1, Problem 3)[/i]

1987 IMO Longlists, 3

Tags: combinatorics proposed , combinatorics

A town has a road network that consists entirely of one-way streets that are used for bus routes. Along these routes, bus stops have been set up. If the one-way signs permit travel from bus stop $X$ to bus stop $Y \neq X$, then we shall say [i]$Y$ can be reached from $X$[/i]. We shall use the phrase [i]$Y$ comes after $X$[/i] when we wish to express that every bus stop from which the bus stop $X$ can be reached is a bus stop from which the bus stop $Y$ can be reached, and every bus stop that can be reached from $Y$ can also be reached from $X$. A visitor to this town discovers that if $X$ and $Y$ are any two different bus stops, then the two sentences [i]“$Y$ can be reached from $X$”[/i] and [i]“$Y$ comes after $X$”[/i] have exactly the same meaning in this town. Let $A$ and $B$ be two bus stops. Show that of the following two statements, exactly one is true: [b] (i)[/b] $B$ can be reached from $A;$ [b] (ii) [/b] $A$ can be reached from $B.$

2001 Turkey Team Selection Test, 1

Tags: function , graph theory , combinatorics proposed , combinatorics

Each one of $2001$ children chooses a positive integer and writes down his number and names of some of other $2000$ children to his notebook. Let $A_c$ be the sum of the numbers chosen by the children who appeared in the notebook of the child $c$. Let $B_c$ be the sum of the numbers chosen by the children who wrote the name of the child $c$ into their notebooks. The number $N_c = A_c - B_c$ is assigned to the child $c$. Determine whether all of the numbers assigned to the children could be positive.

1993 Baltic Way, 14

Tags: combinatorics proposed , combinatorics

A square is divided into $16$ equal squares, obtaining the set of $25$ different vertices. What is the least number of vertices one must remove from this set, so that no $4$ points of the remaining set are the vertices of any square with sides parallel to the sides of the initial square?

1996 Baltic Way, 17

Tags: combinatorics proposed , combinatorics

Using each of the eight digits $1,3,4,5,6,7,8$ and $9$ exactly once, a three-digit number $A$, two two-digit numbers $B$ and $C$, $B<C$, and a one digit number $D$ are formed. The numbers are such that $A+D=B+C=143$. In how many ways can this be done?

2012 France Team Selection Test, 1

Tags: group theory , abstract algebra , graph theory , combinatorics proposed , combinatorics

Let $n$ and $k$ be two positive integers. Consider a group of $k$ people such that, for each group of $n$ people, there is a $(n+1)$-th person that knows them all (if $A$ knows $B$ then $B$ knows $A$). 1) If $k=2n+1$, prove that there exists a person who knows all others. 2) If $k=2n+2$, give an example of such a group in which no-one knows all others.

2001 India IMO Training Camp, 2

Tags: inequalities , combinatorics proposed , combinatorics

Two symbols $A$ and $B$ obey the rule $ABBB = B$. Given a word $x_1x_2\ldots x_{3n+1}$ consisting of $n$ letters $A$ and $2n+1$ letters $B$, show that there is a unique cyclic permutation of this word which reduces to $B$.

1999 Irish Math Olympiad, 4

Tags: geometry , rectangle , combinatorics proposed , combinatorics

A $ 100 \times 100$ square floor consisting of $ 10000$ squares is to be tiled by rectangular $ 1 \times 3$ tiles, fitting exactly over three squares of the floor. $ (a)$ If a $ 2 \times 2$ square is removed from the center of the floor, prove that the rest of the floor can be tiled with the available tiles. $ (b)$ If, instead, a $ 2 \times 2$ square is removed from the corner, prove that such a tiling is not possble.

1999 China National Olympiad, 3

Tags: combinatorics proposed , combinatorics

There are $99$ space stations. Each pair of space stations is connected by a tunnel. There are $99$ two-way main tunnels, and all the other tunnels are strictly one-way tunnels. A group of $4$ space stations is called [i]connected[/i] if one can reach each station in the group from every other station in the group without using any tunnels other than the $6$ tunnels which connect them. Determine the maximum number of connected groups.

2012 Canadian Mathematical Olympiad Qualification Repechage, 1

Tags: pigeonhole principle , combinatorics proposed , combinatorics

The front row of a movie theatre contains $45$ seats. [list] [*] (a) If $42$ people are sitting in the front row, prove that there are $10$ consecutive seats that are all occupied. [*] (b) Show that this conclusion doesn’t necessarily hold if only $41$ people are sitting in the front row.[/list]

2011 Kosovo National Mathematical Olympiad, 3

Tags: invariant , combinatorics proposed , combinatorics

A little boy wrote the numbers $1,2,\cdots,2011$ on a blackboard. He picks any two numbers $x,y$, erases them with a sponge and writes the number $|x-y|$. This process continues until only one number is left. Prove that the number left is even.

2005 District Olympiad, 1

Tags: induction , combinatorics proposed , combinatorics

Let $A_1$, $A_2$, $\ldots$, $A_n$, $n\geq 2$ be $n$ finite sets with the properties i) $|A_i| \geq 2$, for all $1\leq i \leq n$; ii) $|A_i\cap A_j| \neq 1$, for all $1\leq i<j\leq n$. Prove that the elements of the set $\displaystyle \bigcup_{i=1}^n A_i$ can be colored with 2 colors, such that all the sets $A_i$ are bi-color, for all $1\leq i \leq n$.

2007 Balkan MO Shortlist, C2

Tags: function , inequalities , algebra , domain , combinatorics proposed , combinatorics

Let $\mathcal{F}$ be the set of all the functions $f : \mathcal{P}(S) \longrightarrow \mathbb{R}$ such that for all $X, Y \subseteq S$, we have $f(X \cap Y) = \min (f(X), f(Y))$, where $S$ is a finite set (and $\mathcal{P}(S)$ is the set of its subsets). Find \[\max_{f \in \mathcal{F}}| \textrm{Im}(f) |. \]

2009 China National Olympiad, 3

Tags: induction , number theory , greatest common divisor , combinatorics proposed , combinatorics

Given an integer $ n > 3.$ Prove that there exists a set $ S$ consisting of $ n$ pairwisely distinct positive integers such that for any two different non-empty subset of $ S$:$ A,B, \frac {\sum_{x\in A}x}{|A|}$ and $ \frac {\sum_{x\in B}x}{|B|}$ are two composites which share no common divisors.

2011 Stars Of Mathematics, 3

Tags: geometry , perimeter , combinatorics proposed , combinatorics

The checkered plane is painted black and white, after a chessboard fashion. A polygon $\Pi$ of area $S$ and perimeter $P$ consists of some of these unit squares (i.e., its sides go along the borders of the squares). Prove the polygon $\Pi$ contains not more than $\dfrac {S} {2} + \dfrac {P} {8}$, and not less than $\dfrac {S} {2} - \dfrac {P} {8}$ squares of a same color. (Alexander Magazinov)

1997 All-Russian Olympiad, 2

Tags: probability , combinatorics proposed , combinatorics

The Judgment of the Council of Sages proceeds as follows: the king arranges the sages in a line and places either a white hat, black hat or a red hat on each sage's head. Each sage can see the color of the hats of the sages in front of him, but not of his own hat or of the hats of the sages behind him. Then one by one (in an order of their choosing), each sage guesses a color. Afterward, the king executes those sages who did not correctly guess the color of their own hat. The day before, the Council meets and decides to minimize the number of executions. What is the smallest number of sages guaranteed to survive in this case? [i]K. Knop[/i] P.S. Of course, the sages hear the previous guesses. See also [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=530552[/url]

1997 Romania Team Selection Test, 3

Tags: combinatorics proposed , combinatorics

The vertices of a regular dodecagon are coloured either blue or red. Find the number of all possible colourings which do not contain monochromatic sub-polygons. [i]Vasile Pop[/i]

2012 Iran MO (3rd Round), 1

Tags: combinatorics proposed , combinatorics

Let $G$ be a simple undirected graph with vertices $v_1,v_2,...,v_n$. We denote the number of acyclic orientations of $G$ with $f(G)$. [b]a)[/b] Prove that $f(G)\le f(G-v_1)+f(G-v_2)+...+f(G-v_n)$. [b]b)[/b] Let $e$ be an edge of the graph $G$. Denote by $G'$ the graph obtained by omiting $e$ and making it's two endpoints as one vertex. Prove that $f(G)=f(G-e)+f(G')$. [b]c)[/b] Prove that for each $\alpha >1$, there exists a graph $G$ and an edge $e$ of it such that $\frac{f(G)}{f(G-e)}<\alpha$. [i]Proposed by Morteza Saghafian[/i]

2013 India National Olympiad, 4

Tags: Putnam , induction , function , floor function , combinatorics proposed , combinatorics

Let $N$ be an integer greater than $1$ and let $T_n$ be the number of non empty subsets $S$ of $\{1,2,.....,n\}$ with the property that the average of the elements of $S$ is an integer.Prove that $T_n - n$ is always even.

2014 Canada National Olympiad, 2

Tags: floor function , combinatorics proposed , combinatorics , CMO

Let $m$ and $n$ be odd positive integers. Each square of an $m$ by $n$ board is coloured red or blue. A row is said to be red-dominated if there are more red squares than blue squares in the row. A column is said to be blue-dominated if there are more blue squares than red squares in the column. Determine the maximum possible value of the number of red-dominated rows plus the number of blue-dominated columns. Express your answer in terms of $m$ and $n$.

2008 Moldova Team Selection Test, 2

Tags: combinatorics proposed , combinatorics

We say the set $ \{1,2,\ldots,3k\}$ has property $ D$ if it can be partitioned into disjoint triples so that in each of them a number equals the sum of the other two. (a) Prove that $ \{1,2,\ldots,3324\}$ has property $ D$. (b) Prove that $ \{1,2,\ldots,3309\}$ hasn't property $ D$.

2009 China National Olympiad, 3

Tags: induction , combinatorics proposed , combinatorics

Given two integers $ m,n$ satisfying $ 4 < m < n.$ Let $ A_{1}A_{2}\cdots A_{2n \plus{} 1}$ be a regular $ 2n\plus{}1$ polygon. Denote by $ P$ the set of its vertices. Find the number of convex $ m$ polygon whose vertices belongs to $ P$ and exactly has two acute angles.