Olympiad problems

2012 Pre - Vietnam Mathematical Olympiad, 4

Two people A and B play a game in the $m \times n$ grid ($m,n \in \mathbb{N^*}$). Each person respectively (A plays first) draw a segment between two point of the grid such that this segment doesn't contain any point (except the 2 ends) and also the segment (except the 2 ends) doesn't intersect with any other segments. The last person who can't draw is the loser. Which one (of A and B) have the winning tactics?

2014 Argentina Cono Sur TST, 6

Tags: combinatorics proposed , combinatorics

$120$ bags with $100$ coins are placed on the floor. One bag has coins that weigh $9$ grams, the other bags have coins that weigh $10$ grams. One may place some coins (not necessarily from the same bag) on a weighing scale, but it will only properly display the weight if it is less than $1000$ grams. Determine the minimum number of times that the weighing scale may be used in order to identify the bag that has the $9$-gram coins.

2002 Romania Team Selection Test, 4

Tags: function , modular arithmetic , combinatorics proposed , combinatorics

Let $f:\mathbb{Z}\rightarrow\{ 1,2,\ldots ,n\}$ be a function such that $f(x)\not= f(y)$, for all $x,y\in\mathbb{Z}$ such that $|x-y|\in\{2,3,5\}$. Prove that $n\ge 4$. [i]Ioan Tomescu[/i]

2005 Italy TST, 1

Tags: combinatorics proposed , combinatorics , Italy TST , TST , Team Selection Test , double counting

A stage course is attended by $n \ge 4$ students. The day before the final exam, each group of three students conspire against another student to throw him/her out of the exam. Prove that there is a student against whom there are at least $\sqrt[3]{(n-1)(n- 2)} $conspirators.

2009 International Zhautykov Olympiad, 3

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

In a checked $ 17\times 17$ table, $ n$ squares are colored in black. We call a line any of rows, columns, or any of two diagonals of the table. In one step, if at least $ 6$ of the squares in some line are black, then one can paint all the squares of this line in black. Find the minimal value of $ n$ such that for some initial arrangement of $ n$ black squares one can paint all squares of the table in black in some steps.

2013 Bundeswettbewerb Mathematik, 4

Tags: modular arithmetic , quadratics , floor function , combinatorics proposed , combinatorics

Two players $A$ and $B$ play the following game taking alternate moves. In each move, a player writes one digit on the blackboard. Each new digit is written either to the right or left of the sequence of digits already written on the blackboard. Suppose that $A$ begins the game and initially the blackboard was empty. $B$ wins the game if ,after some move of $B$, the sequence of digits written in the blackboard represents a perfect square. Prove that $A$ can prevent $B$ from winning.

2012 Greece National Olympiad, 4

Tags: geometry , trapezoid , combinatorics proposed , combinatorics

