The Macedonian Mathematical Olympiad is held in two rooms numbered $1$ and $2$. At the beginning all of the competitors enter room No. $1$. The final arrangement of the competitors to the rooms is obtained in the following way: a list with the names of a few of the competitors is read aloud; after a name is read, the corresponding competitor and all of his/her acquaintances from the rest of the competitors change the room in which they currently are. Hence, to each list of names corresponds one final arrangement of the competitors to the rooms. Show that the total number of possible final arrangements is not equal to $2009$ (acquaintance between competitors is a symmetrical relation).

Let $n \in N$. Find the maximum number of irreducible fractions a/b (i.e., $gcd(a, b) = 1$) which lie in the interval $(0,1/n)$.

Sergio thinks of a positive integer $S$, less than or equal to $100$. Iván must guess the number that Sergio thought of, using the following procedure: in each step, he chooses two positive integers $A$ and $B$ less than $100$, and asks Sergio what is the greatest common factor between $A+ S$ and $B$. Give a sequence of seven steps that ensures Iván guesses the number $S$ that Sergio thought of. Clarification:In each step, Sergio correctly answers Iván's question.

$49$ natural numbers are written on the board. All their pairwise sums are different. Prove that the largest of the numbers is greater than $600$. [hide=original wording in Russian]На доске написаны 49 натуральных чисел. Все их попарные суммы различны. Докажите, что наибольшее из чисел больше 600[/hide]

$2014$ points are placed on a circumference. On each of the segments with end points on two of the $2014$ points is written a non-negative real number. For any convex polygon with vertices on some of the $2014$ points, the sum of the numbers written on their sides is less or equal than $1$. Find the maximum possible value for the sum of all the written numbers.

$ (a)$ Prove that $ \mathbb{N}$ can be partitioned into three (mutually disjoint) sets such that, if $ m,n \in \mathbb{N}$ and $ |m\minus{}n|$ is $ 2$ or $ 5$, then $ m$ and $ n$ are in different sets. $ (b)$ Prove that $ \mathbb{N}$ can be partitioned into four sets such that, if $ m,n \in \mathbb{N}$ and $ |m\minus{}n|$ is $ 2,3,$ or $ 5$, then $ m$ and $ n$ are in different sets. Show, however, that $ \mathbb{N}$ cannot be partitioned into three sets with this property.

The points $S(i, j)$ with integer Cartesian coordinates $0 < i \leq n, 0 < j \leq m, m \leq n$, form a lattice. Find the number of: [b](a)[/b] rectangles with vertices on the lattice and sides parallel to the coordinate axes; [b](b)[/b] squares with vertices on the lattice and sides parallel to the coordinate axes; [b](c)[/b] squares in total, with vertices on the lattice.

The names of $8$ people are written on slips of paper and placed in a hat. Each of the $8$ people then randomly draw a piece of paper (without replacement). Then, the people are formed into groups satisfying the following requirements: (i) Each person is in the same group as the person who drew his piece of paper. (ii)There are as many groups as possible while still satisfying condition (i). On average, how many groups will there be? (There might be “groups” of only one person.)

A triangle is divided into nine smaller triangles, where counters with the number zero are placed at each of the ten vertices. A [i]movement[/i] consists of choosing one of the nine triangles and applying the same operation to the three counters of that triangle: adding a unit or subtracting a unit. The figure illustrates a possible [i]movement[/i]. We shall call the integer number n [i]dominant [/i] if it is possible, after a few moves, to obtain a configuration in which the counter numbers are all consecutive and the largest of these numbers is $n$. Determine all [i]dominant [/i] numbers. [img]https://cdn.artofproblemsolving.com/attachments/7/3/731160e6e9a2b3292a31c4555d4adbc7028596.png[/img]

Thanos establishes $5$ settlements on a remote planet, randomly choosing one of them to stay in, and then he randomly builds a system of roads between these settlements such that each settlement has exactly one outgoing (unidirectional) road to another settlement. Afterwards, the Avengers randomly choose one of the $5$ settlements to teleport to. Then, they (the Avengers) must use the system of roads to travel from one settlement to another. The probability that the Avengers can find Thanos can be written as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$. Find $m+n$.

Find the least $n\in N$ such that among any $n$ rays in space sharing a common origin there exist two which form an acute angle.

Julián chooses $2007$ points of the plane between which there are no $3$ aligned, and draw with red all the segments that join two of those points. Next, Roberto draws several lines. Its objective is for each red segment to be cut inside by (at least) one of the lines. Determine the minor $\ell$ lines such that, no matter how Julián chooses the $2007$ points, with the properly chosen $\ell$ lines, Roberto will achieve his objective with certainty.

