The map of a country is in the form of a convex polygon with $n (n\geq5)$ sides, such as any 3 diagonals do not concur inside the polygon. Some of the diagonals are roads, which allow movement in both directions and the other diagonals are not roads. There are cities on the intersection points of any two diagonals inside the polygon and at least one of the two diagonals is a road. Prove that you can move from any city to any other city using at most 3 roads.

For a set \(S\) of positive integers and a positive integer \(n\), consider the game of [i]\((n,S)\)-nim[/i], which is as follows. A pile starts with \(n\) watermelons. Two players, Deric and Erek, alternate turns eating watermelons from the pile, with Deric going first. On any turn, the number of watermelons eaten must be an element of \(S\). The last player to move wins. Let \(f(S)\) denote the set of positive integers \(n\) for which Deric has a winning strategy in \((n,S)\)-nim. Let \(T\) be a set of positive integers. Must the sequence \[T, \; f(T), \; f(f(T)), \;\ldots\] be eventually constant? [i]Proposed by Brandon Wang and Edward Wan[/i]

Richard rolls a fair six-sided die repeatedly until he rolls his twentieth prime number or his second even number. Compute the probability that his last roll is prime.

A hundred tourists arrive to a hotel at night. They know that in the hotel there are single rooms numbered as $1, 2, \ldots , n$, and among them $k{}$ (the tourists do not know which) are under repair, the other rooms are free. The tourists, one after another, check the rooms in any order (maybe different for different tourists), and the first room not under repair is taken by the tourist. The tourists don’t know whether a room is occupied until they check it. However it is forbidden to check an occupied room, and the tourists may coordinate their strategy beforehand to avoid this situation. For each $k{}$ find the smallest $n{}$ for which the tourists may select their rooms for sure. [i]Fyodor Ivlev[/i]

A1,A2,...,Am are subsets of X and we have |Ai|=mk (m,k natural numbers) prove that we can separate X into k sets such that every set has at least one member of each Ai.

Every natural number is coloured in one of the $ k$ colors. Prove that there exist four distinct natural numbers $ a, b, c, d$, all coloured in the same colour, such that $ ad \equal{} bc$, $ \displaystyle \frac b a$ is power of 2 and $ \displaystyle \frac c a$ is power of 3.

[u]Round 5[/u] [b]5.1.[/b] Quadrilateral $ABCD$ is such that $\angle ABC = \angle ADC = 90^o$ , $\angle BAD = 150^o$ , $AD = 3$, and $AB = \sqrt3$. The area of $ABCD$ can be expressed as $p\sqrt{q}$ for positive integers $p, q$ where $q$ is not divisible by the square of any prime. Find $p + q$. [b]5.2.[/b] Neetin wants to gamble, so his friend Akshay describes a game to him. The game will consist of three dice: a $100$-sided one with the numbers $1$ to $100$, a tetrahedral one with the numbers $1$ to $4$, and a normal $6$-sided die. If Neetin rolls numbers with a product that is divisible by $21$, he wins. Otherwise, he pays Akshay $100$ dollars. The number of dollars that Akshay must pay Neetin for a win in order to make this game fair is $a/b$ for relatively prime positive integers $a, b$. Find $a + b$. (Fair means the expected net gain is $0$. ) [b]5.3.[/b] What is the sum of the fourth powers of the roots of the polynomial $P(x) = x^2 + 2x + 3$? [u]Round 6[/u] [b]6.1.[/b] Consider the set $S = \{1, 2, 3, 4,..., 25\}$. How many ordered $n$-tuples $S_1 = (a_1, a_2, a_3,..., a_n)$ of pairwise distinct ai exist such that $a_i \in S$ and $i^2 | a_i$ for all $1 \le i \le n$? [b]6.2.[/b] How many ways are there to place $2$ identical rooks and $ 1$ queen on a $ 4 \times 4$ chessboard such that no piece attacks another piece? (A queen can move diagonally, vertically or horizontally and a rook can move vertically or horizontally) [b]6.3.[/b] Let $L$ be an ordered list $\ell_1$, $\ell_2$, $...$, $\ell_{36}$ of consecutive positive integers who all have the sum of their digits not divisible by $11$. It is given that $\ell_1$ is the least element of $L$. Find the least possible value of $\ell_1$. [u]Round 7[/u] [b]7.1.[/b] Spencer, Candice, and Heather love to play cards, but they especially love the highest cards in the deck - the face cards (jacks, queens, and kings). They also each have a unique favorite suit: Spencer’s favorite suit is spades, Candice’s favorite suit is clubs, and Heather’s favorite suit is hearts. A dealer pulls out the $9$ face cards from every suit except the diamonds and wants to deal them out to the $3$ friends. How many ways can he do this so that none of the $3$ friends will see a single card that is part of their favorite suit? [b]7.2.[/b] Suppose a sequence of integers satisfies the recurrence $a_{n+3} = 7a_{n+2} - 14a_{n+1} + 8a_n$. If $a_0 = 4$, $a_1 = 9$, and $a_2 = 25$, find $a_{16}$. Your answer will be in the form $2^a + 2^b + c$, where $2^a < a_{16} < 2^{a+1}$ and $b$ is as large as possible. Find $a + b + c$. [b]7.3.[/b] Parallel lines $\ell_1$ and $\ell_2$ are $1$ unit apart. Unit square $WXYZ$ lies in the same plane with vertex $W$ on $\ell_1$. Line $\ell_2$ intersects segments $YX$ and $YZ$ at points $U$ and $O$, respectively. Given $UO =\frac{9}{10}$, the inradius of $\vartriangle YOU$ can be expressed as $\frac{m}{n}$ for relatively prime positive integers $m, n$. Find $m + n$. [u]Round 8[/u] [b]8.[/b] Let $A$ be the number of contestants who participated in at least one of the three rounds of the 2020 ABMC April contest. Let $B$ be the number of times the letter b appears in the Accuracy Round. Let $M$ be the number of people who submitted both the speed and accuracy rounds before 2:00 PM EST. Further, let $C$ be the number of times the letter c appears in the Speed Round. Estimate $$A \cdot B + M \cdot C.$$Your answer will be scored according to the following formula, where $X$ is the correct answer and $I$ is your input. $$max \left\{ 0, \left\lceil min \left\{13 - \frac{|I-X|}{0.05 |I|}, 13 - \frac{|I-X|}{0.05 |I-2X|} \right\} \right\rceil \right\}$$ PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2766239p24226402]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For what positive integers $n$ is it possible to tile an equilateral triangle of side $n$ with trapezoids each of which has sides $1, 1, 1, 2$? (NB Vassiliev)

