Let $n$ be a positive integer. Humanity will begin to colonize Mars. The SpaceY and SpaceZ agencies will be responsible for traveling between the planets. To prevent the rockets from colliding, they will travel alternately, with SpaceY making the first trip. On each trip, the responsible agency will do one of two types of mission: (i) choose a positive integer $k$ and take $k$ people to Mars, creating a new colony on the planet and settling them in that colony; (ii) choose some existing colony on Mars and a positive integer $k$ strictly smaller than the population of that colony, and bring $k$ people from that colony back to Earth. To maintain the organization on Mars, a mission cannot result in two colonies with the same population and the number of colonies must be at most $n$. The first agency that cannot carry out a mission will go bankrupt. Determine, in terms of $n$, which agency can guarantee that it will not go bankrupt first.

In the film there is $n$ roles. For each $i$ ($1 \le i \le n$), the role of number $i$ can play $a_i$ a person, and one person can play only one role. Every day a casting is held, in which participate people for $n$ roles, and from each role only one person. Let $p$ be a prime number such that $p \ge a_1, \ldots, a_n, n$. Prove that you can have $p^k$ castings such that if we take any $k$ people who are tried in different roles, they together participated in some casting ($k$ is a natural number not exceeding $n$ ).

A cube consisting of $(2N)^3$ unit cubes is pierced by several needles parallel to the edges of the cube (each needle pierces exactly $2N$ unit cubes). Each unit cube is pierced by at least one needle. Let us call any subset of these needles “regular” if there are no two needles in this subset that pierce the same unit cube. a) Prove that there exists a regular subset consisting of $2N^2$ needles such that all of them have either the same direction or two different directions. b) What is the maximum size of a regular subset that does exist for sure? (Nikita Gladkov, Alexandr Zimin)

In each square of an $11\times 11$ board, we are to write one of the numbers $-1$, $0$, or $1$ in such a way that the sum of the numbers in each column is nonnegative and the sum of the numbers in each row is nonpositive. What is the smallest number of zeros that can be written on the board? Justify your answer.

Given a positive integer $n$, an $n$-gun is a $2n$-mino that is formed by putting a $1 \times n$ grid and an $n \times 1$ grid side by side so that one of the corner unit squares of the first grid is next to one of the corner unit squares of the second grid. Find the minimum possible $k$ such that it is possible to color the infinite planar grid with $k$ colors such that any $n$-gun cannot cover two different squares with the same color. [i]Itf0501[/i]

There are given $111$ coins and a $n\times n$ table divided into unit cells. This coins are placed inside the unit cells (one unit cell may contain one coin, many coins, or may be empty), such that the difference between the number of coins from two neighbouring cells (that have a common edge) is $1$. Find the maximal $n$ for this to be possible.

A $4\times4\times4$ cube is composed of $64$ unit cubes. The faces of $16$ unit cubes are to be coloured red. A colouring is called interesting if there is exactly $1$ red unit cube in every $1\times1\times 4$ rectangular box composed of $4$ unit cubes. Determine the number of interesting colourings.

In a sports meeting a total of $m$ medals were awarded over $n$ days. On the first day one medal and $\frac{1}{7}$ of the remaining medals were awarded. On the second day two medals and $\frac{1}{7}$ of the remaining medals were awarded, and so on. On the last day, the remaining $n$ medals were awarded. How many medals did the meeting last, and what was the total number of medals ?

You place $n^2$ indistinguishable pieces on an $n\times n$ chessboard, where $n=2^{90}\approx 1.27\times10^{27}$. Of these pieces, $n$ of them are slightly lighter than usual, while the rest are all the same standard weight, but you are unable to discern this simply by feeling the pieces.\\ However, beneath each row and column of the chessboard, you have set up a scale, which, when turned on, will tell you [i]only[/i] whether the average weight of all the pieces on that row or column is the standard weight, or lighter than standard. On a given step, you are allowed to rearrange every piece on the chessboard, and then turn on all the scales simultaneously, and record their outputs, before turning them all off again. (Note that you can only turn on the scales if all $n^2$ pieces are placed in different squares on the board.) Find an algorithm that, in at most $k$ steps, will always allow you to rearrange the pieces in such a way that every row and column measures lighter than standard on the final step. An algorithm that completes in at most $k$ steps will be awarded: 1 pt for $k>10^{55}$ 10 pts for $k=10^{55}$ 30 pts for $k=10^{30}$ 50 pts for $k=10^{28}$ 65 pts for $k=10^{20}$ 80 pts for $k=10^5$ 90 pts for $k=2021$ 100 pts for $k=500$

Given $2018 \times 4$ grids and tint them with red and blue. So that each row and each column has the same number of red and blue grids, respectively. Suppose there're $M$ ways to tint the grids with the mentioned requirement. Determine $M \pmod {2018}$.

