Olympiad problems

2012 Indonesia TST, 2

The positive integers are colored with black and white such that: - There exists a bijection from the black numbers to the white numbers, - The sum of three black numbers is a black number, and - The sum of three white numbers is a white number. Find the number of possible colorings that satisfies the above conditions.

2016 Belarus Team Selection Test, 4

Tags: induction , combinatorics proposed , combinatorics

On a circle there are $2n+1$ points, dividing it into equal arcs ($n\ge 2$). Two players take turns to erase one point. If after one player's turn, it turned out that all the triangles formed by the remaining points on the circle were obtuse, then the player wins and the game ends. Who has a winning strategy: the starting player or his opponent?

2014 Moldova Team Selection Test, 4

Tags: combinatorics proposed , combinatorics

Consider $n \geq 2$ distinct points in the plane $A_1,A_2,...,A_n$ . Color the midpoints of the segments determined by each pair of points in red. What is the minimum number of distinct red points?

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.

1983 Miklós Schweitzer, 1

Tags: floor function , combinatorics proposed , combinatorics

Given $ n$ points in a line so that any distance occurs at most twice, show that the number of distance occurring exactly once is at least $ \lfloor n/2 \rfloor$. [i]V. T. Sos, L. Szekely[/i]

2008 Junior Balkan Team Selection Tests - Romania, 2

Tags: geometry , geometric transformation , reflection , inequalities , induction , rectangle , combinatorics proposed

Let $ m,n$ be two natural nonzero numbers and sets $ A \equal{} \{ 1,2,...,n\}, B \equal{} \{1,2,...,m\}$. We say that subset $ S$ of Cartesian product $ A \times B$ has property $ (j)$ if $ (a \minus{} x)(b \minus{} y)\le 0$ for each pairs $ (a,b),(x,y) \in S$. Prove that every set $ S$ with propery $ (j)$ has at most $ m \plus{} n \minus{} 1$ elements. [color=#FF0000]The statement was edited, in order to reflect the actual problem asked. The sign of the inequality was inadvertently reversed into $ (a \minus{} x)(b \minus{} y)\ge 0$, and that accounts for the following two posts.[/color]

2009 India IMO Training Camp, 6

Tags: function , combinatorics proposed , combinatorics

Prove The Following identity: $ \sum_{j \equal{} 0}^n \left ({3n \plus{} 2 \minus{} j \choose j}2^j \minus{} {3n \plus{} 1 \minus{} j \choose j \minus{} 1}2^{j \minus{} 1}\right ) \equal{} 2^{3n}$. The Second term on left hand side is to be regarded zero for j=0.

1998 Brazil National Olympiad, 3

Tags: number theory , greatest common divisor , least common multiple , combinatorics proposed , combinatorics , games , Combinatorial games

Two players play a game as follows: there $n > 1$ rounds and $d \geq 1$ is fixed. In the first round A picks a positive integer $m_1$, then B picks a positive integer $n_1 \not = m_1$. In round $k$ (for $k = 2, \ldots , n$), A picks an integer $m_k$ such that $m_{k-1} < m_k \leq m_{k-1} + d$. Then B picks an integer $n_k$ such that $n_{k-1} < n_k \leq n_{k-1} + d$. A gets $\gcd(m_k,n_{k-1})$ points and B gets $\gcd(m_k,n_k)$ points. After $n$ rounds, A wins if he has at least as many points as B, otherwise he loses. For each $(n, d)$ which player has a winning strategy?

2008 Romania Team Selection Test, 4

Tags: inequalities , induction , graph theory , combinatorics proposed , combinatorics

Let $ n$ be a nonzero positive integer. A set of persons is called a $ n$-balanced set if in any subset of $ 3$ persons there exists at least two which know each other and in each subset of $ n$ persons there are two which don't know each other. Prove that a $ n$-balanced set has at most $ (n \minus{} 1)(n \plus{} 2)/2$ persons.

2024 All-Russian Olympiad, 3

Tags: combinatorics , combinatorics proposed

Two boys are given a bag of potatoes, each bag containing $150$ tubers. They take turns transferring the potatoes, where in each turn they transfer a non-zero tubers from their bag to the other boy's bag. Their moves must satisfy the following condition: In each move, a boy must move more tubers than he had in his bag before any of his previous moves (if there were such moves). So, with his first move, a boy can move any non-zero quantity, and with his fifth move, a boy can move $200$ tubers, if before his first, second, third and fourth move, the numbers of tubers in his bag was less than $200$. What is the maximal total number of moves the two boys can do? [i]Proposed by E. Molchanov[/i]

1972 Miklós Schweitzer, 1

Tags: combinatorics proposed , combinatorics , Set systems

Let $ \mathcal{F}$ be a nonempty family of sets with the following properties: (a) If $ X \in \mathcal{F}$, then there are some $ Y \in \mathcal{F}$ and $ Z \in \mathcal{F}$ such that $ Y \cap Z =\emptyset$ and $ Y \cup Z=X$. (b) If $ X \in \mathcal{F}$, and $ Y \cup Z =X , Y \cap Z=\emptyset$, then either $ Y \in \mathcal{F}$ or $ Z \in \mathcal{F}$. Show that there is a decreasing sequence $ X_0 \supseteq X_1 \supseteq X_2 \supseteq ...$ of sets $ X_n \in \mathcal{F}$ such that \[ \bigcap_{n=0}^{\infty} X_n= \emptyset.\] [i]F. Galvin[/i]

2012 All-Russian Olympiad, 1

Tags: combinatorics proposed , combinatorics

Initially, there are $111$ pieces of clay on the table of equal mass. In one turn, you can choose several groups of an equal number of pieces and push the pieces into one big piece for each group. What is the least number of turns after which you can end up with $11$ pieces no two of which have the same mass?

2011 Argentina Team Selection Test, 5

Tags: combinatorics proposed , combinatorics , graph theory

At least $3$ players take part in a tennis tournament. Each participant plays exactly one match against each other participant. After the tournament has ended, we find out that each player has won at least one match. (There are no ties in tennis). Show that in the tournament, there was at least one trio of players $A,B,C$ such that $A$ beat $B$, $B$ beat $C$, and $C$ beat $A$.

2012 Romanian Master of Mathematics, 1

Tags: induction , modular arithmetic , graph theory , combinatorics proposed , combinatorics

Given a finite number of boys and girls, a [i]sociable set of boys[/i] is a set of boys such that every girl knows at least one boy in that set; and a [i]sociable set of girls[/i] is a set of girls such that every boy knows at least one girl in that set. Prove that the number of sociable sets of boys and the number of sociable sets of girls have the same parity. (Acquaintance is assumed to be mutual.) [i](Poland) Marek Cygan[/i]

2005 Silk Road, 2

Tags: combinatorics proposed , combinatorics

Find all $(m,n) \in \mathbb{Z}^2$ that we can color each unit square of $m \times n$ with the colors black and white that for each unit square number of unit squares that have the same color with it and have at least one common vertex (including itself) is even.

Kvant 2024, M2801

Tags: combinatorics , combinatorics proposed , game , ilostthegame

Yuri is looking at the great Mayan table. The table has $200$ columns and $2^{200}$ rows. Yuri knows that each cell of the table depicts the sun or the moon, and any two rows are different (i.e. differ in at least one column). Each cell of the table is covered with a sheet. The wind has blown aways exactly two sheets from each row. Could it happen that now Yuri can find out for at least $10000$ rows what is depicted in each of them (in each of the columns)? [i]Proposed by I. Bogdanov, K. Knop[/i]

2011 ELMO Shortlist, 6

Tags: combinatorics proposed , combinatorics

Do there exist positive integers $k$ and $n$ such that for any finite graph $G$ with diameter $k+1$ there exists a set $S$ of at most $n$ vertices such that for any $v\in V(G)\setminus S$, there exists a vertex $u\in S$ of distance at most $k$ from $v$? [i]David Yang.[/i]

2007 Kyiv Mathematical Festival, 3

Tags: combinatorics proposed , combinatorics

The vertices of 100-gon (i.e., polygon with 100 sides) are colored alternately white or black. One of the vertices contains a checker. Two players in turn do two things: move the checker into other vertice along the side of 100-gon and then erase some side. The game ends when it is impossible to move the checker. At the end of the game if the checker is in the white vertice then the first player wins. Otherwise the second player wins. Does any of the players have winning strategy? If yes, then who? [i]Remark.[/i] The answer may depend on initial position of the checker.

2006 Junior Balkan Team Selection Tests - Romania, 4

Tags: combinatorics proposed , combinatorics

The set of positive integers is partitionated in subsets with infinite elements each. The question (in each of the following cases) is if there exists a subset in the partition such that any positive integer has a multiple in this subset. a) Prove that if the number of subsets in the partition is finite the answer is yes. b) Prove that if the number of subsets in the partition is infinite, then the answer can be no (for a certain partition).

