Olympiad problems

2021 Baltic Way, 15

For which positive integers $n\geq4$ does there exist a convex $n$-gon with side lengths $1, 2, \dots, n$ (in some order) and with all of its sides tangent to the same circle?

2011 Middle European Mathematical Olympiad, 2

Tags: combinatorics proposed , combinatorics

Let $n \geq 3$ be an integer. John and Mary play the following game: First John labels the sides of a regular $n$-gon with the numbers $1, 2,\ldots, n$ in whatever order he wants, using each number exactly once. Then Mary divides this $n$-gon into triangles by drawing $n-3$ diagonals which do not intersect each other inside the $n$-gon. All these diagonals are labeled with number $1$. Into each of the triangles the product of the numbers on its sides is written. Let S be the sum of those $n - 2$ products. Determine the value of $S$ if Mary wants the number $S$ to be as small as possible and John wants $S$ to be as large as possible and if they both make the best possible choices.

2012 Romanian Master of Mathematics, 3

Tags: function , algebra proposed , algebra , combinatorics , combinatorics proposed , Additive combinatorics

Each positive integer is coloured red or blue. A function $f$ from the set of positive integers to itself has the following two properties: (a) if $x\le y$, then $f(x)\le f(y)$; and (b) if $x,y$ and $z$ are (not necessarily distinct) positive integers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$. Prove that there exists a positive number $a$ such that $f(x)\le ax$ for all positive integers $x$. [i](United Kingdom) Ben Elliott[/i]

2012 Middle European Mathematical Olympiad, 3

Tags: combinatorics proposed , combinatorics

Let $ n $ be a positive integer. Consider words of length $n$ composed of letters from the set $ \{ M, E, O \} $. Let $ a $ be the number of such words containing an even number (possibly 0) of blocks $ ME $ and an even number (possibly 0) blocks of $ MO $ . Similarly let $ b $ the number of such words containing an odd number of blocks $ ME $ and an odd number of blocks $ MO $. Prove that $ a>b $.

2001 Romania National Olympiad, 3

Tags: vector , combinatorics proposed , combinatorics

Let $n\in\mathbb{N}^*$ and $v_1,v_2,\ldots ,v_n$ be vectors in the plane with lengths less than or equal to $1$. Prove that there exists $\xi_1,\xi_2,\ldots ,\xi_n\in\{-1,1\}$ such that \[ | \xi_1v_1+\xi_2v_2+\ldots +\xi_nv_n|\le\sqrt{2}\]

2007 China Team Selection Test, 2

Tags: combinatorics proposed , combinatorics

Given $ n$ points arbitrarily in the plane $ P_{1},P_{2},\ldots,P_{n},$ among them no three points are collinear. Each of $ P_{i}$ ($1\le i\le n$) is colored red or blue arbitrarily. Let $ S$ be the set of triangles having $ \{P_{1},P_{2},\ldots,P_{n}\}$ as vertices, and having the following property: for any two segments $ P_{i}P_{j}$ and $ P_{u}P_{v},$ the number of triangles having $ P_{i}P_{j}$ as side and the number of triangles having $ P_{u}P_{v}$ as side are the same in $ S.$ Find the least $ n$ such that in $ S$ there exist two triangles, the vertices of each triangle having the same color.

2008 Iran MO (3rd Round), 1

Tags: combinatorics proposed , combinatorics

Prove that the number of pairs $ \left(\alpha,S\right)$ of a permutation $ \alpha$ of $ \{1,2,\dots,n\}$ and a subset $ S$ of $ \{1,2,\dots,n\}$ such that \[ \forall x\in S: \alpha(x)\not\in S\] is equal to $ n!F_{n \plus{} 1}$ in which $ F_n$ is the Fibonacci sequence such that $ F_1 \equal{} F_2 \equal{} 1$

2009 Iran MO (2nd Round), 1

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

We have a $ (n+2)\times n $ rectangle and we’ve divided it into $ n(n+2) \ \ 1\times1 $ squares. $ n(n+2) $ soldiers are standing on the intersection points ($ n+2 $ rows and $ n $ columns). The commander shouts and each soldier stands on its own location or gaits one step to north, west, east or south so that he stands on an adjacent intersection point. After the shout, we see that the soldiers are standing on the intersection points of a $ n\times(n+2) $ rectangle ($ n $ rows and $ n+2 $ columns) such that the first and last row are deleted and 2 columns are added to the right and left (To the left $1$ and $1$ to the right). Prove that $ n $ is even.

