Olympiad problems

2007 All-Russian Olympiad Regional Round, 9.8

A set contains $ 372$ integers from $ 1,2,...,1200$ . For every element $ a\in S$, the numbers $ a\plus{}4,a\plus{}5,a\plus{}9$ don't belong to $ S$. Prove that $ 600\in S$.

2010 Lithuania National Olympiad, 4

Tags: combinatorics proposed , combinatorics

Arrange arbitrarily $1,2,\ldots ,25$ on a circumference. We consider all $25$ sums obtained by adding $5$ consecutive numbers. If the number of distinct residues of those sums modulo $5$ is $d$ $(0\le d\le 5)$,find all possible values of $d$.

2011 Romanian Masters In Mathematics, 3

Tags: analytic geometry , modular arithmetic , combinatorics proposed , combinatorics

The cells of a square $2011 \times 2011$ array are labelled with the integers $1,2,\ldots, 2011^2$, in such a way that every label is used exactly once. We then identify the left-hand and right-hand edges, and then the top and bottom, in the normal way to form a torus (the surface of a doughnut). Determine the largest positive integer $M$ such that, no matter which labelling we choose, there exist two neighbouring cells with the difference of their labels at least $M$. (Cells with coordinates $(x,y)$ and $(x',y')$ are considered to be neighbours if $x=x'$ and $y-y'\equiv\pm1\pmod{2011}$, or if $y=y'$ and $x-x'\equiv\pm1\pmod{2011}$.) [i](Romania) Dan Schwarz[/i]

2012 ELMO Shortlist, 2

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

Determine whether it's possible to cover a $K_{2012}$ with a) 1000 $K_{1006}$'s; b) 1000 $K_{1006,1006}$'s. [i]David Yang.[/i]

1995 Brazil National Olympiad, 6

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

$X$ has $n$ elements. $F$ is a family of subsets of $X$ each with three elements, such that any two of the subsets have at most one element in common. Show that there is a subset of $X$ with at least $\sqrt{2n}$ members which does not contain any members of $F$.

1997 Korea - Final Round, 4

Tags: combinatorics proposed , combinatorics

Given a positive integer $ n$, find the number of $ n$-digit natural numbers consisting of digits 1, 2, 3 in which any two adjacent digits are either distinct or both equal to 3.

2004 Iran MO (3rd Round), 4

Tags: combinatorial geometry , combinatorics proposed , combinatorics

We have finite white and finite black points that for each 4 oints there is a line that white points and black points are at different sides of this line.Prove there is a line that all white points and black points are at different side of this line.

2007 Romania Team Selection Test, 3

Tags: geometry , geometric transformation , rotation , combinatorics proposed , combinatorics

Let $A_{1}A_{2}\ldots A_{2n}$ be a convex polygon and let $P$ be a point in its interior such that it doesn't lie on any of the diagonals of the polygon. Prove that there is a side of the polygon such that none of the lines $PA_{1}$, $\ldots$, $PA_{2n}$ intersects it in its interior.

1998 IberoAmerican Olympiad For University Students, 7

Tags: geometry , induction , combinatorics proposed , combinatorics , 1998 IberoAmerica Undergrad MO , IberoAmerica Undergrad MO

Some time ago there was a war across the world. In the plane $n$ lines are moving, with the regions contained by the lines being the territories of the countries at war. Each line moves parallel to itself with constant speed (each with its own speed), and no line can reverse its direction. Some of the original countries disappeared (a country disappears iff its area is converted to zero) and within the course of the time, other countries appeared. After some time, the presidents of the existing countries made a treaty to end the war, created the United Nations, and all borders ceased movement. The UN then counted the total numbers of sovereign states that were destroyed and the existing ones, obtaining a total of $k$. Prove that $k\leq \frac{n^3+5n}{6}+1$. Is is possible to have equality?

1999 Italy TST, 4

Tags: floor function , combinatorics proposed , combinatorics