Anya, Borya, and Vasya listed words that could be formed from a given set of letters. They each listed a different number of words : Anya listed the most, Vasya the least . They were awarded points as follows. Each word listed by only one of them scored $2$ points for this child. Each word listed by two of them scored $1$ point for each of these two children. Words listed by all three of them scored $0$ points. Is it possible that Vasya got the highest score, and Anya the lowest? (A Shapovalov)

Three natural numbers $ a,b,c $ with $ \gcd (a,b) =1 $ define in the Diophantine plane a line $ d: ax+by-c=0. $ Prove that: [b]a)[/b] the distance between any two points from $ d $ is at least $ \sqrt{a^2+b^2} . $ [b]b)[/b] the restriction of $ d $ to the first quadrant of the Diophantine plane is a finite line having at most $ 1+\frac{c}{ab} $ elements.

On the VI-th International Festival of Young Mathematicians in Sozopol $n$ teams were participating, each of which was with $k$ participants ($n>k>1$). The organizers of the competition separated the $nk$ participants into $n$ groups, each with $k$ people, in such way that no two teammates are in the same group. Prove that there can be found $n$ participants no two of which are in the same team or group.

The spectators are seated in a row with no empty places. Each is in a seat which does not match the spectator's ticket. An usher can order two spectators in adjacent seats to trade places unless one of them is already seated correctly. Is it true that from any initial arrangement, the spectators can be brought to their correct seats?

[b]a)[/b] Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n$? [b]b)[/b] Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n^2$? [i]Proposed by Morteza Saghafian[/i]

Hannibal and Clarice are still at a barbecue and there are three anticuchos left, each of which it has $10$ pieces. Of the $30$ total pieces, there are $29$ chicken and one meat, the which is at the bottom of one of the anticuchos. To decide who to stay with the piece of meat, they decide to play the following game: they alternately take out a piece of one of the anticuchos (they can take only the outer pieces) and whoever wins the game manages to remove the piece of meat. Clarice decides if she starts or Hannibal starts. What should she decide?

Let $n$ and $t$ be positive integers. What is the number of ways to place $t$ dominoes $(1\times 2$ or $2\times 1$ rectangles) in a $2\times n$ table so that there is no $2\times 2$ square formed by $2$ dominoes and each $2\times 3$ rectangle either does not have a horizontal domino in the middle and last cell in the first row or does not have a horizontal domino in the first and middle cell in the second row (or both)?

On the football training there was $n$ footballers - forwards and goalkeepers. They made $k$ goals. Prove that main trainer can give for every footballer squad number from $1$ to $n$ such, that for every goal the difference between squad number of forward and squad number of goalkeeper is more than $n-k$. [i](S. Berlov)[/i]