2013 All-Russian Olympiad, 3

Tags: combinatorics proposed , combinatorics

The head of the Mint wants to release 12 coins denominations (each - a natural number rubles) so that any amount from 1 to 6543 rubles could be paid without having to pass, using no more than 8 coins. Can he do it? (If the payment amount you can use a few coins of the same denomination.)

2014 Taiwan TST Round 3, 1

Tags: induction , strong induction , combinatorics proposed , combinatorics , Taiwan TST , 2014

Positive integers $x_1, x_2, \dots, x_n$ ($n \ge 4$) are arranged in a circle such that each $x_i$ divides the sum of the neighbors; that is \[ \frac{x_{i-1}+x_{i+1}}{x_i} = k_i \] is an integer for each $i$, where $x_0 = x_n$, $x_{n+1} = x_1$. Prove that \[ 2n \le k_1 + k_2 + \dots + k_n < 3n. \]

2007 Tournament Of Towns, 5

Tags: combinatorics proposed , combinatorics

Attached to each of a number of objects is a tag which states the correct mass of the object. The tags have fallen off and have been replaced on the objects at random. We wish to determine if by chance all tags are in fact correct. We may use exactly once a horizontal lever which is supported at its middle. The objects can be hung from the lever at any point on either side of the support. The lever either stays horizontal or tilts to one side. Is this task always possible?

2014 Germany Team Selection Test, 1

Tags: combinatorics proposed , combinatorics

In Sikinia we only pay with coins that have a value of either $11$ or $12$ Kulotnik. In a burglary in one of Sikinia's banks, $11$ bandits cracked the safe and could get away with $5940$ Kulotnik. They tried to split up the money equally - so that everyone gets the same amount - but it just doesn't worked. After a while their leader claimed that it actually isn't possible. Prove that they didn't get any coin with the value $12$ Kulotnik.

2006 India IMO Training Camp, 1

Tags: linear algebra , matrix , combinatorics proposed , combinatorics

Let $n$ be a positive integer divisible by $4$. Find the number of permutations $\sigma$ of $(1,2,3,\cdots,n)$ which satisfy the condition $\sigma(j)+\sigma^{-1}(j)=n+1$ for all $j \in \{1,2,3,\cdots,n\}$.

2008 India National Olympiad, 4

Tags: analytic geometry , calculus , integration , combinatorics proposed , combinatorics

All the points with integer coordinates in the $ xy$-Plane are coloured using three colours, red, blue and green, each colour being used at least once. It is known that the point $ (0,0)$ is red and the point $ (0,1)$ is blue. Prove that there exist three points with integer coordinates of distinct colours which form the vertices of a right-angled triangle.

2003 China National Olympiad, 2

Tags: probability , combinatorics proposed , combinatorics

Ten people apply for a job. The manager decides to interview the candidates one by one according to the following conditions: i) the first three candidates will not be employed; ii) from the fourth candidates onwards, if a candidate's comptence surpasses the competence of all those who preceded him, then that candidate is employed; iii) if the first nine candidates are not employed, then the tenth candidate will be employed. We assume that none of the $10$ applicants have the same competence, and these competences can be ranked from the first to tenth. Let $P_k$ represent the probability that the $k$th-ranked applicant in competence is employed. Prove that: i) $P_1>P_2>\ldots>P_8=P_9=P_{10}$; ii) $P_1+P_2+P_3>0.7$ iii) $P_8+P_9+P_{10}\le 0.1$. [i]Su Chun[/i]

2011 Turkey Team Selection Test, 3

Tags: function , pigeonhole principle , combinatorics proposed , combinatorics

Let $A$ and $B$ be sets with $2011^2$ and $2010$ elements, respectively. Show that there is a function $f:A \times A \to B$ satisfying the condition $f(x,y)=f(y,x)$ for all $(x,y) \in A \times A$ such that for every function $g:A \to B$ there exists $(a_1,a_2) \in A \times A$ with $g(a_1)=f(a_1,a_2)=g(a_2)$ and $a_1 \neq a_2.$

2004 Iran MO (3rd Round), 1

Tags: number theory , prime numbers , combinatorics proposed , combinatorics

