In the coordinate plane a rectangle with vertices $ (0, 0),$ $ (m, 0),$ $ (0, n),$ $ (m, n)$ is given where both $ m$ and $ n$ are odd integers. The rectangle is partitioned into triangles in such a way that [i](i)[/i] each triangle in the partition has at least one side (to be called a “good” side) that lies on a line of the form $ x \equal{} j$ or $ y \equal{} k,$ where $ j$ and $ k$ are integers, and the altitude on this side has length 1; [i](ii)[/i] each “bad” side (i.e., a side of any triangle in the partition that is not a “good” one) is a common side of two triangles in the partition. Prove that there exist at least two triangles in the partition each of which has two good sides.

Among $239$ coins identical in appearance there are two counterfeit coins. Both counterfeit coins have the same weight different from the weight of a genuine coin. Using a simple balance, determine in three weighings whether the counterfeit coin is heavier or lighter than the genuine coin. A simple balance shows if both sides are in equilibrium or left side is heavier or lighter. It is not required to find the counterfeit coins.

There are $1,000,000$ piles of $1996$ coins in each of them, and in one pile there are only fake coins, and in all the others - only real ones. What is the smallest weighing number that can be used to determine a heap containing counterfeit coins if the scales used have one bowl and allow weighing as much weight as desired with an accuracy of one gram, and it is also known that each counterfeit coin weighs $9$ grams, and each real coin weighs $10$ grams?

Compute the number of triples $(f,g,h)$ of permutations on $\{1,2,3,4,5\}$ such that \begin{align*} & f(g(h(x))) = h(g(f(x))) = g(x) \\ & g(h(f(x))) = f(h(g(x))) = h(x), \text{ and } \\ & h(f(g(x))) = g(f(h(x))) = f(x), \\ \end{align*} for all $x\in \{1,2,3,4,5\}$.

How many paths from $(0,0)$ to $(n,n)$ of length $2n$ are there with exactly $k$ steps. A step is an occurence of the pair $EN$ in the path

There are 100 visually identical coins of three types: golden, silver and copper. There is at least one coin of each type. Each golden coin weighs 3 grams, each silver coins weighs 2 grams and each copper coin weighs 1 gram. How to find the type of each coin performing no more than 101 measurements on a balance scale with no weights.

100 volleyball teams played a one-round tournament. No two matches held at the same time. It turned out that before each match the teams playing against each other had the same number of wins. Find all possible number of wins for the winner of this tournament.

There are $ 2000 $ people, and some of them have called each other. Two people can call each other at most $1$ time. For any two groups of three people $ A$ and $ B $ which $ A \cap B = \emptyset $, there exist one person from each of $A$ and $B$ that haven't called each other. Prove that the number of two people called each other is less than $ 201000 $.

A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual). Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours.

On an infinite checkered plane $100$ chips in form of a $10\times 10$ square are given. These chips are rearranged such that any two adjacent (by side) chips are again adjacent, moreover no two chips are in the same cell. Prove that the chips are again in form of a square.

A regular $2018$-gon is inscribed in a circle. The numbers $1, 2, ..., 2018$ are arranged on the vertices of the $2018$-gon, with each vertex having one number on it, such that the sum of any $2$ neighboring numbers ($2$ numbers are neighboring if the vertices they are on lie on a side of the polygon) equals the sum of the $2$ numbers that are on the antipodes of those $2$ vertices (with respect to the given circle). Determine the number of different arrangements of the numbers. (Two arrangements are identical if you can get from one of them to the other by rotating around the center of the circle).

Let $M=\{1,2,\ldots,3 \cdot n\}$. Partition $M$ into three sets $A,B,C$ which $card$ $A$ $=$ $card$ $B$ $=$ $card$ $C$ $=$ $n .$ Prove that there exists $a$ in $A,b$ in $B, c$ in $C$ such that or $a=b+c,$ or $b=c+a,$ or $c=a+b$ [i]Edited by orl.[/i]

