Olympiad problems

2009 Baltic Way, 16

A [i]$n$-trønder walk[/i] is a walk starting at $(0, 0)$, ending at $(2n, 0)$ with no self intersection and not leaving the first quadrant, where every step is one of the vectors $(1, 1)$, $(1, -1)$ or $(-1, 1)$. Find the number of $n$-trønder walks.

1970 IMO Longlists, 40

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

Let ABC be a triangle with angles $\alpha, \beta, \gamma$ commensurable with $\pi$. Starting from a point $P$ interior to the triangle, a ball reflects on the sides of $ABC$, respecting the law of reflection that the angle of incidence is equal to the angle of reflection. Prove that, supposing that the ball never reaches any of the vertices $A,B,C$, the set of all directions in which the ball will move through time is finite. In other words, its path from the moment $0$ to infinity consists of segments parallel to a finite set of lines.

2013 Iran Team Selection Test, 10

Tags: combinatorics proposed , combinatorics

On each edge of a graph is written a real number,such that for every even tour of this graph,sum the edges with signs alternatively positive and negative is zero.prove that one can assign to each of the vertices of the graph a real number such that sum of the numbers on two adjacent vertices is the number on the edge between them.(tour is a closed path from the edges of the graph that may have repeated edges or vertices)

2010 Junior Balkan MO, 4

Tags: geometry , rectangle , rotation , inequalities , combinatorics proposed , combinatorics

A $9\times 7$ rectangle is tiled with tiles of the two types: L-shaped tiles composed by three unit squares (can be rotated repeatedly with $90^\circ$) and square tiles composed by four unit squares. Let $n\ge 0$ be the number of the $2 \times 2 $ tiles which can be used in such a tiling. Find all the values of $n$.

2009 China Team Selection Test, 2

Tags: modular arithmetic , algebra , polynomial , number theory , combinatorics proposed , combinatorics , Additive combinatorics

Find all the pairs of integers $ (a,b)$ satisfying $ ab(a \minus{} b)\not \equal{} 0$ such that there exists a subset $ Z_{0}$ of set of integers $ Z,$ for any integer $ n$, exactly one among three integers $ n,n \plus{} a,n \plus{} b$ belongs to $ Z_{0}$.

1968 Miklós Schweitzer, 8

Tags: combinatorics proposed , combinatorics

Let $ n$ and $ k$ be given natural numbers, and let $ A$ be a set such that \[ |A| \leq \frac{n(n+1)}{k+1}.\] For $ i=1,2,...,n+1$, let $ A_i$ be sets of size $ n$ such that \[ |A_i \cap A_j| \leq k \;(i \not=j)\ ,\] \[ A= \bigcup_{i=1}^{n+1} A_i.\] Determine the cardinality of $ A$. [i]K. Corradi[/i]

2009 IberoAmerican, 1

Tags: combinatorics proposed , combinatorics

Given a positive integer $ n\geq 2$, consider a set of $ n$ islands arranged in a circle. Between every two neigboring islands two bridges are built as shown in the figure. Starting at the island $ X_1$, in how many ways one can one can cross the $ 2n$ bridges so that no bridge is used more than once?

2009 Macedonia National Olympiad, 3

Tags: combinatorics proposed , combinatorics

The Macedonian Mathematical Olympiad is held in two rooms numbered $1$ and $2$. At the beginning all of the competitors enter room No. $1$. The final arrangement of the competitors to the rooms is obtained in the following way: a list with the names of a few of the competitors is read aloud; after a name is read, the corresponding competitor and all of his/her acquaintances from the rest of the competitors change the room in which they currently are. Hence, to each list of names corresponds one final arrangement of the competitors to the rooms. Show that the total number of possible final arrangements is not equal to $2009$ (acquaintance between competitors is a symmetrical relation).

2009 Romania Team Selection Test, 1

Tags: combinatorics proposed , combinatorics

