Let $N(a,b)$ be the number of ways to cover a table $a \times b$ with domino tiles. Let $M(a,2b+1)$ be the number of ways to cover a table $a \times 2b+1$ with domino tiles, such that there are [b]no[/b] vertical tile in the central column. Prove that $$M(2m,2n+1)=2^m \cdot N(2m,n)\cdot N(2m,n-1)$$

In a school class with $ 3n$ children, any two children make a common present to exactly one other child. Prove that for all odd $ n$ it is possible that the following holds: For any three children $ A$, $ B$ and $ C$ in the class, if $ A$ and $ B$ make a present to $ C$ then $ A$ and $ C$ make a present to $ B$.

Consider a cube and two of its vertices $A$ and $B$, which are the endpoints of a face diagonal. A [i]path [/i] is a sequence of cube angles, each step of one angle along a cube edge is walked to one of the three adjacent angles. Let $a$ be the number of paths of length $2012$ that starts at point $A$ and ends at $A$ and let b be the number of ways of length $2012$ that starts in $A$ and ends in $B$. Decide which of the two numbers $a$ and $b$ is the larger.

For a rational point (x,y), if xy is an integer that divided by 2 but not 3, color (x,y) red, if xy is an integer that divided by 3 but not 2, color (x,y) blue. Determine whether there is a line segment in the plane such that it contains exactly 2017 blue points and 58 red points.

We call a triangle consisting of three vertices of a pentagon [i]big[/i] if it's area is larger than half of the pentagon's area. Find the maximum number of [i]big[/i] triangles that can be in a convex pentagon. [i]Proposed by Gonchigdorj Sandag[/i]

Find the greatest natural number $N$ such that, for any arrangement of the numbers $1, 2, \ldots, 400$ in a chessboard $20 \times 20$, there exist two numbers in the same row or column, which differ by at least $N.$

We call the arrangement of $n$ ones and $m$ zeros around the circle as good, if we can swap neighboring zero and one in such a way that we get an arrangement, that differs from the original by rotation. For what natural $m$ and $n$ does a good arrangement exist?

Some people know each other in a group of people, where "knowing" is a symmetric relation. For a person, we say that it is $social$ if it knows at least $20$ other persons and at least $2$ of those $20$ know each other. For a person, we say that it is $shy$ if it doesn't know at least $20$ other persons and at least $2$ of those $20$ don't know each other. Find the maximal number of people in that group, if we know that group doesn't have any $social$ nor $shy$ persons.

An $n$-mino is a connected figure made by connecting $n$ $1 \times 1 $ squares. Two polyminos are the same if moving the first we can reach the second. For a polymino $P$ ,let $|P|$ be the number of $1 \times 1$ squares in it and $\partial P$ be number of squares out of $P$ such that each of the squares have at least on edge in common with a square from $P$. (a) Prove that for every $x \in (0,1)$:\[\sum_P x^{|P|}(1-x)^{\partial P}=1\] The sum is on all different polyminos. (b) Prove that for every polymino $P$, $\partial P \leq 2|P|+2$ (c) Prove that the number of $n$-minos is less than $6.75^n$. [i]Proposed by Kasra Alishahi[/i]

Let $A$ be a subset with seven elements of the set $\{1,2,3, ...,26\}$. Show that there are two distinct elements of $A$, having the same sum of their elements.

We are given $100$ strictly increasing sequences of positive integers: $A_{i}= (a_{1}^{(i)}, a_{2}^{(i)},...), i = 1, 2,..., 100$. For $1 \leq r, s \leq 100$ we define the following quantities: $f_{r}(u)=$ the number of elements of $A_{r}$ not exceeding $n$; $f_{r,s}(u) =$ the number of elements of $A_{r}\cap A_{s}$ not exceeding $n$. Suppose that $f_{r}(n) \geq\frac{1}{2}n$ for all $r$ and $n$. Prove that there exists a pair of indices $(r, s)$ with $r \not = s$ such that $f_{r,s}(n) \geq\frac{8n}{33}$ for at least five distinct $n-s$ with $1 \leq n < 19920.$