There are $n$ red sticks and $n$ blue sticks. The sticks of each colour have the same total length, and can be used to construct an $n$-gon. We wish to repaint one stick of each colour in the other colour so that the sticks of each colour can still be used to construct an $n$-gon. Is this always possible if (a) $n = 3$, (b) $n > 3$ ?

[b]6.1 [/b] The bindery had 92 sheets of white paper and $135$ sheets of colored paper. It took a sheet of white paper to bind each book. and a sheet of colored paper. After binding several books of white Paper turned out to be half as much as the colored one. How many books were bound? [b]6.2[/b] Prove that if you multiply all the integers from $1$ to $1965$, you get the number, the last whose non-zero digit is even. [b]6.3[/b] The front tires of a car wear out after $25,000$ kilometers, and the rear tires after $15,000$ kilometers of travel. When should you swap tires so that they wear out at the same time? [b]6.4[/b] A rectangle $19$ cm $\times 65$ cm is divided by straight lines parallel to its sides into squares with side 1 cm. How many parts will this rectangle be divided into if you also draw a diagonal in it? [b]6.5[/b] Find the dividend, divisor and quotient in the example: [center][img]https://cdn.artofproblemsolving.com/attachments/2/e/de053e7e11e712305a89d3b9e78ac0901dc775.png[/img] [/center] [b]6.6[/b] Odd numbers from $1$ to $49$ are written out in table form $$\,\,\,1\,\,\,\,\,\, 3\,\,\,\,\,\, 5\,\,\,\,\,\, 7\,\,\,\,\,\, 9$$ $$11\,\,\, 13\,\,\, 15\,\,\, 17\,\,\, 19$$ $$21\,\,\, 23\,\,\, 25\,\,\, 27\,\,\, 29$$ $$31\,\,\, 33\,\,\, 35\,\,\, 37\,\,\, 39$$ $$41\,\,\, 43\,\,\, 45\,\,\, 47\,\,\, 49$$ $5$ numbers are selected, any two of which are not on the same line or in one column. What is their sum? PS. You should use hide for answers.Collected [url=https://artofproblemsolving.com/community/c3988081_1965_leningrad_math_olympiad]here[/url].

Each side and diagonal of a regular $n$-gon ($n \ge 3$) for odd $n$ is colored red or blue. One may choose a vertex and change the color of all segments emanating from that vertex. Prove that, no matter how the edges were colored initially, one can achieve that the number of blue segments at each vertex is even. Prove also that the resulting coloring depends only on the initial coloring.

Find the number of $10$-digit numbers $\overline{a_1a_2... a_{10}}$ which are multiples of $11$ such that the digits are non-increasing from left to right, i.e. $a_i \ge a_{i+1}$ for each $1 \le i \le 9$.

The edges of $K_{2017}$ are each labeled with $1,2,$ or $3$ such that any triangle has sum of labels at least $5.$ Determine the minimum possible average of all $\dbinom{2017}{2}$ labels. (Here $K_{2017}$ is defined as the complete graph on 2017 vertices, with an edge between every pair of vertices.) [i]Proposed by Michael Ma[/i]

The shape of a military base is an equilateral triangle of side $10$ kilometers. Security constraints make cellular phone com­munication possible only within $2.5$ kilometers. Each of $17$ soldiers patrols the base randomly and tries to contact all others. Prove that at each moment at least two soldiers can communicate.

Let $m$ and $n$ be positive integers greater than $1$. In each unit square of an $m\times n$ grid lies a coin with its tail side up. A [i]move[/i] consists of the following steps. [list=1] [*]select a $2\times 2$ square in the grid; [*]flip the coins in the top-left and bottom-right unit squares; [*]flip the coin in either the top-right or bottom-left unit square. [/list] Determine all pairs $(m,n)$ for which it is possible that every coin shows head-side up after a finite number of moves. [i]Thanasin Nampaisarn, Thailand[/i]

The new PUMaC tournament hosts $2020$ students, numbered by the following set of labels $1, 2, . . . , 2020$. The students are initially divided up into $20$ groups of $101$, with each division into groups equally likely. In each of the groups, the contestant with the lowest label wins, and the winners advance to the second round. Out of these $20$ students, we chose the champion uniformly at random. If the expected value of champion’s number can be written as $\frac{a}{b}$, where $a, b$ are relatively prime integers, determine $a + b$.

$25$ checkers are placed on $25$ leftmost squares of $1 \times N$ board. Checker can either move to the empty adjacent square to its right or jump over adjacent right checker to the next square if it is empty. Moves to the left are not allowed. Find minimal $N$ such that all the checkers could be placed in the row of $25$ successive squares but in the reverse order.

