Olympiad problems

2013 Romania Team Selection Test, 3

Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ elements.

1991 APMO, 2

Tags: induction , geometry , parallelogram , analytic geometry , combinatorial geometry , combinatorics unsolved , combinatorics

Suppose there are $997$ points given in a plane. If every two points are joined by a line segment with its midpoint coloured in red, show that there are at least $1991$ red points in the plane. Can you find a special case with exactly $1991$ red points?

2012 Kazakhstan National Olympiad, 2

Tags: combinatorics unsolved , combinatorics

We call a $6\times 6$ table consisting of zeros and ones [i]right[/i] if the sum of the numbers in each row and each column is equal to $3$. Two right tables are called [i]similar[/i] if one can get from one to the other by successive interchanges of rows and columns. Find the largest possible size of a set of pairwise similar right tables.

2001 Italy TST, 4

Tags: induction , calculus , integration , combinatorics unsolved , combinatorics

We are given $2001$ balloons and a positive integer $k$. Each balloon has been blown up to a certain size (not necessarily the same for each balloon). In each step it is allowed to choose at most $k$ balloons and equalize their sizes to their arithmetic mean. Determine the smallest value of $k$ such that, whatever the initial sizes are, it is possible to make all the balloons have equal size after a finite number of steps.

2018 Turkey EGMO TST, 4

Tags: combinatorics , combinatorics proposed , combinatorics unsolved , maximum value

There are $n$ stone piles each consisting of $2018$ stones. The weight of each stone is equal to one of the numbers $1, 2, 3, ...25$ and the total weights of any two piles are different. It is given that if we choose any two piles and remove the heaviest and lightest stones from each of these piles then the pile which has the heavier one becomes the lighter one. Determine the maximal possible value of $n$.

2014 Iran Team Selection Test, 4

Tags: combinatorics unsolved , combinatorics

Find the maximum number of Permutation of set {$1,2,3,...,2014$} such that for every 2 different number $a$ and $b$ in this set at last in one of the permutation $b$ comes exactly after $a$

1990 Canada National Olympiad, 4

Tags: combinatorics unsolved , combinatorics

A particle can travel at speeds up to $ \frac{2m}{s}$ along the $ x$-axis, and up to $ \frac{1m}{s}$ elsewhere in the plane. Provide a labelled sketch of the region which can be reached within one second by the particle starting at the origin.

1972 IMO Longlists, 18

Tags: combinatorics unsolved , combinatorics

We have $p$ players participating in a tournament, each player playing against every other player exactly once. A point is scored for each victory, and there are no draws. A sequence of nonnegative integers $s_1 \le s_2 \le s_3 \le\cdots\le s_p$ is given. Show that it is possible for this sequence to be a set of final scores of the players in the tournament if and only if \[(i)\displaystyle\sum_{i=1}^{p} s_i =\frac{1}{2}p(p-1)\] \[\text{and}\] \[(ii)\text{ for all }k < p,\displaystyle\sum_{i=1}^{k} s_i \ge \frac{1}{2} k(k - 1).\]

1984 IMO Longlists, 61

Tags: probability , expected value , combinatorics unsolved , combinatorics

A fair coin is tossed repeatedly until there is a run of an odd number of heads followed by a tail. Determine the expected number of tosses.

2011 Postal Coaching, 4

Tags: combinatorics unsolved , combinatorics

Suppose there are $n$ boxes in a row and place $n$ balls in them one in each. The balls are colored red, blue or green. In how many ways can we place the balls subject to the condition that any box $B$ has at least one adjacent box having a ball of the same color as the ball in $B$? [Assume that balls in each color are available abundantly.]

1996 China Team Selection Test, 3

Tags: combinatorics unsolved , combinatorics

Let $ M \equal{} \lbrace 2, 3, 4, \ldots\, 1000 \rbrace$. Find the smallest $ n \in \mathbb{N}$ such that any $ n$-element subset of $ M$ contains 3 pairwise disjoint 4-element subsets $ S, T, U$ such that [b]I.[/b] For any 2 elements in $ S$, the larger number is a multiple of the smaller number. The same applies for $ T$ and $ U$. [b]II.[/b] For any $ s \in S$ and $ t \in T$, $ (s,t) \equal{} 1$. [b]III.[/b] For any $ s \in S$ and $ u \in U$, $ (s,u) > 1$.

2001 All-Russian Olympiad, 4

Tags: vector , analytic geometry , floor function , combinatorics unsolved , combinatorics

