Towns $A_1, A_2, . . . , A_{30}$ lie on line $MN$. The distances between the consecutive towns are equal. Each of the towns is the point of origin of a straight highway. The highways are on the same side of $MN$ and form the following angles with it: [img]https://cdn.artofproblemsolving.com/attachments/a/f/6cfcac497bdd729b966705f1060bd4b1caba25.png[/img] Thirty cars start simultaneously from these towns along the highway at the same constant speed. Each intersection has a gate. As soon as the first (in time, not in number) car passes the intersection the gate closes and blocks the way for all other cars approaching this intersection. Which cars will pass all intersections and which will be stopped? Note: This refers to angles measured counterclockwise from straight MN to the corresponding road.

In a football championship with $2021$ teams, each team play with another exactly once. The score of the match(es) is three points to the winner, one point to both players if the match end in draw(tie) and zero point to the loser. The final of the tournament will be played by the two highest score teams. Brazil Football Club won the first match, and it has the advantage if in the final score it draws with any other team. Determine the least score such that Brazil Football Club has a [b]chance[/b] to play the final match.

For positive integers $n, k, r$, denote by $A(n, k, r)$ the number of integer tuples $(x_1, x_2, \ldots, x_k)$ satisfying the following conditions. [list] [*] $x_1 \ge x_2 \ge \cdots \ge x_k \ge 0$ [*] $x_1+x_2+ \cdots +x_k = n$ [*] $x_1-x_k \le r$ [/list] For all positive integers $m, s, t$, prove that $$A(m, s, t)=A(m, t, s).$$

Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct numbers such that the product of two of them equals the third.

An $8\times 8$ chessboard is made of unit squares. We put a rectangular piece of paper with sides of length 1 and 2. We say that the paper and a single square overlap if they share an inner point. Determine the maximum number of black squares that can overlap the paper.

