There are $8$ cities in a certain kingdom. The king wants to have a system of roads constructed so that one can go along those roads from any city to any other one without going through more than one intermediate city and so that no more than $k$ roads go out of any city. For what values of $k$ is this possible? (D. Fomin, Leningrad)

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

The vertices of a regular $2012$-gon are labeled $A_1,A_2,\ldots, A_{2012}$ in some order. It is known that if $k+\ell$ and $m+n$ leave the same remainder when divided by $2012$, then the chords $A_kA_{\ell}$ and $A_mA_n$ have no common points. Vasya walks around the polygon and sees that the first two vertices are labeled $A_1$ and $A_4$. How is the tenth vertex labeled? [i]Proposed by A. Golovanov[/i]

[b]p1.[/b] If $$ \begin{cases} a^2 + b^2 + c^2 = 1000 \\ (a + b + c)^2 = 100 \\ ab + bc = 10 \end{cases}$$ what is $ac$? [b]p2.[/b] If a and b are real numbers such that $a \ne 0$ and the numbers $1$, $a + b$, and $a$ are, in some order, the numbers $0$, $\frac{b}{a}$ , and $b$, what is $b - a$? [b]p3.[/b] Of the first $120$ natural numbers, how many are divisible by at least one of $3$, $4$, $5$, $12$, $15$, $20$, and $60$? [b]p4.[/b] For positive real numbers $a$, let $p_a$ and $q_a$ be the maximum and minimum values, respectively, of $\log_a(x)$ for $a \le x \le 2a$. If $p_a - q_a = \frac12$ , what is $a$? [b]p5.[/b] Let $ABC$ be an acute triangle and let $a$, $b$, and $c$ be the sides opposite the vertices $A$, $B$, and $C$, respectively. If $a = 2b \sin A$, what is the measure of angle $B$? [b]p6.[/b] How many ordered triples $(x, y, z)$ of positive integers satisfy the equation $$x^3 + 2y^3 + 4z^3 = 9?$$ [b]p7.[/b] Joe has invented a robot that travels along the sides of a regular octagon. The robot starts at a vertex of the octagon and every minute chooses one of two directions (clockwise or counterclockwise) with equal probability and moves to the next vertex in that direction. What is the probability that after $8$ minutes the robot is directly opposite the vertex it started from? [b]p8.[/b] Find the nonnegative integer $n$ such that when $$\left(x^2 -\frac{1}{x}\right)^n$$ is completely expanded the constant coefficient is $15$. [b]p9.[/b] For each positive integer $k$, let $$f_k(x) = \frac{kx + 9}{x + 3}.$$ Compute $$f_1 \circ f_2\circ ... \circ f_{13}(2).$$ [b]p10.[/b] Exactly one of the following five integers cannot be written in the form $x^2 + y^2 + 5z^2$, where $x$, $y$, and $z$ are integers. Which one is it? $$2003, 2004, 2005, 2006, 2007$$ [b]p11.[/b] Suppose that two circles $C_1$ and $C_2$ intersect at two distinct points $M$ and $N$. Suppose that $P$ is a point on the line $MN$ that is outside of both $C_1$ and $C_2$. Let $A$ and $B$ be the two distinct points on $C_1$ such that AP and BP are each tangent to $C_1$ and $B$ is inside $C_2$. Similarly, let $D$ and $E$ be the two distinct points on $C_2$ such that $DP$ and $EP$ are each tangent to $C_2$ and $D$ is inside $C_1$. If $AB = \frac{5\sqrt2}{2}$ , $AD = 2$, $BD = 2$, $EB = 1$, and $ED =\sqrt2$, find $AE$. [b]p12.[/b] How many ordered pairs $(x, y)$ of positive integers satisfy the following equation? $$\sqrt{x} +\sqrt{y} =\sqrt{2007}.$$ [b]p13.[/b] The sides $BC$, $CA$, and $CB$ of triangle $ABC$ have midpoints $K$, $L$, and $M$, respectively. If $$AB^2 + BC^2 + CA^2 = 200,$$ what is $AK^2 + BL^2 + CM^2$? [b]p14.[/b] Let $x$ and $y$ be real numbers that satisfy: $$x + \frac{4}{x}= y +\frac{4}{y}=\frac{20}{xy}.$$ Compute the maximum value of $|x - y|$. [b]p15.[/b] $30$ math meet teams receive different scores which are then shuffled around to lend an aura of mystery to the grading. What is the probability that no team receives their own score? Express your answer as a decimal accurate to the nearest hundredth. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Sofía has many boxes where she keeps candies. Every morning, she chooses two of these boxes and places one candy in each. However, each night, a thief selects one box and steals all the candies inside it. Sofía dreams of waking up one day and finding a box with 2024 candies. Prove that Sofía can always fulfill her dream if she has enough boxes.

