Olympiad problems

Kvant 2024, M2798

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]

2009 China Team Selection Test, 3

Tags: combinatorics proposed , combinatorics

Let $ X$ be a set containing $ 2k$ elements, $ F$ is a set of subsets of $ X$ consisting of certain $ k$ elements such that any one subset of $ X$ consisting of $ k \minus{} 1$ elements is exactly contained in an element of $ F.$ Show that $ k \plus{} 1$ is a prime number.

2014 All-Russian Olympiad, 2

Tags: combinatorics proposed , combinatorics

Peter and Bob play a game on a $n\times n$ chessboard. At the beginning, all squares are white apart from one black corner square containing a rook. Players take turns to move the rook to a white square and recolour the square black. The player who can not move loses. Peter goes first. Who has a winning strategy?

2011 All-Russian Olympiad Regional Round, 11.7

Tags: combinatorics proposed , combinatorics

Basil drew several circles on the plane and drew all common tangent lines for all pairs of circles. It turned out that the lines contain all sides of a regular polygon with 2011 vertices. What is the smallest possible number of circles? (Author: N. Agahanov)

2007 Junior Balkan Team Selection Tests - Romania, 1

Tags: analytic geometry , geometry , rectangle , combinatorics proposed , combinatorics

Consider an 8x8 board divided in 64 unit squares. We call [i]diagonal[/i] in this board a set of 8 squares with the property that on each of the rows and the columns of the board there is exactly one square of the [i]diagonal[/i]. Some of the squares of this board are coloured such that in every [i]diagonal[/i] there are exactly two coloured squares. Prove that there exist two rows or two columns whose squares are all coloured.

2010 Romanian Masters In 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]

2013 Iran Team Selection Test, 18

Tags: geometry , parallelogram , rotation , combinatorics proposed , combinatorics

A special kind of parallelogram tile is made up by attaching the legs of two right isosceles triangles of side length $1$. We want to put a number of these tiles on the floor of an $n\times n$ room such that the distance from each vertex of each tile to the sides of the room is an integer and also no two tiles overlap. Prove that at least an area $n$ of the room will not be covered by the tiles. [i]Proposed by Ali Khezeli[/i]

2005 Poland - Second Round, 3

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

In space are given $n\ge 2$ points, no four of which are coplanar. Some of these points are connected by segments. Let $K$ be the number of segments $(K>1)$ and $T$ be the number of formed triangles. Prove that $9T^2<2K^3$.

2013 China Team Selection Test, 3

Tags: combinatorics proposed , combinatorics

$101$ people, sitting at a round table in any order, had $1,2,... , 101$ cards, respectively. A transfer is someone give one card to one of the two people adjacent to him. Find the smallest positive integer $k$ such that there always can through no more than $ k $ times transfer, each person hold cards of the same number, regardless of the sitting order.

2007 Baltic Way, 10

Tags: combinatorics proposed , combinatorics

We are given an $18\times 18$ table, all of whose cells may be black or white. Initially all the cells are coloured white. We may perform the following operation: choose one column or one row and change the colour of all cells in this column or row. Is it possible by repeating the operation to obtain a table with exactly $16$ black cells?

2005 Taiwan National Olympiad, 2

Tags: combinatorics proposed , combinatorics

Ten test papers are to be prepared for the National Olympiad. Each paper has 4 problems, and no two papers have more than 1 problem in common. At least how many problems are needed?

2013 Kazakhstan National Olympiad, 3

Tags: geometry , rectangle , combinatorics proposed , combinatorics

How many non-intersecting pairs of paths we have from (0,0) to (n,n) so that path can move two ways:top or right?

2006 JBMO ShortLists, 14

Tags: combinatorics proposed , combinatorics

Let $ n\ge 5$ be a positive integer. Prove that the set $ \{1,2,\ldots,n\}$ can be partitioned into two non-zero subsets $ S_n$ and $ P_n$ such that the sum of elements in $ S_n$ is equal to the product of elements in $ P_n$.

2007 Peru IMO TST, 4

Tags: combinatorics proposed , combinatorics

Let be a board with $2007 \times 2007$ cells, we colour with black $P$ cells such that: $\bullet$ there are no 3 colored cells that form a L-trinomes in any of its 4 orientations Find the minimum value of $P$, such that when you colour one cell more, this configuration can't keep the condition above.

2012 Romanian Master of Mathematics, 5

Tags: floor function , ceiling function , geometry , rectangle , combinatorics proposed , combinatorics , double counting

