Olympiad problems

2012 Indonesia TST, 3

Let $S$ be a subset of $\{1,2,3,4,5,6,7,8,9,10\}$. If $S$ has the property that the sums of three elements of $S$ are all different, find the maximum number of elements of $S$.

2008 Junior Balkan MO, 4

Tags: linear algebra , matrix , vector , combinatorics proposed , combinatorics

A $ 4\times 4$ table is divided into $ 16$ white unit square cells. Two cells are called neighbors if they share a common side. A [i]move[/i] consists in choosing a cell and the colors of neighbors from white to black or from black to white. After exactly $ n$ moves all the $ 16$ cells were black. Find all possible values of $ n$.

2014 ELMO Shortlist, 6

Tags: function , combinatorics proposed , combinatorics

Let $f_0$ be the function from $\mathbb{Z}^2$ to $\{0,1\}$ such that $f_0(0,0)=1$ and $f_0(x,y)=0$ otherwise. For each positive integer $m$, let $f_m(x,y)$ be the remainder when \[ f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) \] is divided by $2$. Finally, for each nonnegative integer $n$, let $a_n$ denote the number of pairs $(x,y)$ such that $f_n(x,y) = 1$. Find a closed form for $a_n$. [i]Proposed by Bobby Shen[/i]

2003 Vietnam National Olympiad, 3

Tags: combinatorics proposed , combinatorics

Let $S_{n}$ be the number of permutations $(a_{1}, a_{2}, ... , a_{n})$ of $(1, 2, ... , n)$ such that $1 \leq |a_{k}-k | \leq 2$ for all $k$. Show that $\frac{7}{4}S_{n-1}< S_{n}< 2 S_{n-1}$ for $n > 6.$

2009 Korea National Olympiad, 4

Tags: combinatorics proposed , combinatorics

There are $n ( \ge 3) $ students in a class. Some students are friends each other, and friendship is always mutual. There are $ s ( \ge 1 ) $ couples of two students who are friends, and $ t ( \ge 1 ) $ triples of three students who are each friends. For two students $ x, y $ define $ d(x,y)$ be the number of students who are both friends with $ x $ and $ y $. Prove that there exist three students $ u, v, w $ who are each friends and satisfying \[ d(u,v) + d(v,w) + d(w,u) \ge \frac{9t}{s} . \]

2011 Switzerland - Final Round, 10

Tags: geometry , geometric transformation , combinatorics proposed , combinatorics

On each square of an $n\times n$-chessboard, there are two bugs. In a move, each bug moves to a (vertically of horizontally) adjacent square. Bugs from the same square always move to different squares. Determine the maximal number of free squares that can occur after one move. [i](Swiss Mathematical Olympiad 2011, Final round, problem 10)[/i]

2010 International Zhautykov Olympiad, 1

Tags: combinatorics proposed , combinatorics

Positive integers $1,2,...,n$ are written on а blackboard ($n >2$ ). Every minute two numbers are erased and the least prime divisor of their sum is written. In the end only the number 97 remains. Find the least $n$ for which it is possible.

1994 Brazil National Olympiad, 3

Tags: floor function , algorithm , combinatorics proposed , combinatorics

We are given n objects of identical appearance, but different mass, and a balance which can be used to compare any two objects (but only one object can be placed in each pan at a time). How many times must we use the balance to find the heaviest object and the lightest object?

2001 Poland - Second Round, 3

Tags: combinatorics proposed , combinatorics

For a positive integer $n$, let $A_n$ and $B_n$ be the families of $n$-element subsets of $S_n=\{1,2,\ldots ,2n\}$ with respectively even and odd sums of elements. Compute $|A_n|-|B_n|$.

2006 Indonesia MO, 4

Tags: induction , combinatorics proposed , combinatorics

A black pawn and a white pawn are placed on the first square and the last square of a $ 1\times n$ chessboard, respectively. Wiwit and Siti move alternatingly. Wiwit has the white pawn, and Siti has the black pawn. The white pawn moves first. In every move, the player moves her pawn one or two squares to the right or to the left, without passing the opponent's pawn. The player who cannot move anymore loses the game. Which player has the winning strategy? Explain the strategy.

2006 Moldova Team Selection Test, 2

Tags: combinatorics proposed , combinatorics

Let $n\in N$ $n\geq2$ and the set $X$ with $n+1$ elements. The ordered sequences $(a_{1}, a_{2},\ldots,a_{n})$ and $(b_{1},b_{2},\ldots b_{n})$ of distinct elements of $X$ are said to be $\textit{separated}$ if there exists $i\neq j$ such that $a_{i}=b_{j}$. Determine the maximal number of ordered sequences of $n$ elements from $X$ such that any two of them are $\textit{separated}$. Note: ordered means that, for example $(1,2,3)\neq(2,3,1)$.

2011 All-Russian Olympiad Regional Round, 11.4

Tags: induction , combinatorics proposed , combinatorics

2011 storage buildings are connected by roads so that it is possible to reach any building from any other building, possibly using multiple roads. The buildings contain $x_1,\dots,x_{2011}$ kilogram of cement. In one move, it is possible to relocate any quantity of cement from one building to any other building that is connected to it. The target is to have $y_1,\dots,y_{2011}$ redistributed across storage buildings and \[x_1+x_2+\dots+x_{2011}=y_1+y_2+\dots+y_{2011}.\] What is the minimal number of moves that the redistribution can take regardless of values of $x_i$ and $y_i$ and of the road plan? (Author: P. Karasev)

