Consider the $5\times 5$ grid $Z^2_5 = \{(a, b) : 0 \le a, b \le 4\}$. Say that two points $(a, b)$,$(x, y)$ are adjacent if $a - x \equiv -1, 0, 1$ (mod $5$) and $b - y \equiv -1, 0, 1$ (mod $5$) . For example, in the diagram, all of the squares marked with $\cdot$ are adjacent to the square marked with $\times$. [img]https://cdn.artofproblemsolving.com/attachments/2/6/c49dd26ab48ddff5e1beecfbd167d5bb9fe16d.png[/img] What is the largest number of $\times$ that can be placed on the grid such that no two are adjacent?

On the table there are $2n$ coins that look the same. It is known that $n$ of them weigh 9 g. each, while the remaining $n$ weigh 10 g. each. It is required to split the coins into $n$ pairs with total weight of each pair 19 g. Prove that this can be done in less than $n$ weighings using a balance without additional weights (the balance shows which pan is heavier or that their weight is equal).

On a $ \$10000$ order a merchant has a choice between three successive discounts of $ 20 \%$, $ 20 \%$, and $ 10\%$ and three successive discounts of $ 40 \%$, $ 5 \%$, and $ 5 \%$. By choosing the better offer, he can save: $ \textbf{(A)}\ \text{nothing at all} \qquad \textbf{(B)}\ \$440 \qquad \textbf{(C)}\ \$330 \qquad \textbf{(D)}\ \$345 \qquad \textbf{(E)}\ \$360$

An acute triangle $ ABC$ with $ AB \neq AC$ is given. Let $ V$ and $ D$ be the feet of the altitude and angle bisector from $ A$, and let $ E$ and $ F$ be the intersection points of the circumcircle of $ \triangle AVD$ with sides $ AC$ and $ AB$, respectively. Prove that $ AD$, $ BE$ and $ CF$ have a common point.

What is the largest integer $n$ that satisfies $(100^2-99^2)(99^2-98^2)\dots(3^2-2^2)(2^2-1^2)$ is divisible by $3^n$? $ \textbf{(A)}\ 49 \qquad\textbf{(B)}\ 53 \qquad\textbf{(C)}\ 97 \qquad\textbf{(D)}\ 103 \qquad\textbf{(E)}\ \text{None of the above} $

Peter picked a positive integer, multiplied it by 5, multiplied the result by 5,then multiplied the result by 5 again and so on. Altogether $k$ multiplications were made. It so happened that the decimal representations of the original number and of all $k$ resulting numbers in this sequence do not contain digit $7$. Prove that there exists a positive integer such that it can be multiplied $k$ times by $2$ so that no number in this sequence contains digit $7$.

On a circle there are $n$ points such that every point has a distinct number. Determine the number of ways of choosing $k$ points such that for any point there are at least 3 points between this point and the nearest point. (clockwise) ($n,k\geq 2$)

Let $x,y$ and $z$ be positive real numbers such that $xy+yz+xz=3xyz$. Prove that \[ x^2y+y^2z+z^2x \ge 2(x+y+z)-3 \] and determine when equality holds. [i]UK - David Monk[/i]

a) $P(x),R(x)$ are polynomials with rational coefficients and $P(x)$ is not the zero polynomial. Prove that there exist a non-zero polynomial $Q(x)\in\mathbb Q[x]$ that \[P(x)\mid Q(R(x)).\] b) $P,R$ are polynomial with integer coefficients and $P$ is monic. Prove that there exist a monic polynomial $Q(x)\in\mathbb Z[x]$ that \[P(x)\mid Q(R(x)).\]

Let $k\ge 1$ be a positive integer. We consider $4k$ chips, $2k$ of which are red and $2k$ of which are blue. A sequence of those $4k$ chips can be transformed into another sequence by a so-called move, consisting of interchanging a number (possibly one) of consecutive red chips with an equal number of consecutive blue chips. For example, we can move from $r\underline{bb}br\underline{rr}b$ to $r\underline{rr}br\underline{bb}b$ where $r$ denotes a red chip and $b$ denotes a blue chip. Determine the smallest number $n$ (as a function of $k$) such that starting from any initial sequence of the $4k$ chips, we need at most $n$ moves to reach the state in which the first $2k$ chips are red.