Susana and Brenda play a game writing polynomials on the board. Susana starts and they play taking turns. 1) On the preparatory turn (turn 0), Susana choose a positive integer $n_0$ and writes the polynomial $P_0(x)=n_0$. 2) On turn 1, Brenda choose a positive integer $n_1$, different from $n_0$, and either writes the polynomial $$P_1(x)=n_1x+P_0(x) \textup{ or } P_1(x)=n_1x-P_0(x)$$ 3) In general, on turn $k$, the respective player chooses an integer $n_k$, different from $n_0, n_1, \ldots, n_{k-1}$, and either writes the polynomial $$P_k(x)=n_kx^k+P_{k-1}(x) \textup{ or } P_k(x)=n_kx^k-P_{k-1}(x)$$ The first player to write a polynomial with at least one whole whole number root wins. Find and describe a winning strategy.

Prove there exists a constant $c$ (independent of $n$) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where a) $f(n)=n\ln{n}$; b) $f(n)=n$. [i]David Yang.[/i]

For each $i=1,2,..N$, let $a_i,b_i,c_i$ be integers such that at least one of them is odd. Show that one can find integers $x,y,z$ such that $xa_i+yb_i+zc_i$ is odd for at least $\frac{4}{7}N$ different values of $i$.

there are some identical squares with sides parallel, in a plane. Among any $k+1$ of them, there are two with a point in common. Prove they can be divided into $2k-1$ sets, such that all the squares in one set aint pairwise disjoint.

There are two countries $A$ and $B$, where each countries have $n(\ge 2)$ airports. There are some two-way flights among airports of $A$ and $B$, so that each airport has exactly $3$ flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an [i]exotic traveling course[/i] which travels through all $2n$ airports exactly once, and returns to the initial airport. If $N$ denotes the number of all exotic traveling courses, then prove that $\frac{N}{4n}$ is an even integer. (Here, note that two exotic traveling courses are different if their starting place are different.)

Let $n$ be a positive integer divisible by $4$. Find the number of permutations $\sigma$ of $(1,2,3,\cdots,n)$ which satisfy the condition $\sigma(j)+\sigma^{-1}(j)=n+1$ for all $j \in \{1,2,3,\cdots,n\}$.

Let $n\ge 3$ be an integer. Lucas and Matías play a game in a regular $n$-sided polygon with a vertex marked as a trap. Initially Matías places a token at one vertex of the polygon. In each step, Lucas says a positive integer and Matías moves the token that number of vertices clockwise or counterclockwise, at his choice. a) Determine all the $n\ge 3$ such that Matías can locate the token and move it in such a way as to never fall into the trap, regardless of the numbers Lucas says. Give the strategy to Matías. b) Determine all the $n\ge 3$ such that Lucas can force Matías to fall into the trap. Give the strategy to Lucas. Note. The two players know the value of $n$ and see the polygon.

Let $ p,q,n$ be three positive integers with $ p \plus{} q < n$. Let $ (x_{0},x_{1},\cdots ,x_{n})$ be an $ (n \plus{} 1)$-tuple of integers satisfying the following conditions : (a) $ x_{0} \equal{} x_{n} \equal{} 0$, and (b) For each $ i$ with $ 1\leq i\leq n$, either $ x_{i} \minus{} x_{i \minus{} 1} \equal{} p$ or $ x_{i} \minus{} x_{i \minus{} 1} \equal{} \minus{} q$. Show that there exist indices $ i < j$ with $ (i,j)\neq (0,n)$, such that $ x_{i} \equal{} x_{j}$.

For every permutation $ \tau$ of $ 1, 2, \ldots, 10$, $ \tau \equal{} (x_1, x_2, \ldots, x_{10})$, define $ S(\tau) \equal{} \sum_{k \equal{} 1}^{10} |2x_k \minus{} 3x_{k \minus{} 1}|$. Let $ x_{11} \equal{} x_1$. Find [b]I.[/b] The maximum and minimum values of $ S(\tau)$. [b]II.[/b] The number of $ \tau$ which lets $ S(\tau)$ attain its maximum. [b]III.[/b] The number of $ \tau$ which lets $ S(\tau)$ attain its minimum.

Each side of a triangle $ABC$ has been divided into $n+1$ equal parts. Find the number of triangles with the vertices at the division points having no side parallel to or lying at a side of $\triangle ABC$.

A straight line is drawn across an $8\times 8$ chessboard. It is said to [i]pierce [/i]a square if it passes through an interior point of the square. At most how many of the $64$ squares can this line [i]pierce[/i]?

For a positive integer $n$, if $n$ is a product of two different primes and $n \equiv 2 \pmod 3$, then $n$ is called "special number." For example, $14, 26, 35, 38$ is only special numbers among positive integers $1$ to $50$. Prove that for any finite set $S$ with special numbers, there exist two sets $A, B$ such that [list] [*] $A \cap B = \emptyset, A \cup B = S$ [*] $||A| - |B|| \leq 1$ [*] For all primes $p$, the difference between number of elements in $A$ which is multiple of $p$ and number of elements in $B$ which is multiple of $p$ is less than or equal to $1$. [/list]

Let $k\ge 1$ be an integer. Determine the smallest positive integer $n$ such that some cells on an $n \times n$ board can be painted black so that in each row and in each column there are exactly $k$ black cells, and furthermore, the black cells do not share a side or a vertex with another black square. Clarification: You have to answer n based on $k$.