We have a white table with $2$ rows and $5$ columns , and would like to colour all cells of the table according to the following rules: $\bullet$ We must colour the cell in the bottom left corner first. $\bullet$ After that, we can only colour a cell if some adjacent cell has already been coloured. (Two cells are adjacent if they share an edge.) How many different orders are there for colouring all $10$ squares (following these rules)?

Is it possible to colour all integers greater than $1{}$ in three colours (each integer in one colour, all three colours must be used) so that the colour of the product of any two differently coloured numbers is different from the colour of each of the factors?

Let $n \geq 3$ be a positive integer. Find the maximum number of diagonals in a regular $n$-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

Navi and Ozna are playing a game where Ozna starts first and the two take turn making moves. A positive integer is written on the waord. A move is to (i) subtract any positive integer at most 2015 from it or (ii) given that the integer on the board is divisible by $2014$, divide by $2014$. The first person to make the integer $0$ wins. To make Navi's condition worse, Ozna gets to pick integers $a$ and $b$, $a\ge 2015$ such that all numbers of the form $an+b$ will not be the starting integer, where $n$ is any positive integer. Find the minimum number of starting integer where Navi wins.

In a classroom there are $20$ rows of $22$ desks each $(22$ desks have noone in front of them). The $440$ contestants of a certain regional math contest are going to sit at the desks. Before the exam, the organizers left some amount of sweets on each desk, which amount can be any positive integer. When the students go into the room, just before sitting down they look at the desk behind them, the one on the left and the one diagonally opposite to the right of theirs, thus seeing how many sweets each one has; if there is no desk in any of these directions, they simply ignore that position. Then they sit and watch their own sweets. A student gets angry if any of the desks he saw has more than one candy more than his. The organizers managed to distribute the sweets in such a way that no student gets angry. Prove that there are $8$ students with the same amount of sweets.

A finite sequence $x_1,\dots,x_r$ of positive integers is a [i]palindrome[/i] if $x_i=x_{r+1-i}$ for all integers $1 \le i \le r$. Let $a_1,a_2,\dots$ be an infinite sequence of positive integers. For a positive integer $j \ge 2$, denote by $a[j]$ the finite subsequence $a_1,a_2,\dots,a_{j-1}$. Suppose that there exists a strictly increasing infinite sequence $b_1,b_2,\dots$ of positive integers such that for every positive integer $n$, the subsequence $a[b_n]$ is a palindrome and $b_{n+2} \le b_{n+1}+b_n$. Prove that there exists a positive integer $T$ such that $a_i=a_{i+T}$ for every positive integer $i$.

There is a grid of height $2$ stretching infinitely in one direction. Between any two edge-adjacent cells of the grid, there is a door that is locked with probability $\frac12$ independent of all other doors. Philip starts in a corner of the grid (in the starred cell). Compute the expected number of cells that Philip can reach, assuming he can only travel between cells if the door between them is unlocked. [img]https://cdn.artofproblemsolving.com/attachments/f/d/fbf9998270e16055f02539bb532b1577a6f92a.png[/img]

Emperor Zorg wishes to found a colony on a new planet. Each of the $n$ cities that he will establish there will have to speak exactly one of the Empire's $2020$ official languages. Some towns in the colony will be connected by a direct air link, each link can be taken in both directions. The emperor fixed the cost of the ticket for each connection to $1$ galactic credit. He wishes that, given any two cities speaking the same language, it is always possible to travel from one to the other via these air links, and that the cheapest trip between these two cities costs exactly $2020$ galactic credits. For what values of $n$ can Emperor Zorg fulfill his dream?

Consider $13$ weights of integer mass (in grams). It is known that any $6$ of them may be placed onto two pans of a balance achieving equilibrium. Prove that all the weights are of equal mass.

