On a chessboard of $16 \times 16$ squares, a "horse" moves making only movements of two types: from each square you can move either two squares to the right and one up, or two boxes up and one to the right. Determine in how many ways different the horse can move from the lower left square of the board to the top right box.

[u]Round 5[/u] [b]p13.[/b] Initially, the three numbers $20$, $201$, and $2016$ are written on a blackboard. Each minute, Zhuo selects two of the numbers on the board and adds $1$ to each. Find the minimum $n$ for which Zhuo can make all three numbers equal to $n$. [b]p14.[/b] Call a three-letter string rearrangeable if, when the first letter is moved to the end, the resulting string comes later alphabetically than the original string. For example, $AAA$ and $BAA$ are not rearrangeable, while $ABB$ is rearrangeable. How many three-letters strings with (not necessarily distinct) uppercase letters are rearrangeable? [b]p15.[/b] Triangle $ABC$ is an isosceles right triangle with $\angle C = 90^o$ and $AC = 1$. Points $D$, $E$ and $F$ are chosen on sides $BC$,$CA$ and $AB$, respectively, such that $AEF$, $BFD$, $CDE$, and $DEF$ are isosceles right triangles. Find the sum of all distinct possible lengths of segment $DE$. [u]Round 6[/u] [b]p16.[/b] Let $p, q$, and $r$ be prime numbers such that $pqr = 17(p + q + r)$. Find the value of the product $pqr$. [b]p17.[/b] A cylindrical cup containing some water is tilted $45$ degrees from the vertical. The point on the surface of the water closest to the bottom of the cup is $6$ units away. The point on the surface of the water farthest from the bottom of the cup is $10$ units away. Compute the volume of the water in the cup. [b]p18.[/b] Each dot in an equilateral triangular grid with $63$ rows and $2016 = \frac12 \cdot 63 \cdot 64$ dots is colored black or white. Every unit equilateral triangle with three dots has the property that exactly one of its vertices is colored black. Find all possible values of the number of black dots in the grid. [u]Round 7[/u] [b]p19.[/b] Tomasz starts with the number $2$. Each minute, he either adds $2$ to his number, subtracts $2$ from his number, multiplies his number by $2$, or divides his number by $2$. Find the minimum number of minutes he will need in order to make his number equal $2016$. [b]p20.[/b] The edges of a regular octahedron $ABCDEF$ are painted with $3$ distinct colors such that no two edges with the same color lie on the same face. In how many ways can the octahedron be painted? Colorings are considered different under rotation or reflection. [b]p21.[/b] Jacob is trapped inside an equilateral triangle $ABC$ and must visit each edge of triangle $ABC$ at least once. (Visiting an edge means reaching a point on the edge.) His distances to sides $AB$, $BC$, and $CA$ are currently $3$, $4$, and $5$, respectively. If he does not need to return to his starting point, compute the least possible distance that Jacob must travel. [u]Round 8[/u] [b]p22.[/b] Four integers $a, b, c$, and $d$ with a $\le b \le c \le d$ satisfy the property that the product of any two of them is equal to the sum of the other two. Given that the four numbers are not all equal, determine the $4$-tuple $(a, b, c, d)$. [b]p23.[/b] In equilateral triangle $ABC$, points $D$,$E$, and $F$ lie on sides $BC$,$CA$ and $AB$, respectively, such that $BD = 4$ and $CD = 5$. If $DEF$ is an isosceles right triangle with right angle at $D$, compute $EA + FA$. [b]p24.[/b] On each edge of a regular tetrahedron, four points that separate the edge into five equal segments are marked. There are sixteen planes that are parallel to a face of the tetrahedron and pass through exactly three of the marked points. When the tetrahedron is cut along each of these sixteen planes, how many new tetrahedrons are produced? PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2934049p26256220]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Two magicians are performing the following game. Initially the first magician encloses the second magician in a cabin where he can neither see nor hear anything. To start the game, the first magician invites Daniel, from the audience, to put on each square of a chessboard $n \times n$, at his (Daniel's) discretion, a token black or white. Then the first magician asks Daniel to show him a square $C$ of his own choice. At this point, the first magician chooses a square $D$ (not necessarily different from $C$) and replaces the token that is on $D$ with other color token (white with black or black with white). Then he opens the cabin in which the second magician was held. Looking at the chessboard, the second magician guesses what is the square $C$. For what value of $n$, the two magicians have a strategy such that the second magician makes a successful guess.

Given a matrix $\{a_{ij}\}_{i,j=0}^{9}$, $a_{ij}=10i+j+1$. Andrei is going to cover its entries by $50$ rectangles $1\times 2$ (each such rectangle contains two adjacent entries) so that the sum of $50$ products in these rectangles is minimal possible. Help him. [i]A. Badzyan[/i]

Each square of a chessboard is painted either blue or red . Prove that the squares of one colour possess the property that the chess queen can perform a tour of all of them. The rules are that the queen may visit the squares of this colour not necessarily only once each , and may not be placed on squares of the other colour, although she may pass over them ; the queen moves along any horizontal , vertical or diagonal file over any distance. (A . K . Tolpugo , Kiev)

Consider any rectangular table having finitely many rows and columns, with a real number $a(r, c)$ in the cell in row $r$ and column $c$. A pair $(R, C)$, where $R$ is a set of rows and $C$ a set of columns, is called a [i]saddle pair[/i] if the following two conditions are satisfied: [list] [*] $(i)$ For each row $r^{\prime}$, there is $r \in R$ such that $a(r, c) \geqslant a\left(r^{\prime}, c\right)$ for all $c \in C$; [*] $(ii)$ For each column $c^{\prime}$, there is $c \in C$ such that $a(r, c) \leqslant a\left(r, c^{\prime}\right)$ for all $r \in R$. [/list] A saddle pair $(R, C)$ is called a [i]minimal pair[/i] if for each saddle pair $\left(R^{\prime}, C^{\prime}\right)$ with $R^{\prime} \subseteq R$ and $C^{\prime} \subseteq C$, we have $R^{\prime}=R$ and $C^{\prime}=C$. Prove that any two minimal pairs contain the same number of rows.

For a rational number $r$, its *period* is the length of the smallest repeating block in its decimal expansion. for example, the number $r=0.123123123...$ has period $3$. If $S$ denotes the set of all rational numbers of the form $r=\overline{abcdefgh}$ having period $8$, find the sum of all elements in $S$.

Baron Minchausen talked to a mathematician. Baron said that in his country from any town one can reach any other town by a road. Also, if one makes a circular trip from any town, one passes through an odd number of other towns. By this, as an answer to the mathematician’s question, Baron said that each town is counted as many times as it is passed through. Baron also added that the same number of roads start at each town in his country, except for the town where he was born, at which a smaller number of roads start. Then the mathematician said that baron lied. How did he conclude that?

$25$ boys and $25$ girls sit around a table. Show that there is a person who has a girl sitting on either side of them.

In Duckville there is a perpetual trophy with the words “Best child of Duckville” engraved on it. Each inhabitant of Duckville has a non-empty list (which never changes) of other inhabitants of Duckville. Whoever receives the trophy gets to keep it for one day, and then passes it on to someone on their list the next day. Gregers has previously received the trophy. It turns out that each time he does receive it, he is guaranteed to receive it again exactly $2025$ days later (but perhaps earlier, as well). Hedvig received the trophy today. Determine all integers $n>0$ for which we can be absolutely certain that she cannot receive the trophy again in $n$ days, given the above information.

The National Foundation of Happiness (NFoH) wants to estimate the happiness of people of country. NFoH selected $n$ random persons, and on every morning asked from each of them whether she is happy or not. On any two distinct days, exactly half of the persons gave the same answer. Show that after $k$ days, there were at most $n-\frac{n}{k}$ persons whose “yes” answers equals their “no” answers.

Along the direct highway Tmutarakan - Uryupinsk at points $ A_1 $, $ A_2 $, $ \dots $, $ A_ {100} $ are the towers of the DPS mobile operator, and in points $ B_1 $, $ B_2 $, $ \dots $, $ B_ {100} $ are the towers of the "Horn" company. (Tower numbering may not coincide with the order of their location along the highway.) Each tower operates at a distance of $10$ km in both directions along the highway. It is known that $ A_iA_k \geq B_iB_k $ for any $ i $, $ k \leq 100 $. Prove that the total length of all sections of the highway covered by the DPS network is not less than the length of the sections covered by the Horn network .

A board $ n \times n$ ($n \ge 3$) is divided into $n^2$ unit squares. Integers from $O$ to $n$ included, are written down: one integer in each unit square, in such a way that the sums of integers in each $2\times 2$ square of the board are different. Find all $n$ for which such boards exist.

In an exotic country, the National Bank issues coins that can take any value in the interval $[0, 1]$. Find the smallest constant $c > 0$ such that the following holds, no matter the situation in that country: [i]Any citizen of the exotic country that has a finite number of coins, with a total value of no more than $1000$, can split those coins into $100$ boxes, such that the total value inside each box is at most $c$.[/i]

A convex polyhedron has $m$ triangular faces (there can be faces of other kind too). From each vertex there are exactly 4 edges. Find the least possible value of $m$.

[b]p1.[/b] The Evergreen School booked buses for a field trip. Altogether, $138$ people went to West Lake, while $115$ people went to East Lake. The buses all had the same number of seats and every bus has more than one seat. All seats were occupied and everybody had a seat. How many seats were on each bus? [b]p2.[/b] In New Scotland there are three kinds of coins: $1$ cent, $6$ cent, and $36$ cent coins. Josh has $99$ of the $36$-cent coins (and no other coins). He is allowed to exchange a $36$ cent coin for $6$ coins of $6$ cents, and to exchange a $6$ cent coin for $6$ coins of $1$ cent. Is it possible that after several exchanges Josh will have $500$ coins? [b]p3.[/b] Find all solutions $a, b, c, d, e, f, g, h$ if these letters represent distinct digits and the following multiplication is correct: $\begin{tabular}{ccccc} & & a & b & c \\ + & & & d & e \\ \hline & f & a & g & c \\ x & b & b & h & \\ \hline f & f & e & g & c \\ \end{tabular}$ [b]p4.[/b] Is it possible to find a rectangle of perimeter $10$ m and cut it in rectangles (as many as you want) so that the sum of the perimeters is $500$ m? [b]p5.[/b] The picture shows a maze with chambers (shown as circles) and passageways (shown as segments). A cat located in chamber $C$ tries to catch a mouse that was originally in the chamber $M$. The cat makes the first move, moving from chamber $C$ to one of the neighboring chambers. Then the mouse moves, then the cat, and so forth. At each step, the cat and the mouse can move to any neighboring chamber or not move at all. The cat catches the mouse by moving into the chamber currently occupied by the mouse. Can the cat get the mouse? [img]https://cdn.artofproblemsolving.com/attachments/9/9/25f61e1499ff1cfeea591cb436d33eb2cdd682.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

An [i]anti-Pascal[/i] triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following is an anti-Pascal triangle with four rows which contains every integer from $1$ to $10$. \[\begin{array}{ c@{\hspace{4pt}}c@{\hspace{4pt}} c@{\hspace{4pt}}c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{4pt}}c } \vspace{4pt} & & & 4 & & & \\\vspace{4pt} & & 2 & & 6 & & \\\vspace{4pt} & 5 & & 7 & & 1 & \\\vspace{4pt} 8 & & 3 & & 10 & & 9 \\\vspace{4pt} \end{array}\] Does there exist an anti-Pascal triangle with $2018$ rows which contains every integer from $1$ to $1 + 2 + 3 + \dots + 2018$? [i]Proposed by Morteza Saghafian, Iran[/i]

