There are $5$ vertices labelled $1,2,3,4,5$. For any two pairs of vertices $u, v$, the edge $uv$ is drawn with probability $1/2$. If the probability that the resulting graph is a tree is given by $\dfrac{p}{q}$ where $p, q$ are coprime, then find the value of $q^{1/10} + p$.

For a given number $\alpha{}$ let $f_\alpha$ be a function defined as \[f_\alpha(x)=\left\lfloor\alpha x+\frac{1}{2}\right\rfloor.\]Let $\alpha>1$ and $\beta=1/\alpha$. Prove that for any natural $n{}$ the relation $f_\beta(f_\alpha(n))=n$ holds. [i]Proposed by I. Dorofeev[/i]

[b]p1.[/b] Let $X,Y ,Z$ be nonzero real numbers such that the quadratic function $X t^2 - Y t + Z = 0$ has the unique root $t = Y$ . Find $X$. [b]p2.[/b] Let $ABCD$ be a kite with $AB = BC = 1$ and $CD = AD =\sqrt2$. Given that $BD =\sqrt5$, find $AC$. [b]p3.[/b] Find the number of integers $n$ such that $n -2016$ divides $n^2 -2016$. An integer $a$ divides an integer $b$ if there exists a unique integer $k$ such that $ak = b$. [b]p4.[/b] The points $A(-16, 256)$ and $B(20, 400)$ lie on the parabola $y = x^2$ . There exists a point $C(a,a^2)$ on the parabola $y = x^2$ such that there exists a point $D$ on the parabola $y = -x^2$ so that $ACBD$ is a parallelogram. Find $a$. [b]p5.[/b] Figure $F_0$ is a unit square. To create figure $F_1$, divide each side of the square into equal fifths and add two new squares with sidelength $\frac15$ to each side, with one of their sides on one of the sides of the larger square. To create figure $F_{k+1}$ from $F_k$ , repeat this same process for each open side of the smallest squares created in $F_n$. Let $A_n$ be the area of $F_n$. Find $\lim_{n\to \infty} A_n$. [img]https://cdn.artofproblemsolving.com/attachments/8/9/85b764acba2a548ecc61e9ffc29aacf24b4647.png[/img] [b]p6.[/b] For a prime $p$, let $S_p$ be the set of nonnegative integers $n$ less than $p$ for which there exists a nonnegative integer $k$ such that $2016^k -n$ is divisible by $p$. Find the sum of all $p$ for which $p$ does not divide the sum of the elements of $S_p$ . [b]p7. [/b] Trapezoid $ABCD$ has $AB \parallel CD$ and $AD = AB = BC$. Unit circles $\gamma$ and $\omega$ are inscribed in the trapezoid such that circle $\gamma$ is tangent to $CD$, $AB$, and $AD$, and circle $\omega$ is tangent to $CD$, $AB$, and $BC$. If circles $\gamma$ and $\omega$ are externally tangent to each other, find $AB$. [b]p8.[/b] Let $x, y, z$ be real numbers such that $(x+y)^2+(y+z)^2+(z+x)^2 = 1$. Over all triples $(x, y, z)$, find the maximum possible value of $y -z$. [b]p9.[/b] Triangle $\vartriangle ABC$ has sidelengths $AB = 13$, $BC = 14$, and $CA = 15$. Let $P$ be a point on segment $BC$ such that $\frac{BP}{CP} = 3$, and let $I_1$ and $I_2$ be the incenters of triangles $\vartriangle ABP$ and $\vartriangle ACP$. Suppose that the circumcircle of $\vartriangle I_1PI_2$ intersects segment $AP$ for a second time at a point $X \ne P$. Find the length of segment $AX$. [b]p10.[/b] For $1 \le i \le 9$, let Ai be the answer to problem i from this section. Let $(i_1,i_2,... ,i_9)$ be a permutation of $(1, 2,... , 9)$ such that $A_{i_1} < A_{i_2} < ... < A_{i_9}$. For each $i_j$ , put the number $i_j$ in the box which is in the $j$th row from the top and the $j$th column from the left of the $9\times 9$ grid in the bonus section of the answer sheet. Then, fill in the rest of the squares with digits $1, 2,... , 9$ such that $\bullet$ each bolded $ 3\times 3$ grid contains exactly one of each digit from $ 1$ to $9$, $\bullet$ each row of the $9\times 9$ grid contains exactly one of each digit from $ 1$ to $9$, and $\bullet$ each column of the $9\times 9$ grid contains exactly one of each digit from $ 1$ to $9$. PS. You had better use hide for answers.

(a) Let $u$, $v$, and $w$ be the real solutions to the equation $x^3 - 7x + 7 = 0$. Show that there exists a quadratic polynomial $f$ with rational coefficients such that $u = f(v)$, $v = f(w)$, and $w = f(u)$. (b) Let $u$, $v$, and $w$ be the real solutions to the equation $x^3 -7x+4 = 0$. Show that there does not exist a quadratic polynomial $f $with rational coefficients such that $u = f(v)$, $v = f(w)$, and $w = f(u)$.

