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]

Given a positive integer $n\geq 2$. Let $A=\{ (a,b)\mid a,b\in \{ 1,2,…,n\} \}$ be the set of points in Cartesian coordinate plane. How many ways to colour points in $A$, each by one of three fixed colour, such that, for any $a,b\in \{ 1,2,…,n-1\}$, if $(a,b)$ and $(a+1,b)$ have same colour, then $(a,b+1)$ and $(a+1,b+1)$ also have same colour.

Konstantin moves a knight on a $n \times n$- chess board from the lower left corner to the lower right corner with the minimal number of moves. Then Isabelle takes the knight and moves it from the lower left corner to the upper right corner with the minimal number of moves. For which values of $n$ do they need the same number of moves?

Two players take turns playing on a $3\times1001$ board whose squares are initially all white. Each player, in his turn, paints two squares located in the same row or column black, not necessarily adjacent. The player who cannot make his move loses the game. Determine which of the two players has a strategy that allows them to win, no matter how well his opponent plays.

We have big multivolume encyclopaedia about dogs on the shelf in alphabetical order, each volume in its specially selected place. Near each place there is an instruction that prescribes one of four actions: to rearrange this volume is one or two places left or right. If you simultaneously run all instructions, volumes will be placed in the same places in another order. The cynologist Dima performs all the instructions every morning. Once he discovered, that the volume of "Bichons" stands still, which was initially occupied by the volume of "Terriers". Prove , that after some time the volume of "Mudies" will stand on the original place of the volume "Poodles".

Let $ n$ be an integer greater than $ 3.$ Points $ V_{1},V_{2},...,V_{n},$ with no three collinear, lie on a plane. Some of the segments $ V_{i}V_{j},$ with $ 1 \le i < j \le n,$ are constructed. Points $ V_{i}$ and $ V_{j}$ are [i]neighbors[/i] if $ V_{i}V_{j}$ is constructed. Initially, chess pieces $ C_{1},C_{2},...,C_{n}$ are placed at points $ V_{1},V_{2},...,V_{n}$ (not necessarily in that order) with exactly one piece at each point. In a move, one can choose some of the $ n$ chess pieces, and simultaneously relocate each of the chosen piece from its current position to one of its neighboring positions such that after the move, exactly one chess piece is at each point and no two chess pieces have exchanged their positions. A set of constructed segments is called [i]harmonic[/i] if for any initial positions of the chess pieces, each chess piece $ C_{i}(1 \le i \le n)$ is at the point $ V_{i}$ after a finite number of moves. Determine the minimum number of segments in a harmonic set.

All the diagonals of a regular $25$-gon are drawn. Prove that no $9$ of the diagonals pass through one interior point of the $25$-gon. (A Shapovalov)

In each cell of a table $8\times 8$ lives a knight or a liar. By the tradition, the knights always say the truth and the liars always lie. All the inhabitants of the table say the following statement "The number of liars in my column is (strictly) greater than the number of liars in my row". Determine how many possible configurations are compatible with the statement.

$n$ points are given on a circle $\omega$. There is a circle with radius smaller than $\omega$ such that all these points lie inside or on the boundary of this circle. Prove that we can draw a diameter of $\omega$ with endpoints not belonging to the given points such that all the $n$ given points remain in one side of the diameter.

The numbers 1, 2, ... , 36 are written in the cells of a $6 \times 6$ grid. Two cells are called neighbors if they have a common side or vertex. A frog is located at the cell with the number 1 written on it. Every minute, if a neighboring cell has a bigger number than the cell where the frog is located, the frog jumps to the neighboring cell that has the biggest number written on it. The frog continues like this until there are no neighboring cells with a bigger number than the cell where the frog is located. What is the biggest possible number of jumps the frog can make?

A square-shaped pizza with side length $30$ cm is cut into pieces (not necessarily rectangular). All cuts are parallel to the sides, and the total length of the cuts is $240$ cm. Show that there is a piece whose area is at least $36$ cm$^2$

Given a positive integer $n$, there are $n$ boxes $B_1,...,B_n$. The following procedure can be used to add balls. $$\text{(Procedure) Chosen two positive integers }n\geq i\geq j\geq 1\text{, we add one ball each to the boxes }B_k\text{ that }i\geq k\geq j.$$ For positive integers $x_1,...,x_n$ let $f(x_1,...,x_n)$ be the minimum amount of procedures to get all boxes have its amount of balls to be a multiple of 3, starting with $x_i$ balls for $B_i(i=1,...,n)$. Find the largest possible value of $f(x_1,...,x_n)$. (If $x_1,...,x_n$ are all multiples of 3, $f(x_1,...,x_n)=0$.)

A numismatist Fred has some coins. A diameter of any coin is no more than $10$ cm. All the coins are contained in a one-layer box of dimensions $30$ cm by $70$ cm. He is presented with a new coin. Its diameter is $25$ cm. Prove that it is possible to put all the coins in a one-layer box of dimensions $55$ cm by $55$ cm. (Fedja Nazarov, St Petersburg)

Positive numbers are written in the squares of a 10 × 10 table. Frogs sit in five squares and cover the numbers in these squares. Kostya found the sum of all visible numbers and got 10. Then each frog jumped to an adjacent square and Kostya’s sum changed to $10^2$. Then the frogs jumped again, and the sum changed to $10^3$ and so on: every new sum was 10 times greater than the previous one. What maximum sum can Kostya obtain?

A rectangle \( m \times n \), where \( m \) and \( n \) are natural numbers strictly greater than 1, is partitioned into \( mn \) unit squares, each of which can be colored either black or white. An operation consists of changing the color of all the squares in a row or in a column to the opposite color. Is it possible that, although initially exactly one square is colored black and all the others are white, after a finite number of moves all squares have the same color?