[u]Round 6[/u] [b]p16.[/b] Let $a_1, a_2, ... , a_{2011}$ be a sequence of numbers such that $a_1 = 2011$ and $a_1+a_2+...+a_n = n^2 \cdot a_n$ for $n = 1, 2, ... 2011$. (That is, $a_1 = 1^2\cdot a_1$, $a_1 + a_2 = 2^2 \cdot a_2$, $...$) Compute $a_{2011}$. [b]p17.[/b] Three rectangles, with dimensions $3 \times 5$, $4 \times 2$, and $6 \times 4$, are each divided into unit squares which are alternately colored black and white like a checkerboard. Each rectangle is cut along one of its diagonals into two triangles. For each triangle, let m be the total black area and n the total white area. Find the maximum value of $|m - n|$ for the $6$ triangles. [b]p18.[/b] In triangle $ABC$, $\angle BAC = 90^o$, and the length of segment $AB$ is $2011$. Let $M$ be the midpoint of $BC$ and $D$ the midpoint of $AM$. Let $E$ be the point on segment $AB$ such that $EM \parallel CD$. What is the length of segment $BE$? [u]Round 7[/u] [b]p19.[/b] How many integers from $1$ to $100$, inclusive, can be expressed as the difference of two perfect squares? (For example, $3 = 2^2 - 1^2$). [b]p20.[/b] In triangle $ABC$, $\angle ABC = 45$ and $\angle ACB = 60^o$. Let $P$ and $Q$ be points on segment $BC$, $F$ a point on segment $AB$, and $E$ a point on segment $AC$ such that $F Q \parallel AC$ and $EP \parallel AB$. Let $D$ be the foot of the altitude from $A$ to $BC$. The lines $AD$, $F Q$, and $P E$ form a triangle. Find the positive difference, in degrees, between the largest and smallest angles of this triangle. [b]p21.[/b] For real number $x$, $\lceil x \rceil$ is equal to the smallest integer larger than or equal to $x$. For example, $\lceil 3 \rceil = 3$ and $\lceil 2.5 \rceil = 3$. Let $f(n)$ be a function such that $f(n) = \left\lceil \frac{n}{2}\right\rceil + f\left( \left\lceil \frac{n}{2}\right\rceil\right)$ for every integer $n$ greater than $1$. If $f(1) = 1$, find the maximum value of $f(k) - k$, where $k$ is a positive integer less than or equal to $2011$. [u]Round 8[/u] The answer to each of the three questions in this round depends on the answer to one of the other questions. There is only one set of correct answers to these problems; however, each question will be scored independently, regardless of whether the answers to the other questions are correct. [b]p22.[/b] Let $W$ be the answer to problem 24 in this guts round. Let $f(a) = \frac{1}{1 -\frac{1}{1- \frac{1}{a}}}$. Determine$|f(2) + ... + f(W)|$. [b]p23.[/b] Let $X$ be the answer to problem $22$ in this guts round. How many odd perfect squares are less than $8X$? [b]p24.[/b] Let $Y$ be the answer to problem $23$ in this guts round. What is the maximum number of points of intersections of two regular $(Y - 5)$-sided polygons, if no side of the first polygon is parallel to any side of the second polygon? [u]Round 9[/u] [b]p25.[/b] Cross country skiers $s_1, s_2, s_3, ..., s_7$ start a race one by one in that order. While each skier skis at a constant pace, the skiers do not all ski at the same rate. In the course of the race, each skier either overtakes another skier or is overtaken by another skier exactly two times. Find all the possible orders in which they can finish. Write each possible finish as an ordered septuplet $(a, b, c, d, e, f, g)$ where $a, b, c, d, e, f, g$ are the numbers $1-7$ in some order. (So a finishes first, b finishes second, etc.) [b]p26.[/b] Archie the Alchemist is making a list of all the elements in the world, and the proportion of earth, air, fire, and water needed to produce each. He writes the proportions in the form E:A:F:W. If each of the letters represents a whole number from $0$ to $4$, inclusive, how many different elements can Archie list? Note that if Archie lists wood as $2:0:1:2$, then $4:0:2:4$ would also produce wood. In addition, $0:0:0:0$ does not produce an element. [b]p27.[/b] Let $ABCD$ be a rectangle with $AB = 10$ and $BC = 12$. Let $M$ be the midpoint of $CD$, and $P$ be the point on $BM$ such that $DP = DA$. Find the area of quadrilateral $ABPD$. [u]Round 10[/u] [b]p28.[/b] David the farmer has an infinitely large grass-covered field which contains a straight wall. He ties his cow to the wall with a rope of integer length. The point where David ties his rope to the wall divides the wall into two parts of length $a$ and $b$, where $a > b$ and both are integers. The rope is shorter than the wall but is longer than $a$. Suppose that the cow can reach grass covering an area of $\frac{165\pi}{2}$. Find the ratio $\frac{a}{b}$ . You may assume that the wall has $0$ width. [b]p29.[/b] Let $S$ be the number of ordered quintuples $(a, b, x, y, n)$ of positive integers such that $$\frac{a}{x}+\frac{b}{y}=\frac{1}{n}$$ $$abn = 2011^{2011}$$ Compute the remainder when $S$ is divided by $2012$. [b]p30.[/b] Let $n$ be a positive integer. An $n \times n$ square grid is formed by $n^2$ unit squares. Each unit square is then colored either red or blue such that each row or column has exactly $10$ blue squares. A move consists of choosing a row or a column, and recolor each unit square in the chosen row or column – if it is red, we recolor it blue, and if it is blue, we recolor it red. Suppose that it is possible to obtain fewer than $10n$ blue squares after a sequence of finite number of moves. Find the maximum possible value of $n$. PS. You should use hide for answers. First rounds have been posted [url=https://artofproblemsolving.com/community/c4h2786905p24497746]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Some cells of an infinite chessboard (infinite in all directions) are coloured blue so that at least one of the $100$ cells in any $10 \times 10$ rectangular grid is blue. Prove that, for any positive integer $n$, it is possible to select $n$ rows and $n$ columns so that all of the $n^2$ cells in their intersections are blue.

There is a connected network with $ 2008$ computers, in which any of the two cycles don't have any common vertex. A hacker and a administrator are playing a game in this network. On the $ 1st$ move hacker selects one computer and hacks it, on the $ 2nd$ move administrator selects another computer and protects it. Then on every $ 2k\plus{}1th$ move hacker hacks one more computer(if he can) which wasn't protected by the administrator and is directly connected (with an edge) to a computer which was hacked by the hacker before and on every $ 2k\plus{}2th$ move administrator protects one more computer(if he can) which wasn't hacked by the hacker and is directly connected (with an edge) to a computer which was protected by the administrator before for every $ k>0$. If both of them can't make move, the game ends. Determine the maximum number of computers which the hacker can guarantee to hack at the end of the game.

How many ways are there to express 1000000 as a product of exactly three integers greater than 1? (For the purpose of this problem, $abc$ is not considered different from $bac$, etc.)

Let $C$ be a fixed circle, $u > 0$ be a fixed real and let $v_0 , v_1 , v_2 , \ldots$ be a sequence of positive real numbers. Two ants $A$ and $B$ walk around the perimeter of $C$ in opposite directions, starting from the same starting point. Ant $A$ has a constant speed $u$, while ant $B$ has an initial speed $v_0$. For each positive integer $n$, when the two ants collide for the $n$−th time, they change the directions in which they walk around the perimeter of $C$, with ant $A$ remaining at speed $u$ and ant $B$ stops walking at speed $v_{n-1}$ to walk at speed $v_n$. (a) If the sequence $\{v_n\}$ is strictly increasing, with $\lim_{n\rightarrow \infty} v_n = +\infty$, prove that there is exactly one point in $C$ that ant $A$ will pass "infinitely" many times. (b) Prove that there is a sequence $\{v_n\}$ with $\lim_{n\rightarrow\infty} v_n = +\infty$, such that ant $A$ will pass "infinitely" many times through all points on the circle $C$.

Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

We have $ n \geq 2$ lamps $ L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $ L_{i}$ and its neighbours (only one neighbour for $ i \equal{} 1$ or $ i \equal{} n$, two neighbours for other $ i$) are in the same state, then $ L_{i}$ is switched off; – otherwise, $ L_{i}$ is switched on. Initially all the lamps are off except the leftmost one which is on. $ (a)$ Prove that there are infinitely many integers $ n$ for which all the lamps will eventually be off. $ (b)$ Prove that there are infinitely many integers $ n$ for which the lamps will never be all off.

[b]p1.[/b] Ana, Bob, Cho, Dan, and Eve want to use a microwave. In order to be fair, they choose a random order to heat their food in (all orders have equal probability). Ana's food needs $5$ minutes to cook, Bob's food needs $7$ minutes, Cho's needs $1$ minute, Dan's needs $12$ minutes, and Eve's needs $5$ minutes. What is the expected number of minutes Bob has to wait for his food to be done? [b]p2.[/b] $ABC$ is an equilateral triangle. $H$ lies in the interior of $ABC$, and points $X$, $Y$, $Z$ lie on sides $AB, BC, CA$, respectively, such that $HX\perp AB$, $HY \perp BC$, $HZ\perp CA$. Furthermore, $HX =2$, $HY = 3$, $HZ = 4$. Find the area of triangle $ABC$. [b]p3.[/b] Amy, Ben, and Chime play a dice game. They each take turns rolling a die such that the $first$ person to roll one of his favorite numbers wins. Amy's favorite number is $1$, Ben's favorite numbers are $2$ and $3$, and Chime's are $4$, $5$, and $6$. Amy rolls first, Ben rolls second, and Chime rolls third. If no one has won after Chime's turn, they repeat the sequence until someone has won. What's the probability that Chime wins the game? [b]p4.[/b] A point $P$ is chosen randomly in the interior of a square $ABCD$. What is the probability that the angle $\angle APB$ is obtuse? [b]p5.[/b] Let $ABCD$ be the quadrilateral with vertices $A = (3, 9)$, $B = (1, 1)$, $C = (5, 3)$, and $D = (a, b)$, all of which lie in the first quadrant. Let $M$ be the midpoint of $AB$, $N$ the midpoint of $BC$, $O$ the midpoint of $CD$, and $P$ the midpoint of $AD$. If $MNOP$ is a square, find $(a, b)$. [b]p6.[/b] Let $M$ be the number of positive perfect cubes that divide $60^{60}$. What is the prime factorization of $M$? [b]p7.[/b] Given that $x$, $y$, and $z$ are complex numbers with $|x|=|y| =|z|= 1$, $x + y + z = 1$ and $xyz = 1$, find $|(x + 2)(y + 2)(z + 2)|$. [b]p8.[/b] If $f(x)$ is a polynomial of degree $2008$ such that $f(m) = \frac{1}{m}$ for $m = 1, 2, ..., 2009$, find $f(2010)$. [b]p9.[/b] A drunkard is randomly walking through a city when he stumbles upon a $2 \times 2$ sliding tile puzzle. The puzzle consists of a $2 \times 2$ grid filled with a blank square, as well as $3$ square tiles, labeled $1$, $2$, and $3$. During each turn you may fill the empty square by sliding one of the adjacent tiles into it. The following image shows the puzzle's correct state, as well as two possible moves you can make: [img]https://cdn.artofproblemsolving.com/attachments/c/6/7ddd9305885523deeee2a530dc90505875d1cc.png[/img] Assuming that the puzzle is initially in an incorrect (but solvable) state, and that the drunkard will make completely random moves to try and solve it, how many moves is he expected to make before he restores the puzzle to its correct state? [b]p10.[/b] How many polynomials $p(x)$ exist such that the coeffients of $p(x)$ are a rearrangement of $\{0, 1, 2, .., deg \, p(x)\}$ and all of the roots of $p(x)$ are rational? (Note that the leading coefficient of $p(x)$ must be nonzero.) PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In some tournament there were $8$ players. Every two players played exactly one match, each of them finished with the win of one of the players or with a draw. Winner of the match got $2$ points, his opponent $0$ points and in the case of draw every player got $1$ point. When all matches had finished it turned out that every player had the same number of points. Determine the minimal total numbers of draws.

In a badminton competition, $16$ players participate, of which $10$ are professionals and $6$ are amateurs. In the first phase, eight games are drawn. Among the eight winners of these games, four games are drawn. The four winners qualify for the semi-finals of the competition. Assuming that, whenever a professional player and an amateur play each other, the professional wins the game, what is the probability that an amateur player will reach the semi-finals of the competition?

For an integer $n \geq 5,$ two players play the following game on a regular $n$-gon. Initially, three consecutive vertices are chosen, and one counter is placed on each. A move consists of one player sliding one counter along any number of edges to another vertex of the $n$-gon without jumping over another counter. A move is legal if the area of the triangle formed by the counters is strictly greater after the move than before. The players take turns to make legal moves, and if a player cannot make a legal move, that player loses. For which values of $n$ does the player making the first move have a winning strategy?

In an art museum, $n$ paintings are exhibited, where $n \geq 33.$ In total, $15$ colors are used for these paintings such that any two paintings have at least one common color, and no two paintings have exactly the same colors. Determine all possible values of $n \geq 33$ such that regardless of how we color the paintings with the given properties, we can choose four distinct paintings, which we can label as $T_1, T_2, T_3,$ and $T_4,$ such that any color that is used in both $T_1$ and $T_2$ can also be found in either $T_3$ or $T_4$.

An integer $n\geq 3$ is [i]poli-pythagorean[/i] if there exist $n$ positive integers pairwise distinct such that we can order these numbers in the vertices of a regular $n$-gon such that the sum of the squares of consecutive vertices is also a perfect square. For instance, $3$ is poli-pythagorean, because if we write $44,117,240$ in the vertices of a triangle we notice: $$44^2+117^2=125^2, 117^2+240^2=267^2, 240^2+44^2=244^2$$ Determine all poli-pythagorean integers.