We say $m \circ n$ for natural m,n $\Longleftrightarrow$ nth number of binary representation of m is 1 or mth number of binary representation of n is 1. and we say $m \bullet n$ if and only if $m,n$ doesn't have the relation $\circ$ We say $A \subset \mathbb{N}$ is golden $\Longleftrightarrow$ $\forall U,V \subset A$ that are finite and arenot empty and $U \cap V = \emptyset$,There exist $z \in A$ that $\forall x \in U,y \in V$ we have $z \circ x ,z \bullet y$ Suppose $\mathbb{P}$ is set of prime numbers.Prove if $\mathbb{P}=P_1 \cup ... \cup P_k$ and $P_i \cap P_j = \emptyset$ then one of $P_1,...,P_k$ is golden.

2007 Czech and Slovak Olympiad III A, 4

Tags: arithmetic sequence , combinatorics proposed , combinatorics

The set $M=\{1,2,\ldots,2007\}$ has the following property: If $n$ is an element of $M$, then all terms in the arithmetic progression with its first term $n$ and common difference $n+1$, are in $M$. Does there exist an integer $m$ such that all integers greater than $m$ are elements of $M$?

1997 Iran MO (2nd round), 3

Tags: combinatorics proposed , combinatorics

We have a $n\times n$ table and we’ve written numbers $0,+1 \ or \ -1$ in each $1\times1$ square such that in every row or column, there is only one $+1$ and one $-1$. Prove that by swapping the rows with each other and the columns with each other finitely, we can swap $+1$s with $-1$s.

2010 Stars Of Mathematics, 1

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

Let $D$ be the set of all pairs $(i,j)$, $1\le i,j\le n$. Prove there exists a subset $S \subset D$, with $|S|\ge\left \lfloor\frac{3n(n+1)}{5}\right \rfloor$, such that for any $(x_1,y_1), (x_2,y_2) \in S$ we have $(x_1+x_2,y_1+y_2) \not \in S$. (Peter Cameron)

2010 Canadian Mathematical Olympiad Qualification Repechage, 6

Tags: geometry , combinatorics proposed , combinatorics

There are $15$ magazines on a table, and they cover the surface of the table entirely. Prove that one can always take away $7$ magazines in such a way that the remaining ones cover at least $\dfrac{8}{15}$ of the area of the table surface

2020 Turkey Junior National Olympiad, 4

Tags: combinatorics , combinatorics proposed , Turkey

There are dwarves in a forest and each one of them owns exactly 3 hats which are numbered with numbers $1, 2, \dots 28$. Three hats of a dwarf are numbered with different numbers and there are 3 festivals in this forest in a day. In the first festival, each dwarf wears the hat which has the smallest value, in the second festival, each dwarf wears the hat which has the second smallest value and in the final festival each dwarf wears the hat which has the biggest value. After that, it is realized that there is no dwarf pair such that both of two dwarves wear the same value in at least two festivals. Find the maximum value of number of dwarves.

1999 Turkey MO (2nd round), 3

Tags: function , combinatorics proposed , combinatorics

For any two positive integers $n$ and $p$, prove that there are exactly ${{(p+1)}^{n+1}}-{{p}^{n+1}}$ functions $f:\left\{ 1,2,...,n \right\}\to \left\{ -p,-p+1,-p+2,....,p-1,p \right\}$ such that $\left| f(i)-f(j) \right|\le p$ for all $i,j\in \left\{ 1,2,...,n \right\}$.

2024 All-Russian Olympiad, 2

Tags: combinatorics , combinatorics proposed

Let $n \ge 3$ be an odd integer. In a $2n \times 2n$ board, we colour $2(n-1)^2$ cells. What is the largest number of three-square corners that can surely be cut out of the uncoloured figure? [i]Proposed by G. Sharafetdinova[/i]

2016 Korea Winter Program Practice Test, 3

Tags: combinatorics , combinatorics proposed

$p, q, r$ are natural numbers greater than 1. There are $pq$ balls placed on a circle, and one number among $0, 1, 2, \cdots , pr-1$ is written on each ball, satisfying following conditions. (1) If $i$ and $j$ is written on two adjacent balls, $|i-j|=1$ or $|i-j|=pr-1$. (2) $i$ is written on a ball $A$. If we skip $q-1$ balls clockwise from $A$ and see $q^{th}$ ball, $i+r$ or $i-(p-1)r$ is written on it. (This condition is satisfied for every ball.) If $p$ is even, prove that the number of pairs of two adjacent balls with $1$ and $2$ written on it is odd.