Prove that $\frac{1}{x+y+1}-\frac{1}{(x+1)(y+1)}<\frac{1}{11}$ for all positive $x$ and $y$.

Let $P(x)$ be a polynomial of degree $n$ with real coefficients and let $a\geq 3$. Prove that \[\max_{0\leq j \leq n+1}\left | a^j-P(j) \right |\geq 1\]

a) Let $x$ be a positive real number. Show that $x + 1 / x\ge 2$. b) Let $n\ge 2$ be a positive integer and let $x _1,y_1,x_2,y_2,...,x_n,y_n$ be positive real numbers such that $x _1+x _2+...+x _n \ge x _1y_1+x _2y_2+...+x _ny_n$. Show that $x _1+x _2+...+x _n \le \frac{x _1}{y_1}+\frac{x _2}{y_2}+...+\frac{x _n}{y_n}$

If $x$ is a real and $4y^2+4xy+x+6=0$, then the complete set of values of $x$ for which $y$ is real, is: $\text{(A)} \ x\le -2~\text{or}~x\ge3 \qquad \text{(B)} \ x\le 2~\text{or}~x\ge3 \qquad \text{(C)} \ x\le -3 ~\text{or}~x\ge 2$ $\text{(D)} \ -3\le x \le 2\qquad \text{(E)} \ \-2\le x \le 3$

A tuple of real numbers $(a_1, a_2, \dots, a_m)$ is called [i]stable [/i]if for each $k \in \{1, 2, \cdots, m-1\}$, $$ \left \vert \frac{a_1+ a_2 + \cdots + a_k}{k} - a_{k+1} \right \vert < 1. $$ Does there exist a stable $n$-tuple $(x_1, x_2, \dots, x_n)$ such that for any real number $x$, the $(n+1)$-tuple $(x, x_1, x_2, \dots, x_n)$ is not stable?

Let $x,y,z$ be real numbers such that $x^2+y^2+z^2=1$.Find the largest posible value of $$|x^3+y^3+z^3-xyz|$$

Find all functions $f:\mathbb{R}\to \mathbb{R}$ such that for all $x, y\in \mathbb{R}$ the following holds: \[f(x)+f(y)=f(xy)+f(f(x)+f(y))\]

Let $n$ be a fixed positive integer. Determine the smallest possible rank of an $n\times n$ matrix that has zeros along the main diagonal and strictly positive real numbers off the main diagonal. [i]Proposed by Ilya Bogdanov and Grigoriy Chelnokov, MIPT, Moscow.[/i]

Let $b$ be an odd positive integer. The sequence $a_1, a_2, a_3, a_4$, is definedin the next way: $a_1$ and $a_2$ are positive integers and for all $k \ge 2$, $$a_{k+1}= \begin{cases} \frac{a_k + a_{k-1}}{2} \,\,\, if \,\,\, a_k + a_{k-1} \,\,\, is \,\,\, even \\ \frac{a_k + a_{k-1+b}}{2}\,\,\, if \,\,\, a_k + a_{k-1}\,\,\, is \,\,\,odd\end{cases}$$ a) Prove that if $b = 1$, then after a certain term, the sequence will become constant. b) For each $b \ge 3$ (odd), prove that there exist values of $a_1$ and $a_2$ for which the sequence will become constant after a certain term.

Solve the system of equations $\begin{cases} x^3+y = x^2+1\\ 2y^3+z=2y^2+1 \\ 3z^3+x=3z^2+1 \end{cases}$

Let $n$ be the product of the first $10$ primes, and let $$S=\sum_{xy\mid n} \varphi(x) \cdot y,$$ where $\varphi(x)$ denotes the number of positive integers less than or equal to $x$ that are relatively prime to $x$, and the sum is taken over ordered pairs $(x, y)$ of positive integers for which $xy$ divides $n$. Compute $\tfrac{S}{n}.$