There are $11$ empty boxes. In one move, a player can put one coin in each of some $10$ boxes. Two people play, taking turns. The winner is the player after whose move in one of the boxes there will be $21$ coins. Who has a winning strategy?

[u]Round 1 [/u] [b]p1. [/b]Twelve people, some are knights and some are knaves, are sitting around a table. Knaves always lie and knights always tell the truth. At some point they start up a conversation. The first person says, “There are no knights around this table.” The second says, “There is at most one knight at this table.” The third – “There are at most two knights at the table.” And so on until the 12th says, “There are at most eleven knights at the table.” How many knights are at the table? Justify your answer. [b]p2.[/b] Show that in the sequence $10017$, $100117$, $1001117$, $...$ all numbers are divisible by $53$. [b]p3.[/b] Harry and Draco have three wands: a bamboo wand, a willow wand, and a cherry wand, all of the same length. They must perform a spell wherein they take turns picking a wand and breaking it into three parts – first Harry, then Draco, then Harry again. But in order for the spell to work, Harry has to make sure it is possible to form three triangles out of the pieces of the wands, where each triangle has a piece from each wand. How should he break the wands to ensure the success of the spell? [b]p4.[/b] A $2\times 2\times 2$ cube has $4$ equal squares on each face. The squares that share a side are called neighbors (thus, each square has $4$ neighbors – see picture). Is it possible to write an integer in each square in such a way that the sum of each number with its $4$ neighbors is equal to $13$? If yes, show how. If no, explain why not. [img]https://cdn.artofproblemsolving.com/attachments/8/4/0f7457f40be40398dee806d125ba26780f9d3a.png[/img] [b]p5.[/b] Two girls are playing a game. The first player writes the letters $A$ or $B$ in a row, left to right, adding one letter on her turn. The second player switches any two letters after each move by the first player (the letters do not have to be adjacent), or does nothing, which also counts as a move. The game is over when each player has made $2011$ moves. Can the second player plan her moves so that the resulting letters form a palindrome? (A palindrome is a sequence that reads the same forward and backwards, e.g. $AABABAA$.) [u]Round 2 [/u] [b]p6.[/b] A red square is placed on a table. $2010$ white squares, each the same size as the red square, are then placed on the table in such a way that the red square is fully covered and the sides of every white square are parallel to the sides of the red square. Is it always possible to remove one of the white squares so the red square remains completely covered? [b]p7.[/b] A computer starts with a given positive integer to which it randomly adds either $54$ or $77$ every second and prints the resulting sum after each addition. For example, if the computer is given the number $1$, then a possible output could be: $1$, $55$, $109$, $186$, $…$ Show that after finitely many seconds the computer will print a number whose last two digits are the same. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be a positive integer relatively prime to $6$. We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