Let $v_1, v_2, \ldots, v_m$ be vectors in $\mathbb{R}^n$, such that each has a strictly positive first coordinate. Consider the following process. Start with the zero vector $w = (0, 0, \ldots, 0) \in \mathbb{R}^n$. Every round, choose an $i$ such that $1 \le i \le m$ and $w \cdot v_i \le 0$, and then replace $w$ with $w + v_i$. Show that there exists a constant $C$ such that regardless of your choice of $i$ at each step, the process is guaranteed to terminate in (at most) $C$ rounds. The constant $C$ may depend on the vectors $v_1, \ldots, v_m$.

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$. (Ilke Chanakchi, Ralf Schiffler)

The sides of an equilateral triangle $ABC$ are divided into $n$ equal parts $(n \geq 2) .$ For each point on a side, we draw the lines parallel to other sides of the triangle $ABC,$ e.g. for $n=3$ we have the following diagram: [asy] unitsize(150); defaultpen(linewidth(0.7)); int n = 3; /* # of vertical lines, including AB */ pair A = (0,0), B = dir(-30), C = dir(30); draw(A--B--C--cycle,linewidth(2)); dot(A,UnFill(0)); dot(B,UnFill(0)); dot(C,UnFill(0)); label("$A$",A,W); label("$C$",C,NE); label("$B$",B,SE); for(int i = 1; i < n; ++i) { draw((i*A+(n-i)*B)/n--(i*A+(n-i)*C)/n); draw((i*B+(n-i)*A)/n--(i*B+(n-i)*C)/n); draw((i*C+(n-i)*A)/n--(i*C+(n-i)*B)/n); } [/asy] For each $n \geq 2,$ find the number of existing parallelograms.

In chess, a knight placed on a chess board can move by jumping to an adjacent square in one direction (up, down, left, or right) then jumping to the next two squares in a perpendicular direction. We then say that a square in a chess board can be attacked by a knight if the knight can end up on that square after a move. Thus, depending on where a knight is placed, it can attack as many as eight squares, or maybe even less. In a $10 \times 10$ chess board, what is the maximum number of knights that can be placed such that each square on the board can be attacked by at most one knight?

The load for the space station "Salute" is packed in containers. There are more than $35$ containers, and the total weight is $18$ metric tons. There are $7$ one-way transport spaceships "Progress", each able to bring $3$ metric tons to the station. It is known that they are able to take an arbitrary subset of $35$ containers. Prove that they are able to take all the load.

Each pair of vertices of a regular $67$-gon is joined by a line segment. Suppose $n$ of these segments are selected, and each of them is painted one of ten available colors. Find the minimum possible value of $n$ for which, regardless of which $n$ segments were selected and how they were painted, there will always be a vertex of the polygon that belongs to seven segments of the same color.

In a certain country there are $2023$ islands and $2022$ bridges, such that every bridge connects two different islands and any two islands have at most one bridge in common, and from any island, using bridges one can get to any other island. If in any three islands there is an island with bridges connected to each of the other two islands, call these three islands an "island group". We know that any two "island group"s have at least $1$ common island. What is the minimum number of islands with only $1$ bridge connected to it?

Suppose that necklace $\, A \,$ has 14 beads and necklace $\, B \,$ has 19. Prove that for any odd integer $n \geq 1$, there is a way to number each of the 33 beads with an integer from the sequence \[ \{ n, n+1, n+2, \dots, n+32 \} \] so that each integer is used once, and adjacent beads correspond to relatively prime integers. (Here a ``necklace'' is viewed as a circle in which each bead is adjacent to two other beads.)

Let $n=2k-1$, where $k\ge 6$ is an integer. Let $T$ be the set of all $n$-tuples $$\textbf{x}=(x_1,x_2,\dots ,x_n), \text{ where, for } i=1,2,\dots ,n, \text{ } x_i \text{ is } 0 \text{ or } 1.$$ For $\textbf{x}=(x_1,x_2,\dots ,x_n)$ and $\textbf{y}=(y_1,y_2,\dots ,y_n)$ in $T$, let $d(\textbf{x},\textbf{y})$ denote the number of integers $j$ with $1\le j\le n$ such that $x_j\neq x_y$. $($In particular, $d(\textbf{x},\textbf{x})=0)$. Suppose that there exists a subset $S$ of $T$ with $2^k$ elements which has the following property: given any element $\textbf{x}$ in $T$, there is a unique $\textbf{y}$ in $S$ with $d(\textbf{x},\textbf{y})\le 3$. Prove that $n=23$.