Let $n$ be a positive integer. Determine the smallest positive integer $k$ with the following property: it is possible to mark $k$ cells on a $2n \times 2n$ board so that there exists a unique partition of the board into $1 \times 2$ and $2 \times 1$ dominoes, none of which contain two marked cells.

A unit square is divided into polygons, so that all sides of a polygon are parallel to sides of the given square. If the total length of the segments inside the square (without the square) is $2n$ (where $n$ is a positive real number), prove that there exists a polygon whose area is greater than $\frac{1}{(n+1)^2}$.

$6$ people stand in a circle with water guns. Each person randomly selects another person to shoot. What is the probability that no pair of people shoots at each other?

A domino is a $1 \times 2$ (or 2 $\times 1$) rectangular piece; namely, made up of two squares. There is an $8 \times 8$ board such that each domino can be cover exactly two of its squares. John places $n$ dominoes on the board, so that each one covers exactly two squares of the board and it is no longer possible to place a piece more without overlapping with any of those already placed. Determine the smallest value of $n$ for which the described situation is possible.

Let $p\ge 5$ be a prime number. Consider the function given by the formula $$f (x_1,..., x_p) = x_1 + 2x_2 +... + px_p.$$ Let $A_k$ denote the set of all these permutations $(a_1,..., a_p)$ of the set $\{1,..., p\}$, for integer number $f (a_1,..., a_p) - k$ is divisible by $p$ and $a_i \ne i$ for all $i \in \{1,..., p\}$. Prove that the sets $A_1$ and $A_4$ have the same number of elements.

Billiam is distributing his ample supply of balls among an ample supply of boxes. He distributes the balls as follows: he places a ball in the first empty box, and then for the greatest positive integer n such that all $n$ boxes from box $1$ to box $n$ have at least one ball, he takes all of the balls in those $n$ boxes and puts them into box $n +1$. He then repeats this process indefinitely. Find the number of repetitions of this process it takes for one box to have at least $2022$ balls.

Naomi has a class of $100$ students who will compete with each other in five teams. Once the teams are made, each student will shake hands with every other student, except the students in his or her own team. Naomi chooses to partition the students into teams so as to maximize the number of handshakes. How many handshakes will there be?

a) Given a chain of $60$ links each weighing $1$ g. Find the smallest number of links that need to be broken if we want to be able to get from the obtained parts all weights $1$ g, $2$ g, . . . , $59$ g, $60$ g? A broken link also weighs $1$ g. b) Given a chain of $150$ links each weighing $1$ g. Find the smallest number of links that need to be broken if we want to be able to get from the obtained parts all weights $1$ g, $2$ g, . . . , $149$ g, $150$ g? A broken link also weighs $1$ g.

[b]T[/b]wo ordered pairs $(a,b)$ and $(c,d)$, where $a,b,c,d$ are real numbers, form a basis of the coordinate plane if $ad \neq bc$. Determine the number of ordered quadruples $(a,b,c)$ of integers between $1$ and $3$ inclusive for which $(a,b)$ and $(c,d)$ form a basis for the coordinate plane.

Let $n$ be a positive integer and $\{A,B,C\}$ a partition of $\{1,2,\ldots,3n\}$ such that $|A|=|B|=|C|=n$. Prove that there exist $x \in A$, $y \in B$, $z \in C$ such that one of $x,y,z$ is the sum of the other two.

Let $n$ be a positive integer. We are given a $3n \times 3n$ board whose unit squares are colored in black and white in such way that starting with the top left square, every third diagonal is colored in black and the rest of the board is in white. In one move, one can take a $2 \times 2$ square and change the color of all its squares in such way that white squares become orange, orange ones become black and black ones become white. Find all $n$ for which, using a finite number of moves, we can make all the squares which were initially black white, and all squares which were initially white black. Proposed by [i]Boris Stanković and Marko Dimitrić, Bosnia and Herzegovina[/i]

Let $S$ be a finite set of points on a plane, where no three points are collinear, and the convex hull of $S$, $\Omega$, is a $2016-$gon $A_1A_2\ldots A_{2016}$. Every point on $S$ is labelled one of the four numbers $\pm 1,\pm 2$, such that for $i=1,2,\ldots , 1008,$ the numbers labelled on points $A_i$ and $A_{i+1008}$ are the negative of each other. Draw triangles whose vertices are in $S$, such that any two triangles do not have any common interior points, and the union of these triangles is $\Omega$. Prove that there must exist a triangle, where the numbers labelled on some two of its vertices are the negative of each other.

We define the following operation which will be applied to a row of bars being situated side-by-side on positions $1, 2, \ldots ,N$. Each bar situated at an odd numbered position is left as is, while each bar at an even numbered position is replaced by two bars. After that, all bars will be put side-by- side in such a way that all bars form a new row and are situated on positions $1, \ldots,M$. From an initial number $a_0 > 0$ of bars there originates a sequence $(a_n)_{n \geq 0}$, where an is the number of bars after having applied the operation $n$ times. [b](a)[/b] Prove that for no $n > 0$ can we have $a_n = 1997$. [b](b)[/b] Determine all natural numbers that can only occur as $a_0$ or $a_1$.

There are 10 numbers on a board. The product of any four of them is divisible by 30. Prove that at least one of the numbers on the board is divisible by 30.