For an integer $n \geq 5,$ two players play the following game on a regular $n$-gon. Initially, three consecutive vertices are chosen, and one counter is placed on each. A move consists of one player sliding one counter along any number of edges to another vertex of the $n$-gon without jumping over another counter. A move is legal if the area of the triangle formed by the counters is strictly greater after the move than before. The players take turns to make legal moves, and if a player cannot make a legal move, that player loses. For which values of $n$ does the player making the first move have a winning strategy?

Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.

For a positive integer $k\ge 2$ define $\mathcal{T}_k=\{(x,y)\mid x,y=0,1,\ldots, k-1\}$ to be a collection of $k^2$ lattice points on the cartesian coordinate plane. Let $d_1(k)>d_2(k)>\cdots$ be the decreasing sequence of the distinct distances between any two points in $T_k$. Suppose $S_i(k)$ be the number of distances equal to $d_i(k)$. Prove that for any three positive integers $m>n>i$ we have $S_i(m)=S_i(n)$.

There is a set of $ n$ coins with distinct integer weights $ w_1, w_2, \ldots , w_n$. It is known that if any coin with weight $ w_k$, where $ 1 \leq k \leq n$, is removed from the set, the remaining coins can be split into two groups of the same weight. (The number of coins in the two groups can be different.) Find all $ n$ for which such a set of coins exists.

