A natural number is written in each square of an $ m \times n$ chess board. The allowed move is to add an integer $ k$ to each of two adjacent numbers in such a way that non-negative numbers are obtained. (Two squares are adjacent if they have a common side.) Find a necessary and sufficient condition for it to be possible for all the numbers to be zero after finitely many operations.

Each of $n$ black squares and $n$ white squares can be obtained by a translation from each other. Every two squares of different colours have a common point. Prove that ther is a point belonging at least to $n$ squares. [i](V. Dolnikov)[/i]

Suppose Alan, Michael, Kevin, Igor, and Big Rahul are in a running race. It is given that exactly one pair of people tie (for example, two people both get second place), so that no other pair of people end in the same position. Each competitor has equal skill; this means that each outcome of the race, given that exactly two people tie, is equally likely. The probability that Big Rahul gets first place (either by himself or he ties for first) can be expressed in the form $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Compute $m+n$.

Lisa writes a positive whole number in the decimal system on the blackboard and now makes in each turn the following: The last digit is deleted from the number on the board and then the remaining shorter number (or 0 if the number was one digit) becomes four times the number deleted number added. The number on the board is now replaced by the result of this calculation. Lisa repeats this until she gets a number for the first time was on the board. (a) Show that the sequence of moves always ends. (b) If Lisa begins with the number $53^{2022} - 1$, what is the last number on the board? Example: If Lisa starts with the number $2022$, she gets $202 + 4\cdot 2 = 210$ in the first move and overall the result $$2022 \to 210 \to 21 \to 6 \to 24 \to 18 \to 33 \to 15 \to 21$$. Since Lisa gets $21$ for the second time, the turn order ends. [i](Stephan Pfannerer)[/i]

There are an even number of points in a plane. No three of them lie on one straight line. Half of the points are red, the other half are blue. Prove that there exists a connecting line of a red and a blue point such that in each of the half-planes bounded by that line the number of red points is equal to the number of blue points.

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.

$ 30$ persons are sitting at round table. $ 30 \minus{} N$ of them always speak true ("true speakers") while the other $ N$ of them sometimes speak true sometimes not ("lie speakers"). Question: "Who is your right neighbour - "true speaker" or "lie speaker" ?" is asked to all 30 persons and 30 answers are collected. What is maximal number $ N$ for which (with knowledge of these answers) we can always be sure (decide) about at least one person who is "true speaker".

Let $n \geq 2$ be a natural. Define $$X = \{ (a_1,a_2,\cdots,a_n) | a_k \in \{0,1,2,\cdots,k\}, k = 1,2,\cdots,n \}$$. For any two elements $s = (s_1,s_2,\cdots,s_n) \in X, t = (t_1,t_2,\cdots,t_n) \in X$, define $$s \vee t = (\max \{s_1,t_1\},\max \{s_2,t_2\}, \cdots , \max \{s_n,t_n\} )$$ $$s \wedge t = (\min \{s_1,t_1 \}, \min \{s_2,t_2,\}, \cdots, \min \{s_n,t_n\})$$ Find the largest possible size of a proper subset $A$ of $X$ such that for any $s,t \in A$, one has $s \vee t \in A, s \wedge t \in A$.

What is the largest number of cells that can be marked on a $100 \times 100$ board in such a way that a chess king from any cell attacks no more than two marked ones? (The cell on which a king stands is also considered to be attacked by this king.)

In a building there are $119$ inhabitants who live in $120$ apartments (several inhabitants can live in the same apartment). We call an apartment [i]overcrowded [/i] if $15$ or more people live in it. Every day in some overcrowded apartment (if there is one) its inhabitants have a fight and yes they all go to live in a different apartment (which may or may not be already inhabited). Should you always terminate this process?

Dedalo buys a finite number of binary strings, each of finite length and made up of the binary digits 0 and 1. For each string, he pays $(\frac{1}{2})^L$ drachmas, where $L$ is the length of the string. The Minotaur is able to escape the labyrinth if he can find an infinite sequence of binary digits that does not contain any of the strings Dedalo bought. Dedalo’s aim is to trap the Minotaur. For instance, if Dedalo buys the strings $00$ and $11$ for a total of half a drachma, the Minotaur is able to escape using the infinite string $01010101 \ldots$. On the other hand, Dedalo can trap the Minotaur by spending $75$ cents of a drachma: he could for example buy the strings $0$ and $11$, or the strings $00, 11, 01$. Determine all positive integers $c$ such that Dedalo can trap the Minotaur with an expense of at most $c$ cents of a drachma.

A regular polygon of $ n$ sides ($ n\geq3$) has its vertex numbered from 1 to $ n$. One draws all the diagonals of the polygon. Show that if $ n$ is odd, it is possible to assign to each side and to each diagonal an integer number between 1 and $ n$, such that the next two conditions are simultaneously satisfied: (a) The number assigned to each side or diagonal is different to the number assigned to any of the vertices that is endpoint of it. (b) For each vertex, all the sides and diagonals that have it as an endpoint, have different number assigned.

