Found problems: 1488
2006 Estonia National Olympiad, 5
Consider a rectangular grid of $ 10 \times 10$ unit squares. We call a [i]ship[/i] a figure made up of unit squares connected by common edges. We call a [i]fleet[/i] a set of ships where no two ships contain squares that share a common vertex (i.e. all ships are vertex-disjoint). Find the greatest natural number that, for each its representation as a sum of positive integers, there exists a fleet such that the summands are exactly the numbers of squares contained in individual ships.
2011 Iran Team Selection Test, 3
There are $n$ points on a circle ($n>1$). Define an "interval" as an arc of a circle such that it's start and finish are from those points. Consider a family of intervals $F$ such that for every element of $F$ like $A$ there is almost one other element of $F$ like $B$ such that $A \subseteq B$ (in this case we call $A$ is sub-interval of $B$). We call an interval maximal if it is not a sub-interval of any other interval. If $m$ is the number of maximal elements of $F$ and $a$ is number of non-maximal elements of $F,$ prove that $n\geq m+\frac a2.$
2005 India IMO Training Camp, 3
A merida path of order $2n$ is a lattice path in the first quadrant of $xy$- plane joining $(0,0)$ to $(2n,0)$ using three kinds of steps $U=(1,1)$, $D= (1,-1)$ and $L= (2,0)$, i.e. $U$ joins $x,y)$ to $(x+1,y+1)$ etc... An ascent in a merida path is a maximal string of consecutive steps of the form $U$. If $S(n,k)$ denotes the number of merdia paths of order $2n$ with exactly $k$ ascents, compute $S(n,1)$ and $S(n,n-1)$.
1997 IberoAmerican, 1
Let $n$ be a positive integer. Consider the sum $x_1y_1 + x_2y_2 +\cdots + x_ny_n$, where that values of the variables $x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n$ are either 0 or 1.
Let $I(n)$ be the number of 2$n$-tuples $(x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n)$ such that the sum of the number is odd, and let $P(n)$ be the number of 2$n$-tuples $(x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n)$ such that the sum is an even number. Show that: \[ \frac{P(n)}{I(n)}=\frac{2^n+1}{2^n-1} \]
2004 Bulgaria National Olympiad, 3
A group consist of n tourists. Among every 3 of them there are 2 which are not familiar. For every partition of the tourists in 2 buses you can find 2 tourists that are in the same bus and are familiar with each other. Prove that is a tourist familiar to at most $\displaystyle \frac 2{5}n$ tourists.
2012 Indonesia TST, 2
Suppose $S$ is a subset of $\{1,2,3,\ldots,2012\}$. If $S$ has at least $1000$ elements, prove that $S$ contains two different elements $a,b$, where $b$ divides $2a$.
2002 All-Russian Olympiad, 4
There are 2002 towns in a kingdom. Some of the towns are connected by roads in such a manner that, if all roads from one city closed, one can still travel between any two cities. Every year, the kingdom chooses a non-self-intersecting cycle of roads, founds a new town, connects it by roads with each city from the chosen cycle, and closes all the roads from the original cycle. After several years, no non-self-intersecting cycles remained. Prove that at that moment there are at least 2002 towns, exactly one road going out from each of them.
2001 All-Russian Olympiad, 3
The $2001$ towns in a country are connected by some roads, at least one road from each town, so that no town is connected by a road to every other city. We call a set $D$ of towns [i]dominant[/i] if every town not in $D$ is connected by a road to a town in $D$. Suppose that each dominant set consists of at least $k$ towns. Prove that the country can be partitioned into $2001-k$ republics in such a way that no two towns in the same republic are connected by a road.
2008 Tuymaada Olympiad, 1
Several irrational numbers are written on a blackboard. It is known that for every two numbers $ a$ and $ b$ on the blackboard, at least one of the numbers $ a\over b\plus{}1$ and $ b\over a\plus{}1$ is rational. What maximum number of irrational numbers can be on the blackboard?
[i]Author: Alexander Golovanov[/i]
1982 IMO Longlists, 24
Prove that if a person a has infinitely many descendants (children, their children, etc.), then a has an infinite sequence $a_0, a_1, \ldots$ of descendants (i.e., $a = a_0$ and for all $n \geq 1, a_{n+1}$ is always a child of $a_n$). It is assumed that no-one can have infinitely many children.
[i]Variant 1[/i]. Prove that if $a$ has infinitely many ancestors, then $a$ has an infinite descending sequence of ancestors (i.e., $a_0, a_1, \ldots$ where $a = a_0$ and $a_n$ is always a child of $a_{n+1}$).
[i]Variant 2.[/i] Prove that if someone has infinitely many ancestors, then all people cannot descend from $A(dam)$ and $E(ve)$.
2001 Taiwan National Olympiad, 3
Let $n\ge 3$ be an integer and let $A_{1}, A_{2},\dots, A_{n}$ be $n$ distinct subsets of $S=\{1, 2,\dots, n\}$. Show that there exists $x\in S$ such that the n subsets $A_{i}-\{x\}, i=1,2,\dots n$ are also disjoint.
what i have is [hide="this"]we may assume that the union of the $A_{i}$s is $S$. [/hide]
1979 IMO Longlists, 13
The plane is divided into equal squares by parallel lines; i.e., a square net is given. Let $M$ be an arbitrary set of $n$ squares of this net. Prove that it is possible to choose no fewer than $n/4$ squares of $M$ in such a way that no two of them have a common point.
2010 Paenza, 5
In $4$-dimensional space, a set of $1 \times 2 \times 3 \times 4$ bricks is given. Decide whether it is possible to build boxes of the following sizes using these bricks:
[list]i) $2 \times 5 \times 7 \times 12$
ii) $5 \times 5 \times 10 \times 12$
iii) $6 \times 6 \times 6 \times 6$.[/list]
2011 Greece National Olympiad, 2
In the Cartesian plane $Oxy$ we consider the points ${A_1}\left( {40,1} \right), {A_2}\left( {40,2} \right), \ldots , {A_{40}}\left( {40,40} \right)$ as well as the segments $O{A_1},O{A_2},\ldots,O{A_{40}}$. A point of the Cartesian plane $Oxy$ is called "good", if its coordinates are integers and it is internal of one segment $O{A_i}, i=1,2,3,\ldots,40$. Additionally, one of the segments $O{A_1},O{A_2},\ldots,O{A_{40}}$ is called "good" if it contains a "good" point. Find the number of "good" segments and "good" points.
2006 MOP Homework, 2
Determine the number of subset $S$ of the set $T = {1, 2,..., 2005}$
such that the sum of elements in $s$ is congruent to 2006 modulo
2048.
1994 All-Russian Olympiad Regional Round, 11.4
On the vertices of a convex $ n$-gon are put $ m$ stones, $ m > n$. In each move we can choose two stones standing at the same vertex and move them to
the two distinct adjacent vertices. After $ N$ moves the number of stones at each vertex was the same as at the beginning. Prove that $ N$ is divisible by $ n$.
2011 Albania Team Selection Test, 5
The sweeties shop called "Olympiad" sells boxes of $6,9$ or $20$ chocolates. Groups of students from a school that is near the shop collect money to buy a chocolate for each student; to make this they buy a box and than give to everybody a chocolate. Like this students can create groups of $15=6+9$ students, $38=2*9+20$ students, etc. The seller has promised to the students that he can satisfy any group of students, and if he will need to open a new box of chocolate for any group (like groups of $4,7$ or $10$ students) than he will give all the chocolates for free to this group. Can there be constructed the biggest group that profits free chocolates, and if so, how many students are there in this group?
2009 All-Russian Olympiad, 6
There are $ k$ rooks on a $ 10 \times 10$ chessboard. We mark all the squares that at least one rook can capture (we consider the square where the rook stands as captured by the rook). What is the maximum value of $ k$ so that the following holds for some arrangement of $ k$ rooks: after removing any rook from the chessboard, there is at least one marked square not captured by any of the remaining rooks.
1976 IMO Longlists, 51
Four swallows are catching a fly. At first, the swallows are at the four vertices of a tetrahedron, and the fly is in its interior. Their maximal speeds are equal. Prove that the swallows can catch the fly.
1997 China Team Selection Test, 2
There are $ n$ football teams in a round-robin competition where every 2 teams meet once. The winner of each match receives 3 points while the loser receives 0 points. In the case of a draw, both teams receive 1 point each. Let $ k$ be as follows: $ 2 \leq k \leq n \minus{} 1$. At least how many points must a certain team get in the competition so as to ensure that there are at most $ k \minus{} 1$ teams whose scores are not less than that particular team's score?
2006 MOP Homework, 5
Set $X$ has $56$ elements. Determine the least positive integer $n$ such that for any 15 subsets of $X$, if the union of any $7$ of
the subsets has at least $n$ elements, then 3 of the subsets have
nonempty intersection.
1997 Pre-Preparation Course Examination, 3
We say three sets $A_1, A_2, A_3$ form a triangle if for each $1 \leq i,j \leq 3$ we have $A_i \cap A_j \neq \emptyset$, and $A_1 \cap A_2 \cap A_3 = \emptyset$. Let $f(n)$ be the smallest positive integer such that any subset of $\{1,2,3,\ldots, n\}$ of the size $f(n)$ has at least one triangle. Find a formula for $f(n)$.
1989 IMO Longlists, 72
To each pair $ (x, y)$ of distinct elements of a finite set $ X$ a number $ f(x, y)$ equal to 0 or 1 is assigned in such a way that $ f(x, y) \neq f(y, x)$ $ \forall x,y$ and $ x \neq y.$ Prove that exactly one of the following situations occurs:
[b](i)[/b] $ X$ is the union of two disjoint nonempty subsets $ U, V$ such that $ f(u, v) \equal{} 1$ $ \forall u \in U, v \in V.$
[b](ii)[/b] The elements of $ X$ can be labeled $ x_1, \ldots , x_n$ so that \[ f(x_1, x_2) \equal{} f(x_2, x_3) \equal{} \cdots \equal{} f(x_{n\minus{}1}, x_n) \equal{} f(x_n, x_1) \equal{} 1.\]
[i]Alternative formulation:[/i]
In a tournament of n participants, each pair plays one game (no ties). Prove that exactly one of the following situations occurs:
[b](i)[/b] The league can be partitioned into two nonempty groups such that each player in one of these groups has won against each player of the other.
[b](ii)[/b] All participants can be ranked 1 through $ n$ so that $ i\minus{}$th player wins the game against the $ (i \plus{} 1)$st and the $ n\minus{}$th player wins against the first.
2005 Czech-Polish-Slovak Match, 4
We distribute $n\ge1$ labelled balls among nine persons $A,B,C, \dots , I$. How many ways are there to do this so that $A$ gets the same number of balls as $B,C,D$ and $E$ together?
2010 Tournament Of Towns, 6
Each cell of a $1000\times 1000$ table contains $0$ or $1$. Prove that one can either cut out $990$ rows so that at least one $1$ remains in each column, or cut out $990$ columns so that at least one $0$ remains in each row.