Cards numbered with numbers $1$ to $1000$ are to be placed on the cells of a $1\times 1994$ rectangular board one by one, according to the following rule: If the cell next to the cell containing the card $n$ is free, then the card $n+1$ must be put on it. Prove that the number of possible arrangements is not more than half a mllion.

A square $ 600 \times 600$ divided into figures of $4$ cells of the forms in the figure: In the figures of the first two types in shaded cells The number $ 2 ^ k $ is written, where $ k $ is the number of the column in which this cell. Prove that the sum of all the numbers written is divisible by $9$.

Thirty nine nonzero numbers are written in a row. The sum of any two neighbouring numbers is positive, while the sum of all the numbers is negative. Is the product of all these numbers negative or positive? (4 points) Boris Frenkin

Let $S$ be a set of $n$ points in the plane such that no four points are collinear. Let $\{d_1,d_2,\cdots ,d_k\}$ be the set of distances between pairs of distinct points in $S$, and let $m_i$ be the multiplicity of $d_i$, i.e. the number of unordered pairs $\{P,Q\}\subseteq S$ with $|PQ|=d_i$. Prove that $\sum_{i=1}^k m_i^2\leq n^3-n^2$.

[u]Round 5 [/u] [b]p13.[/b] Circles $\omega_1$, $\omega_2$, and $\omega_3$ have radii $8$, $5$, and $5$, respectively, and each is externally tangent to the other two. Circle $\omega_4$ is internally tangent to $\omega_1$, $\omega_2$, and $\omega_3$, and circle $\omega_5$ is externally tangent to the same three circles. Find the product of the radii of $\omega_4$ and $\omega_5$. [b]p14.[/b] Pythagoras has a regular pentagon with area $1$. He connects each pair of non-adjacent vertices with a line segment, which divides the pentagon into ten triangular regions and one pentagonal region. He colors in all of the obtuse triangles. He then repeats this process using the smaller pentagon. If he continues this process an infinite number of times, what is the total area that he colors in? Please rationalize the denominator of your answer. p15. Maisy arranges $61$ ordinary yellow tennis balls and $3$ special purple tennis balls into a $4 \times 4 \times 4$ cube. (All tennis balls are the same size.) If she chooses the tennis balls’ positions in the cube randomly, what is the probability that no two purple tennis balls are touching? [u]Round 6 [/u] [b]p16.[/b] Points $A, B, C$, and $D$ lie on a line (in that order), and $\vartriangle BCE$ is isosceles with $\overline{BE} = \overline{CE}$. Furthermore, $F$ lies on $\overline{BE}$ and $G$ lies on $\overline{CE}$ such that $\vartriangle BFD$ and $\vartriangle CGA$ are both congruent to $\vartriangle BCE$. Let $H$ be the intersection of $\overline{DF}$ and $\overline{AG}$, and let $I$ be the intersection of $\overline{BE}$ and $\overline{AG}$. If $m \angle BCE = arcsin \left( \frac{12}{13} \right)$, what is $\frac{\overline{HI}}{\overline{FI}}$ ? [b]p17.[/b] Three states are said to form a tri-state area if each state borders the other two. What is the maximum possible number of tri-state areas in a country with fifty states? Note that states must be contiguous and that states touching only at “corners” do not count as bordering. [b]p18.[/b] Let $a, b, c, d$, and $e$ be integers satisfying $$2(\sqrt[3]{2})^2 + \sqrt[3]{2}a + 2b + (\sqrt[3]{2})^2c +\sqrt[3]{2}d + e = 0$$ and $$25\sqrt5 i + 25a - 5\sqrt5 ib - 5c + \sqrt5 id + e = 0$$ where $i =\sqrt{-1}$. Find $|a + b + c + d + e|$. [u]Round 7[/u] [b]p19.[/b] What is the greatest number of regions that $100$ ellipses can divide the plane into? Include the unbounded region. [b]p20.[/b] All of the faces of the convex polyhedron $P$ are congruent isosceles (but NOT equilateral) triangles that meet in such a way that each vertex of the polyhedron is the meeting point of either ten base angles of the faces or three vertex angles of the faces. (An isosceles triangle has two base angles and one vertex angle.) Find the sum of the numbers of faces, edges, and vertices of $P$. [b]p21.[/b] Find the number of ordered $2018$-tuples of integers $(x_1, x_2, .... x_{2018})$, where each integer is between $-2018^2$ and $2018^2$ (inclusive), satisfying $$6(1x_1 + 2x_2 +...· + 2018x_{2018})^2 \ge (2018)(2019)(4037)(x^2_1 + x^2_2 + ... + x^2_{2018}).$$ PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c4h2784936p24472982]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

We are given $2n$ natural numbers \[1, 1, 2, 2, 3, 3, \ldots, n - 1, n - 1, n, n.\] Find all $n$ for which these numbers can be arranged in a row such that for each $k \leq n$, there are exactly $k$ numbers between the two numbers $k$.