The numbers $1,2,3,\dots,1000$ are written on the board. Patya and Vassya are playing a game. They take turn alternatively erasing a number from the board. Patya begins. If after a turn all numbers (maybe one) on the board be divisible by a natural number greater than $1$ the player who last played loses. If after some number of steps the only remaining number on the board be $1$ then they call it a draw. Determine the result of the game if they both play their best.

Alice and Bob are playing the following game: They have an $8\times8$ chessboard. Initially, all grids are white. Each round, Alice chooses a white grid and paints it black. Then Bob chooses one of the neighbors of that grid and paints it black. Or he does nothing. After that, Alice may decide to continue the game or not. The goal of Alice is to maximize the number of connected components of black grids, on the other hand, Bob wants to minimize that number. If both of them are extremely smart, how many connected components will be in the end of the game?

Two piles of coins lie on a table. It is known that the sum of the weights of the coins in the two piles are equal, and for any natural number $k$, not exceeding the number of coins in either pile, the sum of the weights of the $k$ heaviest coins in the first pile is not more than that of the second pile. Show that for any natural number $x$, if each coin (in either pile) of weight not less than $x$ is replaced by a coin of weight $x$, the first pile will not be lighter than the second. [i]D. Fon-der-Flaas[/i]

For a sequence of zeros and ones Vasya makes move of the following form until the process doesn't halt 1. If the first digit of the sequence is zero, this digit is erased. 2. If the first digit is one and there are at least two digits, Vasya swaps first two digits, reverses the sequence and replaces ones with zeros and zeros with ones. 3. If the sequence is empty or consists of a single one, the process stops. Find the number of sequences of length 2025 starting from which Vasya can get to the empty sequence. [i]M. Zorka[/i]

