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]

A table of the type $~$ $ (n_1, n_2, ... , n_m) ,\ n_1 \ge n_2 \ge ... \ge n_m $ $~$ is defined in the following way: $~$ $n_1$ $~$ squares are ordered horizontally one next to another, then $~$ $n_2$ $~$ squares are ordered horizontally beneath the already ordered $~$ $n_1$ $~$ squares. The procedure continues until a net composed of $~$ $n_1$ $~$ squares in the first row, $~$ $n_2$ $~$ in the second, $~$ $n_i$ $~$ in the $~$ $i$-th row is obtained, such that there are totally $~$ $n=n_1+n_2+...+n_m$ $~$ squares in the net. The ordered rows form a straight line on the left, as shown in the example. The obtained table is filled with the numbers from $~$ $1$ $~$ till $~$ $n$ $~$ in a way that the numbers in each row and column become greater from left to right and from top to bottom, respectively. An example of a table of the type $~$ $(5,4,2,1)$ $~$ and one possible way of filling it is attached to the post. Find the number of ways the table of type $~$ $(4,3,2)$ $~$ can be filled.

Two positive integers $m$ and $n$ are written on the board. We replace one of two numbers in each step on the board by either their sum, or product, or ratio (if it is an integer). Depending on the numbers $m$ and $n$, specify all the pairs that can appear on the board in pairs. (Radovan Švarc)

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.

How many integers between $2$ and $100$ inclusive [i]cannot[/i] be written as $m \cdot n,$ where $m$ and $n$ have no common factors and neither $m$ nor $n$ is equal to $1$? Note that there are $25$ primes less than $100.$

Find all sets comprising of 4 natural numbers such that the product of any 3 numbers in the set leaves a remainder of 1 when divided by the remaining number.

Find all the natural numbers $a, b, c$ satisfying the following equation: $$a^{12} + 3^b = 1788^c$$.

Can we partition the positive integers in two sets such that none of the sets contains an infinite arithmetic progression of nonzero ratio ?

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.

Isaac writes each fraction $\frac{1^2}{300}$ , $\frac{2^2}{300}$ , $...$, $\frac{300^2}{300}$ in reduced form. Compute the sum of all denominators over all the reduced fractions that Isaac writes down.

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]

Let $ABC$ be a triangle with $\angle ABC \neq 90^\circ$ and $AB$ its shortest side. Denote by $H$ the intersection of the altitudes of triangle $ABC$. Let $K$ be the circle through $A$ with centre $B$. Let $D$ be the other intersection of $K$ and $AC$. Let $K$ intersect the circumcircle of $BCD$ again at $E$. If $F$ is the intersection of $DE$ and $BH$, show that $BD$ is tangent to the circle through $D$, $F$, and $H$.

Find $n$ such that each of the numbers $n,(n+1),...,(n+20)$ has the common divider greater than one with the number $30030 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$.

Does there exist an infinite sequence $a_1,a_2,\dotsc$ of real numbers which is bounded, not periodic, and satisfies the recursion $a_{n+1}=a_na_{n-1}+1$?

Find all possible values of $C\in \mathbb R$ such that there exists a real sequence $\{a_n\}_{n=1}^\infty$ such that $$a_na_{n+1}^2\ge a_{n+2}^4 +C$$ for all $n\ge 1$.

Let $p$ and $q$ be odd prime numbers. Assume that there exists a positive integer $n$ such that $pq-1= n^3$. Express $p+q$ in terms of $n$

Find the smallest integer $n$ such that each subset of $\{1,2,\ldots, 2004\}$ with $n$ elements has two distinct elements $a$ and $b$ for which $a^2-b^2$ is a multiple of $2004$.

One-round hockey tournament is finished (each plays with each one time, the winner gets $2$ points, looser -- $0$, and $1$ point for draw). For arbitrary subgroup of teams there exists a team (may be from that subgroup) that has got an odd number of points in the games with the teams of the subgroup. Prove that there was even number of the participants.

Let \[\mathcal{S} = \sum_{i=1}^{\infty}\left(\prod_{j=1}^i \dfrac{3j - 2}{12j}\right).\] Then $(\mathcal{S} + 1)^3 = \tfrac mn$ with $m$ and $n$ coprime positive integers. Find $10m + n$. [i]Proposed by Justin Lee and Evan Chang[/i]

Point $O$ is the intersection of the perpendicular bisectors of the sides of the triangle $\vartriangle ABC$ . Let $D$ be the intersection of the line $AO$ with the segment $[BC]$. Knowing that $OD = BD = \frac 13 BC$, find the measures of the angles of the triangle $\vartriangle ABC$.

Let $n$ be a natural number. Suppose that $x_0=0$ and that $x_i>0$ for all $i\in\{1,2,\ldots ,n\}$. If $\sum_{i=1}^nx_i=1$ , prove that \[1\leq\sum_{i=1}^{n} \frac{x_i}{\sqrt{1+x_0+x_1+\ldots +x_{i-1}}\sqrt{x_i+\ldots+x_n}} < \frac{\pi}{2} \]

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

Let the triangle $ ADB_1$ s.t. $ m(\angle DAB_1)\ne 90^\circ$.On the sides of this triangle externally are constructed the squares $ ABCD$ and $ AB_1C_1D_1$ with centers $ O_1$ and $ O_2$, respectively.Prove that the circumcircles of the triangles $ BAB_1$, $ DAD_1$ and $ O_1AO_2$ share a common point, that differs from $ A$.

Let $U_1 , U_2 , U_3$ be iid random variables on [0,1], which in order of magnitude, $U_1^{\ast} \le U_2^{\ast} \leq U_3 ^ {\ast}$. Let $\alpha, p_1 , p_2 , p_3 \in [0,1]$ such that $P(U_j ^ {\ast} \ge p_j)= \alpha$ ( j = 1,2,3). Prove that $$P \left( p_1 + (p_2-p_1) U_3^{\ast} + (p_3- p_2) U_2^{\ast} + (1-p_3) U_1^{\ast} \geq \frac{1}{2} \right) \geq 1-\alpha$$