For non-empty subsets $A,B \subset \mathbb{Z}$ define \[A+B=\{a+b:a\in A, b\in B\},\ A-B=\{a-b:a\in A, b\in B\}.\] In the sequel we work with non-empty finite subsets of $\mathbb{Z}$. Prove that we can cover $B$ by at most $\frac{|A+B|}{|A|}$ translates of $A-A$, i.e. there exists $X\subset Z$ with $|X|\leq \frac{|A+B|}{|A|}$ such that \[B\subseteq \cup_{x\in X} (x+(A-A))=X+A-A.\]

2006 Romania National Olympiad, 4

Tags: combinatorics proposed , combinatorics

$\displaystyle 2n$ students $\displaystyle (n \geq 5)$ participated at table tennis contest, which took $\displaystyle 4$ days. In every day, every student played a match. (It is possible that the same pair meets twice or more times, in different days) Prove that it is possible that the contest ends like this: - there is only one winner; - there are $\displaystyle 3$ students on the second place; - no student lost all $\displaystyle 4$ matches. How many students won only a single match and how many won exactly $\displaystyle 2$ matches? (In the above conditions)

2009 Balkan MO Shortlist, C1

Tags: symmetry , geometry , rectangle , combinatorics proposed , combinatorics

A $ 9 \times 12$ rectangle is partitioned into unit squares. The centers of all the unit squares, except for the four corner squares and eight squares sharing a common side with one of them, are coloured red. Is it possible to label these red centres $ C_1,C_2,\ldots ,C_{96}$ in such way that the following to conditions are both fulfilled i) the distances $C_1C_2,\ldots ,C_{95}C_{96}, C_{96}C_{1}$ are all equal to $ \sqrt {13}$, ii) the closed broken line $ C_1C_2\ldots C_{96}C_1$ has a centre of symmetry? [i]Bulgaria[/i]

2000 Bundeswettbewerb Mathematik, 1

Tags: combinatorics proposed , combinatorics

We are given $n \geq 3$ weights of masses $1, 2, 3, \ldots , n$ grams. Find all $n$ for which it is possible to divide these weights into three groups with the same mass.

2013 Iran Team Selection Test, 2

Tags: floor function , induction , group theory , abstract algebra , combinatorics proposed , combinatorics

Find the maximum number of subsets from $\left \{ 1,...,n \right \}$ such that for any two of them like $A,B$ if $A\subset B$ then $\left | B-A \right |\geq 3$. (Here $\left | X \right |$ is the number of elements of the set $X$.)

2017 Benelux, 2

Tags: combinatorics , combinatorics proposed , games

Let $n\geq 2$ be an integer. Alice and Bob play a game concerning a country made of $n$ islands. Exactly two of those $n$ islands have a factory. Initially there is no bridge in the country. Alice and Bob take turns in the following way. In each turn, the player must build a bridge between two different islands $I_1$ and $I_2$ such that: $\bullet$ $I_1$ and $I_2$ are not already connected by a bridge. $\bullet$ at least one of the two islands $I_1$ and $I_2$ is connected by a series of bridges to an island with a factory (or has a factory itself). (Indeed, access to a factory is needed for the construction.) As soon as a player builds a bridge that makes it possible to go from one factory to the other, this player loses the game. (Indeed, it triggers an industrial battle between both factories.) If Alice starts, then determine (for each $n\geq 2$) who has a winning strategy. ([i]Note:[/i] It is allowed to construct a bridge passing above another bridge.)

2006 Romania Team Selection Test, 2

Tags: induction , combinatorics proposed , combinatorics

Let $m$ and $n$ be positive integers and $S$ be a subset with $(2^m-1)n+1$ elements of the set $\{1,2,3,\ldots, 2^mn\}$. Prove that $S$ contains $m+1$ distinct numbers $a_0,a_1,\ldots, a_m$ such that $a_{k-1} \mid a_{k}$ for all $k=1,2,\ldots, m$.

2006 District Olympiad, 2

