Betty has a $3\times 4$ grid of dots. She colors each dot either red or maroon. Compute the number of ways Betty can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color.

Let $Q$ be a square with side length $6$. Find the smallest integer $n$ such that in $Q$ there exists a set $S$ of $n$ points with the property that any square with side $1$ completely contained in $Q$ contains in its interior at least one point from $S$.

Kostya had two sets of $17$ coins: in one set all the coins were real, and in the other set there were exactly $5$ fakes (all the coins look the same; all real coins weigh the same, all fake coins also weigh the same, but it is unknown lighter or heavier than real ones). Kostya gave away one of the sets friend, and subsequently forgot which of the two sets had stayed. With the help of two weighings, can Kostya on a cup scale without weights, find out which of the two did he give away the sets?

An ordered quadruple of numbers is called [i]ten-esque[/i] if it is composed of 4 nonnegative integers whose sum is equal to $10$. Ana chooses a ten-esque quadruple $(a_1, a_2, a_3, a_4)$ and Banana tries to guess it. At each stage Banana offers a ten-esque quadtruple $(x_1,x_2,x_3,x_4)$ and Ana tells her the value of \[|a_1-x_1|+|a_2-x_2|+|a_3-x_3|+|a_4-x_4|\] How many guesses are needed for Banana to figure out the quadruple Ana chose?

100 people from 25 countries, four from each countries, stay on a circle. Prove that one may partition them onto 4 groups in such way that neither no two countrymans, nor two neighbours will be in the same group.

Today was realized the National Olimpiad in Cuba, this is the 3rd problem of the second day: Prof that we can color the lattice points in the plane with two color so that every rectangle with vertices in the lattice points and edges parallels to the co-ordinate axis that have area 2^n is not monocromatic [/img]

Find all sets X of points in a plane, not all collinear, such that: For any two distinct circumferences, each contains three points of X, its intersection points are points of X.

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.

Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys. (a) Show that $P_2(3) = \frac23$. (b) Prove that $P_1(n) = \frac1n$. (c) For all integers $n \geq 2$, prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$ (d) Determine a formula for $P_2 (n)$.

$k$ is a positive integer. $A$ company has a special method to sell clocks. Every customer can reason with two customers after he has bought a clock himself $;$ it's not allowed to reason with an agreed person. These new customers can reason with other two persons and it goes like this.. If both of the customers agreed by a person could play a role (it can be directly or not) in buying clocks by at least $k$ customers, this person gets a present. Prove that, if $n$ persons have bought clocks, then at most $\frac{n}{k+2}$ presents have been accepted.

Find the number of unordered choices of $ k $ lists, each having $ m $ distinct ordered objects, among a number of $ mn $ objects. [i]Cătălin Țigăeru[/i]

Physicists at Princeton are trying to analyze atom entanglement using the following experiment. Originally there is one atom in the space and it starts splitting according to the following procedure. If after $n$ minutes there are atoms $a_1, \dots, a_N$, in the following minute every atom $a_i$ splits into four new atoms, $a_i^{(1)},a_i^{(2)},a_i^{(3)},a_i^{(4)}$. Atoms $a_i^{(j)}$ and $a_k^{(j)}$ are entangled if and only the atoms $a_i$ and $a_k$ were entangled after $n$ minutes. Moreover, atoms $a_i^{(j)}$ and $a_k^{(j+1)}$ are entangled for all $1 \le i$, $k \le N$ and $j = 1$, $2$, $3$. Therefore, after one minute there is $4$ atoms, after two minutes there are $16$ atoms and so on. Physicists are now interested in the number of unordered quadruplets of atoms $\{b_1, b_2, b_3, b_4\}$ among which there is an odd number of entanglements. What is the number of such quadruplets after $3$ minutes? [i]Remark[/i]. Note that atom entanglement is not transitive. In other words, if atoms $a_i$, $a_j$ are entangled and if $a_j$, $a_k$ are entangled, this does not necessarily mean that $a_i$ and $a_k$ are entangled.

We say the set $ \{1,2,\ldots,3k\}$ has property $ D$ if it can be partitioned into disjoint triples so that in each of them a number equals the sum of the other two. (a) Prove that $ \{1,2,\ldots,3324\}$ has property $ D$. (b) Prove that $ \{1,2,\ldots,3309\}$ hasn't property $ D$.