Given a positive integer $n\ge 3$, colour each cell of an $n\times n$ square array with one of $\lfloor (n+2)^2/3\rfloor$ colours, each colour being used at least once. Prove that there is some $1\times 3$ or $3\times 1$ rectangular subarray whose three cells are coloured with three different colours. [i](Russia) Ilya Bogdanov, Grigory Chelnokov, Dmitry Khramtsov[/i]

2007 Moldova Team Selection Test, 4

Tags: geometry , rhombus , Putnam , combinatorics proposed , combinatorics

We are given $n$ distinct points in the plane. Consider the number $\tau(n)$ of segments of length 1 joining pairs of these points. Show that $\tau(n)\leq \frac{n^{2}}3$.

2009 China Team Selection Test, 3

Tags: combinatorics proposed , combinatorics

Let $ X$ be a set containing $ 2k$ elements, $ F$ is a set of subsets of $ X$ consisting of certain $ k$ elements such that any one subset of $ X$ consisting of $ k \minus{} 1$ elements is exactly contained in an element of $ F.$ Show that $ k \plus{} 1$ is a prime number.

1989 Romania Team Selection Test, 5

Tags: rotation , combinatorics proposed , combinatorics

A laticial cycle of length $n$ is a sequence of lattice points $(x_k, y_k)$, $k = 0, 1,\cdots, n$, such that $(x_0, y_0) = (x_n, y_n) = (0, 0)$ and $|x_{k+1} -x_{k}|+|y_{k+1} - y_{k}| = 1$ for each $k$. Prove that for all $n$, the number of latticial cycles of length $n$ is a perfect square.

2004 Pre-Preparation Course Examination, 1

Tags: function , floor function , ceiling function , combinatorics proposed , combinatorics

A network is a simple directed graph such that each edge $ e$ has two intger lower and upper capacities $ 0\leq c_l(e)\leq c_u(e)$. A circular flow on this graph is a function such that: 1) For each edge $ e$, $ c_l(e)\leq f(e)\leq c_u(e)$. 2) For each vertex $ v$: \[ \sum_{e\in v^\plus{}}f(e)\equal{}\sum_{e\in v^\minus{}}f(e)\] a) Prove that this graph has a circular flow, if and only if for each partition $ X,Y$ of vertices of the network we have: \[ \sum_{\begin{array}{c}{e\equal{}xy}\\{x\in X,y\in Y}\end{array}} c_l(e)\leq \sum_{\begin{array}{c}{e\equal{}yx}\\{y\in Y,x\in X}\end{array}} c_l(e)\] b) Suppose that $ f$ is a circular flow in this network. Prove that there exists a circular flow $ g$ in this network such that $ g(e)\equal{}\lfloor f(e)\rfloor$ or $ g(e)\equal{}\lceil f(e)\rceil$ for each edge $ e$.

1970 IMO Longlists, 35

Tags: combinatorics proposed , combinatorics

Find for every value of $n$ a set of numbers $p$ for which the following statement is true: Any convex $n$-gon can be divided into $p$ isosceles triangles.

2009 Iran Team Selection Test, 7

Tags: induction , inequalities , combinatorics proposed , combinatorics

Suppose three direction on the plane . We draw $ 11$ lines in each direction . Find maximum number of the points on the plane which are on three lines .

2008 Polish MO Finals, 4

Tags: analytic geometry , combinatorics proposed , combinatorics

Each point of a plane with both coordinates being integers has been colored black or white. Show that there exists an infinite subset of colored points, whose points are in the same color, having a center of symmetry. [EDIT: added condition about being infinite - now it makes sense]

1983 IMO Longlists, 2

Tags: combinatorics proposed , combinatorics

Seventeen cities are served by four airlines. It is noted that there is direct service (without stops) between any two cities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

2008 Bulgaria Team Selection Test, 1

Tags: induction , combinatorics proposed , combinatorics , graph theory , Hamiltonian path , Chessboard

Let $n$ be a positive integer. There is a pawn in one of the cells of an $n\times n$ table. The pawn moves from an arbitrary cell of the $k$th column, $k \in \{1,2, \cdots, n \}$, to an arbitrary cell in the $k$th row. Prove that there exists a sequence of $n^{2}$ moves such that the pawn goes through every cell of the table and finishes in the starting cell.

2011 China Team Selection Test, 2

Tags: inequalities , geometry , perpendicular bisector , combinatorics proposed , combinatorics

Let $S$ be a set of $n$ points in the plane such that no four points are collinear. Let $\{d_1,d_2,\cdots ,d_k\}$ be the set of distances between pairs of distinct points in $S$, and let $m_i$ be the multiplicity of $d_i$, i.e. the number of unordered pairs $\{P,Q\}\subseteq S$ with $|PQ|=d_i$. Prove that $\sum_{i=1}^k m_i^2\leq n^3-n^2$.