[b]p1.[/b] Four witches are riding their brooms around a circle with circumference $10$ m. They are standing at the same spot, and then they all start to ride clockwise with the speed of $1$, $2$, $3$, and $4$ m/s, respectively. Assume that they stop at the time when every pair of witches has met for at least two times (the first position before they start counts as one time). What is the total distance all the four witches have travelled? [b]p2.[/b] Suppose $A$ is an equilateral triangle, $O$ is its inscribed circle, and $B$ is another equilateral triangle inscribed in $O$. Denote the area of triangle $T$ as $[T]$. Evaluate $\frac{[A]}{[B]}$. [b]p3. [/b]Tim has bought a lot of candies for Halloween, but unfortunately, he forgot the exact number of candies he has. He only remembers that it's an even number less than $2020$. As Tim tries to put the candies into his unlimited supply of boxes, he finds that there will be $1$ candy left if he puts seven in each box, $6$ left if he puts eleven in each box, and $3$ left if he puts thirteen in each box. Given the above information, find the total number of candies Tim has bought. [b]p4.[/b] Let $f(n)$ be a function defined on positive integers n such that $f(1) = 0$, and $f(p) = 1$ for all prime numbers $p$, and $$f(mn) = nf(m) + mf(n)$$ for all positive integers $m$ and $n$. Let $$n = 277945762500 = 2^23^35^57^7$$ Compute the value of $\frac{f(n)}{n}$ . [b]p5.[/b] Compute the only positive integer value of $\frac{404}{r^2-4}$ , where $r$ is a rational number. [b]p6.[/b] Let $a = 3 +\sqrt{10}$ . If $$\prod^{\infty}_{k=1} \left( 1 + \frac{5a + 1}{a^k + a} \right)= m +\sqrt{n},$$ where $m$ and $n$ are integers, find $10m + n$. [b]p7.[/b] Charlie is watching a spider in the center of a hexagonal web of side length $4$. The web also consists of threads that form equilateral triangles of side length $1$ that perfectly tile the hexagon. Each minute, the spider moves unit distance along one thread. If $\frac{m}{n}$ is the probability, in lowest terms, that after four minutes the spider is either at the edge of her web or in the center, find the value of $m + n$. [b]p8.[/b] Let $ABC$ be a triangle with $AB = 10$; $AC = 12$, and $\omega$ its circumcircle. Let $F$ and $G$ be points on $\overline{AC}$ such that $AF = 2$, $FG = 6$, and $GC = 4$, and let $\overrightarrow{BF}$ and $\overrightarrow{BG}$ intersect $\omega$ at $D$ and $E$, respectively. Given that $AC$ and $DE$ are parallel, what is the square of the length of $BC$? [b]p9.[/b] Two blue devils and $4$ angels go trick-or-treating. They randomly split up into $3$ non-empty groups. Let $p$ be the probability that in at least one of these groups, the number of angels is nonzero and no more than the number of devils in that group. If $p = \frac{m}{n}$ in lowest terms, compute $m + n$. [b]p10.[/b] We know that$$2^{22000} = \underbrace{4569878...229376}_{6623\,\,\, digits}.$$ For how many positive integers $n < 22000$ is it also true that the first digit of $2^n$ is $4$? PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

You are racing an Artificially Intelligent Robot, called Al, that you built. You can run at a constant speed of $10$ m/s throughout the race. Meanwhile, Al starts running at a constant speed of $ 1$ m/s. Thereafter, when exactly $ 1$ second has passed from when Al last changed its speed, Al’s speed instantaneously becomes $1$ m/s faster, so that Al runs at a constant speed of $k$ m/s in the kth second of the race. (Start counting seconds at $ 1$). Suppose Al beats you by exactly $1$ second. How many meters was the race?

Let $m$ be a positive integer. Determine the smallest positive integer $n$ for which there exist real numbers $x_1, x_2,...,x_n \in (-1, 1)$ such that $|x_1| + |x_2| +...+ |x_n| = m + |x_1 + x_2 + ... + x_n|$.

How many finite sequances $x_1,x_2,\cdots,x_m$ are there such that $x_i=1$ or 2 and $\sum \limits_{i=1}^mx_i=10$ ? [list=1] [*] 89 [*] 73 [*] 107 [*] 119 [/list]

Let $n,p \geq 2$ be two integers and $A$ an $n\times n$ matrix with real elements such that $A^{p+1} = A$. a) Prove that $\textrm{rank} \left( A \right) + \textrm{rank} \left( I_n - A^p \right) = n$. b) Prove that if $p$ is prime then \[ \textrm{rank} \left( I_n - A \right) = \textrm{rank} \left( I_n - A^2 \right) = \ldots = \textrm{rank} \left( I_n - A^{p-1} \right) . \]

Prove that for every polynomial $P(x)$ with real coefficients there exist a positive integer $m$ and polynomials $P_{1}(x),\ldots , P_{m}(x)$ with real coefficients such that \[P(x) = (P_{1}(x))^{3}+\ldots +(P_{m}(x))^{3}\]

Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\deg f>\deg g$. Suppose that for infinitely many primes $p$ the polynomial $pf+g$ has a rational root. Prove that $f$ has a rational root.

Let $n\geq 2$ be an integer and let $a_1, a_2, \ldots, a_n$ be positive real numbers with sum $1$. Prove that $$\sum_{k=1}^n \frac{a_k}{1-a_k}(a_1+a_2+\cdots+a_{k-1})^2 < \frac{1}{3}.$$

Initially on a blackboard, the equation $a_1x^2+b_1x+c=0$ is written where $a_1, b_1, c_1$ are integers and $(a_1+c_1)b_1 > 0$. At each move, if the equation $ax^2+bx+c=0$ is written on the board and there is a $x \in \mathbb{R}$ satisfying the equation, Alice turns this equation into $(b+c)x^2+(c+a)x+(a+b)=0$. Prove that Alice will stop after a finite number of moves.

[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].