Find the largest possible number of rooks that can be placed on a $3n \times 3n$ chessboard so that each rook is attacked by at most one rook.

Let $a_1,a_2,\cdots$ be a strictly increasing sequence on positive integers. Is it always possible to partition the set of natural numbers $\mathbb{N}$ into infinitely many subsets with infinite cardinality $A_1,A_2,\cdots$, so that for every subset $A_i$, if we denote $b_1<b_2<\cdots$ be the elements of $A_i$, then for every $k\in \mathbb{N}$ and for every $1\le i\le a_k$, it satisfies $b_{i+1}-b_{i}\le k$?

A castle is surrounded by a circular wall with $9$ towers which are guarded by knights during the night. Every hour the castle clock strikes and the guards shift to the neighboring towers, each guard always moves in the same direction (either clockwise or counterclockwise). Given that (i) during the night each knight guards every tower (ii) at some hour each tower was guarded by at least two knights (iii) at some hour exactly $5$ towers were guarded by single knights, prove that at some hour one of the towers was unguarded.

Each number from the set $\{1,2,3,4,5,6,7,8\}$ is either colored red or blue, following these rules: a) The number $4$ is colored red, and there is at least one number colored blue. b) If two numbers $x, y$ have different colors and $x + y \leq 8$, then the number $x + y$ is colored blue. c) If two numbers $x, y$ have different colors and $x \cdot y \leq 8$, then the number $x \cdot y$ is colored red. Find all possible ways the numbers from this set can be colored.

A very well known family of mathematicians has three children called [i]Antonia, Bernhard[/i] and [i]Christian[/i]. Each evening one of the children has to do the dishes. One day, their dad decided to construct of plan that says which child has to do the dishes at which day for the following $55$ days. Let $x$ be the number of possible such plans in which Antonia has to do the dishes on three consecutive days at least once. Furthermore, let $y$ be the number of such plans in which there are three consecutive days in which Antonia does the dishes on the first, Bernhard on the second and Christian on the third day. Determine, whether $x$ and $y$ are different and if so, then decide which of those is larger.

We call a subset $B$ of natural numbers [i]loyal[/i] if there exists natural numbers $i\le j$ such that $B=\{i,i+1,\ldots,j\}$. Let $Q$ be the set of all [i]loyal[/i] sets. For every subset $A=\{a_1<a_2<\ldots<a_k\}$ of $\{1,2,\ldots,n\}$ we set \[f(A)=\max_{1\le i \le k-1}{a_{i+1}-a_i}\qquad\text{and}\qquad g(A)=\max_{B\subseteq A, B\in Q} |B|.\] Furthermore, we define \[F(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} f(A)\qquad\text{and}\qquad G(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} g(A).\] Prove that there exists $m\in \mathbb N$ such that for each natural number $n>m$ we have $F(n)>G(n)$. (By $|A|$ we mean the number of elements of $A$, and if $|A|\le 1$, we define $f(A)$ to be zero). [i]Proposed by Javad Abedi[/i]

