In a remote island, a language in which every word can be written using only the letters $a$, $b$, $c$, $d$, $e$, $f$, $g$ is spoken. Let's say two words are [i]synonymous[/i] if we can transform one into the other according to the following rules: i) Change a letter by another two in the following way: \[a \rightarrow bc,\ b \rightarrow cd,\ c \rightarrow de,\ d \rightarrow ef,\ e \rightarrow fg,\ f\rightarrow ga,\ g\rightarrow ab\] ii) If a letter is between other two equal letters, these can be removed. For example, $dfd \rightarrow f$. Show that all words in this language are synonymous.

Let $\alpha_1,\ldots,\alpha_d,\beta_1,\ldots,\beta_e\in\mathbb{C}$ be such that the polynomials $f_1(x) =\prod_{i=1}^d(x-\alpha_i)$ and $f_2(x) =\prod_{i=1}^e(x-\beta_i)$ have integer coefficients. Suppose that there exist polynomials $g_1, g_2 \in\mathbb{Z}[x]$ such that $f_1g_1 +f_2g_2 = 1$. Prove that $\left|\prod_{i=1}^d \prod_{j=1}^e (\alpha_i - \beta_j)\right|=1$

Let $S$ be the set of all pairs $(a,b)$ of real numbers satisfying $1+a+a^2+a^3 = b^2(1+3a)$ and $1+2a+3a^2 = b^2 - \frac{5}{b}$. Find $A+B+C$, where \[ A = \prod_{(a,b) \in S} a , \quad B = \prod_{(a,b) \in S} b , \quad \text{and} \quad C = \sum_{(a,b) \in S} ab. \][i]Proposed by Evan Chen[/i]

In the nation of Onewaynia, certain pairs of cities are connected by roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges). Some roads have a traffic capacity of 1 unit and other roads have a traffic capacity of 2 units. However, on every road, traffic is only allowed to travel in one direction. It is known that for every city, the sum of the capacities of the roads connected to it is always odd. The transportation minister needs to assign a direction to every road. Prove that he can do it in such a way that for every city, the difference between the sum of the capacities of roads entering the city and the sum of the capacities of roads leaving the city is always exactly one. [i]Proposed by Zuming Feng and Yufei Zhao[/i]

Arutyun and Amayak show another effective trick. A spectator writes down on a board a sequence of $N$ (decimal) digits. Amayak closes two adjacent digits by a black disc. Then Arutyun comes and says both closed digits (and their order). For which minimal $N$ they may show such a trick? [i]K. Knop, O. Leontieva[/i]

The lock of a safe consists of 3 wheels, each of which may be set in 8 different ways positions. Due to a defect in the safe mechanism the door will open if any two of the three wheels are in the correct position. What is the smallest number of combinations which must be tried if one is to guarantee being able to open the safe (assuming the "right combination" is not known)?

Determine all positive integers $n$ such that $n$ divides $3^n - 2^n$.

Is there an infinite sequence of prime numbers $p_1, p_2, ..., p_n, ...,$ such that for every $i \in \mathbb{N}, p_{i + 1} \in \{2p_i - 1, 2p_i + 1\}$ is satisfied? Explain the answer.

In a country, there are towns, some of which are connected by roads. There is a route (not necessarily direct) between every two towns. The Minister of Education has ensured that every town without a school is connected via a direct road to a town that has a school. The Minister of State Optimization wants to ensure that there is a unique path between any two towns (without repeating traveled segments), which may require removing some roads. Is it always possible to achieve this without constructing additional schools while preserving what the Minister of Education has accomplished?

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.

Let $A_{1}A_{2}B_{1}B_{2}$ be a convex quadrilateral. At adjacent vertices $A_{1}$ and $A_{2}$ there are two Argentinian cities. At adjacent vertices $B_{1}$ and $B_{2}$ there are two Brazilian cities. There are $a$ Argentinian cities and $b$ Brazilian cities in the quadrilateral interior, no three of which collinear. Determine if it's possible, independently from the cities position, to build straight roads, each of which connects two Argentinian cities ou two Brazilian cities, such that: $\bullet$ Two roads does not intersect in a point which is not a city; $\bullet$ It's possible to reach any Argentinian city from any Argentinian city using the roads; and $\bullet$ It's possible to reach any Brazilian city from any Brazilian city using the roads. If it's always possible, construct an algorithm that builds a possible set of roads.

Let $D_{1}, D_{2}, . . . , D_{n}$ be rectangular parallelepipeds in space, with edges parallel to the $x, y, z$ axes. For each $D_{i}$, let $x_{i} , y_{i} , z_{i}$ be the lengths of its projections onto the $x, y, z$ axes, respectively. Suppose that for all pairs $D_{i}$ , $D_{j}$, if at least one of $x_{i} < x_{j}$ , $y_{i} < y_{j}$, $z_{i} < z_{j}$ holds, then $x_{i} \leq x_{j}$ , $y_{i} \leq y_{j}$, and $z_{i} < z_{j}$ . If the volume of the region $\bigcup^{n}_{i=1}{D_{i}}$ equals 1997, prove that there is a subset $\{D_{i_{1}}, D_{i_{2}}, . . . , D_{i_{m}}\}$ of the set $\{D_{1}, . . . , D_{n}\}$ such that $(i)$ if $k \not= l $ then $D_{i_{k}} \cap D_{i_{l}} = \emptyset $, and $(ii)$ the volume of $\bigcup^{m}_{k=1}{D_{i_{k}}}$ is at least 73.

For integers $n \ge k \ge 0$ we define the [i]bibinomial coefficient[/i] $\left( \binom{n}{k} \right)$ by \[ \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!} .\] Determine all pairs $(n,k)$ of integers with $n \ge k \ge 0$ such that the corresponding bibinomial coefficient is an integer. [i]Remark: The double factorial $n!!$ is defined to be the product of all even positive integers up to $n$ if $n$ is even and the product of all odd positive integers up to $n$ if $n$ is odd. So e.g. $0!! = 1$, $4!! = 2 \cdot 4 = 8$, and $7!! = 1 \cdot 3 \cdot 5 \cdot 7 = 105$.[/i]

A grandpa has a finite number of boxes in his attic. Each box is a straight rectangular prism with integer edge lengths. For every box its width is greater or equal to its height and its length is greater or equal to its width. A box can be put inside another box if and only if all of its dimensions are respectively smaller than the other one's. You can put two or more boxes in a bigger box only if the smaller boxes are all already inside one of the boxes. The grandpa decided to put the boxes in each other so that there would be a minimal number of visible boxes in the attic (boxes that have not been put inside another). He decided to use the following algorithm: at each step he finds the longest sequence of boxes so that the first can be put in the second, the second can be put in the third, etc., and then he puts them inside each other in the aforementioned order. The grandpa used the algorithm until no box could be put inside another. It is known that at each step the longest sequence of boxes was unique, e.g., at no moment were there two different sequences with the same length. The grandpa now claims that he has the minimal possible number of visible boxes in his attic. Is the claim necessarily true?

Given a table $m\times n$, in each cell of which a number $+1$ or $-1$ is written. It is known that initially exactly one $-1$ is in the table, all the other numbers being $+1$. During a move, it is allowed to chose any cell containing $-1$, replace this $-1$ by $0$, and simultaneously multiply all the numbers in the neighbouring cells by $-1$ (we say that two cells are neighbouring if they have a common side). Find all $(m,n)$ for which using such moves one can obtain the table containing zeros only, regardless of the cell in which the initial $-1$ stands.