The following isosceles trapezoid consists of equal equilateral triangles with side length $1$. The side $A_1E$ has length $3$ while the larger base $A_1A_n$ has length $n-1$. Starting from the point $A_1$ we move along the segments which are oriented to the right and up(obliquely right or left). Calculate (in terms of $n$ or not) the number of all possible paths we can follow, in order to arrive at points $B,\Gamma,\Delta, E$, if $n$ is an integer greater than $3$. [color=#00CCA7][Need image][/color]

2006 Iran MO (3rd Round), 4

Tags: analytic geometry , algorithm , pigeonhole principle , geometry , combinatorics proposed , combinatorics

The image shown below is a cross with length 2. If length of a cross of length $k$ it is called a $k$-cross. (Each $k$-cross ahs $6k+1$ squares.) [img]http://aycu08.webshots.com/image/4127/2003057947601864020_th.jpg[/img] a) Prove that space can be tiled with $1$-crosses. b) Prove that space can be tiled with $2$-crosses. c) Prove that for $k\geq5$ space can not be tiled with $k$-crosses.

2014 Middle European Mathematical Olympiad, 4

Tags: invariant , induction , modular arithmetic , binomial coefficients , combinatorics proposed , combinatorics

In Happy City there are $2014$ citizens called $A_1, A_2, \dots , A_{2014}$. Each of them is either [i]happy[/i] or [i]unhappy[/i] at any moment in time. The mood of any citizen $A$ changes (from being unhappy to being happy or vice versa) if and only if some other happy citizen smiles at $A$. On Monday morning there were $N$ happy citizens in the city. The following happened on Monday during the day: the citizen $A_1$ smiled at citizen $A_2$, then $A_2$ smiled at $A_3$, etc., and, finally, $A_{2013}$ smiled at $A_{2014}$. Nobody smiled at anyone else apart from this. Exactly the same repeated on Tuesday, Wednesday and Thursday. There were exactly $2000$ happy citizens on Thursday evening. Determine the largest possible value of $N$.

2001 Tuymaada Olympiad, 1

Tags: combinatorics proposed , combinatorics

All positive integers are distributed among two disjoint sets $N_{1}$ and $N_{2}$ such that no difference of two numbers belonging to the same set is a prime greater than 100. Find all such distributions. [i]Proposed by N. Sedrakyan[/i]

2012 Junior Balkan MO, 3

Tags: ceiling function , modular arithmetic , combinatorics proposed , combinatorics

On a board there are $n$ nails, each two connected by a rope. Each rope is colored in one of $n$ given distinct colors. For each three distinct colors, there exist three nails connected with ropes of these three colors. a) Can $n$ be $6$ ? b) Can $n$ be $7$ ?

2002 Tournament Of Towns, 6

Tags: combinatorics proposed , combinatorics

The $52$ cards of a standard deck are placed in a $13\times 4$ array. If every two adjacent cards, vertically or horizontally, have the same suit or have the same value, prove that all $13$ cards of the same suit are in the same row.

2004 Bulgaria Team Selection Test, 3

Tags: Ross Mathematics Program , induction , linear algebra , matrix , combinatorics proposed , combinatorics

In any cell of an $n \times n$ table a number is written such that all the rows are distinct. Prove that we can remove a column such that the rows in the new table are still distinct.

2011 Middle European Mathematical Olympiad, 4

Tags: ceiling function , floor function , graph theory , expected value , combinatorics proposed , combinatorics , Probabilistic Method

Let $n \geq 3$ be an integer. At a MEMO-like competition, there are $3n$ participants, there are n languages spoken, and each participant speaks exactly three different languages. Prove that at least $\left\lceil\frac{2n}{9}\right\rceil$ of the spoken languages can be chosen in such a way that no participant speaks more than two of the chosen languages. [b]Note.[/b] $\lceil x\rceil$ is the smallest integer which is greater than or equal to $x$.

1977 IMO Longlists, 4

Tags: combinatorics proposed , combinatorics

We are given $n$ points in space. Some pairs of these points are connected by line segments so that the number of segments equals $[n^2/4],$ and a connected triangle exists. Prove that any point from which the maximal number of segments starts is a vertex of a connected triangle.

1991 Romania Team Selection Test, 10

Tags: function , combinatorics proposed , combinatorics

Let $a_1<a_2<\cdots<a_n$ be positive integers. Some colouring of $\mathbb{Z}$ is periodic with period $t$ such that for each $x\in \mathbb{Z}$ exactly one of $x+a_1,x+a_2,\dots,x+a_n$ is coloured. Prove that $n\mid t$. [i]Andrei Radulescu-Banu[/i]

1974 IMO Longlists, 16

Tags: combinatorics proposed , combinatorics

A pack of $2n$ cards contains $n$ different pairs of cards. Each pair consists of two identical cards, either of which is called the twin of the other. A game is played between two players $A$ and $B$. A third person called the [i]dealer[/i] shuffles the pack and deals the cards one by one face upward onto the table. One of the players, called the [i]receiver[/i], takes the card dealt, provided he does not have already its twin. If he does already have the twin, his opponent takes the dealt card and becomes the receiver. $A$ is initially the receiver and takes the first card dealt. The player who first obtains a complete set of $n$ different cards wins the game. What fraction of all possible arrangements of the pack lead to $A$ winning? Prove the correctness of your answer.

