Found problems: 1800
2005 Junior Balkan MO, 3
Prove that there exist
(a) 5 points in the plane so that among all the triangles with vertices among these points there are 8 right-angled ones;
(b) 64 points in the plane so that among all the triangles with vertices among these points there are at least 2005 right-angled ones.
2010 Switzerland - Final Round, 5
Some sides and diagonals of a regular $ n$-gon form a connected path that visits each vertex exactly once. A [i]parallel pair[/i] of edges is a pair of two different parallel edges of the path. Prove that
(a) if $ n$ is even, there is at least one [i]parallel pair[/i].
(b) if $ n$ is odd, there can't be one single [i]parallel pair[/i].
2009 CentroAmerican, 3
There are 2009 boxes numbered from 1 to 2009, some of which contain stones. Two players, $ A$ and $ B$, play alternately, starting with $ A$. A move consists in selecting a non-empty box $ i$, taking one or more stones from that box and putting them in box $ i \plus{} 1$. If $ i \equal{} 2009$, the selected stones are eliminated. The player who removes the last stone wins
a) If there are 2009 stones in the box 2 and the others are empty, find a winning strategy for either player.
b) If there is exactly one stone in each box, find a winning strategy for either player.
2008 Saint Petersburg Mathematical Olympiad, 6
A diagonal of a 100-gon is called good if it divides the 100-gon into two polygons each with an odd number of sides. A 100-gon was split into triangles with non-intersecting diagonals, exactly 49 of which are good. The triangles are colored into two colors such that no two triangles that border each other are colored with the same color. Prove that there is the same number of triangles colored with one color as with the other.
Fresh translation; slightly reworded.
1995 Taiwan National Olympiad, 3
Suppose that $n$ persons meet in a meeting, and that each of the persons is acquainted to exactly $8$ others. Any two acquainted persons have exactly $4$ common acquaintances, and any two non-acquainted persons have exactly $2$ common acquaintances. Find all possible values of $n$.
2009 Pan African, 1
Consider $n$ children in a playground, where $n\ge 2$. Every child has a coloured hat, and every pair of children is joined by a coloured ribbon. For every child, the colour of each ribbon held is different, and also different from the colour of that child’s hat. What is the minimum number of colours that needs to be used?
2012 China Team Selection Test, 3
Let $a_1<a_2$ be two given integers. For any integer $n\ge 3$, let $a_n$ be the smallest integer which is larger than $a_{n-1}$ and can be uniquely represented as $a_i+a_j$, where $1\le i<j\le n-1$. Given that there are only a finite number of even numbers in $\{a_n\}$, prove that the sequence $\{a_{n+1}-a_{n}\}$ is eventually periodic, i.e. that there exist positive integers $T,N$ such that for all integers $n>N$, we have
\[a_{T+n+1}-a_{T+n}=a_{n+1}-a_{n}.\]
2005 Romania Team Selection Test, 4
We consider a polyhedra which has exactly two vertices adjacent with an odd number of edges, and these two vertices are lying on the same edge.
Prove that for all integers $n\geq 3$ there exists a face of the polyhedra with a number of sides not divisible by $n$.
2003 ITAMO, 2
A museum has the shape of a $n \times n$ square divided into $n^2$ rooms of the shape of a unit square $(n>1)$. Between every two adjacent rooms (i.e. sharing a wall) there is a door. A night guardian wants to organize an inspection journey through the museum according to the following rules. He starts from some room and, whenever he enters a room, he stays there for exactly one minute and then proceeds to another room. He is allowed to enter a room more than once, but at the end of his journey he must have spent exactly $k$ minutes in every room. Find all $n$ and $k$ for which it is possible to organize such a journey.
2024 All-Russian Olympiad, 5
A straight road consists of green and red segments in alternating colours, the first and last segment being green. Suppose that the lengths of all segments are more than a centimeter and less than a meter, and that the length of each subsequent segment is larger than the previous one. A grasshopper wants to jump forward along the road along these segments, stepping on each green segment at least once an without stepping on any red segment (or the border between neighboring segments). Prove that the grasshopper can do this in such a way that among the lengths of his jumps no more than $8$ different values occur.
[i]Proposed by T. Korotchenko[/i]
2010 Bosnia Herzegovina Team Selection Test, 6
Prove that total number of ones which is showed in all nonrestricted partitions of natural number $n$ is equal to sum of numbers of distinct elements in that partitions.
2014 ELMO Shortlist, 1
You have some cyan, magenta, and yellow beads on a non-reorientable circle, and you can perform only the following operations:
1. Move a cyan bead right (clockwise) past a yellow bead, and turn the yellow bead magenta.
2. Move a magenta bead left of a cyan bead, and insert a yellow bead left of where the magenta bead ends up.
3. Do either of the above, switching the roles of the words ``magenta'' and ``left'' with those of ``yellow'' and ``right'', respectively.
4. Pick any two disjoint consecutive pairs of beads, each either yellow-magenta or magenta-yellow, appearing somewhere in the circle, and swap the orders of each pair.
5. Remove four consecutive beads of one color.
Starting with the circle: ``yellow, yellow, magenta, magenta, cyan, cyan, cyan'', determine whether or not you can reach
a) ``yellow, magenta, yellow, magenta, cyan, cyan, cyan'',
b) ``cyan, yellow, cyan, magenta, cyan'',
c) ``magenta, magenta, cyan, cyan, cyan'',
d) ``yellow, cyan, cyan, cyan''.
[i]Proposed by Sammy Luo[/i]
2002 Tournament Of Towns, 3
The vertices of a $50\text{-gon}$ divide a circumference into $50$ arcs, whose lengths are $1,2,\ldots 50$ in some order. It is known that any two opposite arcs (corresponding to opposite sides) differ by $25$. Prove that the polygon has two parallel sides.
2024 All-Russian Olympiad, 8
$1000$ children, no two of the same height, lined up. Let us call a pair of different children $(a,b)$ good if between them there is no child whose height is greater than the height of one of $a$ and $b$, but less than the height of the other. What is the greatest number of good pairs that could be formed? (Here, $(a,b)$ and $(b,a)$ are considered the same pair.)
[i]Proposed by I. Bogdanov[/i]
2008 Iran MO (3rd Round), 5
$ n$ people decide to play a game. There are $ n\minus{}1$ ropes and each of its two ends are in hand of one of the players, in such a way that ropes and players form a tree. (Each person can hold more than rope end.)
At each step a player gives one of the rope ends he is holding to another player. The goal is to make a path of length $ n\minus{}1$ at the end.
But the game regulations change before game starts. Everybody has to give one of his rope ends only two one of his neighbors. Let $ a$ and $ b$ be minimum steps for reaching to goal in these two games. Prove that $ a\equal{}b$ if and only if by removing all players with one rope end (leaves of the tree) the remaining people are on a path. (the remaining graph is a path.)
[img]http://i37.tinypic.com/2l9h1tv.png[/img]
2010 Kyiv Mathematical Festival, 5
1) Cells of $8 \times 8$ table contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exists integer written in the same row or in the same column such that it is not relatively prime with $a$. Find maximum possible number of prime integers in the table.
2) Cells of $2n \times 2n$ table, $n \ge 2,$ contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exist integers written in the same row and in the same column such that they are not relatively prime with $a$. Find maximum possible number of prime integers in the table.
1978 Miklós Schweitzer, 1
Let $ \mathcal{H}$ be a family of finite subsets of an infinite set $ X$ such that every finite subset of $ X$ can be represented as the union of two disjoint sets from $ \mathcal{H}$. Prove that for every positive integer $ k$ there is a subset of $ X$ that can be represented in at least $ k$ different ways as the union of two disjoint sets from $ \mathcal{H}$.
[i]P. Erdos[/i]
1990 Balkan MO, 4
Find the least number of elements of a finite set $A$ such that there exists a function $f : \left\{1,2,3,\ldots \right\}\rightarrow A$ with the property: if $i$ and $j$ are positive integers and $i-j$ is a prime number, then $f(i)$ and $f(j)$ are distinct elements of $A$.
1994 All-Russian Olympiad, 6
I'll post some nice combinatorics problems here, taken from the wonderful training book "Les olympiades de mathmatiques" (in French) written by Tarik Belhaj Soulami.
Here goes the first one:
Let $\mathbb{I}$ be a non-empty subset of $\mathbb{Z}$ and let $f$ and $g$ be two functions defined on $\mathbb{I}$. Let $m$ be the number of pairs $(x,\;y)$ for which $f(x) = g(y)$, let $n$ be the number of pairs $(x,\;y)$ for which $f(x) = f(y)$ and let $k$ be the number of pairs $(x,\;y)$ for which $g(x) = g(y)$. Show that \[2m \leq n + k.\]
2007 District Olympiad, 4
The points of a circle are colored in green and yellow, such that every equilateral triangle inscribed in the circle has exactly 2 vertices colored in yellow. Prove that there exist a square inscribed in the circle which has at least 3 vertices colored in yellow.
2005 All-Russian Olympiad Regional Round, 10.4
10.4, 11.3 Given $N\geq 3$ points enumerated with 1, 2, ..., $N$. Each two numbers are connected by mean of arrow from a lesser number to a greater one. A coloring of all arrows into red and blue is called [i]monochromatic[/i] iff for any numbers $A$ and $B$ there are [color=red]no[/color] two monochromatic paths from $A$ to $B$ of different colors. Find the number of monochromatic colorings.
([i]I. Bogdanov, G. Chelnokov[/i])
1994 Iran MO (2nd round), 1
The sides of an equilateral triangle $ABC$ are divided into $n$ equal parts $(n \geq 2) .$ For each point on a side, we draw the lines parallel to other sides of the triangle $ABC,$ e.g. for $n=3$ we have the following diagram:
[asy]
unitsize(150);
defaultpen(linewidth(0.7));
int n = 3; /* # of vertical lines, including AB */
pair A = (0,0), B = dir(-30), C = dir(30);
draw(A--B--C--cycle,linewidth(2)); dot(A,UnFill(0)); dot(B,UnFill(0)); dot(C,UnFill(0));
label("$A$",A,W); label("$C$",C,NE); label("$B$",B,SE);
for(int i = 1; i < n; ++i) {
draw((i*A+(n-i)*B)/n--(i*A+(n-i)*C)/n);
draw((i*B+(n-i)*A)/n--(i*B+(n-i)*C)/n);
draw((i*C+(n-i)*A)/n--(i*C+(n-i)*B)/n);
}
[/asy]
For each $n \geq 2,$ find the number of existing parallelograms.
2008 China Team Selection Test, 4
Prove that for arbitary positive integer $ n\geq 4$, there exists a permutation of the subsets that contain at least two elements of the set $ G_{n} \equal{} \{1,2,3,\cdots,n\}$: $ P_{1},P_{2},\cdots,P_{2^n \minus{} n \minus{} 1}$ such that $ |P_{i}\cap P_{i \plus{} 1}| \equal{} 2,i \equal{} 1,2,\cdots,2^n \minus{} n \minus{} 2.$
2012 Iran MO (3rd Round), 3
In a tree with $n$ vertices, for each vertex $x_i$, denote the longest paths passing through it by $l_i^1,l_i^2,...,l_i^{k_i}$. $x_i$ cuts those longest paths into two parts with $(a_i^1,b_i^1),(a_i^2,b_i^2),...,(a_i^{k_i},b_i^{k_i})$ vertices respectively. If $\max_{j=1,...,k_i} \{a_i^j\times b_i^j\}=p_i$, find the maximum and minimum values of $\sum_{i=1}^{n} p_i$.
[i]Proposed by Sina Rezaei[/i]
2014 Korea National Olympiad, 2
How many one-to-one functions $f : \{1, 2, \cdots, 9\} \rightarrow \{1, 2, \cdots, 9\}$ satisfy (i) and (ii)?
(i) $f(1)>f(2)$, $f(9)<9$.
(ii) For each $i=3, 4, \cdots, 8$, if $f(1), \cdots, f(i-1)$ are smaller than $f(i)$, then $f(i+1)$ is also smaller than $f(i)$.