In the unit squares of a transparent $1 \times 100$ tape, numbers $1,2,\cdots,100$ are written in the ascending order.We fold this tape on it's lines with arbitrary order and arbitrary directions until we reach a $1 \times1$ tape with $100$ layers.A permutation of the numbers $1,2,\cdots,100$ can be seen on the tape, from the top to the bottom. Prove that the number of possible permutations is between $2^{100}$ and $4^{100}$. ([i]e.g.[/i] We can produce all permutations of numbers $1,2,3$ with a $1\times3$ tape) [i]Proposed by Morteza Saghafian[/i]

A subset $S$ of the set of integers 0 - 99 is said to have property $A$ if it is impossible to fill a crossword-puzzle with 2 rows and 2 columns with numbers in $S$ (0 is written as 00, 1 as 01, and so on). Determine the maximal number of elements in the set $S$ with the property $A.$

Several points on the plane are given, no three of them lie on the same line. Some of these points are connected by line segments. Assume that any line that does not pass through any of these points intersects an even number of these segments. Prove that from each point exits an even number of the segments.

In a $9\times 9$ table, all cells contain zeros. The following operations can be performed on the table: 1. Choose an arbitrary row, add one to all the numbers in that row, and shift all these numbers one cell to the right (and place the last number in the first position). 2. Choose an arbitrary column, subtract one from all its numbers, and shift all these numbers one cell down (and place the bottommost number in the top cell). Is it possible to obtain a table in which all cells, except two, contain zeros, with 1 in the bottom-left cell and -1 in the top-right cell after several such operations? [i]Proposed by N. Vlasova[/i]

You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.