There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.) Each person is required to designate one of their friends as their best friend. If $A$ designates $B$ as her best friend, then (unfortunately) it does not follow that $B$ necessarily designates $A$ as her best friend. Someone designated as a best friend is called a $1$-best friend. More generally, if $n> 1$ is a positive integer, then a user is an $n$-best friend provided that they have been designated the best friend of someone who is an $(n-1)$-best friend. Someone who is a $k$-best friend for every positive integer $k$ is called popular. (a) Prove that every popular person is the best friend of a popular person. (b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person. [i]Romania (Dan Schwarz)[/i]

Let $k\geqslant 2$ be an integer. Consider the sequence $(x_n)_{n\geqslant 1}$ defined by $x_1=a>0$ and $x_{n+1}=x_n+\lfloor k/x_n\rfloor$ for $n\geqslant 1.$ Prove that the sequence is convergent and determine its limit.

Two equal circles $S_1$ and $S_2$ meet at two different points. The line $\ell$ intersects $S_1$ at points $A,C$ and $S_2$ at points $B,D$ respectively (the order on $\ell$: $A,B,C,D$) . Define circles $\Gamma_1$ and $\Gamma_2$ as follows: both $\Gamma_1$ and $\Gamma_2$ touch $S_1$ internally and $S_2$ externally, both $\Gamma_1$ and $\Gamma_2$ line $\ell$, $\Gamma_1$ and $\Gamma_2$ lie in the different halfplanes relatively to line $\ell$. Suppose that $\Gamma_1$ and $\Gamma_2$ touch each other. Prove that $AB=CD$. I. Voronovich

Let $P$ be a convex polygon. Prove that there exists a convex hexagon that is contained in $P$ and whose area is at least $\frac34$ of the area of the polygon $P$. [i]Alternative version.[/i] Let $P$ be a convex polygon with $n\geq 6$ vertices. Prove that there exists a convex hexagon with [b]a)[/b] vertices on the sides of the polygon (or) [b]b)[/b] vertices among the vertices of the polygon such that the area of the hexagon is at least $\frac{3}{4}$ of the area of the polygon. [i]Proposed by Ben Green and Edward Crane, United Kingdom[/i]

Six line segments of lengths $17, 18, 19, 20, 21$ and $23$ form the side edges of a triangular pyramid (also called a tetrahedron). Can there exist a sphere tangent to all six lines?

Find all the real numbers $x$ such that $\frac{1}{[x]}+\frac{1}{[2x]}=\{x\}+\frac{1}{3}$ where $[x]$ denotes the integer part of $x$ and $\{x\}=x-[x]$. For example, $[2.5]=2, \{2.5\} = 0.5$ and $[-1.7]= -2, \{-1.7\} = 0.3$

The triangle $ABC$ is given. Let $A', B'$ and $C'$ be the midpoints of the sides $BC, CA$ and $AB$ and $O_a,O_b$ and $O_c$ be the circumcenters of the triangles $CAC', ABA'$ and $BCB'$ respectively. Prove that the triangles $ABC$ and $O_aO_bO_c$ are similar. [i]Proposed by Don Luu (Vietnam)[/i]

Find the number of all $ 6$-digit natural numbers such that the sum of their digits is $ 10$ and each of the digits $ 0,1,2,3$ occurs at least once in them. [14 points out of 100 for the 6 problems]

Find all natural numbers \( n \) for which it is possible to construct an \( n \times n \) square using only tetrominoes like the one below:

Circles with radii $R$ and $r$ ($R > r$) are externally tangent. Another common tangent of the circles in drawn. This tangent and the circles bound a region inside which a circle as large as possible is drawn. What is the radius of this circle?

Which of the following could not be the unit's digit [one's digit] of the square of a whole number? $ \text{(A)}\ 1\qquad\text{(B)}\ 4\qquad\text{(C)}\ 5\qquad\text{(D)}\ 6\qquad\text{(E)}\ 8 $

Does there exist a finite set $A$ of positive integers of at least two elements and an infinite set $B$ of positive integers, such that any two distinct elements in $A+B$ are coprime, and for any coprime positive integers $m,n$, there exists an element $x$ in $A+B$ satisfying $x\equiv n \pmod m$ ? Here $A+B=\{a+b|a\in A, b\in B\}$.

For how many integers $k$ such that $0 \le k \le 2014$ is it true that the binomial coefficient $\binom{2014}{k}$ is a multiple of 4?

Find the number of ways to arrange the letters in $LE X I NGTON$ such that the string $LE X$ does not appear.

On a blackboard, there are $10$ numbers written: $1, 2, \dots, 10$. Nahyun repeatedly performs the following operations. [b](Operation)[/b] Nahyun chooses two numbers from the 10 numbers on the blackboard that are not in a divisor-multiple relationship, erases them, and writes their GCD and LCM on the blackboard. If every two numbers on the blackboard form a divisor-multiple relationship, Nahyun stops the process. What is the maximum number of operations Nahyun can perform? (Note: $a, b$ are in a divisor-multiple relationship iff $a \mid b$ or $b \mid a$.)