Niek has $16$ square cards that are yellow on one side and red on the other. He puts down the cards to form a $4 \times 4$-square. Some of the cards show their yellow side and some show their red side. For a colour pattern he calculates the [i]monochromaticity [/i] as follows. For every pair of adjacent cards that share a side he counts $+1$ or $-1$ according to the following rule: $+1$ if the adjacent cards show the same colour, and $-1$ if the adjacent cards show different colours. Adding this all together gives the monochromaticity (which might be negative). For example, if he lays down the cards as below, there are $15$ pairs of adjacent cards showing the same colour, and $9$ such pairs showing different colours. [asy] unitsize(1 cm); int i; fill(shift((0,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((1,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((2,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((3,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((0,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((1,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red); fill(shift((2,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((3,1))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((0,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((1,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((2,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((3,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red); fill(shift((0,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red); fill(shift((1,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((2,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), yellow); fill(shift((3,3))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), red); for (i = 0; i <= 4; ++i) { draw((i,0)--(i,4)); draw((0,i)--(4,i)); } [/asy] The monochromaticity of this pattern is thus $15 \cdot (+1) + 9 \cdot (-1) = 6$. Niek investigates all possible colour patterns and makes a list of all possible numbers that appear at least once as a value of the monochromaticity. That is, Niek makes a list with all numbers such that there exists a colour pattern that has this number as its monochromaticity. (a) What are the three largest numbers on his list? ([i]Explain your answer. If your answer is, for example, $ 12$, $9$ and $6$, then you have to show that these numbers do in fact appear on the list by giving a colouring for each of these numbers, and furthermore prove that the numbers $7$, $ 8$, $10$, $11$ and all numbers bigger than $ 12$ do not appear.[/i]) (b) What are the three smallest (most negative) numbers on his list? (c) What is the smallest positive number (so, greater than $0$) on his list?

A polygon can be divided into 100 rectangles, but not into 99. Prove that it cannot be divided into 100 triangles. [i]A. Shapovalov[/i]

For positive integers $n, k, r$, denote by $A(n, k, r)$ the number of integer tuples $(x_1, x_2, \ldots, x_k)$ satisfying the following conditions. [list] [*] $x_1 \ge x_2 \ge \cdots \ge x_k \ge 0$ [*] $x_1+x_2+ \cdots +x_k = n$ [*] $x_1-x_k \le r$ [/list] For all positive integers $s, t \ge 2$, prove that $$A(st, s, t) = A(s(t-1), s, t) = A((s-1)t, s, t).$$

Find, with proof, the number of positive integers whose base-$n$ representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by $\pm 1$ from some digit further to the left. (Your answer should be an explicit function of $n$ in simplest form.)

[b]p1.[/b] How many two-digit primes have a units digit of $3$? [b]p2.[/b] How many ways can you arrange the letters $A$, $R$, and $T$ such that it makes a three letter combination? Each letter is used once. [b]p3.[/b] Hanna and Kevin are running a $100$ meter race. If Hanna takes $20$ seconds to finish the race and Kevin runs $15$ meters per second faster than Hanna, by how many seconds does Kevin finish before Hanna? [b]p4.[/b] It takes an ant $3$ minutes to travel a $120^o$ arc of a circle with radius $2$. How long (in minutes) would it take the ant to travel the entirety of a circle with radius $2022$? [b]p5.[/b] Let $\vartriangle ABC$ be a triangle with angle bisector $AD$. Given $AB = 4$, $AD = 2\sqrt2$, $AC = 4$, find the area of $\vartriangle ABC$. [b]p6.[/b] What is the coefficient of $x^5y^2$ in the expansion of $(x + 2y + 4)^8$? [b]p7.[/b] Find the least positive integer $x$ such that $\sqrt{20475x}$ is an integer. [b]p8.[/b] What is the value of $k^2$ if $\frac{x^5 + 3x^4 + 10x^2 + 8x + k}{x^3 + 2x + 4}$ has a remainder of $2$? [b]p9.[/b] Let $ABCD$ be a square with side length $4$. Let $M$, $N$, and $P$ be the midpoints of $\overline{AB}$, $\overline{BC}$ and $\overline{CD}$, respectively. The area of the intersection between $\vartriangle DMN$ and $\vartriangle ANP$ can be written as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Find $a + b$. [b]p10.[/b] Let $x$ be all the powers of two from $2^1$ to $2^{2023}$ concatenated, or attached, end to end ($x = 2481632...$). Let y be the product of all the powers of two from $2^1$ to $2^{2023}$ ($y = 2 \cdot 4 \cdot 8 \cdot 16 \cdot 32... $ ). Let 2a be the largest power of two that divides $x$ and $2^b$ be the largest power of two that divides $y$. Compute $\frac{b}{a}$ . [b]p11.[/b] Larry is making a s’more. He has to have one graham cracker on the top and one on the bottom, with eight layers in between. Each layer can made out of chocolate, more graham crackers, or marshmallows. If graham crackers cannot be placed next to each other, how many ways can he make this s’more? [b]p12.[/b] Let $ABC$ be a triangle with $AB = 3$, $BC = 4$, $AC = 5$. Circle $O$ is centered at $B$ and has radius $\frac{8\sqrt{3}}{5}$ . The area inside the triangle but not inside the circle can be written as $\frac{a-b\sqrt{c}-d\pi}{e}$ , where $gcd(a, b, d, e) =1$ and $c$ is squarefree. Find $a + b + c + d + e$. [b]p13.[/b] Let $F(x)$ be a quadratic polynomial. Given that $F(x^2 - x) = F (2F(x) - 1)$ for all $x$, the sum of all possible values of $F(2022)$ can be written as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Find $a + b$. [b]p14.[/b] Find the sum of all positive integers $n$ such that $6\phi (n) = \phi (5n)+8$, where $\phi$ is Euler’s totient function. Note: Euler’s totient $(\phi)$ is a function where $\phi (n)$ is the number of positive integers less than and relatively prime to $n$. For example, $\phi (4) = 2$ since only $1$, $3$ are the numbers less than and relatively prime to $4$. [b]p15.[/b] Three numbers $x$, $y$, and $z$ are chosen at random from the interval $[0, 1]$. The probability that there exists an obtuse triangle with side lengths $x$, $y$, and $z$ can be written in the form $\frac{a\pi-b}{c}$ , where $a$, $b$, $c$ are positive integers with $gcd(a, b, c) = 1$. Find $a + b + c$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For any nonnegative integer $n$, let $S(n)$ be the sum of the digits of $n$. Let $K$ be the number of nonnegative integers $n \le 10^{10}$ that satisfy the equation \[ S(n) = (S(S(n)))^2. \] Find the remainder when $K$ is divided by $1000$.

There are $50$ male and $50$ female members registered in the QED-DB, who are also there are numbered from $1$ to $100$. In $100$ rounds, Andreas chooses at random one member for the seminar in Bad Tolz, whereupon Katharina already has two each time selected QED members of different sexes may or may not be paired up. Of course QED members cannot be coupled multiple times, ignoring relationships from the time before but both conscientiously. The stability of a relationship between two QED members is the amount of the difference between their numbers in DB and the sum of all stabilities is the promotion of young talent in the QED. What is the greatest possible demand of offspring guaranteed to achieve orgasm? [hide=original wording]In der QED-DB sind 50 m¨annliche und 50 weibliche Mitglieder eingetragen, welche dort mit den Zahlen von 1 bis 100 durchnummeriert sind. In 100 Runden w¨ahlt Andreas jeweils zuf¨allig ein Mitglied fu¨r das Seminar in Bad T¨olz aus, woraufhin jedes Mal Katharina zwei bereits ausgew¨ahlte QEDler unterschiedlichen Geschlechts verkuppeln darf, aber nicht muss. Natu¨rlich k¨onnen QEDler nicht mehrfach verkuppelt werden, Beziehungen aus der Zeit davor ignorieren beide aber gewissenhaft. Die Stabilit¨at einer Beziehung zwischen zwei QEDlern ist der Betrag der Differenz ihrer Zahlen in der DB und die Summe aller Stabilit¨aten ist die Nachwuchsf¨orderung im QED. Was ist die gr¨oßtm¨ogliche Nachwuchsf¨orderung, welche die Orgas garantiert erreichen k¨onnen¿[/hide]

On a flat plane in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue. At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet. After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls. Let $k(\mathfrak{L})$ be the largest number $k$ such that, no matter how Merlin paints the labyrinth $\mathfrak{L},$ Morgana can always place at least $k$ knights such that no two of them can ever meet. For each $n,$ what are all possible values for $k(\mathfrak{L}),$ where $\mathfrak{L}$ is a labyrinth with $n$ walls?

Numbers from$ 1$ to $8$ were written at the vertices of the cube, and on each edge the absolute value of the difference between the numbers at its ends.. What is the smallest number of different numbers that can be written on the edges?

A circle is divided into arcs of equal size by $n$ points ($n \ge 1$). For any positive integer $x$, let $P_n(x)$ denote the number of possibilities for colouring all those points, using colours from $x$ given colours, so that any rotation of the colouring by $ i \cdot \frac{360^o}{n}$ , where i is a positive integer less than $n$, gives a colouring that differs from the original in at least one point. Prove that the function $P_n(x)$ is a polynomial with respect to $x$.

There are $25$ IMO participants attending a party. Every two of them speak to each other in some language, and they use only one language even if they both know some other language as well. Among every three participants there is a person who uses the same language to speak to the other two (in that group of three). Prove that there is an IMO participant who speaks the same language to at least $10$ other participants

Let $ n,k$ be given positive integers satisfying $ k\le 2n \minus{} 1$. On a table tennis tournament $ 2n$ players take part, they play a total of $ k$ rounds match, each round is divided into $ n$ groups, each group two players match. The two players in different rounds can match on many occasions. Find the greatest positive integer $ m \equal{} f(n,k)$ such that no matter how the tournament processes, we always find $ m$ players each of pair of which didn't match each other.

Two disjoint subsets of the set $\{1,2, ... ,m\}$ have the same sums of elements. Prove that each of the subsets $A,B$ has less than $m / \sqrt2$ elements.

Define a colouring in tha plane the following way: - we pick a positive integer $m$; - let $K_{1}$, $K_{2}$, ..., $K_{m}$ be different circles with nonzero radii such that $K_{i}\subset K_{j}$ or $K_{j}\subset K_{i}$ if $i \neq j$; - the points in the plane that lie outside an arbitrary circle (one that is amongst the circles we pick) are coloured differently than the points that lie inside the circle. There are $2019$ points in the plane such that any $3$ of them are not collinear. Determine the maximum number of colours which we can use to colour the given points.

How many ways are there to represent $10^6$ as the product of three factors? Factorizations which only differ in the order of the factors are considered to be distinct.

Prove that the number $A=\frac{(4n)!}{(2n)!n!}$ is an integer and divisible by $2^{n+1}$, where $n$ is a positive integer.

We call a $5$-tuple of integers [i]arrangeable[/i] if its elements can be labeled $a, b, c, d, e$ in some order so that $a-b+c-d+e=29$. Determine all $2017$-tuples of integers $n_1, n_2, . . . , n_{2017}$ such that if we place them in a circle in clockwise order, then any $5$-tuple of numbers in consecutive positions on the circle is arrangeable. [i]Warut Suksompong, Thailand[/i]

$1989$ equal circles are arbitrarily placed on the table without overlap. What is the least number of colors are needed such that all the circles can be painted with any two tangential circles colored differently.

Let $n$ be a positive integer. Each cell of an $n \times n$ table is coloured in one of $k$ colours where every colour is used at least once. Two different colours $A$ and $B$ are said to touch each other, if there exists a cell coloured in $A$ sharing a side with a cell coloured in $B$. The table is coloured in such a way that each colour touches at most $2$ other colours. What is the maximal value of $k$ in terms of $n$?

Let $a_1,a_2, \dots a_n$ be positive real numbers. Define $b_1,b_2, \dots b_n$ as follows. \begin{align*} b_1&=a_1 \\ b_2&=max(a_1,a_2)\\ b_i&=max(b_{i-1},b_{i-2}+a_i) \text{ for } i=3,4 \dots n \end{align*} Also define $c_1,c_2 \dots c_n$ as follows. \begin{align*} c_n&=a_n \\ c_{n-1}&=max(a_n,a_{n-1})\\ c_i&=max(c_{i+1},c_{i+2}+a_i) \text{ for } i=n-2,n-3 \dots 1 \end{align*} Prove that $b_n=c_1$.\\