Tags: combinatorics proposed , combinatorics

A $9\times 9$ array is filled with integers from 1 to 81. Prove that there exists $k\in\{1,2,3,\ldots, 9\}$ such that the product of the elements in the row $k$ is different from the product of the elements in the column $k$ of the array.

1999 USAMO, 1

Tags: induction , combinatorics proposed , combinatorics

Some checkers placed on an $n \times n$ checkerboard satisfy the following conditions: (a) every square that does not contain a checker shares a side with one that does; (b) given any pair of squares that contain checkers, there is a sequence of squares containing checkers, starting and ending with the given squares, such that every two consecutive squares of the sequence share a side. Prove that at least $(n^{2}-2)/3$ checkers have been placed on the board.

2013 Iran Team Selection Test, 14

Tags: geometry , rectangle , analytic geometry , induction , combinatorics proposed , combinatorics

we are given $n$ rectangles in the plane. Prove that between $4n$ right angles formed by these rectangles there are at least $[4\sqrt n]$ distinct right angles.

2007 China Team Selection Test, 2

Tags: combinatorics proposed , combinatorics

Given an integer $ k > 1.$ We call a $ k \minus{}$digits decimal integer $ a_{1}a_{2}\cdots a_{k}$ is $ p \minus{}$monotonic, if for each of integers $ i$ satisfying $ 1\le i\le k \minus{} 1,$ when $ a_{i}$ is an odd number, $ a_{i} > a_{i \plus{} 1};$ when $ a_{i}$ is an even number, $ a_{i}<a_{i \plus{} 1}.$ Find the number of $ p \minus{}$monotonic $ k \minus{}$digits integers.

2012 Indonesia TST, 2

Tags: combinatorics proposed , combinatorics

A TV station holds a math talent competition, where each participant will be scored by 8 people. The scores are F (failed), G (good), or E (exceptional). The competition is participated by three people, A, B, and C. In the competition, A and B get the same score from exactly 4 people. C states that he has differing scores with A from at least 4 people, and also differing scores with B from at least 4 people. Assuming C tells the truth, how many scoring schemes can occur?

2013 Kazakhstan National Olympiad, 3

Tags: geometry , rectangle , combinatorics proposed , combinatorics

How many non-intersecting pairs of paths we have from (0,0) to (n,n) so that path can move two ways:top or right?

2007 All-Russian Olympiad, 8

Tags: linear algebra , matrix , geometry , rectangle , combinatorics proposed , combinatorics

Given a matrix $\{a_{ij}\}_{i,j=0}^{9}$, $a_{ij}=10i+j+1$. Andrei is going to cover its entries by $50$ rectangles $1\times 2$ (each such rectangle contains two adjacent entries) so that the sum of $50$ products in these rectangles is minimal possible. Help him. [i]A. Badzyan[/i]

2010 Contests, 1

Tags: combinatorics proposed , combinatorics

Let $S$ be a subset with $673$ elements of the set $\{1,2,\ldots ,2010\}$. Prove that one can find two distinct elements of $S$, say $a$ and $b$, such that $6$ divides $a+b$.

2014 Contests, 1

Tags: absolute value , combinatorics proposed , combinatorics

In a bag there are $1007$ black and $1007$ white balls, which are randomly numbered $1$ to $2014$. In every step we draw one ball and put it on the table; also if we want to, we may choose two different colored balls from the table and put them in a different bag. If we do that we earn points equal to the absolute value of their differences. How many points can we guarantee to earn after $2014$ steps?

2014 Contests, 3a

Tags: analytic geometry , combinatorics proposed , combinatorics

A grasshopper is jumping about in a grid. From the point with coordinates $(a, b)$ it can jump to either $(a + 1, b),(a + 2, b),(a + 1, b + 1),(a, b + 2)$ or $(a, b + 1)$. In how many ways can it reach the line $x + y = 2014?$ Where the grasshopper starts in $(0, 0)$.