Turbo the snail sits on a point on a circle with circumference $1$. Given an infinite sequence of positive real numbers $c_1, c_2, c_3, \dots$, Turbo successively crawls distances $c_1, c_2, c_3, \dots$ around the circle, each time choosing to crawl either clockwise or counterclockwise. Determine the largest constant $C > 0$ with the following property: for every sequence of positive real numbers $c_1, c_2, c_3, \dots$ with $c_i < C$ for all $i$, Turbo can (after studying the sequence) ensure that there is some point on the circle that it will never visit or crawl across.

Let $M\subset \{1, 2, 3, . . . , 2007\}$ a set with the following property: Among every three numbers one can always choose two from $M$ such that one is divisible by the other. How many numbers can $M$ contain at most?

Let us call a figure on a sheet of squares an arbitrary finite set of connected squares, i.e. a set of squares in which it is possible to go from any square to any other by walking only on the squares of this figure. Prove that for every natural n there exists such a figure on the sheet of squares that it can be cut into "corners" (Fig. 1) exactly in $F_n$ ways, where $F_n$ s the $n$-th Fibonacci number (in the series of Fibonacci numbers $F_1 = F_2 = 1$ and for each $i > 1$ holds $F_{i+2} = F_{i+1} + F_i$). For example, a rectangle of $2 \times 3$ squares can be cut at the corners in exactly two ways (Fig. $2$). [img]https://cdn.artofproblemsolving.com/attachments/6/5/c82340623ff5f92a410bd73755ba8cbdc501ff.png[/img]

On sport games there was 1991 participant from which every participant knows at least n other participants(friendship is mutual). Determine the lowest possible n for which we can be sure that there are 6 participants between which any two participants know each other.

There are $3n$ participants in the Mathematical Olympiad competition. They are assigned seats in three rows, with $n$ seats in each, and are admitted into the hall one at a time, after which they immediately take their seats. Calculate the probability that until the last competitor takes his seat, at any moment for each two rows the difference in the number of players sitting in them is no greater than 1.

How many non-decreasing tuples of integers $(a_1, a_2, \dots, a_{16})$ are there such that $0 \leq a_i \leq 16$ for all $i$, and the sum of all $a_i$ is even? [i]Proposed by Nancy Kuang[/i]

$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.

The Bank of Zürich issues coins with an $H$ on one side and a $T$ on the other side. Alice has $n$ of these coins arranged in a line from left to right. She repeatedly performs the following operation: if some coin is showing its $H$ side, Alice chooses a group of consecutive coins (this group must contain at least one coin) and flips all of them; otherwise, all coins show $T$ and Alice stops. For instance, if $n = 3$, Alice may perform the following operations: $THT \to HTH \to HHH \to TTH \to TTT$. She might also choose to perform the operation $THT \to TTT$. For each initial configuration $C$, let $m(C)$ be the minimal number of operations that Alice must perform. For example, $m(THT) = 1$ and $m(TTT) = 0$. For every integer $n \geq 1$, determine the largest value of $m(C)$ over all $2^n$ possible initial configurations $C$. [i]Massimiliano Foschi, Italy[/i]

Some of the vertices of unit squares of an $n\times n$ chessboard are colored so that any $k\times k$ ( $1\le k\le n$) square consisting of these unit squares has a colored point on at least one of its sides. Let $l(n)$ denote the minimum number of colored points required to satisfy this condition. Prove that $\underset{n\to \infty }{\mathop \lim }\,\frac{l(n)}{{{n}^{2}}}=\frac{2}{7}$.

A rectangular $1$ by $10$ strip is divided into $10$ $1$ by $1$ squares. The numbers $1$, $2$, $3$,$...$, $10$ are placed in the squares in the following way. First the number $1$ is placed in an arbitrary square, then $2$ is placed in a neighbouring square, then $3$ is placed into a free square neighbouring one of the squares occupied earlier, and so on (up to $10$). How many different permutations of $1$,$2$, $3$,$...$, $10$ can one get in this way? (A Shen)

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. [i]David Yang.[/i]

$a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ are $2n$ positive real numbers such that $a_1,a_2,\cdots ,a_n$ aren't all equal. And assume that we can divide $a_1,a_2,\cdots ,a_n$ into two subsets with equal sums.similarly $b_1,b_2,\cdots ,b_n$ have these two conditions. Prove that there exist a simple $2n$-gon with sides $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$ and parallel to coordinate axises Such that the lengths of horizontal sides are among $a_1,a_2,\cdots ,a_n$ and the lengths of vertical sides are among $b_1,b_2,\cdots ,b_n$.(simple polygon is a polygon such that it doesn't intersect itself)

Let $n\ge 2$ be an integer. Consider a $2n+1\times 2n+1$ board. All cells lying both in an even row and an even column have been removed. The remaining cells form a [i]labyrinth[/i]. An ant takes a walk in the labyrinth. A single step of the ant consists of moving to a neighbouring cell. Determine, in terms of $n$, the smallest possible number of steps so that every cell of the labirynth is visited by the ant. The ant chooses the start cell. The start cell and the end cell are considered visited. Each cell could be visited several times. The picture depicts the labyrinth for $n=3$ and possible steps of the ant in its four locations.