A [i]lattice point[/i] in the plane is a point with integral coordinates. The[i] centroid[/i] of four points $(x_i,y_i )$, $i = 1, 2, 3, 4$, is the point $\left(\frac{x_1 +x_2 +x_3 +x_4}{4},\frac{y_1 +y_2 +y_3 +y_4 }{4}\right)$. Let $n$ be the largest natural number for which there are $n$ distinct lattice points in the plane such that the centroid of any four of them is not a lattice point. Prove that $n = 12$.

Let $n$ be a positive integer. Ana and Banana play a game. Banana thinks of a function $f\colon\mathbb{Z}\to\mathbb{Z}$ and a prime number $p$. He tells Ana that $f$ is nonconstant, $p<100$, and $f(x+p)=f(x)$ for all integers $x$. Ana's goal is to determine the value of $p$. She writes down $n$ integers $x_1,\dots,x_n$. After seeing this list, Banana writes down $f(x_1),\dots,f(x_n)$ in order. Ana wins if she can determine the value of $p$ from this information. Find the smallest value of $n$ for which Ana has a winning strategy. [i]Anthony Wang[/i]

Does there exist an integer $ n > 1$ which satisfies the following condition? The set of positive integers can be partitioned into $ n$ nonempty subsets, such that an arbitrary sum of $ n \minus{} 1$ integers, one taken from each of any $ n \minus{} 1$ of the subsets, lies in the remaining subset.

Consider a natural number $n\geqslant 3$ and a graph $G{}$ with a chromatic number $\chi(G)=n$ which has more than $n{}$ vertices. Prove that there exist two vertex-disjoint subgraphs $G_1{}$ and $G_2{}$ of $G{}$ such that $\chi(G_1)+\chi(G_2)\geqslant n+1.$ [i]Proposed by V. Dolnikov[/i]

A $7 \times 7$ square is divided into unit squares by lines parallel to its sides. Some Swiss crosses (obtained by removing corner unit squares from a square of side $3$) are to be put on the large square, with the edges along division lines. Find the smallest number of unit squares that need to be marked in such a way that every cross covers at least one marked square.

Let $n\ge5$ be an integer. A trapezoid with base lengths of $1$ and $r$ is tiled by $n$ (not necessarily congruent) equilateral triangles. In terms of $n$, find the maximum possible value of $r$. [i]Linus Tang[/i]

Let the decimal representations of numbers $A$ and $B$ be given as: $A = 0.a_1a_2\cdots a_k > 0$, $B = 0.b_1b_2\cdots b_k > 0$ (where $a_k, b_k$ can be 0), and let $S$ be the count of numbers $0.c_1c_2\cdots c_k$ such that $0.c_1c_2\cdots c_k < A$ and $0.c_kc_{k-1}\cdots c_1 < B$ ($c_k, c_1$ can also be 0). (Here, $0.c_1c_2\cdots c_r (c_r \neq 0)$ is considered the same as $0.c_1c_2\cdots c_r0\cdots0$). Prove: $\left| S - 10^k AB \right| \leq 9k.$

We call a permutation of the numbers $1$, $2$, $3$, $\dots$ , $n$ 'kawaii' if there is exactly one number that is greater than its position. For example: $1$, $4$, $3$, $2$ is a kawaii permutation (when $n=4$) because only the number $4$ is greater than its position $2$. How many kawaii permutations are there if $n=14$?

$12$ knights are sitting at a round table. Every knight is an enemy with two of the adjacent knights but with none of the others. $5$ knights are to be chosen to save the princess, with no enemies in the group. How many ways are there for the choice?

[list] [*] There are $128$ coins of two different weights, $64$ each. How can one always find two coins of different weights by performing no more than $7$ weightings on a regular balance? [*] There are $8$ coins of two different weights, $4$ each. How can one always find two coins of different weights by performing two weightings on a regular balance?[/list]

On a highway, a pedestrian and a cyclist were going in the same direction, while a cart and a car were coming from the opposite direction. All were travelling at different constant speeds. The cyclist caught up with the pedestrian at $10$ o'clock. After a time interval, she met the cart, and after another time interval equal to the first, she met the car. After a third time interval, the car met the pedestrian, and after another time interval equal to the third, the car caught up with the cart. If the pedestrian met the car at $11$ o'clock, when did he meet the cart?