2007 Turkey Team Selection Test, 3

Tags: linear algebra , matrix , LaTeX , induction , absolute value , combinatorics proposed , combinatorics

We write $1$ or $-1$ on each unit square of a $2007 \times 2007$ board. Find the number of writings such that for every square on the board the absolute value of the sum of numbers on the square is less then or equal to $1$.

2012 May Olympiad, 5

Tags: floor function , combinatorics proposed , combinatorics

There are 12 people such that for every person A and person B there exists a person C that is a friend to both of them. Determine the minimum number of pairs of friends and construct a graph where the edges represent friendships.

2024 Baltic Way, 10

Tags: combinatorics , grid , combinatorics proposed

A frog is located on a unit square of an infinite grid oriented according to the cardinal directions. The frog makes moves consisting of jumping either one or two squares in the direction it is facing, and then turning according to the following rules: i) If the frog jumps one square, it then turns $90^\circ$ to the right; ii) If the frog jumps two squares, it then turns $90^\circ$ to the left. Is it possible for the frog to reach the square exactly $2024$ squares north of the initial square after some finite number of moves if it is initially facing: a) North; b) East?

2007 All-Russian Olympiad, 5

Tags: induction , algebra , polynomial , function , combinatorics proposed , combinatorics

Two numbers are written on each vertex of a convex $100$-gon. Prove that it is possible to remove a number from each vertex so that the remaining numbers on any two adjacent vertices are different. [i]F. Petrov [/i]

2000 Iran MO (3rd Round), 1

Tags: combinatorics proposed , combinatorics

In a tennis tournament where $ n$ players $ A_1,A_2,\dots,A_n$ take part, any two players play at most one match, and $ k \leq \frac {n(n \minus{} 1)}{2}$ $ 2$ matches are played. The winner of a match gets $ 1$ point while the loser gets $ 0$. Prove that a sequence $ d_1,d_2,\dots,d_n$ of nonnegative integers can be the sequence of scores of the players ($ d_i$ being the score of$ A_i$) if and only if $ (i)\ \ d_1 \plus{} d_2 \plus{} \dots \plus{} d_n \equal{} k$, and $ (ii)\ \text{for any} X\subset\{A_1,\dots,A_n\}$, the number of matches between the players in $ X$ is at most $ \sum_{A_j\in X}d_j$

2006 Taiwan National Olympiad, 1

Tags: probability , expected value , combinatorics proposed , combinatorics , Random walk , random walks

There are 94 safes and 94 keys. Each key can open only one safe, and each safe can be opened by only one key. We place randomly one key into each safe. 92 safes are then randomly chosen, and then locked. What is the probability that we can open all the safes with the two keys in the two remaining safes? (Once a safe is opened, the key inside the safe can be used to open another safe.)

2002 Bundeswettbewerb Mathematik, 1

Tags: induction , combinatorics proposed , combinatorics

A pile of cards, numbered with $1$, $2$, ..., $n$, is being shuffled. Afterwards, the following operation is repeatedly performed: If the uppermost card of the pile has the number $k$, then we reverse the order of the $k$ uppermost cards. Prove that, after finitely many executions of this operation, the card with the number $1$ will become the uppermost card of the pile.

2003 CentroAmerican, 1

Tags: combinatorics proposed , combinatorics

Two players $A$ and $B$ take turns playing the following game: There is a pile of $2003$ stones. In his first turn, $A$ selects a divisor of $2003$ and removes this number of stones from the pile. $B$ then chooses a divisor of the number of remaining stones, and removes that number of stones from the new pile, and so on. The player who has to remove the last stone loses. Show that one of the two players has a winning strategy and describe the strategy.