A grid consists of $2n$ vertical and $2n$ horizontal lines, each group disposed at equal distances. The lines are all painted in red and black, such that exactly $n$ vertical and $n$ horizontal lines are red. Find the smallest $n$ such that for any painting satisfying the above condition, there is a square formed by the intersection of two vertical and two horizontal lines, all of the same colour.

A journalist is looking for a person $Z$ at a meeting of $n$ persons. He has been told that $Z$ knows all the other people at the meeting but none of them knows $Z$. The journalist may ask any person about any other person: “Do you know that person?” One person can be questioned many times. All answers are truthful. (a) Can the journalist always find $Z$ by asking less than $n$ questions? (b) What is the minimal number of questions which are needed to find $Z$? (G Galperin)

The audience chooses two of twenty-nine cards, numbered from $1$ to $29$ respectively. The assistant of a magician chooses two of the remaining twenty-seven cards, and asks a member of the audience to take them to the magician, who is in another room. The two cards are presented to the magician in an arbitrary order. By an arrangement with the assistant beforehand, the magician is able to deduce which two cards the audience has chosen only from the two cards he receives. Explain how this may be done.

The signs "$+$" or "$-$" are placed in all cells of a $4 \times 4$ square table. It is allowed to change a sign of any cell altogether with signs of all its adjacent cells (i.e. cells having a common side with it). Find the number of different tables that could be obtained by iterating this procedure.

Let $n$ be a positive integer, and Megavan has a $(3n+1)\times (3n+1)$ board. All squares, except one, are tiled by non-overlapping $1\times 3$ triominoes. In each step, he can choose a triomino that is untouched in the step right before it, and then shift this triomino horizontally or vertically by one square, as long as the triominoes remain non-overlapping after this move. Show that there exist some $k$, such that after $k$ moves Megavan can no longer make any valid moves irregardless of the initial configuration, and find the smallest possible $k$ for each $n$. [i](Note: While he cannot undo a move immediately before the current step, he may still choose to move a triomino that has already been moved at least two steps before.)[/i] [i]Proposed by Ivan Chan Kai Chin[/i]

Suppose we have $2016$ points in a $2$-dimensional plane such that no three lie on a line. Two quadrilaterals are not disjoint if they share an edge or vertex, or if their edges intersect. Show that there are at least $504$ quadrilaterals with vertices among these points such that any two of the quadrilaterals are disjoint.

A convex $n$-vertex polygon is partitioned into triangles by nonintersecting diagonals . The following operation, called perestroyka (=reconstruction) , is allowed: two triangles $ABD$ and $BCD$ with a common side may be replaced by the triangles $ABC$ and $ACD$. By $P(n)$ denote the smallest number of perestroykas needed to transform any partitioning into any other one. Prove that (a) $P ( n ) \ge n - 3$ (b) $P (n) \le 2n - 7$ (c) $P(n) \le 2n - 10$ if $n \ge 13$ . ( D.Fomin , based on ideas of W. Thurston , D . Sleator, R. Tarjan)

If we fill $1\sim 16$ into $4\times4$ chessboard randomly. What is the possibility of the sum of each rows and columns are all even?

Consider positive integers $2,3,\ldots,n-1,n$ where $n\ge96.$ Consider any partition in two (sub)sets. Show that at least one of these two sets always contains two numbers and their product. Show that the statement does not hold for $n=95,$ e.g. there is a partition without the mentioned property.

In the television program “Field of Miracles,” the presenter played the prize as follows. The player was shown three boxes, one of which contained a prize. The player pointed to one of the boxes, after which the leader opened one of the other two remaining boxes, which turned out to be empty. After this, the player could either insist on the original choice, or change it and choose the third box. In what case does his chance of winning increase? (There are three possible answers: both boxes are equal, it is better to keep the original choice, it is better to change it. Try to justify your answer.)

A trader owns horses of $3$ races, and exacly $b_j$ of each race (for $j=1,2,3$). He want to leave these horses heritage to his $3$ sons. He knowns that the boy $i$ for horse $j$ (for $i,j=1,2,3$) would pay $a_{ij}$ golds, such that for distinct $i,j$ holds holds $a_{ii}> a_{ij}$ and $a_{jj} >a_{ij}$. Prove that there exists a natural number $n$ such that whenever it holds $\min\{b_1,b_2,b_3\}>n$, trader can give the horses to their sons such that after getting the horses each son values his horses more than the other brother is getting, individually.

How many ways are there to permute the letters $\{S,C,R, A,M,B,L,E\}$ without the permutation containing the substring $L AME$?

We call a tiling of an $m\times$ n rectangle with arabos (see figure below) [i]regular[/i] if there is no sub-rectangle which is tiled with arabos. Prove that if for some $m$ and $n$ there exists a [i]regular[/i] tiling of the $m\times n$ rectangle then there exists a [i]regular[/i] tiling also for the $2m \times 2n$ rectangle. [img]https://cdn.artofproblemsolving.com/attachments/1/1/2ab41cc5107a21760392253ed52d9e4ecb22d1.png[/img]

