Olympiad problems

2012 Iran MO (3rd Round), 1

Prove that the number of incidences of $n$ distinct points on $n$ distinct lines in plane is $\mathcal O (n^{\frac{4}{3}})$. Find a configuration for which $\Omega (n^{\frac{4}{3}})$ incidences happens.

2009 Iran MO (2nd Round), 3

Tags: topology , geometry , circumcircle , calculus , integration , invariant , combinatorics proposed

$11$ people are sitting around a circle table, orderly (means that the distance between two adjacent persons is equal to others) and $11$ cards with numbers $1$ to $11$ are given to them. Some may have no card and some may have more than $1$ card. In each round, one [and only one] can give one of his cards with number $ i $ to his adjacent person if after and before the round, the locations of the cards with numbers $ i-1,i,i+1 $ don’t make an acute-angled triangle. (Card with number $0$ means the card with number $11$ and card with number $12$ means the card with number $1$!) Suppose that the cards are given to the persons regularly clockwise. (Mean that the number of the cards in the clockwise direction is increasing.) Prove that the cards can’t be gathered at one person.

2011 ELMO Shortlist, 7

Tags: graph theory , combinatorics proposed , combinatorics

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. [i]David Yang.[/i]

2011 All-Russian Olympiad, 1

Tags: combinatorics proposed , combinatorics

In every cell of a table with $n$ rows and ten columns, a digit is written. It is known that for every row $A$ and any two columns, you can always find a row that has different digits from $A$ only when it intersects with two columns. Prove that $n\geq512$.

2010 Baltic Way, 6

Tags: modular arithmetic , combinatorics proposed , combinatorics

An $n\times n$ board is coloured in $n$ colours such that the main diagonal (from top-left to bottom-right) is coloured in the first colour; the two adjacent diagonals are coloured in the second colour; the two next diagonals (one from above and one from below) are coloured in the third colour, etc; the two corners (top-right and bottom-left) are coloured in the $n$-th colour. It happens that it is possible to place on the board $n$ rooks, no two attacking each other and such that no two rooks stand on cells of the same colour. Prove that $n=0\pmod{4}$ or $n=1\pmod{4}$.

2009 South East Mathematical Olympiad, 4

Tags: geometry , combinatorics proposed , combinatorics

Given 12 red points on a circle , find the mininum value of $n$ such that there exists $n$ triangles whose vertex are the red points . Satisfies: every chord whose points are the red points is the edge of one of the $n$ triangles .

2011 IberoAmerican, 1

Tags: combinatorics proposed , combinatorics

The number $2$ is written on the board. Ana and Bruno play alternately. Ana begins. Each one, in their turn, replaces the number written by the one obtained by applying exactly one of these operations: multiply the number by $2$, multiply the number by $3$ or add $1$ to the number. The first player to get a number greater than or equal to $2011$ wins. Find which of the two players has a winning strategy and describe it.

2005 Iran Team Selection Test, 3

Tags: induction , combinatorics proposed , combinatorics

Suppose there are 18 lighthouses on the Persian Gulf. Each of the lighthouses lightens an angle with size 20 degrees. Prove that we can choose the directions of the lighthouses such that whole of the blue Persian (always Persian) Gulf is lightened.

2004 Bulgaria Team Selection Test, 2

Tags: combinatorics proposed , combinatorics , Ramsey Theory , graph theory

The edges of a graph with $2n$ vertices ($n \ge 4$) are colored in blue and red such that there is no blue triangle and there is no red complete subgraph with $n$ vertices. Find the least possible number of blue edges.

1998 Iran MO (3rd Round), 3

Tags: combinatorics proposed , combinatorics

Let $ABC$ be a given triangle. Consider any painting of points of the plane in red and green. Show that there exist either two red points on the distance $1$, or three green points forming a triangle congruent to triangle $ABC$.

2005 Indonesia MO, 1

Tags: calculus , integration , inequalities , combinatorics proposed , combinatorics

Let $ n$ be a positive integer. Determine the number of triangles (non congruent) with integral side lengths and the longest side length is $ n$.

2024 Middle European Mathematical Olympiad, 3

Tags: combinatorics , combinatorics proposed , game , game strategy

There are $2024$ mathematicians sitting in a row next to the river Tisza. Each of them is working on exactly one research topic, and if two mathematicians are working on the same topic, everyone sitting between them is also working on it. Marvin is trying to figure out for each pair of mathematicians whether they are working on the same topic. He is allowed to ask each mathematician the following question: “How many of these 2024 mathematicians are working on your topic?” He asks the questions one by one, so he knows all previous answers before he asks the next one. Determine the smallest positive integer $k$ such that Marvin can always accomplish his goal with at most $k$ questions.

2012 Tuymaada Olympiad, 3

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

Prove that $N^2$ arbitrary distinct positive integers ($N>10$) can be arranged in a $N\times N$ table, so that all $2N$ sums in rows and columns are distinct. [i]Proposed by S. Volchenkov[/i]