A $15$-inch-long stick has four marks on it, dividing it into five segments of length $1,2,3, 4$, and $5$ inches (although not neccessarily in that order) to make a “ruler.” Here is an example. [img]https://cdn.artofproblemsolving.com/attachments/0/e/065d42b36083453f3586970125bedbc804b8a1.png[/img] Using this ruler, you could measure $8$ inches (between the marks $B$ and $D$) and $11$ inches (between the end of the ruler at $A$ and the mark at $E$), but there’s no way you could measure $12$ inches. Prove that it is impossible to place the four marks on the stick such that the five segments have length $1,2,3, 4$, and $5$ inches, and such that every integer distance from $1$ inch through $15$ inches could be measured.

Ada rolls a standard $4$-sided die $5$ times. The probability that the die lands on at most two distinct sides can be written as $ \frac{A}{B}$ for relatively prime positive integers $A$ and $B$. Find $1000A +B$

Suppose there are 18 lighthouses on the Persian Gulf. Each of the lighthouses lightens an angle with size 20 degrees. Prove that we can choose the directions of the lighthouses such that whole of the blue Persian (always Persian) Gulf is lightened.

Given an equilateral triangle, all points on its sides are colored in one of two given colors. Prove that the is a right-angled triangle such that its three vertices are in the same color and on the sides of the equilateral triangle. [i]Alhaji Akbar, Jakarta[/i]

Prove that, for every integer $n \ge 2$, it is possible to divide a regular hexagon into $n$ quadrilaterals such that any two of them are similar. Clarification: Two quadrilaterals are similar if they have their corresponding sides proportional and their corresponding angles are equal, that is, the quadrilaterals $ABCD$ and $EFGH$ are similar if $\frac{AB}{EF}= \frac{BC}{FG}= \frac{CD}{GH} = \frac{DA}{HE}$, $\angle ABC = \angle EFG$, $\angle BCD = \angle FGH$, $\angle CDA = \angle GHE$ and $\angle DAB = \angle HEF$.

Let $K$ be a positive integer. Egor has $100$ cards with the number “$2$” written on them, and $100$ cards with the number “$3$” written on them. Egor wants to paint each card red or blue so that no subset of cards of the same color has the sum of the numbers equal to $K$. Find the greatest $K$ such that Egor will not be able to paint the cards in such a way.

Let $ a_1, a_2, \ldots , a_n$ be distinct positive integers and let $ M$ be a set of $ n \minus{} 1$ positive integers not containing $ s \equal{} a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n.$ A grasshopper is to jump along the real axis, starting at the point $ 0$ and making $ n$ jumps to the right with lengths $ a_1, a_2, \ldots , a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $ M.$ [i]Proposed by Dmitry Khramtsov, Russia[/i]

$16$ children are sitting at a round table. After the break, they sit down again on table. They find that each child is either sitting on its original [lace or in one of the two neighboring places. How many seating arrangements are possible in this way after the break?

We are given $n \geq 3$ weights of masses $1, 2, 3, \ldots , n$ grams. Find all $n$ for which it is possible to divide these weights into three groups with the same mass.

For each positive integer $n$, decide whether it is possible to tile a square with exactly $n+1$ similar rectangles, each with a positive area and aspect ratio $1:n$.

An infinite squared sheet is given, with squares of side length $1$. The “distance” between two squares is defined as the length of the shortest path from one of these squares to the other if moving between them like a chess rook (measured along the trajectory of the centre of the rook). Determine the minimum number of colours with which it is possible to colour the sheet (each square being given a single colour) in such a way that each pair of squares with distance between them equal to $6$ units is given different colours. Give an example of such a colouring and prove that using a smaller number of colours we cannot achieve this goal. (AG Pechkovskiy, IV Itenberg)

In a cardboard box are a large number of loose socks. Some of the socks are red, the others are blue. It is stated that the total number of socks does not exceed $1993$. Furthermore, it is stated that the probability of pulling two socks from the same color when two socks are randomly drawn from the box is $1/2$. What is according to the available information, the largest number of red socks that can exist in the box?

Is it possible to tile $2003 \times 2003$ board by $1 \times 2$ dominoes placed horizontally and $1 \times 3$ rectangles placed vertically?

Denmark has played an international football match against Georgia. the fight ended $5-5$, and between the first and the last goal the game has justnever stood . No country has scored three goals in a row, and Denmark scored the sixth goal. Can you use this information to determine which country scored the fifth goal?