There are $n\geq1$ cities on a horizontal line. Each city is guarded by a pair of stationary elephants, one just to the left and one just ot the right of the city, and facing away from it. The $2n$ elephants are of different sizes. If an elephant walks forward, it will knock aside any elephant that it approaches from behind, and in face-to-face meeting, the smaller elephant will be knocked aside. A moving elephant will keep walking in the same direction until it is knocked aside. Show that there is a unique city with the property that if any of the other cities orders its elephants to walk, then that city will not be invaded by an elephant. [url=https://artofproblemsolving.com/community/c6h1268873p6622370]IMO 2015, Shortlist C1[/url], modified by G. Smith

[center][u]Guts Round[/u] / [u]Set 7[/u][/center] [b]p19.[/b] Let $N_{21}$ be the answer to question 21. Suppose a jar has $3N_{21}$ colored balls in it: $N_{21}$ red, $N_{21}$ green, and $N_{21}$ blue balls. Jonathan takes one ball at a time out of the jar uniformly at random without replacement until all the balls left in the jar are the same color. Compute the expected number of balls left in the jar after all balls are the same color. [b]p20.[/b] Let $N_{19}$ be the answer to question 19. For every non-negative integer $k$, define $$f_k(x) = x(x - 1) + (x + 1)(x - 2) + ...+ (x + k)(x - k - 1),$$ and let $r_k$ and $s_k$ be the two roots of $f_k(x)$. Compute the smallest positive integer $m$ such that $|r_m - s_m| > 10N_{19}$. [b]p21.[/b] Let $N_{20}$ be the answer to question 20. In isosceles trapezoid $ABCD$ (where $\overline{BC}$ and $\overline{AD}$ are parallel to each other), the angle bisectors of $A$ and $D$ intersect at $F$, and the angle bisectors of points $B$ and $C$ intersect at $H$. Let $\overline{BH}$ and $\overline{AF}$ intersect at $E$, and let $\overline{CH}$ and $\overline{DF}$ intersect at $G$. If $CG = 3$, $AE = 15$, and $EG = N_{20}$, compute the area of the quadrilateral formed by the four tangency points of the largest circle that can fit inside quadrilateral $EFGH$.

There are $n$ points in the page such that no three of them are collinear.Prove that number of triangles that vertices of them are chosen from these $n$ points and area of them is 1,is not greater than $\frac23(n^2-n)$.

A square board with a size of $2020 \times 2020$ is divided into $2020^2$ small squares of size $1 \times 1$. Each of these small squares will be coloured black or white. Determine the number of ways to colour the board such that for every $2\times 2$ square, which consists of $4$ small squares, contains $2$ black small squares and $2$ white small squares.

Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. [b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.

If $S$ is a set which consists of $12$ elements, what is the maximum number of pairs $(a,b)$ such that $a, b\in S$ and $\frac{b}{a}$ is a prime number?

There are $11$ quadratic equations on the board, where each coefficient is replaced by a star. Initially, each of them looks like this $$\star x^2 + \star x + \star= 0.$$ Two players are playing a game making alternating moves. In one move each ofthem replaces one star with a real nonzero number. The first player tries to make as many equations as possible without roots and the second player tries to make the number of equations without roots as small as possible. What is the maximal number of equations without roots that the first player can achieve if the second player plays to her best? Describe the strategies of both players.

Let $S$ be a finite set of cells in a square grid. On each cell of $S$ we place a grasshopper. Each grasshopper can face up, down, left or right. A grasshopper arrangement is Asturian if, when each grasshopper moves one cell forward in the direction in which it faces, each cell of $S$ still contains one grasshopper. [list] [*] Prove that, for every set $S$, the number of Asturian arrangements is a perfect square. [*] Compute the number of Asturian arrangements if $S$ is the following set:

A research facility has $60$ rooms, numbered $1, 2, \dots 60$, arranged in a circle. The entrance is in room $1$ and the exit is in room $60$, and there are no other ways in and out of the facility. Each room, except for room $60$, has a teleporter equipped with an integer instruction $1 \leq i < 60$ such that it teleports a passenger exactly $i$ rooms clockwise. On Monday, a researcher generates a random permutation of $1, 2, \dots, 60$ such that $1$ is the first integer in the permutation and $60$ is the last. Then, she configures the teleporters in the facility such that the rooms will be visited in the order of the permutation. On Tuesday, however, a cyber criminal hacks into a randomly chosen teleporter, and he reconfigures its instruction by choosing a random integer $1 \leq j' < 60$ such that the hacked teleporter now teleports a passenger exactly $j'$ rooms clockwise (note that it is possible, albeit unlikely, that the hacked teleporter's instruction remains unchanged from Monday). This is a problem, since it is possible for the researcher, if she were to enter the facility, to be trapped in an endless \say{cycle} of rooms. The probability that the researcher will be unable to exit the facility after entering in room $1$ can be written as $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Given positive integer $ m \geq 17$, $ 2m$ contestants participate in a circular competition. In each round, we devide the $ 2m$ contestants into $ m$ groups, and the two contestants in one group play against each other. The groups are re-divided in the next round. The contestants compete for $ 2m\minus{}1$ rounds so that each contestant has played a game with all the $ 2m\minus{}1$ players. Find the least possible positive integer $ n$, so that there exists a valid competition and after $ n$ rounds, for any $ 4$ contestants, non of them has played with the others or there have been at least $ 2$ games played within those $ 4$.