Found problems: 1800
2005 QEDMO 1st, 13 (C4)
Let $n$ be a positive integer.
Find the number of sequences $a_1,a_2,...,a_k$ of different numbers from $\{ 1,2,3,...,n\}$ with the following property:
for every number $a$ of the sequence (except the first one) there exists a previous number $b$ such that their difference is $1$ (so $a-b= \pm 1$)
2021 Bundeswettbewerb Mathematik, 2
A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual).
Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours.
2012 ELMO Shortlist, 7
Consider a graph $G$ with $n$ vertices and at least $n^2/10$ edges. Suppose that each edge is colored in one of $c$ colors such that no two incident edges have the same color. Assume further that no cycles of size $10$ have the same set of colors. Prove that there is a constant $k$ such that $c$ is at least $kn^\frac{8}{5}$ for any $n$.
[i]David Yang.[/i]
1997 Korea - Final Round, 1
A [i]word[/i] is a sequence of 0 and 1 of length 8. Let $ x$ and $ y$ be two words differing in exactly three places.
Prove that the number of words differing from each of $ x$ and $ y$ in at least five places is 188.
2013 JBMO TST - Turkey, 3
Two players $A$ and $B$ play a game with a ball and $n$ boxes placed onto the vertices of a regular $n$-gon where $n$ is a positive integer. Initially, the ball is hidden in a box by player $A$. At each step, $B$ chooses a box, then player $A$ says the distance of the ball to the selected box to player $B$ and moves the ball to an adjacent box. If $B$ finds the ball, then $B$ wins. Find the least number of steps for which $B$ can guarantee to win.
2011 ELMO Problems, 2
Wanda the Worm likes to eat Pascal's triangle. One day, she starts at the top of the triangle and eats $\textstyle\binom{0}{0}=1$. Each move, she travels to an adjacent positive integer and eats it, but she can never return to a spot that she has previously eaten. If Wanda can never eat numbers $a,b,c$ such that $a+b=c$, prove that it is possible for her to eat 100,000 numbers in the first 2011 rows given that she is not restricted to traveling only in the first 2011 rows.
(Here, the $n+1$st row of Pascal's triangle consists of entries of the form $\textstyle\binom{n}{k}$ for integers $0\le k\le n$. Thus, the entry $\textstyle\binom{n}{k}$ is considered adjacent to the entries $\textstyle\binom{n-1}{k-1}$, $\textstyle\binom{n-1}{k}$, $\textstyle\binom{n}{k-1}$, $\textstyle\binom{n}{k+1}$, $\textstyle\binom{n+1}{k}$, $\textstyle\binom{n+1}{k+1}$.)
[i]Linus Hamilton.[/i]
2001 India IMO Training Camp, 2
Two symbols $A$ and $B$ obey the rule $ABBB = B$. Given a word $x_1x_2\ldots x_{3n+1}$ consisting of $n$ letters $A$ and $2n+1$ letters $B$, show that there is a unique cyclic permutation of this word which reduces to $B$.
1998 Federal Competition For Advanced Students, Part 2, 3
Let $a_n$ be a sequence recursively de fined by $a_0 = 0, a_1 = 1$ and $a_{n+2} = a_{n+1} + a_n$. Calculate the sum of $a_n\left( \frac 25\right)^n$ for all positive integers $n$. For what value of the base $b$ we get the sum $1$?
Russian TST 2015, P4
Let $G$ be a tournoment such that it's edges are colored either red or blue.
Prove that there exists a vertex of $G$ like $v$ with the property that, for every other vertex $u$ there is a mono-color directed path from $v$ to $u$.
2014 Turkey MO (2nd round), 6
$5$ airway companies operate in a country consisting of $36$ cities. Between any pair of cities exactly one company operates two way flights. If some air company operates between cities $A, B$ and $B, C$ we say that the triple $A, B, C$ is [i]properly-connected[/i]. Determine the largest possible value of $k$ such that no matter how these flights are arranged there are at least $k$ properly-connected triples.
2008 China Team Selection Test, 3
Let $ S$ be a set that contains $ n$ elements. Let $ A_{1},A_{2},\cdots,A_{k}$ be $ k$ distinct subsets of $ S$, where $ k\geq 2, |A_{i}| \equal{} a_{i}\geq 1 ( 1\leq i\leq k)$. Prove that the number of subsets of $ S$ that don't contain any $ A_{i} (1\leq i\leq k)$ is greater than or equal to $ 2^n\prod_{i \equal{} 1}^k(1 \minus{} \frac {1}{2^{a_{i}}}).$
2011 Stars Of Mathematics, 4
Let $n\geq 2$ be an integer. Let us call [i]interval[/i] a subset $A \subseteq \{1,2,\ldots,n\}$ for which integers $1\leq a < b\leq n$ do exist, such that $A = \{a,a+1,\ldots,b-1,b\}$. Let a family $\mathcal{A}$ of subsets $A_i \subseteq \{1,2,\ldots,n\}$, with $1\leq i \leq N$, be such that for any $1\leq i < j \leq N$ we have $A_i \cap A_j$ being an interval.
Prove that $\displaystyle N \leq \left \lfloor n^2/4 \right \rfloor$, and that this bound is sharp.
(Dan Schwarz - after an idea by Ron Graham)
2004 Turkey Team Selection Test, 1
An $11\times 11$ chess board is covered with one $\boxed{ }$ shaped and forty $\boxed{ }\boxed{ }\boxed{ }$ shaped tiles. Determine the squares where $\boxed{}$ shaped tile can be placed.
2009 Indonesia TST, 1
2008 persons take part in a programming contest. In one round, the 2008 programmers are divided into two groups. Find the minimum number of groups such that every two programmers ever be in the same group.
1982 Miklós Schweitzer, 3
Let $ G(V,E)$ be a connected graph, and let $ d_G(x,y)$ denote the length of the shortest path joining $ x$ and $ y$ in $ G$. Let $ r_G(x)\equal{} \max \{ d_G(x,y) : \; y \in V \ \}$ for $ x \in V$, and let $ r(G)\equal{} \min \{ r_G(x) : \;x \in V\ \}$. Show that if $ r(G) \geq 2$, then $ G$ contains a path of length $ 2r(G)\minus{}2$ as an induced subgraph.
[i]V. T. Sos[/i]
2013 Argentina Cono Sur TST, 3
$1390$ ants are placed near a line, such that the distance between their heads and the line is less than $1\text{cm}$ and the distance between the heads of two ants is always larger than $2\text{cm}$. Show that there is at least one pair of ants such that the distance between their heads is at least $10$ meters (consider the head of an ant as point).
2006 ITAMO, 4
The squares of an infinite chessboard are numbered $1,2,\ldots $ along a spiral, as shown in the picture. A [i]rightline[/i] is the sequence of the numbers in the squares obtained by starting at one square at going to the right.
a) Prove that exists a rightline without multiples of $3$.
b) Prove that there are infinitely many pairwise disjoint rightlines not containing multiples of $3$.
2011 ELMO Problems, 6
Consider the infinite grid of lattice points in $\mathbb{Z}^3$. Little D and Big Z play a game, where Little D first loses a shoe on an unmunched point in the grid. Then, Big Z munches a shoe-free plane perpendicular to one of the coordinate axes. They continue to alternate turns in this fashion, with Little D's goal to lose a shoe on each of $n$ consecutive lattice points on a line parallel to one of the coordinate axes. Determine all $n$ for which Little D can accomplish his goal.
[i]David Yang.[/i]
2012 Kosovo Team Selection Test, 4
Each term in a sequence $1,0,1,0,1,0...$starting with the seventh is the sum of the last 6 terms mod 10 .Prove that the sequence $...,0,1,0,1,0,1...$ never occurs
2007 All-Russian Olympiad Regional Round, 8.2
Pete chose a positive integer $ n$. For each (unordered) pair of its decimal digits, he wrote their difference on the blackboard. After that, he erased some of these differences, and the remaining ones are $ 2,0,0,7$. Find the smallest number $ n$ for which this situation is possible.
2006 Lithuania National Olympiad, 4
Find the maximal cardinality $|S|$ of the subset $S \subset A=\{1, 2, 3, \dots, 9\}$ given that no two sums $a+b | a, b \in S, a \neq b$ are equal.
2002 Tournament Of Towns, 2
All the species of plants existing in Russia are catalogued (numbered by integers from $2$ to $2000$ ; one after another, without omissions or repetitions). For any pair of species the gcd of their catalogue numbers was calculated and recorded but the catalogue numbers themselves were lost. Is it possible to restore the catalogue numbers from the data in hand?
2007 Pre-Preparation Course Examination, 1
a) There is an infinite sequence of $0,1$, like $\dots,a_{-1},a_{0},a_{1},\dots$ (i.e. an element of $\{0,1\}^{\mathbb Z}$). At each step we make a new sequence. There is a function $f$ such that for each $i$, $\mbox{new }a_{i}=f(a_{i-100},a_{i-99},\dots,a_{i+100})$. This operation is mapping $F: \{0,1\}^{\mathbb Z}\longrightarrow\{0,1\}^{\mathbb Z}$. Prove that if $F$ is 1-1, then it is surjective.
b) Is the statement correct if we have an $f_{i}$ for each $i$?
1999 Korea - Final Round, 2
A permutation $a_1,a_2,\cdots ,a_6$ of numbers $1,2,\cdots ,6$ can be transformed to $1,2,\cdots,6$ by transposing two numbers exactly four times. Find the number of such permutations.
2014 All-Russian Olympiad, 3
In a convex $n$-gon, several diagonals are drawn. Among these diagonals, a diagonal is called [i]good[/i] if it intersects exactly one other diagonal drawn (in the interior of the $n$-gon). Find the maximum number of good diagonals.