There are 10,000 vertices in a graph, with at least one edge coming out of each vertex. Call a set $S{}$ of vertices [i]delightful[/i] if no two of its vertices are connected by an edge, but any vertex not from $S{}$ is connected to at least one vertex from $S{}$. For which smallest $m$ is there necessarily a delightful set of at most $m$ vertices?

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 Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k>0$ coins showing $H$, then he turns over the $k$th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n=3$ the process starting with the configuration $THT$ would be $THT \to HHT \to HTT \to TTT$, which stops after three operations. (a) Show that, for each initial configuration, Harry stops after a finite number of operations. (b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$. [i]Proposed by David Altizio, USA[/i]

General Tilly and the Duke of Wallenstein play "Divide and rule!" (Divide et impera!). To this end, they arrange $N$ tin soldiers in $M$ companies and command them by turns. Both of them must give a command and execute it in their turn. Only two commands are possible: The command "[i]Divide![/i]" chooses one company and divides it into two companies, where the commander is free to choose their size, the only condition being that both companies must contain at least one tin soldier. On the other hand, the command "[i]Rule![/i]" removes exactly one tin soldier from each company. The game is lost if in your turn you can't give a command without losing a company. Wallenstein starts to command. a) Can he force Tilly to lose if they start with $7$ companies of $7$ tin soldiers each? b) Who loses if they start with $M \ge 1$ companies consisting of $n_1 \ge 1, n_2 \ge 1, \dotsc, n_M \ge 1$ $(n_1+n_2+\dotsc+n_M=N)$ tin soldiers?

At the ends of a checkered strip measuring $1 \times 101$ squares there are two chips: on the left is the chip of the first player, on the right is the second. Per turn dares to move his piece in the direction of the opposite edge of the strip by 1, 2, 3 or 4 cells. In this case, you are allowed to jump over opponent's chip, but it is forbidden to place your chip on the same square with her. The first one to reach the opposite edge of the strip wins. Who wins if the game is played correctly: the one who goes first, or him rival?

Given the natural number N, consider triples of different positive integers $(a, b, c)$ such that $a + b + c = N$. Take the largest possible system of these triples such that no two triples of the system have any common elements. Denote the number of triples of this system by $K(N)$. Prove that: (a) $K(N) >\frac{N}{6}-1$ (b) $K(N) <\frac{2N}{9}$ (L.D. Kurliandchik, Leningrad)

There are $n$ students each having $r$ positive integers. Their $nr$ positive integers are all different. Prove that we can divide the students into $k$ classes satisfying the following conditions. (a) $ k \le 4r $ (b) If a student $A$ has the number $m$, then the student $B$ in the same class can't have a number $l$ such that \[ (m-1)! < l < (m+1)!+1 \]

There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n \minus{} 1$ is not divisible by $ 3$. [i]Proposed by Dusan Dukic, Serbia[/i]

Given a $20 \times 101$ square table with $20$ rows and $101$ columns. One wants to fill numbers $0$ and $1$ in the unit squares of the table satisfying the following conditions: $[\text{i}]$ Each square has exactly one number to be filled in. $[\text{ii}]$ Each column is filled with exactly two $1'$s. $[\text{iii}]$ Any two rows with no more than one column are filled with two $1'$s. $a.$ How many ways to fill the numbers satisfying the given conditions? $b.$ With a satisfied numbering way, we number the rows in order from top to bottom. A triple of row (distinct, unordered) $\{a; b; c\}$ is said to be [i]united[/i] if the sets of numbers in the three rows are $(a_1, a_2, . . . , a_{101}), (b_1, b_2, . . . . , b_{101}),$ and $(c_1, c_2, . . . . , c_{101})$ satisfied$$\sum\limits_{i = 1}^{101} {({a_i}{b_i} + {b_i}{c_i} + {c_i}{a_i})} = 3.$$ Prove that: there are at least $10$ [i]united[/i] sets.

In a country there are $100$ airports. Super-Air operates direct flights between some pairs of airports (in both directions). The [i]traffic[/i] of an airport is the number of airports it has a direct Super-Air connection with. A new company, Concur-Air, establishes a direct flight between two airports if and only if the sum of their traffics is at least $100.$ It turns out that there exists a round-trip of Concur-Air flights that lands in every airport exactly once. Show that then there also exists a round-trip of Super-Air flights that lands in every airport exactly once.

[u]Round 5[/u] [b]p13.[/b] Find the number of six-digit positive integers that satisfy all of the following conditions: (i) Each digit does not exceed $3$. (ii) The number $1$ cannot appear in two consecutive digits. (iii) The number $2$ cannot appear in two consecutive digits. [b]p14.[/b] Find the sum of all distinct prime factors of $103040301$. [b]p15.[/b] Let $ABCA'B'C'$ be a triangular prism with height $3$ where bases $ABC$ and $A'B'C'$ are equilateral triangles with side length $\sqrt6$. Points $P$ and $Q$ lie inside the prism so that $ABCP$ and $A'B'C'Q$ are regular tetrahedra. The volume of the intersection of these two tetrahedra can be expressed in the form $\frac{\sqrt{m}}{n}$ , where $m$ and $n$ are positive integers and $m$ is not divisible by the square of any prime. Find $m + n$. [u]Round 6[/u] [b]p16.[/b] Let $a_0, a_1, ...$ be an infinite sequence such that $a^2_n -a_{n-1}a_{n+1} = a_n -a_{n-1}$ for all positive integers $n$. Given that $a_0 = 1$ and $a_1 = 4$, compute the smallest positive integer $k$ such that $a_k$ is an integer multiple of $220$. [b]p17.[/b] Vincent the Bug is on an infinitely long number line. Every minute, he jumps either $2$ units to the right with probability $\frac23$ or $3$ units to the right with probability $\frac13$ . The probability that Vincent never lands exactly $15$ units from where he started can be expressed as $\frac{p}{q}$ where $p$ and $q$ are relatively prime positive integers. What is $p + q$? [b]p18.[/b] Battler and Beatrice are playing the “Octopus Game.” There are $2022$ boxes lined up in a row, and inside one of the boxes is an octopus. Beatrice knows the location of the octopus, but Battler does not. Each turn, Battler guesses one of the boxes, and Beatrice reveals whether or not the octopus is contained in that box at that time. Between turns, the octopus teleports to an adjacent box and secretly communicates to Beatrice where it teleported to. Find the least positive integer $B$ such that Battler has a strategy to guarantee that he chooses the box containing the octopus in at most $B$ guesses. [u]Round 7[/u] [b]p19.[/b] Given that $f(x) = x^2-2$ the number $f(f(f(f(f(f(f(2.5)))))))$ can be expressed as $\frac{a}{b}$ for relatively prime positive integers $a$ and $b$. Find the greatest positive integer $n$ such that $2^n$ divides $ab+a+b-1$. [b]p20.[/b] In triangle $ABC$, the shortest distance between a point on the $A$-excircle $\omega$ and a point on the $B$-excircle $\Omega$ is $2$. Given that $AB = 5$, the sum of the circumferences of $\omega$ and $\Omega$ can be written in the form $\frac{m}{n}\pi$, where $m$ and $n$ are relatively prime positive integers. What is $m+n$? (Note: The $A$-excircle is defined to be the circle outside triangle $ABC$ that is tangent to the rays $\overrightarrow{AB}$ and $\overrightarrow{AC}$ and to the side $ BC$. The $B$-excircle is defined similarly for vertex $B$.) [b]p21.[/b] Let $a_0, a_1, ...$ be an infinite sequence such that $a_0 = 1$, $a_1 = 1$, and there exists two fixed integer constants $x$ and $y$ for which $a_{n+2}$ is the remainder when $xa_{n+1}+ya_n$ is divided by $15$ for all nonnegative integers $n$. Let $t$ be the least positive integer such that $a_t = 1$ and $a_{t+1} = 1$ if such an integer exists, and let $t = 0$ if such an integer does not exist. Find the maximal value of t over all possible ordered pairs $(x, y)$. [u]Round 8[/u] [b]p22.[/b] A mystic square is a $3$ by $3$ grid of distinct positive integers such that the least common multiples of the numbers in each row and column are the same. Let M be the least possible maximal element in a mystic square and let $N$ be the number of mystic squares with $M$ as their maximal element. Find $M + N$. [b]p23.[/b] In triangle $ABC$, $AB = 27$, $BC = 23$, and $CA = 34$. Let $X$ and $Y$ be points on sides $ AB$ and $AC$, respectively, such that $BX = 16$ and $CY = 7$. Given that $O$ is the circumcenter of $BXY$ , the value of $CO^2$ can be written as $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Compute $m + n$. [b]p24.[/b] Alan rolls ten standard fair six-sided dice, and multiplies together the ten numbers he obtains. Given that the probability that Alan’s result is a perfect square is $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers, compute $a$. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2949416p26408251]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For a set $S$ of nonnegative integers, let $r_S(n)$ denote the number of ordered pairs $(s_1, s_2)$ such that $s_1 \in S$, $s_2 \in S$, $s_1 \neq s_2$, and $s_1 + s_2 = n$. Is it possible to partition the nonnegative integers into two sets $A$ and $B$ in such a way that $r_A(n) = r_B(n)$ for all $n$?

All $n$-digit words from the alphabet $\{0, 1\}$ considered. These $2^n$ words should be in a sequence $w_0, w_1, w_2, ..., w_{2^-1}$ be arranged that $w_m$ from $w_{m-1}$ by changing of a single ornament ($m = 1, 2, 3, ..., 2n-1$). Prove that the following algorithm achievesthis : a) Start with $w_0 = 000... 00$. b) Let $w_{m-1} = a_1a_2a_3 ... a_n$ with $a_i \in \{0; 1\}$, $i = 1, 2, 3, ..., n$. Determine the exponent $e(m)$ of the highest power of two dividing $m$ and set $j = e(m)+1$. In $w_{m-1}$ replace the ornament $a_j$ with $1-aj$. this is now $w_m$.