Participants to an olympiad worked on $n$ problems. Each problem was worth a [color=#FF0000]positive [/color]integer number of points, determined by the jury. A contestant gets $0$ points for a wrong answer, and all points for a correct answer to a problem. It turned out after the olympiad that the jury could impose worths of the problems, so as to obtain any (strict) final ranking of the contestants. Find the greatest possible number of contestants.

2012 Uzbekistan National Olympiad, 1

Tags: combinatorics unsolved , combinatorics

Given a digits {$0,1,2,...,9$} . Find the number of numbers of 6 digits which cantain $7$ or $7$'s digit and they is permulated(For example 137456 and 314756 is one numbers).

1994 Vietnam National Olympiad, 1

Tags: invariant , combinatorics unsolved , combinatorics

There are $n+1$ containers arranged in a circle. One container has $n$ stones, the others are empty. A move is to choose two containers $A$ and $B$, take a stone from $A$ and put it in one of the containers adjacent to $B$, and to take a stone from $B$ and put it in one of the containers adjacent to $A$. We can take $A = B$. For which $n$ is it possible by series of moves to end up with one stone in each container except that which originally held $n$ stones.

2009 Turkey Team Selection Test, 3

Tags: combinatorics unsolved , combinatorics

In a class of $ n\geq 4$ some students are friends. In this class any $ n \minus{} 1$ students can be seated in a round table such that every student is sitting next to a friend of him in both sides, but $ n$ students can not be seated in that way. Prove that the minimum value of $ n$ is $ 10$.

2007 Estonia National Olympiad, 5

Tags: combinatorics unsolved , combinatorics

Juhan wants to order by weight five balls of pairwise different weight, using only a balance scale. First, he labels the balls with numbers 1 to 5 and creates a list of weighings, such that each element in the list is a pair of two balls. Then, for every pair in the list, he weighs the two balls against each other. Can Juhan sort the balls by weight, using a list with less than 10 pairs?

2013 CentroAmerican, 1

Tags: geometry , rectangle , combinatorics unsolved , combinatorics

Ana and Beatriz take turns in a game that starts with a square of side $1$ drawn on an infinite grid. Each turn consists of drawing a square that does not overlap with the rectangle already drawn, in such a way that one of its sides is a (complete) side of the figure already drawn. A player wins if she completes a rectangle whose area is a multiple of $5$. If Ana goes first, does either player have a winning strategy?

2009 Kurschak Competition, 1

Tags: combinatorics unsolved , combinatorics

Let $n,k$ be arbitrary positive integers. We fill the entries of an $n\times k$ array with integers such that all the $n$ rows contain the integers $1,2,\dots,k$ in some order. Add up the numbers in all $k$ columns – let $S$ be the largest of these sums. What is the minimal value of $S$?

1999 Taiwan National Olympiad, 6

Tags: induction , combinatorics unsolved , combinatorics

There are eight different symbols designed on $n\geq 2$ different T-shirts. Each shirt contains at least one symbol, and no two shirts contain all the same symbols. Suppose that for any $k$ symbols $(1\leq k\leq 7)$ the number of shirts containing at least one of the $k$ symbols is even. Determine the value of $n$.

2019 Latvia Baltic Way TST, 5

Tags: monovariant , invariant , combinatorics , combinatorics unsolved , Process

There are $2019$ students sitting around circular table. Initially each of them have one candy. Teacher is allowed to pick one student, who has at least one can candy, and this student can decide, whether he gives his candy to his neighbour on the right or on the left. Prove that no matter what students teacher picks during the process, students can always ensure that any point of time no student has more than $2$ candies.

2005 MOP Homework, 6

Tags: combinatorics unsolved , combinatorics

A computer network is formed by connecting $2004$ computers by cables. A set $S$ of these computers is said to be independent if no pair of computers of $S$ is connected by a cable. Suppose that the number of cables used is the minimum number possible such that the size of any independent set is at most $50$. Let $c(L)$ be the number of cables connected to computer $L$. Show that for any distinct computers $A$ and $B$, $c(A)=c(B)$ if they are connected by a cable and $|c(A)-c(B)| \le 1$ otherwise. Also, find the number of cables used in the network.

1991 Kurschak Competition, 3

Tags: combinatorics unsolved , combinatorics

Consider $998$ red points on the plane with no three collinear. We select $k$ blue points in such a way that inside each triangle whose vertices are red points, there is a blue point as well. Find the smallest $k$ for which the described selection of blue points is possible for any configuration of $998$ red points.

2003 All-Russian Olympiad, 2

Tags: geometry , rectangle , analytic geometry , combinatorics unsolved , combinatorics

Is it possible to write a positive integer in every cell of an infinite chessboard, in such a manner that, for all positive integers $m, n$, the sum of numbers in every $m\times n$ rectangle is divisible by $m + n$ ?

2009 Indonesia MO, 4

Tags: floor function , combinatorics unsolved , combinatorics

In an island, there exist 7 towns and a railway system which connected some of the towns. Every railway segment connects 2 towns, and in every town there exists at least 3 railway segments that connects the town to another towns. Prove that there exists a route that visits 4 different towns once and go back to the original town. (Example: $ A\minus{}B\minus{}C\minus{}D\minus{}A$)

2006 Estonia Math Open Senior Contests, 1

Tags: combinatorics unsolved , combinatorics

All the streets in a city run in one of two perpendicular directions, forming unit squares. Organizers of a car race want to mark down a closed race track in the city in such a way that it would not go through any of the crossings twice and that the track would turn 90◦ right or left at every crossing. Find all possible values of the length of the track.