In how many ways can the set $N ={1, 2, \cdots, n}$ be partitioned in the form $p(N) = A_{1}\cup A_{2}\cup \cdots \cup A_{k},$ where $A_{i}$ consists of elements forming arithmetic progressions, all with the same common positive difference $d_{p}$ and of length at least one? At least two? [hide="Solution"] [b]Part 1[/b] Claim: There are $2^{n}-2$ ways of performing the desired partitioning. Let $d(k)$ equal the number of ways $N$ can be partitioned as above with common difference $k.$ We are thus trying to evaluate $\sum_{i=1}^{n-1}d(i)$ [b]Lemma: $d(i) = 2^{n-i}$[/b] We may divide $N$ into various rows where the first term of each row denotes a residue $\bmod{i}.$ The only exception is the last row, as no row starts with $0$; the last row will start with $i.$ We display the rows as such: $1, 1+i, 1+2i, 1+3i, \cdots$ $2, 2+i, 2+2i, 2+3i, \cdots$ $\cdots$ $i, 2i, 3i, \cdots$ Since all numbers have one lowest remainder $\bmod{i}$ and we have covered all possible remainders, all elements of $N$ occur exactly once in these rows. Now, we can take $k$ line segments and partition a given row above; all entries within two segments would belong to the same set. For example, we can have: $1| 1+i, 1+2i, 1+3i | 1+4i | 1+5i, 1+6i, 1+7i, 1+8i,$ which would result in the various subsets: ${1},{1+i, 1+2i, 1+3i},{1+4i},{1+5i, 1+6i, 1+7i, 1+8i}.$ For any given row with $k$ elements, we can have at most $k-1$ segments. Thus, we can arrange any number of segments where the number lies between $0$ and $k-1$, inclusive, in: $\binom{k-1}{0}+\binom{k-1}{1}+\cdots+\binom{k-1}{k-1}= 2^{k-1}$ ways. Applying the same principle to the other rows and multiplying, we see that the result always gives us $2^{n-i},$ as desired. We now proceed to the original proof. Since $d(i) = 2^{n-i}$ by the above lemma, we have: $\sum_{i=1}^{n-1}d(i) = \sum_{i=1}^{n-1}2^{n-i}= 2^{n}-2$ Thus, there are $2^{n}-2$ ways of partitioning the set as desired. [b]Part 2[/b] Everything is the same as above, except the lemma slightly changes to $d(i) = 2^{n-i}-i.$ Evaluating the earlier sum gives us: $\sum_{i=1}^{n-1}d(i) = \sum_{i=1}^{n-1}2^{n-i}-i = 2^{n}-\frac{n(n-1)}{2}-2$ [/hide]

An exam was taken by some students. Each problem was worth $1$ point for the correct answer, and $0$ points for an incorrect one. For each question, at least one student answered it correctly. Also, there are two students with different scores on the exam. Prove that there exists a question for which the following holds: The average score of the students who answered the question correctly is greater than the average score of the students who didn't.

Ana draws a checkered board that has at least 20 rows and at least 24 columns. Then, Beto must completely cover that board, without holes or overlaps, using only pieces of the following two types: Each piece must cover exactly 4 or 3 squares of the board, as shown in the figure, without leaving the board. It is permitted to rotate the pieces and it is not necessary to use all types of pieces. Explain why, regardless of how many rows and how many columns Ana's board has, Beto can always complete his task.

A ten-level $2$-tree is drawn in the plane: a vertex $A_1$ is marked, it is connected by segments with two vertices $B_1$ and $B_2$, each of $B_1$ and $B_2$ is connected by segments with two of the four vertices $C_1, C_2, C_3, C_4$ (each $C_i$ is connected with one $B_j$ exactly); and so on, up to $512$ vertices $J_1, \ldots, J_{512}$. Each of the vertices $J_1, \ldots, J_{512}$ is coloured blue or golden. Consider all permutations $f$ of the vertices of this tree, such that (i) if $X$ and $Y$ are connected with a segment, then so are $f(X)$ and $f(Y)$, and (ii) if $X$ is coloured, then $f(X)$ has the same colour. Find the maximum $M$ such that there are at least $M$ permutations with these properties, regardless of the colouring.

Given a $n \times n$ square board. Two players by turn remove some side of unit square if this side is not a bound of $n \times n$ square board. The player lose if after his move $n \times n$ square board became broken into two parts. Who has a winning strategy?

There are $330$ seats in the first row of the auditorium. Some of these seats are occupied by $25$ viewers. Prove that among the pairwise distances between these viewers, there are two equal.