For what values of $ n$ does there exist an $ n \times n$ array of entries -1, 0 or 1 such that the $ 2 \cdot n$ sums obtained by summing the elements of the rows and the columns are all different?

There are two numbers on a board, $1/2009$ and $1/2008$. Alex and Ben play the following game. At each move, Alex names a number $x$ (of his choice), while Ben responds by increasing one of the numbers on the board (of his choice) by $x$. Alex wins if at some moment one of the numbers on the board becomes $1$. Can Alex win (no matter how Ben plays)?

Given 10 light switches, each can be in two states: on and off. For each pair of switches there is a light bulb which is on if and only if when both switches are on (45 bulbs in total). The bulbs and the switches are unmarked so it is unclear which switches correspond to which bulb. In the beginning all switches are off. How many flips are needed to find out regarding all bulbs which switches are connected to it? On each step you can flip precisely one switch

In a mathematical competition, in which $6$ problems were posed to the participants, every two of these problems were solved by more than $\frac 25$ of the contestants. Moreover, no contestant solved all the $6$ problems. Show that there are at least $2$ contestants who solved exactly $5$ problems each. [i]Radu Gologan and Dan Schwartz[/i]

[b]p1.[/b] Compute $2017 + 7201 + 1720 + 172$. [b]p2. [/b]A number is called [i]downhill [/i]if its digits are distinct and in descending order. (For example, $653$ and $8762$ are downhill numbers, but $97721$ is not.) What is the smallest downhill number greater than 86432? [b]p3.[/b] Each vertex of a unit cube is sliced off by a planar cut passing through the midpoints of the three edges containing that vertex. What is the ratio of the number of edges to the number of faces of the resulting solid? [b]p4.[/b] In a square with side length $5$, the four points that divide each side into five equal segments are marked. Including the vertices, there are $20$ marked points in total on the boundary of the square. A pair of distinct points $A$ and $B$ are chosen randomly among the $20$ points. Compute the probability that $AB = 5$. [b]p5.[/b] A positive two-digit integer is one less than five times the sum of its digits. Find the sum of all possible such integers. [b]p6.[/b] Let $$f(x) = 5^{4^{3^{2^{x}}}}.$$ Determine the greatest possible value of $L$ such that $f(x) > L$ for all real numbers $x$. [b]p7.[/b] If $\overline{AAAA}+\overline{BB} = \overline{ABCD}$ for some distinct base-$10$ digits $A, B, C, D$ that are consecutive in some order, determine the value of $ABCD$. (The notation $\overline{ABCD}$ refers to the four-digit integer with thousands digit $A$, hundreds digit $B$, tens digit $C$, and units digit $D$.) [b]p8.[/b] A regular tetrahedron and a cube share an inscribed sphere. What is the ratio of the volume of the tetrahedron to the volume of the cube? [b]p9.[/b] Define $\lfloor x \rfloor$ as the greatest integer less than or equal to x, and ${x} = x - \lfloor x \rfloor$ as the fractional part of $x$. If $\lfloor x^2 \rfloor =2 \lfloor x \rfloor$ and $\{x^2\} =\frac12 \{x\}$, determine all possible values of $x$. [b]p10.[/b] Find the largest integer $N > 1$ such that it is impossible to divide an equilateral triangle of side length $ 1$ into $N$ smaller equilateral triangles (of possibly different sizes). [b]p11.[/b] Let $f$ and $g$ be two quadratic polynomials. Suppose that $f$ has zeroes $2$ and $7$, $g$ has zeroes $1$ and $ 8$, and $f - g$ has zeroes $4$ and $5$. What is the product of the zeroes of the polynomial $f + g$? [b]p12.[/b] In square $PQRS$, points $A, B, C, D, E$, and $F$ are chosen on segments $PQ$, $QR$, $PR$, $RS$, $SP$, and $PR$, respectively, such that $ABCDEF$ is a regular hexagon. Find the ratio of the area of $ABCDEF$ to the area of $PQRS$. [b]p13.[/b] For positive integers $m$ and $n$, define $f(m, n)$ to be the number of ways to distribute $m$ identical candies to $n$ distinct children so that the number of candies that any two children receive differ by at most $1$. Find the number of positive integers n satisfying the equation $f(2017, n) = f(7102, n)$. [b]p14.[/b] Suppose that real numbers $x$ and $y$ satisfy the equation $$x^4 + 2x^2y^2 + y^4 - 2x^2 + 32xy - 2y^2 + 49 = 0.$$ Find the maximum possible value of $\frac{y}{x}$. [b]p15.[/b] A point $P$ lies inside equilateral triangle $ABC$. Let $A'$, $B'$, $C'$ be the feet of the perpendiculars from $P$ to $BC, AC, AB$, respectively. Suppose that $PA = 13$, $PB = 14$, and $PC = 15$. Find the area of $A'B'C'$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Points $ A_1,A_2,...,A_n$ and $ B_1,B_2,...,B_n$ are given on a plane. Show that the points $ B_i$ can be renumbered in such a way that the angle between vectors $ A_iA_j^{\longrightarrow}$ and $ B_iB_j^{\longrightarrow}$ is acute or right whenever $ i\neq j$.