2010 Romanian Master of Mathematics, 1

Tags: induction , modular arithmetic , combinatorics proposed , combinatorics

For a finite non empty set of primes $P$, let $m(P)$ denote the largest possible number of consecutive positive integers, each of which is divisible by at least one member of $P$. (i) Show that $|P|\le m(P)$, with equality if and only if $\min(P)>|P|$. (ii) Show that $m(P)<(|P|+1)(2^{|P|}-1)$. (The number $|P|$ is the size of set $P$) [i]Dan Schwarz, Romania[/i]

2011 Iran MO (3rd Round), 2

Tags: combinatorics proposed , combinatorics

prove that the number of permutations such that the order of each element is a multiple of $d$ is $\frac{n!}{(\frac{n}{d})!d^{\frac{n}{d}}} \prod_{i=0}^{\frac{n}{d}-1} (id+1)$. [i]proposed by Mohammad Mansouri[/i]

2010 Indonesia TST, 3

Tags: combinatorics proposed , combinatorics

In a party, each person knew exactly $ 22$ other persons. For each two persons $ X$ and $ Y$, if $ X$ and $ Y$ knew each other, there is no other person who knew both of them, and if $ X$ and $ Y$ did not know each other, there are exactly $ 6$ persons who knew both of them. Assume that $ X$ knew $ Y$ iff $ Y$ knew $ X$. How many people did attend the party? [i]Yudi Satria, Jakarta[/i]

2014 Contests, 1

Tags: induction , analytic geometry , graphing lines , slope , combinatorics proposed , combinatorics

Find the number of $(a_1,a_2, ... ,a_{2014})$ permutations of the $(1,2, . . . ,2014)$ such that, for all $1\leq i<j\leq2014$, $i+a_i \leq j+a_j$.

1993 IberoAmerican, 2

Tags: pigeonhole principle , geometry , circumcircle , rhombus , perpendicular bisector , combinatorics proposed , combinatorics

Let $P$ and $Q$ be two distinct points in the plane. Let us denote by $m(PQ)$ the segment bisector of $PQ$. Let $S$ be a finite subset of the plane, with more than one element, that satisfies the following properties: (i) If $P$ and $Q$ are in $S$, then $m(PQ)$ intersects $S$. (ii) If $P_1Q_1, P_2Q_2, P_3Q_3$ are three diferent segments such that its endpoints are points of $S$, then, there is non point in $S$ such that it intersects the three lines $m(P_1Q_1)$, $m(P_2Q_2)$, and $m(P_3Q_3)$. Find the number of points that $S$ may contain.

2019 Turkey EGMO TST, 1

Tags: combinatorics , combinatorics proposed

$A_1, A_2, ..., A_n$ are the subsets of $|S|=2019$ such that union of any three of them gives $S$ but if we combine two of subsets it doesn't give us $S$. Find the maximum value of $n$.

2003 Nordic, 1

Tags: combinatorics proposed , combinatorics

The squares of a rectangular chessboard with 10 rows and 14 columns are colored alternatingly black and white in the usual manner. Some stones are placed the board (possibly more than one on the same square) so that there are an odd number of stones in each row and each column. Show that the total number of stones on black squares is even.

1973 Bundeswettbewerb Mathematik, 3

Tags: modular arithmetic , combinatorics proposed , combinatorics

For covering the floor of a rectangular room rectangular tiles of sizes $2 \times 2$ and $4 \times 1$ were used. Show that it's not possible to cover the floor if there is one plate less of one type and one more of the other type.

1993 Baltic Way, 13

Tags: combinatorics proposed , combinatorics

An equilateral triangle $ABC$ is divided into $100$ congruent equilateral triangles. What is the greatest number of vertices of small triangles that can be chosen so that no two of them lie on a line that is parallel to any of the sides of the triangle $ABC$?

2014 Korea - Final Round, 3

Tags: combinatorics proposed , combinatorics

There are $n$ students sitting on a round table. You collect all of $ n $ name tags and give them back arbitrarily. Each student gets one of $n$ name tags. Now $n$ students repeat following operation: The students who have their own name tags exit the table. The other students give their name tags to the student who is sitting right to him. Find the number of ways giving name tags such that there exist a student who don't exit the table after 4 operations.

2009 Indonesia TST, 4

Tags: modular arithmetic , combinatorics proposed , combinatorics

2008 boys and 2008 girls sit on 4016 chairs around a round table. Each boy brings a garland and each girl brings a chocolate. In an "activity", each person gives his/her goods to the nearest person on the left. After some activities, it turns out that all boys get chocolates and all girls get garlands. Find the number of possible arrangements.

2010 Slovenia National Olympiad, 5

Tags: combinatorics proposed , combinatorics

Ten pirates find a chest filled with golden and silver coins. There are twice as many silver coins in the chest as there are golden. They divide the golden coins in such a way that the difference of the numbers of coins given to any two of the pirates is not divisible by $10.$ Prove that they cannot divide the silver coins in the same way.