There are 20 students in a high school class, and each student has exactly three close friends in the class. Five of the students have bought tickets to an upcoming concert. If any student sees that at least two of their close friends have bought tickets, then they will buy a ticket too. Is it possible that the entire class buys tickets to the concert? (Assume that friendship is mutual; if student $A$ is close friends with student $B$, then $B$ is close friends with $A$.)

In how many ways can we fill the cells of a $4\times4$ grid such that each cell contains exactly one positive integer and the product of the numbers in each row and each column is $2020$?

Let $n$ be a positive integer. A square $ABCD$ is divided into $n^2$ identical small squares by drawing $(n-1)$ equally spaced lines parallel to the side $AB$ and another $(n- 1)$ equally spaced lines parallel to $BC$, thus giving rise to $(n+1)^2$ intersection points. The points $A, C$ are coloured red and the points $B, D$ are coloured blue. The rest of the intersection points are coloured either red or blue. Prove that the number of small squares having exactly $3$ vertices of the same colour is even.

There is a square table with side $n$. Is it possible to enter the numbers $0$, $1$ or $2$ into the cells of this table so that all sums of numbers in rows and columns are different and take values from $1$ to $2n$, if: a) $n = 7$ ? b) $n = 8$ ?

[b]p1.[/b] Compute $$\left(\frac{1}{10}\right)^{\frac12}\left(\frac{1}{10^2}\right)^{\frac{1}{2^4}}\left(\frac{1}{10^3}\right)^{\frac{1}{2^3}} ...$$ [b]p2.[/b] Consider the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4,...,$ where the positive integer $m$ appears $m$ times. Let $d(n)$ denote the $n$th element of this sequence starting with $n = 1$. Find a closed-form formula for $d(n)$. [b]p3.[/b] Let $0 < \theta < \frac{\pi}{2}$, prove that $$ \left( \frac{\sin^2 \theta}{2}+\frac{2}{\cos^2 \theta} \right)^{\frac14}+ \left( \frac{\cos^2 \theta}{2}+\frac{2}{\sin^2 \theta} \right)^{\frac14} \ge (68)^{\frac14} $$ and determine the value of \theta when the inequality holds as equality. [b]p4.[/b] In $\vartriangle ABC$, parallel lines to $AB$ and $AC$ are drawn from a point $Q$ lying on side $BC$. If $a$ is used to represent the ratio of the area of parallelogram $ADQE$ to the area of the triangle $\vartriangle ABC$, (i) find the maximum value of $a$. (ii) find the ratio $\frac{BQ}{QC}$ when $a =\frac{24}{49}.$ [img]https://cdn.artofproblemsolving.com/attachments/5/8/eaa58df0d55e6e648855425e581a6ba0ad3ea6.png[/img] [b]p5.[/b] Prove the following inequality $$\frac{1}{2009} < \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{5}{6} \cdot \frac{7}{8}...\frac{2007}{2008}<\frac{1}{40}$$ PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].Thanks to gauss202 for sending the problems.

There are scales and $(n+1)$ weights with the total weight $2n$. Each weight is an integer. We put all the weights in turn on the lighter side of the scales, starting from the heaviest one, and if the scales is in equilibrium -- on the left side. Prove that when all the weights will be put on the scales, they will be in equilibrium.

Consider the equilateral triangular lattice in the complex plane defined by the Eisenstein integers; let the ordered pair $(x,y)$ denote the complex number $x+y\omega$ for $\omega=e^{2\pi i/3}$. We define an $\omega$-chessboard polygon to be a (non self-intersecting) polygon whose sides are situated along lines of the form $x=a$ or $y=b$, where $a$ and $b$ are integers. These lines divide the interior into unit triangles, which are shaded alternately black and white so that adjacent triangles have different colors. To tile an $\omega$-chessboard polygon by lozenges is to exactly cover the polygon by non-overlapping rhombuses consisting of two bordering triangles. Finally, a [i]tasteful tiling[/i] is one such that for every unit hexagon tiled by three lozenges, each lozenge has a black triangle on its left (defined by clockwise orientation) and a white triangle on its right (so the lozenges are BW, BW, BW in clockwise order). a) Prove that if an $\omega$-chessboard polygon can be tiled by lozenges, then it can be done so tastefully. b) Prove that such a tasteful tiling is unique. [i]Victor Wang.[/i]

Some squares of an $n \times n$ chessboard have been marked ($n \in N^*$). Prove that if the number of marked squares is at least $n\left(\sqrt{n} + \frac12\right)$, then there exists a rectangle whose vertices are centers of marked squares.