[u]Round 5[/u] [b]p13.[/b] In coordinate space, a lattice point is a point all of whose coordinates are integers. The lattice points $(x, y, z)$ in three-dimensional space satisfying $0 \le x, y, z \le 5$ are colored in n colors such that any two points that are $\sqrt3$ units apart have different colors. Determine the minimum possible value of $n$. [b]p14.[/b] Determine the number of ways to express $121$ as a sum of strictly increasing positive Fibonacci numbers. [b]p15.[/b] Let $ABCD$ be a rectangle with $AB = 7$ and $BC = 15$. Equilateral triangles $ABP$, $BCQ$, $CDR$, and $DAS$ are constructed outside the rectangle. Compute the area of quadrilateral $P QRS$. [u] Round 6[/u] Each of the three problems in this round depends on the answer to one of the other problems. There is only one set of correct answers to these problems; however, each problem will be scored independently, regardless of whether the answers to the other problems are correct. [b]p16.[/b] Let $C$ be the answer to problem $18$. Suppose that $x$ and $y$ are real numbers with $y > 0$ and $$x + y = C$$ $$x +\frac{1}{y} = -2.$$ Compute $y +\frac{1}{y}$. [b]p17.[/b] Let $A$ be the answer to problem $16$. Let $P QR$ be a triangle with $\angle P QR = 90^o$, and let $X$ be the foot of the perpendicular from point $Q$ to segment $P R$. Given that $QX = A$, determine the minimum possible area of triangle $PQR$. [b]p18.[/b] Let $B$ be the answer to problem $17$ and let $K = 36B$. Alice, Betty, and Charlize are identical triplets, only distinguishable by their hats. Every day, two of them decide to exchange hats. Given that they each have their own hat today, compute the probability that Alice will have her own hat in $K$ days. [u]Round 7[/u] [b]p19.[/b] Find the number of positive integers a such that all roots of $x^2 + ax + 100$ are real and the sum of their squares is at most $2013$. [b]p20.[/b] Determine all values of $k$ such that the system of equations $$y = x^2 - kx + 1$$ $$x = y^2 - ky + 1$$ has a real solution. [b]p21.[/b] Determine the minimum number of cuts needed to divide an $11 \times 5 \times 3$ block of chocolate into $1\times 1\times 1$ pieces. (When a block is broken into pieces, it is permitted to rotate some of the pieces, stack some of the pieces, and break any set of pieces along a vertical plane simultaneously.) [u]Round 8[/u] [b]p22.[/b] A sequence that contains the numbers $1, 2, 3, ... , n$ exactly once each is said to be a permutation of length $n$. A permutation $w_1w_2w_3... w_n$ is said to be sad if there are indices $i < j < k$ such that $w_j > w_k$ and $w_j > w_i$. For example, the permutation $3142756$ is sad because $7 > 6$ and $7 > 1$. Compute the number of permutations of length $11$ that are not sad. [b]p23.[/b] Let $ABC$ be a triangle with $AB = 39$, $BC = 56$, and $CA = 35$. Compute $\angle CAB - \angle ABC$ in degrees. [b]p24.[/b] On a strange planet, there are $n$ cities. Between any pair of cities, there can either be a one-way road, two one-way roads in different directions, or no road at all. Every city has a name, and at the source of every one-way road, there is a signpost with the name of the destination city. In addition, the one-way roads only intersect at cities, but there can be bridges to prevent intersections at non-cities. Fresh Mann has been abducted by one of the aliens, but Sophy Moore knows that he is in Rome, a city that has no roads leading out of it. Also, there is a direct one-way road leading from each other city to Rome. However, Rome is the secret police’s name for the so-described city; its official name, the name appearing on the labels of the one-way roads, is unknown to Sophy Moore. Sophy Moore is currently in Athens and she wants to head to Rome in order to rescue Fresh Mann, but she does not know the value of $n$. Assuming that she tries to minimize the number of roads on which she needs to travel, determine the maximum possible number of roads that she could be forced to travel in order to find Rome. Express your answer as a function of $n$. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c4h2809419p24782489]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

In a $m\times n$ chessboard ($m,n\ge 2$), some dominoes are placed (without overlap) with each domino covering exactly two adjacent cells. Show that if no more dominoes can be added to the grid, then at least $2/3$ of the chessboard is covered by dominoes. [i]Proposed by DVDthe1st, mzy and jjax[/i]

Find all integers $n \ge 4$ with the following property: Each field of the $n \times n$ table can be painted white or black in such a way that each square of this table had the same color as exactly the two adjacent squares. (Squares are adjacent if they have exactly one side in common.) How many different colorings of the $6 \times 6$ table fields meet the above conditions?

On a $ 50 \times 50$ board, the centers of several unit squares are colored black. Find the maximum number of centers that can be colored black in such a way that no three black points form a right-angled triangle.

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.

A square grid $100 \times 100$ is tiled in two ways - only with dominoes and only with squares $2 \times 2$. What is the least number of dominoes that are entirely inside some square $2 \times 2$?

Let $n\ge 3$. Suppose $a_1, a_2, ... , a_n$ are $n$ distinct in pairs real numbers. In terms of $n$, find the smallest possible number of different assumed values by the following $n$ numbers: $$a_1 + a_2, a_2 + a_3,..., a_{n- 1} + a_n, a_n + a_1$$

$k > 1$ is fixed. Show that for $n$ sufficiently large for every partition of $\{1,2,\dots,n\}$ into $k$ disjoint subsets we can find $a \neq b$ such that $a$ and $b$ are in the same subset and $a+1$ and $b+1$ are in the same subset. What is the smallest $n$ for which this is true?

The columns and the row of a $3n \times 3n$ square board are numbered $1,2,\ldots ,3n$. Every square $(x,y)$ with $1 \leq x,y \leq 3n$ is colored asparagus, byzantium or citrine according as the modulo $3$ remainder of $x+y$ is $0,1$ or $2$ respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3n^2$ tokens of each color. Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.

There are $n$ distinct straight lines on a plane such that every line intersects exactly $12$ others. Determine all the possible values of $n$.

Prove that one can cut $a \times b$ rectangle, $\frac{b}{2} < a < b$, into three pieces and rearrange them into a square (without overlaps and holes).