Let $A=\{-2562,-2561,...,2561,2562\}$. Prove that for any bijection (1-1, onto function) $f:A\to A$, $$\sum_{k=1}^{2562}\left\lvert f(k)-f(-k)\right\rvert\text{ is maximized if and only if } f(k)f(-k)<0\text{ for any } k=1,2,...,2562.$$

Smallville is populated by unmarried men and women, some of them are acquainted. Two city’s matchmakers are aware of all acquaintances. Once, one of matchmakers claimed: “I could arrange that every brunette man would marry a woman he was acquainted with”. The other matchmaker claimed “I could arrange that every blonde woman would marry a man she was acquainted with”. An amateur mathematician overheard their conversation and said “Then both arrangements could be done at the same time! ” Is he right?

In the coordinate plane are finitely many [i]walls[/i]; which are disjoint line segments, none of which are parallel to either axis. A bulldozer starts at an arbitrary point and moves in the $+x$ direction. Every time it hits a wall, it turns at a right angle to its path, away from the wall, and continues moving. (Thus the bulldozer always moves parallel to the axes.) Prove that it is impossible for the bulldozer to hit both sides of every wall. [i]Proposed by Linus Hamilton and David Stoner[/i]

Antonio plays a game where he continually flips a fair coin to see the sequence of heads ($H$) and tails ($T$) that he flips. Antonio wins the game if he sees on four consecutive flips the sequence $TTHT$ before he sees the sequence $HTTH$. The probability that Antonio wins the game is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Find the number of ways one can put numbers $1$ or $2$ in each cell of an $8\times 8$ chessboard in such a way that the sum of the numbers in each column and in each row is an odd number. (Two ways are considered different if the number in some cell in the first way is different from the number in the cell situated in the corresponding position in the second way)

The racing tournament has $12$ stages and $ n $ participants. After each stage, all participants, depending on the occupied place $ k $, receive points $ a_k $ (the numbers $ a_k $ are natural and $ a_1> a_2> \dots> a_n $). For what is the smallest $ n $ the tournament organizer can choose the numbers $ a_1 $, $ \dots $, $ a_n $ so that after the penultimate stage for any possible distribution of places at least two participants had a chance to take first place.

A computer network is formed by connecting $2004$ computers by cables. A set $S$ of these computers is said to be independent if no pair of computers of $S$ is connected by a cable. Suppose that the number of cables used is the minimum number possible such that the size of any independent set is at most $50$. Let $c(L)$ be the number of cables connected to computer $L$. Show that for any distinct computers $A$ and $B$, $c(A)=c(B)$ if they are connected by a cable and $|c(A)-c(B)| \le 1$ otherwise. Also, find the number of cables used in the network.

Let $n$ be a positive integer. Let $\mathcal{F}$ be a family of sets that contains more than half of all subsets of an $n$-element set $X$. Prove that from $\mathcal{F}$ we can select $\lceil \log_2 n \rceil + 1$ sets that form a separating family on $X$, i.e., for any two distinct elements of $X$ there is a selected set containing exactly one of the two elements. Moderator says: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=614827&hilit=Schweitzer+2014+separating

In a class of $30$ students, each students knows exactly six other students. (Of course, knowing is a mutual relation, so if $A$ knows $B$, then $B$ knows $A$). A group of three students is balanced if either all three students know each other, or no one knows anyone else within that group. How many balanced groups exist?

There are several contestants at a math olympiad. We say that two contestants $ A$ and $ B$ are [i]indirect friends[/i] if there are contestants $ C_1, C_2, ..., C_n$ such that $ A$ and $ C_1$ are friends, $ C_1$ and $ C_2$ are friends, $ C_2$ and $ C_3$ are friends, ..., $ C_n$ and $ B$ are friends. In particular, if $ A$ and $ B$ are friends themselves, they are [i]indirect friends[/i] as well. Some of the contestants were friends before the olympiad. During the olympiad, some contestants make new friends, so that after the olympiad every contestant has at least one friend among the other contestants. We say that a contestant is [i]special[/i] if, after the olympiad, he has exactly twice as indirect friends as he had before the olympiad. Prove that the number of special contestants is less or equal than $ \frac{2}{3}$ of the total number of contestants.

Let $f$ be a function that associates a positive integer $(x, y)$ with each pair of positive integers $f(x, y)$. Suppose that $f(x, y) \le xy$ for all positive integers $x$, $y$. Show that there are $2023$ different pairs $(x_1, y_1)$,$...$, $ (x_{2023}, y_{2023}$) such that $$f(x_1, y_1) = f(x_2, y_2) = ....= f(x_{2023}, y_{2023}).$$

Given $5$ points in the plane, no three of them being collinear. Show that among these $5$ points, we can always find $4$ points forming a convex quadrilateral.