[u]Round 9[/u] [b]p25. [/b]Define a sequence $\{a_n\}_{n \ge 1}$ of positive real numbers by $a_1 = 2$ and $a^2_n -2a_n +5 =4a_{n-1}$ for $n \ge 2$. Suppose $k$ is a positive real number such that $a_n <k$ for all positive integers $n$. Find the minimum possible value of $k$. [b]p26.[/b] Let $\vartriangle ABC$ be a triangle with $AB = 13$, $BC = 14$, and $C A = 15$. Suppose the incenter of $\vartriangle ABC$ is $I$ and the incircle is tangent to $BC$ and $AB$ at $D$ and $E$, respectively. Line $\ell$ passes through the midpoints of $BD$ and $BE$ and point $X$ is on $\ell$ such that $AX \parallel BC$. Find $X I$ . [b]p27.[/b] Let $x, y, z$ be positive real numbers such that $x y + yz +zx = 20$ and $x^2yz +x y^2z +x yz^2 = 100$. Additionally, let $s = \max (x y, yz,xz)$ and $m = \min(x, y, z)$. If $s$ is maximal, find $m$. [u]Round 10[/u] [b]p28.[/b] Let $\omega_1$ be a circle with center $O$ and radius $1$ that is internally tangent to a circle $\omega_2$ with radius $2$ at $T$ . Let $R$ be a point on $\omega_1$ and let $N$ be the projection of $R$ onto line $TO$. Suppose that $O$ lies on segment $NT$ and $\frac{RN}{NO} = \frac4 3$ . Additionally, let $S$ be a point on $\omega_2$ such that $T,R,S$ are collinear. Tangents are drawn from $S$ to $\omega_1$ and touch $\omega_1$ at $P$ and $Q$. The tangent to $\omega_1$ at $R$ intersects $PQ$ at $Z$. Find the area of triangle $\vartriangle ZRS$. [b]p29.[/b] Let $m$ and $n$ be positive integers such that $k =\frac{ m^2+n^2}{mn-1}$ is also a positive integer. Find the sum of all possible values of $k$. [b]p30.[/b] Let $f_k (x) = k \cdot \ min (x,1-x)$. Find the maximum value of $k \le 2$ for which the equation $f_k ( f_k ( f_k (x))) = x$ has fewer than $8$ solutions for $x$ with $0 \le x \le 1$. [u]Round 11[/u] In the following problems, $A$ is the answer to Problem $31$, $B$ is the answer to Problem $32$, and $C$ is the answer to Problem $33$. For this set, you should find the values of $A$,$B$, and $C$ and submit them as answers to problems $31$, $32$, and $33$, respectively. Although these answers depend on each other, each problem will be scored separately. [b]p31.[/b] Find $$A \cdot B \cdot C + \dfrac{1}{B+ \dfrac{1}{C +\dfrac{1}{B+\dfrac{1}{...}}}}$$ [b]p32.[/b] Let $D = 7 \cdot B \cdot C$. An ant begins at the bottom of a unit circle. Every turn, the ant moves a distance of $r$ units clockwise along the circle, where $r$ is picked uniformly at random from the interval $\left[ \frac{\pi}{2D} , \frac{\pi}{D} \right]$. Then, the entire unit circle is rotated $\frac{\pi}{4}$ radians counterclockwise. The ant wins the game if it doesn’t get crushed between the circle and the $x$-axis for the first two turns. Find the probability that the ant wins the game. [b]p33.[/b] Let $m$ and $n$ be the two-digit numbers consisting of the products of the digits and the sum of the digits of the integer $2016 \cdot B$, respectively. Find $\frac{n^2}{m^2 - mn}$. [u]Round 12[/u] [b]p34.[/b] There are five regular platonic solids: the tetrahedron, cube, octahedron, dodecahedron, and icosahedron. For each of these solids, define its adjacency angle to be the dihedral angle formed between two adjacent faces. Estimate the sum of the adjacency angles of all five solids, in degrees. If your estimate is $E$ and the correct answer is $A$, your score for this problem will be $\max \left(0, \lfloor 15 -\frac12 |A-E| \rfloor \right).$ [b]p35.[/b] Estimate the value of $$\log_{10} \left(\prod_{k|2016} k!\right), $$ where the product is taken over all positive divisors $k$ of $2016$. If your estimate is $E$ and the correct answer is $A$, your score for this problem will be $\max \left(0, \lceil 15 \cdot \min \left(\frac{E}{A}, 2- \frac{E}{A}\right) \rceil \right).$ [b]p36.[/b] Estimate the value of $\sqrt{2016}^{\sqrt[4]{2016}}$. If your estimate is $E$ and the correct answer is $A$, your score for this problem will be $\max \left(0, \lceil 15 \cdot \min \left(\frac{\ln E}{\ln A}, 2- \frac{\ln E}{\ln A}\right) \rceil \right).$ PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h3158461p28714996]here [/url] and 5-8 [url=https://artofproblemsolving.com/community/c3h3158474p28715078]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Given $n$ points $X_1,X_2,\ldots, X_n$ in the interval $0 \leq X_i \leq 1, i = 1, 2,\ldots, n$, show that there is a point $y, 0 \leq y \leq 1$, such that \[\frac{1}{n} \sum_{i=1}^{n} | y - X_i | = \frac 12.\]

$n$ numbers are written on a blackboard. Someone then repeatedly erases two numbers and writes half their arithmetic mean instead, until only a single number remains. If all the original numbers were $1$, show that the final number is not less than $\frac{1}{n}$.

In every acyclic graph with 2022 vertices we can choose $k$ of the vertices such that every chosen vertex has at most 2 edges to chosen vertices. Find the maximum possible value of $k$.

[b]p1.[/b] What is $20\times 20 - 19\times 19$? [b]p2.[/b] Andover has a total of $1440$ students and teachers as well as a $1 : 5$ teacher-to-student ratio (for every teacher, there are exactly $5$ students). In addition, every student is either a boarding student or a day student, and $70\%$ of the students are boarding students. How many day students does Andover have? [b]p3.[/b] The time is $2:20$. If the acute angle between the hour hand and the minute hand of the clock measures $x$ degrees, find $x$. [img]https://cdn.artofproblemsolving.com/attachments/b/a/a18b089ae016b15580ec464c3e813d5cb57569.png[/img] [b]p4.[/b] Point $P$ is located on segment $AC$ of square $ABCD$ with side length $10$ such that $AP >CP$. If the area of quadrilateral $ABPD$ is $70$, what is the area of $\vartriangle PBD$? [b]p5.[/b] Andrew always sweetens his tea with sugar, and he likes a $1 : 7$ sugar-to-unsweetened tea ratio. One day, he makes a $100$ ml cup of unsweetened tea but realizes that he has run out of sugar. Andrew decides to borrow his sister's jug of pre-made SUPERSWEET tea, which has a $1 : 2$ sugar-to-unsweetened tea ratio. How much SUPERSWEET tea, in ml,does Andrew need to add to his unsweetened tea so that the resulting tea is his desired sweetness? [b]p6.[/b] Jeremy the architect has built a railroad track across the equator of his spherical home planet which has a radius of exactly $2020$ meters. He wants to raise the entire track $6$ meters off the ground, everywhere around the planet. In order to do this, he must buymore track, which comes from his supplier in bundles of $2$ meters. What is the minimum number of bundles he must purchase? Assume the railroad track was originally built on the ground. [b]p7.[/b] Mr. DoBa writes the numbers $1, 2, 3,..., 20$ on the board. Will then walks up to the board, chooses two of the numbers, and erases them from the board. Mr. DoBa remarks that the average of the remaining $18$ numbers is exactly $11$. What is the maximum possible value of the larger of the two numbers that Will erased? [b]p8.[/b] Nathan is thinking of a number. His number happens to be the smallest positive integer such that if Nathan doubles his number, the result is a perfect square, and if Nathan triples his number, the result is a perfect cube. What is Nathan's number? [b]p9.[/b] Let $S$ be the set of positive integers whose digits are in strictly increasing order when read from left to right. For example, $1$, $24$, and $369$ are all elements of $S$, while $20$ and $667$ are not. If the elements of $S$ are written in increasing order, what is the $100$th number written? [b]p10.[/b] Find the largest prime factor of the expression $2^{20} + 2^{16} + 2^{12} + 2^{8} + 2^{4} + 1$. [b]p11.[/b] Christina writes down all the numbers from $1$ to $2020$, inclusive, on a whiteboard. What is the sum of all the digits that she wrote down? [b]p12.[/b] Triangle $ABC$ has side lengths $AB = AC = 10$ and $BC = 16$. Let $M$ and $N$ be the midpoints of segments $BC$ and $CA$, respectively. There exists a point $P \ne A$ on segment $AM$ such that $2PN = PC$. What is the area of $\vartriangle PBC$? [b]p13.[/b] Consider the polynomial $$P(x) = x^4 + 3x^3 + 5x^2 + 7x + 9.$$ Let its four roots be $a, b, c, d$. Evaluate the expression $$(a + b + c)(a + b + d)(a + c + d)(b + c + d).$$ [b]p14.[/b] Consider the system of equations $$|y - 1| = 4 -|x - 1|$$ $$|y| =\sqrt{|k - x|}.$$ Find the largest $k$ for which this system has a solution for real values $x$ and $y$. [b]p16.[/b] Let $T_n = 1 + 2 + ... + n$ denote the $n$th triangular number. Find the number of positive integers $n$ less than $100$ such that $n$ and $T_n$ have the same number of positive integer factors. [b]p17.[/b] Let $ABCD$ be a square, and let $P$ be a point inside it such that $PA = 4$, $PB = 2$, and $PC = 2\sqrt2$. What is the area of $ABCD$? [b]p18.[/b] The Fibonacci sequence $\{F_n\}$ is defined as $F_0 = 0$, $F_1 = 1$, and $F_{n+2}= F_{n+1} + F_n$ for all integers $n \ge 0$. Let $$ S =\dfrac{1}{F_6 + \frac{1}{F_6}}+\dfrac{1}{F_8 + \frac{1}{F_8}}+\dfrac{1}{F_{10} +\frac{1}{F_{10}}}+\dfrac{1}{F_{12} + \frac{1}{F_{12}}}+ ... $$ Compute $420S$. [b]p19.[/b] Let $ABCD$ be a square with side length $5$. Point $P$ is located inside the square such that the distances from $P$ to $AB$ and $AD$ are $1$ and $2$ respectively. A point $T$ is selected uniformly at random inside $ABCD$. Let $p$ be the probability that quadrilaterals $APCT$ and $BPDT$ are both not self-intersecting and have areas that add to no more than $10$. If $p$ can be expressed in the form $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$, find $m + n$. Note: A quadrilateral is self-intersecting if any two of its edges cross. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In the plane you have $2018$ points between which there are not three on the same line. These points are colored with $30$ colors so that no two colors have the same number of points. All triangles are formed with their three vertices of different colors. Determine the number of points for each of the $30$ colors so that the total number of triangles with the three vertices of different colors is as large as possible.

We have $ n \geq 2$ lamps $ L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $ L_{i}$ and its neighbours (only one neighbour for $ i \equal{} 1$ or $ i \equal{} n$, two neighbours for other $ i$) are in the same state, then $ L_{i}$ is switched off; – otherwise, $ L_{i}$ is switched on. Initially all the lamps are off except the leftmost one which is on. $ (a)$ Prove that there are infinitely many integers $ n$ for which all the lamps will eventually be off. $ (b)$ Prove that there are infinitely many integers $ n$ for which the lamps will never be all off.

A finite non-empty set of integers is called $3$-[i]good[/i] if the sum of its elements is divisible by $3$. Find the number of $3$-good subsets of $\{0,1,2,\ldots,9\}$.

[u]Round 6[/u] [b]p16.[/b] Let $ABC$ be a triangle with $AB = 3$, $BC = 4$, and $CA = 5$. There exist two possible points $X$ on $CA$ such that if $Y$ and $Z$ are the feet of the perpendiculars from $X$ to $AB$ and $BC,$ respectively, then the area of triangle $XY Z$ is $1$. If the distance between those two possible points can be expressed as $\frac{a\sqrt{b}}{c}$ for positive integers $a$, $b$, and $c$ with $b$ squarefree and $gcd(a, c) = 1$, then find $a +b+ c$. [b]p17.[/b] Let $f(n)$ be the number of orderings of $1,2, ... ,n$ such that each number is as most twice the number preceding it. Find the number of integers $k$ between $1$ and $50$, inclusive, such that $f (k)$ is a perfect square. [b]p18.[/b] Suppose that $f$ is a function on the positive integers such that $f(p) = p$ for any prime p, and that $f (xy) = f(x) + f(y)$ for any positive integers $x$ and $y$. Define $g(n) = \sum_{k|n} f (k)$; that is, $g(n)$ is the sum of all $f(k)$ such that $k$ is a factor of $n$. For example, $g(6) = f(1) + 1(2) + f(3) + f(6)$. Find the sum of all composite $n$ between $50$ and $100$, inclusive, such that $g(n) = n$. [u]Round 7[/u] [b]p19.[/b] AJ is standing in the center of an equilateral triangle with vertices labelled $A$, $B$, and $C$. They begin by moving to one of the vertices and recording its label; afterwards, each minute, they move to a different vertex and record its label. Suppose that they record $21$ labels in total, including the initial one. Find the number of distinct possible ordered triples $(a, b, c)$, where a is the number of $A$'s they recorded, b is the number of $B$'s they recorded, and c is the number of $C$'s they recorded. [b]p20.[/b] Let $S = \sum_{n=1}^{\infty} (1- \{(2 + \sqrt3)^n\})$, where $\{x\} = x - \lfloor x\rfloor$ , the fractional part of $x$. If $S =\frac{\sqrt{a} -b}{c}$ for positive integers $a, b, c$ with $a $ squarefree, find $a + b + c$. [b]p21.[/b] Misaka likes coloring. For each square of a $1\times 8$ grid, she flips a fair coin and colors in the square if it lands on heads. Afterwards, Misaka places as many $1 \times 2$ dominos on the grid as possible such that both parts of each domino lie on uncolored squares and no dominos overlap. Given that the expected number of dominos that she places can be written as $\frac{a}{b}$, for positive integers $a$ and $b$ with $gcd(a, b) = 1$, find $a + b$. PS. You should use hide for answers. Rounds 1-3 have been posted [url=https://artofproblemsolving.com/community/c4h3131401p28368159]here [/url] and 4-5 [url=https://artofproblemsolving.com/community/c4h3131422p28368457]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In the space there are 8 points that no four of them are in the plane. 17 of the connecting segments are coloured blue and the other segments are to be coloured red. Prove that this colouring will create at least four triangles. Prove also that four cannot be subsituted by five. Remark: Blue triangles are those triangles whose three edges are coloured blue.

Find all integers $n \ge 3$ with the following property: it is possible to assign pairwise different positive integers to the vertices of an $n$-gonal prism in such a way that vertices with labels $a$ and $b$ are connected by an edge if and only if $a | b$ or $b | a$. Poland

Let $p$ be an odd prime, and put $N=\frac{1}{4} (p^3 -p) -1.$ The numbers $1,2, \dots, N$ are painted arbitrarily in two colors, red and blue. For any positive integer $n \leqslant N,$ denote $r(n)$ the fraction of integers $\{ 1,2, \dots, n \}$ that are red. Prove that there exists a positive integer $a \in \{ 1,2, \dots, p-1\}$ such that $r(n) \neq a/p$ for all $n = 1,2, \dots , N.$ [I]Netherlands[/i]

The sequence $n_1<n_2<\ldots < n_k$ consists of all positive integers $n$ for which in a square $n \times n$ one can mark $10$ cells such that in any square $3 \times 3$ an odd amount of cells are marked. Find $n_{k-2}$.

Let $n$ be a positive with $n\geq 3$. Consider a board of $n \times n$ boxes. In each step taken the colors of the $5$ boxes that make up the figure bellow change color (black boxes change to white and white boxes change to black) The figure can be rotated $90°, 180°$ or $270°$. Firstly, all the boxes are white.Determine for what values of $n$ it can be achieved, through a series of steps, that all the squares on the board are black.

A $7\times 7$ square is cut into pieces following types: [img]https://cdn.artofproblemsolving.com/attachments/e/d/458b252c719946062b655340cbe8415d1bdaf9.png[/img] Show that exactly one of the pieces is of type (b). [img]https://cdn.artofproblemsolving.com/attachments/4/9/f3dd0e13fed9838969335c82f5fe866edc83e8.png[/img]

Let $\Gamma = \{\varepsilon,0,00,\ldots\}$ be the set of all finite strings consisting of only zeroes. We consider $\textit{six-state unary DFAs}$ $D = (F,q_0,\delta)$ where $F$ is a subset of $Q = \{1,2,3,4,5,6\}$, not necessarily strict and possibly empty; $q_0\in Q$ is some $\textit{start state}$; and $\delta: Q\rightarrow Q$ is the $\textit{transition function}$. For each such DFA $D$, we associate a set $F_D\subseteq\Gamma$ as the set of all strings $w\in\Gamma$ such that \[\underbrace{\delta(\cdots(\delta(q_0))\cdots)}_{|w|\text{ applications}}\in F,\] We say a set $\mathcal D$ of DFAs is $\textit{diverse}$ if for all $D_1,D_2\in\mathcal D$ we have $F_{D_1}\neq F_{D_2}$. What is the maximum size of a diverse set?

A $k$-coloring of a graph $G$ is a coloring of its vertices using $k$ possible colors such that the end points of any edge have different colors. We say a graph $G$ is uniquely $k$-colorable if one hand it has a $k$-coloring, on the other hand there do not exist vertices $u$ and $v$ such that $u$ and $v$ have the same color in one $k$-coloring and $u$ and $v$ have different colors in another $k$-coloring. Prove that if a graph $G$ with $n$ vertices $(n \ge 3)$ is uniquely $3$-colorable, then it has at least $2n-3$ edges.

Given an integer $n$ greater than $1$, suppose $x_1,x_2,\ldots,x_n$ are integers such that none of them is divisible by $n$, and neither their sum. Prove that there exists atleast $n-1$ non-empty subsets $\mathcal I\subseteq \{1,\ldots, n\}$ such that $\sum_{i\in\mathcal I}x_i$ is divisible by $n$

A pile of cards, numbered with $1$, $2$, ..., $n$, is being shuffled. Afterwards, the following operation is repeatedly performed: If the uppermost card of the pile has the number $k$, then we reverse the order of the $k$ uppermost cards. Prove that, after finitely many executions of this operation, the card with the number $1$ will become the uppermost card of the pile.

In chess tournament participates $n$ participants ($n >1$). In tournament each of participants plays with each other exactly $1$ game. For each game participant have $1$ point if he wins game, $0,5$ point if game is drow and $0$ points if he lose game. If after ending of tournament participant have at least $ 75 % $ of maximum possible points he called $winner$ $of$ $tournament$. Find maximum possible numbers of $winners$ $of$ $tournament$.

There are many $a\times b$ rectangular cardboard pieces ($a,b\in\mathbb{N}$ such that $a<b$). It is given that by putting such pieces together without overlapping one can make $49\times 51$ rectangle, and $99\times 101$ rectangle. Can one uniquely determine $a,b$ from this?