Let $X$ be an $n$-element set and let $A_1,\ldots ,A_m$ be subsets of $X$ such that i) $|A_i|=3$ for each $i=1,\ldots ,m$. ii) $|A_i\cap A_j|\le 1$ for any two distinct indices $i,j$. Show that there exists a subset of $X$ with at least $\lfloor\sqrt{2n}\rfloor$ elements which does not contain any of the $A_i$’s.

2005 Romania Team Selection Test, 1

Tags: geometry , rectangle , modular arithmetic , combinatorics proposed , combinatorics

On a $2004 \times 2004$ chess table there are 2004 queens such that no two are attacking each other\footnote[1]{two queens attack each other if they lie on the same row, column or direction parallel with on of the main diagonals of the table}. Prove that there exist two queens such that in the rectangle in which the center of the squares on which the queens lie are two opposite corners, has a semiperimeter of 2004.

1993 Iran MO (2nd round), 1

Tags: combinatorics proposed , combinatorics

$G$ is a graph with $n$ vertices $A_1,A_2,\ldots,A_n,$ such that for each pair of non adjacent vertices $A_i$ and $A_j$ , there exist another vertex $A_k$ that is adjacent to both $A_i$ and $A_j .$ [b](a) [/b]Find the minimum number of edges in such a graph. [b](b) [/b]If $n = 6$ and $A_1,A_2,A_3,A_4,A_5,$ and $A_6$ form a cycle of length $6,$ find the number of edges that must be added to this cycle such that the above condition holds.

2008 Canada National Olympiad, 5

Tags: algebra , polynomial , combinatorics proposed , combinatorics

A [i]self-avoiding rook walk[/i] on a chessboard (a rectangular grid of unit squares) is a path traced by a sequence of moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook's path is non-self-intersecting. Let $ R(m, n)$ be the number of self-avoiding rook walks on an $ m \times n$ ($ m$ rows, $ n$ columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, $ R(m, 1) \equal{} 1$ for all natural numbers $ m$; $ R(2, 2) \equal{} 2$; $ R(3, 2) \equal{} 4$; $ R(3, 3) \equal{} 11$. Find a formula for $ R(3, n)$ for each natural number $ n$.

2024 Middle European Mathematical Olympiad, 4

Tags: combinatorics , combinatorics proposed , Sequence , Sequences , palindromes , Periodic sequence

A finite sequence $x_1,\dots,x_r$ of positive integers is a [i]palindrome[/i] if $x_i=x_{r+1-i}$ for all integers $1 \le i \le r$. Let $a_1,a_2,\dots$ be an infinite sequence of positive integers. For a positive integer $j \ge 2$, denote by $a[j]$ the finite subsequence $a_1,a_2,\dots,a_{j-1}$. Suppose that there exists a strictly increasing infinite sequence $b_1,b_2,\dots$ of positive integers such that for every positive integer $n$, the subsequence $a[b_n]$ is a palindrome and $b_{n+2} \le b_{n+1}+b_n$. Prove that there exists a positive integer $T$ such that $a_i=a_{i+T}$ for every positive integer $i$.

2014 ISI Entrance Examination, 8

Tags: modular arithmetic , combinatorics proposed , combinatorics

$n(>1)$ lotus leaves are arranged in a circle. A frog jumps from a particular leaf from another under the following rule: [list] [*]It always moves clockwise. [*]From starting it skips one leaf and then jumps to the next. After that it skips two leaves and jumps to the following. And the process continues. (Remember the frog might come back on a leaf twice or more.)[/list] Given that it reaches all leaves at least once. Show $n$ cannot be odd.

2010 Benelux, 1

Tags: combinatorics proposed , combinatorics , combinatorics solved , symmetry , Subsets , Bounding