Imagine a square scheme consisting of $n\times n$ fields with edge length $1$, where $n$ is an arbitrary positive integer. What is the maximum possible length of a route you can follow along the edges of the fields from point $A$ in the lower left corner to point $B$ in the upper right corner if you must never return to one point where you have been before? (The figure shows for $n = 5$ an example of a permitted route and an example of a not permitted route). [img]https://cdn.artofproblemsolving.com/attachments/6/e/92931d87f11b9fb3120b8dccc2c37c35a04456.png[/img]

Given a segment $AB$ of length $2003$ in a coordinate plane, determine the maximal number of unit squares with vertices in the lattice points whose intersection with the given segment is non-empty.

A plane is cut into unit squares, which are then colored in $n$ colors. A polygon $P$ is created from $n$ unit squares that are connected by their sides. It is known that any cell polygon created by $P$ with translation, covers $n$ unit squares in different colors. Prove that the plane can be covered with copies of $P$ so that each cell is covered exactly once.

An $n\times n$ board is coloured in $n$ colours such that the main diagonal (from top-left to bottom-right) is coloured in the first colour; the two adjacent diagonals are coloured in the second colour; the two next diagonals (one from above and one from below) are coloured in the third colour, etc; the two corners (top-right and bottom-left) are coloured in the $n$-th colour. It happens that it is possible to place on the board $n$ rooks, no two attacking each other and such that no two rooks stand on cells of the same colour. Prove that $n=0\pmod{4}$ or $n=1\pmod{4}$.

Let $n>1$ be a given positive integer. Petro and Vasyl play the following game. They take turns making moves and Petro goes first. In one turn, a player chooses one of the numbers from $1$ to $n$ that wasn't selected before and writes it on the board. The first player after whose turn the product of the numbers on the board will be divisible by $n$ loses. Who wins if every player wants to win? Find answer for each $n>1$. [i]Proposed by Mykhailo Shtandenko, Anton Trygub[/i]

A rectangle $R$ is partitioned into smaller rectangles whose sides are parallel with the sides of $R$. Let $B$ be the set of all boundary points of all the rectangles in the partition, including the boundary of $R$. Let S be the set of all (closed) segments whose points belong to $B$. Let a maximal segment be a segment in $S$ which is not a proper subset of any other segment in $S$. Let an intersection point be a point in which $4$ rectangles of the partition meet. Let $m$ be the number of maximal segments, $i$ the number of intersection points and $r$ the number of rectangles. Prove that $m + i = r + 3$.

Determine the greatest positive integer $A{}$ with the following property: however we place the numbers $1,2,\ldots, 100$ on a $10\times 10$ board, each number appearing exactly once, we can find two numbers on the same row or column which differ by at least $A{}$.

Graph $G$ is defined in 3d space. It has $e$ edges and every vertex are connected if the distance between them is $1.$ Given that there exists the Hamilton cycle, prove that for $e>1,$ we have $$\min d(v)\le 1+2\left(\frac{e}{2}\right)^{0.4}.$$

In the Cartesian plane $Oxy$ we consider the points ${A_1}\left( {40,1} \right), {A_2}\left( {40,2} \right), \ldots , {A_{40}}\left( {40,40} \right)$ as well as the segments $O{A_1},O{A_2},\ldots,O{A_{40}}$. A point of the Cartesian plane $Oxy$ is called "good", if its coordinates are integers and it is internal of one segment $O{A_i}, i=1,2,3,\ldots,40$. Additionally, one of the segments $O{A_1},O{A_2},\ldots,O{A_{40}}$ is called "good" if it contains a "good" point. Find the number of "good" segments and "good" points.

A disc is divided into $30$ segments which are labelled by $50,100,150,\ldots,1500$ in some order. Show that there always exist three successive segments, the sum of whose labels is at least $2350$.

Let $n$ be a positive integer, and let $x_1, x_2, \dots, x_n$ be distinct positive integers with $x_1 = 1$. Construct an $n \times 3$ table where the entries of the $k$-th row are $x_k, 2x_k, 3x_k$ for $k = 1, 2, \dots, n$. Now follow a procedure where, in each step, two identical entries are removed from the table. This continues until there are no more identical entries in the table. [list=a] [*] Prove that at least three entries remain at the end of the procedure. [*] Prove that there are infinitely many possible choices for $n$ and $x_1, x_2, \dots, x_n$ such that only three entries remain. [/list]

In each cell, a strip of length $100$ is worth a chip. You can change any $2$ neighboring chips and pay $1$ rouble, and you can also swap any $2$ chips for free, between which there are exactly $4$ chips. For what is the smallest amount of rubles you can rearrange chips in reverse order?