1992 Baltic Way, 15

Tags: search , combinatorics proposed , combinatorics

Noah has 8 species of animals to fit into 4 cages of the ark. He plans to put species in each cage. It turns out that, for each species, there are at most 3 other species with which it cannot share the accomodation. Prove that there is a way to assign the animals to their cages so that each species shares with compatible species.

2007 Bulgaria National Olympiad, 1

Tags: combinatorics proposed , combinatorics

Let $k>1$ be a given positive integer. A set $S$ of positive integers is called [i]good[/i] if we can colour the set of positive integers in $k$ colours such that each integer of $S$ cannot be represented as sum of two positive integers of the same colour. Find the greatest $t$ such that the set $S=\{a+1,a+2,\ldots ,a+t\}$ is [i]good[/i] for all positive integers $a$. [i]A. Ivanov, E. Kolev[/i]

2007 South africa National Olympiad, 6

Tags: IMO Shortlist , combinatorics proposed , combinatorics

Prove that it is not possible to write numbers $ 1,2,3,...,25$ on the squares of $ 5$x$ 5$ chessboard such that any neighboring numbers differ by at most $ 4$.

1992 Brazil National Olympiad, 6

Tags: search , combinatorics proposed , combinatorics

Given a set of n elements, find the largest number of subsets such that no subset is contained in any other

1971 IMO Longlists, 1

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

The points $S(i, j)$ with integer Cartesian coordinates $0 < i \leq n, 0 < j \leq m, m \leq n$, form a lattice. Find the number of: [b](a)[/b] rectangles with vertices on the lattice and sides parallel to the coordinate axes; [b](b)[/b] squares with vertices on the lattice and sides parallel to the coordinate axes; [b](c)[/b] squares in total, with vertices on the lattice.

2010 Contests, 2

Tags: induction , search , combinatorics proposed , combinatorics

How many ways are there to line up $19$ girls (all of different heights) in a row so that no girl has a shorter girl both in front of and behind her?

1993 Balkan MO, 2

Tags: calculus , integration , ceiling function , floor function , inequalities , combinatorics proposed , combinatorics

A positive integer given in decimal representation $\overline{ a_na_{n-1} \ldots a_1a_0 }$ is called [i]monotone[/i] if $a_n\leq a_{n-1} \leq \cdots \leq a_0$. Determine the number of monotone positive integers with at most 1993 digits.

2006 Macedonia National Olympiad, 5

Tags: ceiling function , combinatorics proposed , combinatorics

All segments joining $n$ points (no three of which are collinear) are coloured in one of $k$ colours. What is the smallest $k$ for which there always exists a closed polygonal line with the vertices at some of the $n$ points, whose sides are all of the same colour?

2014 Baltic Way, 8

Tags: combinatorics proposed , combinatorics

Albert and Betty are playing the following game. There are $100$ blue balls in a red bowl and $100$ red balls in a blue bowl. In each turn a player must make one of the following moves: a) Take two red balls from the blue bowl and put them in the red bowl. b) Take two blue balls from the red bowl and put them in the blue bowl. c) Take two balls of different colors from one bowl and throw the balls away. They take alternate turns and Albert starts. The player who first takes the last red ball from the blue bowl or the last blue ball from the red bowl wins. Determine who has a winning strategy.

2005 Georgia Team Selection Test, 12

Tags: combinatorics proposed , combinatorics

$ 30$ students participated in the mathematical Olympiad. Each of them was given $ 8$ problems to solve. Jury estimated their work with the following rule: 1) Each problem was worth $ k$ points, if it wasn't solved by exactly $ k$ students; 2) Each student received the maximum possible points in each problem or got $ 0$ in it; Lasha got the least number of points. What's the maximal number of points he could have? Remark: 1) means that if the problem was solved by exactly $ k$ students, than each of them got $ 30 \minus{} k$ points in it.

2015 Indonesia MO, 1

Tags: combinatorics proposed , combinatorics

Albert, Bernard, and Cheryl are playing marbles. At the beginning, each of them brings 5 red marbles, 7 green marbles and 13 blue marbles and in the middle of the table, there is a box of infinitely many red, blue and green marbles. In each turn, each player may choose 2 marbles of different color and replace them with 2 marbles of the third color. After a finite number of steps, this conversation happens. Albert : " I have only red marbles" Bernard : "I have only blue marbles" Cheryl: "I have only green marbles" Which of the three are lying?

2009 China National Olympiad, 2

Tags: combinatorics proposed , combinatorics

Let $ P$ be a convex $ n$ polygon each of which sides and diagnoals is colored with one of $ n$ distinct colors. For which $ n$ does: there exists a coloring method such that for any three of $ n$ colors, we can always find one triangle whose vertices is of $ P$' and whose sides is colored by the three colors respectively.

2007 Tuymaada Olympiad, 4

Tags: combinatorics proposed , combinatorics

Determine maximum real $ k$ such that there exist a set $ X$ and its subsets $ Y_{1}$, $ Y_{2}$, $ ...$, $ Y_{31}$ satisfying the following conditions: (1) for every two elements of $ X$ there is an index $ i$ such that $ Y_{i}$ contains neither of these elements; (2) if any non-negative numbers $ \alpha_{i}$ are assigned to the subsets $ Y_{i}$ and $ \alpha_{1}+\dots+\alpha_{31}=1$ then there is an element $ x\in X$ such that the sum of $ \alpha_{i}$ corresponding to all the subsets $ Y_{i}$ that contain $ x$ is at least $ k$.