[b]p1.[/b] Thirty players participate in a chess tournament. Every player plays one game with every other player. What maximal number of players can get exactly $5$ points? (any game adds $1$ point to the winner’s score, $0$ points to a loser’s score, in the case of a draw each player obtains $1/2$ point.) [b]p2.[/b] A father and his son returned from a fishing trip. To make their catches equal the father gave to his son some of his fish. If, instead, the son had given his father the same number of fish, then father would have had twice as many fish as his son. What percent more is the father's catch more than his son's? [b]p3.[/b] What is the maximal number of pieces of two shapes, [img]https://cdn.artofproblemsolving.com/attachments/a/5/6c567cf6a04b0aa9e998dbae3803b6eeb24a35.png[/img] and [img]https://cdn.artofproblemsolving.com/attachments/8/a/7a7754d0f2517c93c5bb931fb7b5ae8f5e3217.png[/img], that can be used to tile a $7\times 7$ square? [b]p4.[/b] Six shooters participate in a shooting competition. Every participant has $5$ shots. Each shot adds from 1 to $10$ points to shooter’s score. Every person can score totally for all five shots from $5$ to $50$ points. Each participant gets $7$ points for at least one of his shots. The scores of all participants are different. We enumerate the shooters $1$ to $6$ according to their scores, the person with maximal score obtains number $1$, the next one obtains number $2$, the person with minimal score obtains number $6$. What score does obtain the participant number 3? The total number of all obtained points is $264$. [b]p5.[/b] There are $2014$ stones in a pile. Two players play the following game. First, player $A$ takes some number of stones (from $1$ to $30$) from the pile, then player B takes $1$ or $2$ stones, then player $A$ takes $2$ or $3$ stones, then player $B$ takes $3$ or $4$ stones, then player A takes $4$ or $5$ stones, etc. The player who gets the last stone is the winner. If no player gets the last stone (there is at least one stone in the pile but the next move is not allowed) then the game results in a draw. Who wins the game using the right strategy? PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[u]Round 9[/u] [b]p25.[/b] Maisy the Bear is at the origin of the Cartesian Plane. WhenMaisy is on the point $(m,n)$ then it can jump to either $(m,n +1)$ or $(m+1,n)$. Let $L(x, y)$ be the number of pathsMaisy can take to reach the point $(x, y)$. The sum of $L(x, y)$ over all lattice points $(x, y)$ with both coordinates between $0$ and $2020$, inclusive, can be written as ${2k \choose k} - j$ for a minimum positive integer k and corresponding positive integer $j$ . Find $k + j$ . [b]p26.[/b] A circle with center $O$ and radius $2$ and a circle with center $P$ and radius $3$ are externally tangent at $A$. Points $B$ and $C$ are on the circle with center $O$ such that $\vartriangle ABC$ is equilateral. Segment $AB$ extends past B to point $D$ and $AC$ extends past $C$ to point $E$ such that $BD = CE =\sqrt3$. A line through $D$ is tangent to circle $P$ at $F$. The value of $EF^2$ can be expressed as $\frac{a+b\sqrt{c}}{d}$ where $a$, $b$, $c$, and $d$ are integers, c is squarefree, and $gcd(a,b,d) = 1$. Find $a +b +c +d$. [b]p27.[/b] Find the number of trailing zeroes at the end of $$\sum^{2021}_{i=1}(2021^i -1) = (2021^1 -1)...(2021^{2021}-1).$$ [u]Round 10[/u] [b]p28.[/b] Points $A, B, C, P$, and $D$ lie on circle ω in that order. Let $AC$ and $BD$ intersect at $I$ . Given that $PI = PC = PD$, $\angle DAB = 137^o$, and $\angle ABC = 109^o$, find the measure of $\angle BIC$ in degrees. [b]p29.[/b] Find the sum of all positive integers $n < 2021$ such that when ${d_1,d_2,... ,d_k}$ are the positive integer factors of $n$, then $$\left( \sum^{k}_{i=1}d_i \right) \left( \sum^{k}_{i=1} \frac{1}{d_i} \right)= r^2$$ for some rational number $r$ . [b]p30.[/b] Let $a, b, c, d$ and $e$ be positive real numbers. Define the function $f (x, y) = \frac{x}{y}+\frac{y}{x}$ for all positive real numbers. Given that $f (a,b) = 7$, $f (b,c) = 5$, $f (c,d) = 3$, and $f (d,e) = 2$, find the sum of all possible values of $f (e,a)$. [u]Round 11[/u] [b]p31.[/b] There exist $100$ (not necessarily distinct) complex numbers $r_1, r_2,..., r_{100}$ such that for any positive integer $1 \le k \le 100$, we have that $P(r_k ) = 0$ where the polynomial $P$ is defined as $$P(x) = \sum^{101}_{i=1}i \cdot x^{101-i} = x^{100} +2x^{99} +3x^{98} +...+99x^2 +100x +101.$$ Find the value of $$\prod^{100}_{j=1} (r^2_j+1) = (r^2_1 +1)(r^2_2 +1)...(r^2_{100} +1).$$ [b]p32.[/b] Let $BT$ be the diameter of a circle $\omega_1$, and $AT$ be a tangent of $\omega_1$. Line $AB$ intersects $\omega_1$ at $C$, and $\vartriangle ACT$ has circumcircle $\omega_2$. Points $P$ and $S$ exist such that $PA$ and $PC$ are tangent to $\omega_2$ and $SB = BT = 20$. Given that $AT = 15$, the length of $PS$ can be written as $\frac{a\sqrt{b}}{c}$ , where $a$, $b$, and $c$ are positive integers, $b$ is squarefree, and $gcd(a,b) = 1$. Find $a +b +c$. [b]p33.[/b] There are a hundred students in math team. Each pair of students are either mutually friends or mutually enemies. It is given that if any three students are chosen, then they are not all mutually friends. The maximum possible number of ways to choose four students such that it is possible to label them $A, B, C$, and $D$ such that $A$ and $B$ are friends, $B$ and $C$ are friends, $C$ and $D$ are friends, and D and A are friends can be expressed as $n^4$. Find $n$. [u]Round 12[/u] [b]p34.[/b] Let $\{p_i\}$ be the prime numbers, such that $p_1 = 2, p_2 = 3, p_3 = 5, ...$ For each $i$ , let $q_i$ be the nearest perfect square to $p_i$ . Estimate $\sum^{2021}_{i=1}|p_i=q_i |$. If the correct answer is $A$ and your answer is $E$, your score will be $\left \lfloor 30 \cdot \max - \left(0,1-5 \cdot \left| \log_{10} \frac{A}{E} \right| \right)\right \rfloor.$ [b]p35.[/b] Estimate the number of digits of $(2021!)^{2021}$. If the correct answer is $A$ and your answer is $E$, your score will be $\left \lfloor 15 \cdot \max \left(0,2- \cdot \left| \log_{10} \frac{A}{E} \right| \right) \right \rfloor.$ [b]p36.[/b] Pick a positive integer between$ 1$ and $1000$, inclusive. If your answer is $E$ and a quarter of the mean of all the responses to this problem is $A$, your score will be $$ \lfloor \max \left(0,30- |A-E|, 2-|E-1000| \right) \rfloor.$$ Note that if you pick $1000$, you will automatically get $2$ points. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h3166489p28814241]here [/url] and 5-8 [url=https://artofproblemsolving.com/community/c3h3166494p28814284]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[b]p1.[/b] Consider a right triangle with legs of lengths $a$ and $b$ and hypotenuse of length $c$ such that the perimeter of the right triangle is numerically (ignoring units) equal to its area. Prove that there is only one possible value of $a + b - c$, and determine that value. [b]p2.[/b] Last August, Jennifer McLoud-Mann, along with her husband Casey Mann and an undergraduate David Von Derau at the University of Washington, Bothell, discovered a new tiling pattern of the plane with a pentagon. This is the fifteenth pattern of using a pentagon to cover the plane with no gaps or overlaps. It is unknown whether other pentagons tile the plane, or even if the number of patterns is finite. Below is a portion of this new tiling pattern. [img]https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvOS8xLzM4M2RjZDEzZTliYTlhYTJkZDU4YTA4ZGMwMTA0MzA5ODk1NjI0LnBuZw==&rn=bW1wYyAyMDE1LnBuZw==[/img] Determine the five angles (in degrees) of the pentagon $ABCDE$ used in this tiling. Explain your reasoning, and give the values you determine for the angles at the bottom. [b]p3.[/b] Let $f(x) =\sqrt{2019 + 4\sqrt{2015}} +\sqrt{2015} x$. Find all rational numbers $x$ such that $f(x)$ is a rational number. [b]p4.[/b] Alice has a whiteboard and a blackboard. The whiteboard has two positive integers on it, and the blackboard is initially blank. Alice repeats the following process. $\bullet$ Let the numbers on the whiteboard be $a$ and $b$, with $a \le b$. $\bullet$ Write $a^2$ on the blackboard. $\bullet$ Erase $b$ from the whiteboard and replace it with $b - a$. For example, if the whiteboard began with 5 and 8, Alice first writes $25$ on the blackboard and changes the whiteboard to $5$ and $3$. Her next move is to write $9$ on the blackboard and change the whiteboard to $2$ and $3$. Alice stops when one of the numbers on the whiteboard is 0. At this point the sum of the numbers on the blackboard is $2015$. a. If one of the starting numbers is $1$, what is the other? b. What are all possible starting pairs of numbers? [b]p5.[/b] Professor Beatrix Quirky has many multi-volume sets of books on her shelves. When she places a numbered set of $n$ books on her shelves, she doesn’t necessarily place them in order with book $1$ on the left and book $n$ on the right. Any volume can be placed at the far left. The only rule is that, except the leftmost volume, each volume must have a volume somewhere to its left numbered either one more or one less. For example, with a series of six volumes, Professor Quirky could place them in the order $123456$, or $324561$, or $564321$, but not $321564$ (because neither $4$ nor $6$ is to the left of $5$). Let’s call a sequence of numbers a [i]quirky [/i] sequence of length $n$ if: 1. the sequence contains each of the numbers from $1$ to $n$, once each, and 2. if $k$ is not the first term of the sequence, then either $k + 1$ or $k - 1$ occurs somewhere before $k$ in the sequence. Let $q_n$ be the number of quirky sequences of length $n$. For example, $q_3 = 4$ since the quirky sequences of length $3$ are $123$, $213$, $231$, and $321$. a. List all quirky sequences of length $4$. b. Find an explicit formula for $q_n$. Prove that your formula is correct. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Does the set $\{1,2,3,...,3000\}$ contain a subset $ A$ consisting of 2000 numbers that $x\in A$ implies $2x \notin A$ ?!! :?:

Let $T$ be the set of all positive integer divisors of $2004_{100}$. What is the largest possible number of elements that a subset $S$ of $T$ can have if no element of $S$ is an integer multiple of any other element of $S$?

Define a sequence $ < a_n > _{n\geq0}$ by $ a_0 \equal{} 0$, $ a_1 \equal{} 1$ and \[ a_n \equal{} 2a_{n \minus{} 1} \plus{} a_{n \minus{} 2},\] for $ n\geq2.$ $ (a)$ For every $ m > 0$ and $ 0\leq j\leq m,$ prove that $ 2a_m$ divides $ a_{m \plus{} j} \plus{} ( \minus{} 1)^ja_{m \minus{} j}$. $ (b)$ Suppose $ 2^k$ divides $ n$ for some natural numbers $ n$ and $ k$. Prove that $ 2^k$ divides $ a_n.$

Find all integers $n > 1$ for which it is possible to fill the cells of an $n \times n$ grid with the integers from $1$ to $n^2$, without repetition, such that the average of the $n$ numbers in each row and each column is an integer.