A finite set of integers is called [i]bad[/i] if its elements add up to $2010$. A finite set of integers is a [i]Benelux-set[/i] if none of its subsets is bad. Determine the smallest positive integer $n$ such that the set $\{502, 503, 504, . . . , 2009\}$ can be partitioned into $n$ Benelux-sets. (A partition of a set $S$ into $n$ subsets is a collection of $n$ pairwise disjoint subsets of $S$, the union of which equals $S$.) [i](2nd Benelux Mathematical Olympiad 2010, Problem 1)[/i]

2012 ELMO Shortlist, 5

Tags: quadratics , modular arithmetic , combinatorics proposed , combinatorics

Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1\pmod{4}$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1\pmod{8}$. Show $A$ and $B$ are isomorphic to each other. [i]Linus Hamilton.[/i]

1977 IMO Longlists, 32

Tags: Ramsey Theory , combinatorics proposed , combinatorics

In a room there are nine men. Among every three of them there are two mutually acquainted. Prove that some four of them are mutually acquainted.

2002 Baltic Way, 10

Tags: combinatorics proposed , combinatorics

Let $N$ be a positive integer. Two persons play the following game. The first player writes a list of positive integers not greater than $25$, not necessarily different, such that their sum is at least $200$. The second player wins if he can select some of these numbers so that their sum $S$ satisfies the condition $200-N\le S\le 200+N$. What is the smallest value of $N$ for which the second player has a winning strategy?

2006 Iran MO (2nd round), 3

Tags: induction , least common multiple , combinatorics proposed , combinatorics

Some books are placed on each other. Someone first, reverses the upper book. Then he reverses the $2$ upper books. Then he reverses the $3$ upper books and continues like this. After he reversed all the books, he starts this operation from the first. Prove that after finite number of movements, the books become exactly like their initial configuration.

1995 Baltic Way, 12

Tags: combinatorics proposed , combinatorics

Assume we have $95$ boxes and $19$ balls distributed in these boxes in an arbitrary manner. We take $6$ new balls at a time and place them in $6$ of the boxes, one ball in each of the six. Can we, by repeating this process a suitable number of times, achieve a situation in which each of the $95$ boxes contains an equal number of balls?

1969 Miklós Schweitzer, 11

Tags: combinatorics proposed , combinatorics

Let $ A_1,A_2,...$ be a sequence of infinite sets such that $ |A_i \cap A_j| \leq 2$ for $ i \not\equal{}j$. Show that the sequence of indices can be divided into two disjoint sequences $ i_1<i_2<...$ and $ j_1<j_2<...$ in such a way that, for some sets $ E$ and $ F$, $ |A_{i_n} \cap E|\equal{}1$ and $ |A_{j_n} \cap F|\equal{}1$ for $ n\equal{}1,2,... .$ [i]P. Erdos[/i]

2010 Balkan MO, 3

Tags: induction , geometry , trigonometry , combinatorics proposed , combinatorics , Extremal combinatorics , marvio

A strip of width $w$ is the set of all points which lie on, or between, two parallel lines distance $w$ apart. Let $S$ be a set of $n$ ($n \ge 3$) points on the plane such that any three different points of $S$ can be covered by a strip of width $1$. Prove that $S$ can be covered by a strip of width $2$.

1989 Iran MO (2nd round), 1

Tags: combinatorics proposed , combinatorics

In a sport competition, $m$ teams have participated. We know that each two teams have competed exactly one time and the result is winning a team and losing the other team (i.e. there is no equal result). Prove that there exists a team $x$ such that for each team $y,$ either $x$ wins $y$ or there exists a team $z$ for which $x$ wins $z$ and $z$ wins $y.$ [i][i.e. prove that in every tournament there exists a king.][/i]

2001 China National Olympiad, 2

Tags: combinatorics proposed , combinatorics

Let $P_1P_2\ldots P_{24}$ be a regular $24$-sided polygon inscribed in a circle $\omega$ with circumference $24$. Determine the number of ways to choose sets of eight distinct vertices from these $24$ such that none of the arcs has length $3$ or $8$.