2013 ELMO Shortlist, 9

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]

1996 Iran MO (3rd Round), 1

Tags: arithmetic sequence , combinatorics proposed , combinatorics

Suppose that $S$ is a finite set of real numbers with the property that any two distinct elements of $S$ form an arithmetic progression with another element in $S$. Give an example of such a set with 5 elements and show that no such set exists with more than $5$ elements.

2007 ITAMO, 4

Tags: linear algebra , matrix , combinatorics proposed , combinatorics

Today is Barbara's birthday, and Alberto wants to give her a gift playing the following game. The numbers 0,1,2,...,1024 are written on a blackboard. First Barbara erases $2^{9}$ numbers, then Alberto erases $2^{8}$ numbers, then Barbara $2^{7}$ and so on, until there are only two numbers a,b left. Now Barbara earns $|a-b|$ euro. Find the maximum number of euro that Barbara can always win, independently of Alberto's strategy.

1977 IMO Longlists, 41

Tags: combinatorics proposed , combinatorics

A wheel consists of a fixed circular disk and a mobile circular ring. On the disk the numbers $1, 2, 3, \ldots ,N$ are marked, and on the ring $N$ integers $a_1,a_2,\ldots ,a_N$ of sum $1$ are marked. The ring can be turned into $N$ different positions in which the numbers on the disk and on the ring match each other. Multiply every number on the ring with the corresponding number on the disk and form the sum of $N$ products. In this way a sum is obtained for every position of the ring. Prove that the $N$ sums are different.

2001 Hungary-Israel Binational, 1

Tags: induction , graph theory , combinatorics proposed , combinatorics

Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$. The edges of $K_{n}(n \geq 3)$ are colored with $n$ colors, and every color is used. Show that there is a triangle whose sides have different colors.

2012 Iran Team Selection Test, 2

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

Let $n$ be a natural number. Suppose $A$ and $B$ are two sets, each containing $n$ points in the plane, such that no three points of a set are collinear. Let $T(A)$ be the number of broken lines, each containing $n-1$ segments, and such that it doesn't intersect itself and its vertices are points of $A$. Define $T(B)$ similarly. If the points of $B$ are vertices of a convex $n$-gon (are in [i]convex position[/i]), but the points of $A$ are not, prove that $T(B)<T(A)$. [i]Proposed by Ali Khezeli[/i]