Find all positive integer $k$ such that one can find a number of triangles in the Cartesian plane, the centroid of each triangle is a lattice point, the union of these triangles is a square of side length $k$ (the sides of the square are not necessarily parallel to the axis, the vertices of the square are not necessarily lattice points), and the intersection of any two triangles is an empty-set, a common point or a common edge.

The positive integer $n \geqslant 2$ is given. How many ways can the cells of the $n\times n$ square be colored in four colors so that any two cells with a common side or vertex are colored in different colors? [i] I. Efremov [/i]

There are $2016$ participants in the Olcotournament of chess. It is known that in any set of four participants, there is one of them who faced the other three. Prove there is at least $2013$ participants who faced everyone else.

A circle is divided by $2019$ points into equal parts. Two players delete these points in turns. A player wins, if after his turn it is possible to draw a diameter of the circle such that there are no undeleted points on one side of it. Which player has a winning strategy?

There are three piles of matches on the table: one with $100$ matches, one with $200$, and one with $300$. Two players play the following game. They play alternatively, and a player on turn removes one of the piles and divides one of the remaining piles into two nonempty piles. The player who cannot make a legal move loses. Who has a winning strategy? (K. Kokhas’)

The cells of a $50\times 50$ square are painted in four colors. Prove that there is a cell, on four sides of which (i.e. top, bottom, left and on the right) there are cells of the same color as it (not necessarily adjacent to this cell).

Is there an infinite periodic sequence consisting of the letters $a$ and$ b$, such that if all letters are replaced simultaneously $a$ to $aba$ and letters $b$ to $bba$ does it transform into itself (possibly with a shift)? (A sequence is called periodic if there is such natural number $n$, which for every $i = 1, 2, . . . i$-th member of this sequence is equal to the ($i + n$)- th.)

In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$

A lattice point in the plane is a point both of whose coordinates are integers. Each lattice point has four neighboring points: upper, lower, left, and right. Let $k$ be a circle with radius $r \geq 2$, that does not pass through any lattice point. An interior boundary point is a lattice point lying inside the circle $k$ that has a neighboring point lying outside $k$. Similarly, an exterior boundary point is a lattice point lying outside the circle $k$ that has a neighboring point lying inside $k$. Prove that there are four more exterior boundary points than interior boundary points.

Find the number of positive integers less than or equal to $2017$ that have at least one pair of adjacent digits that are both even. For example, count the numbers $24$, $1862$, and $2012$, but not $4$, $58$, or $1276$.

On an infinite checkerboard two players alternately mark one unmarked cell. One of them uses $\times$, the other $\circ$. The first who fills a $2\times 2$ square with his symbols wins. Can the player who starts always win?

Let \(n\ge3\) be a fixed integer, and let \(\alpha\) be a fixed positive real number. There are \(n\) numbers written around a circle such that there is exactly one \(1\) and the rest are \(0\)'s. An [i]operation[/i] consists of picking a number \(a\) in the circle, subtracting some positive real \(x\le a\) from it, and adding \(\alpha x\) to each of its neighbors. Find all pairs \((n,\alpha)\) such that all the numbers in the circle can be made equal after a finite number of operations. [i]Proposed by Anthony Wang[/i]

At a chess tournament the winner gets 1 point and the defeated one 0 points. A tie makes both obtaining $\frac{1}{2}$ points. 14 players, none of them equally aged, participated in a competition where everybody played against all the other players. After the competition a ranking was carried out. Of the two players with the same number of points the younger received the better ranking. After the competition Jan realizes that the best three players together got as many points as the last 9 players obtained points together. And Joerg noted that the number of ties was maximal. Determine the number of ties.

There are $4n$ segments of unit length inside a circle radius $n$. Show that given any line $L$ there is a chord of the circle parallel or perpendicular to $L$ which intersects at least two of the $4n$ segments.

Two real numbers between $0$ and $1$ are randomly chosen. Calculate the probability that any one of them is less than the square of the other.

Ivan writes the matrix $\begin{pmatrix} 2 & 3\\ 2 & 4\end{pmatrix}$ on the board. Then he performs the following operation on the matrix several times: [b]1.[/b] he chooses a row or column of the matrix, and [b]2.[/b] he multiplies or divides the chosen row or column entry-wise by the other row or column, respectively. Can Ivan end up with the matrix $\begin{pmatrix} 2 & 4\\ 2 & 3\end{pmatrix}$ after finitely many steps?

Let $n$ be a nonzero natural number and let $S = \{1, 2, . . . , n\}$. A $3 \times n$ board is called [i]beautiful [/i] if it can be completed with numbers from the set $S$ like this as long as the following conditions are met: $\bullet$ on each line, each number from the set S appears exactly once, $\bullet$ on each column the sum of the products of two numbers on that column is divisible by $n$ (that is, if the numbers $a, b, c$ are written on a column, it must be $ab + bc + ca$ be divisible by $n$). For which values ​​of the natural number $n$ are there beautiful tables ¸and for which values ​​do not exist? Justify your answer.

In a dance, a group $S$ of $1994$ students stand in a big circle. Each student claps the hands of each of his two neighbours a number of times. For each student $x,$ let $f(x)$ be the total number of times $x$ claps the hands of his neighbours. As an example, suppose there are $3$ students $A, B$ and $C$. A claps hand with $B$ two times, $B$ claps hand with $C$ three times and $C$ claps hand with $A$ five times. Then $f(A) = 7, f(B) = 5$ and $f(C) = 8.$ (i) Prove that $\{f(x) | x \in S\}\ne\{n | n$ is an integer, $2 \le n \le 1995\}$. (ii) Find an example in which $\{f(x) | x \in S\} = \{n | n$ is an integer, $n \ne 3, 2 \le n \le 1996\}$

There is a central train station in point $O$, which is connected to other train stations $A_1, A_2, \ldots, A_8$ with tracks. There is also a track between stations $A_i$ and $A_{i+1}$ for each $i$ from $1$ to $8$ (here $A_9 = A_1$). The length of each track $A_iA_{i+1}$ is equal to $1$, and the length of each track $OA_i$ is equal to $2$, for each $i$ from $1$ to $8$. There are also $8$ trains $B_1, B_2, \ldots, B_8$, with speeds $1, 2, \ldots, 8$ correspondently. Trains can move only by the tracks above, in both directions. No time is wasted on changing directions. If two or more trains meet at some point, they will move together from now on, with the speed equal to that of the fastest of them. Is it possible to arrange trains into stations $A_1, A_2, \ldots, A_8$ (each station has to contain one train initially), and to organize their movement in such a way, that all trains arrive at $O$ in time $t < \frac{1}{2}$? [i](Proposed by Bogdan Rublov)[/i]

Rose and Brunno play the game on a board shaped like a regular 1001-gon. Initially, all vertices of the board are white, and there is a chip at one of them. On each turn, Rose chooses an arbitrary positive integer \( k \), then Brunno chooses a direction: clockwise or counterclockwise, and moves the chip in the chosen direction by \( k \) vertices. If at the end of the turn the chip stands at a white vertex, this vertex is painted red. Find the greatest number of vertices that Rose can make red regardless of Brunno's actions, if the number of turns is not limited.

In Simoland there are $2017n$ cities arranged in a $2017\times n$ lattice grid. There are $2016$ MRT (train) tracks and each track can only go north and east, or south and east. Suppose that all the tracks together pass through all the cities. Determine the largest possible value of $n$.

A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.

Unit square $ABCD$ is divided into $10^{12}$ smaller squares (not necessarily equal). Prove that the sum of perimeters of all the smaller squares having common points with diagonal $AC$ does not exceed 1500. [i]Proposed by A. Kanel-Belov[/i]

[b]p1.[/b] A permutation on $\{1, 2,..., n\}$ is an ordered arrangement of the numbers. For example, $32154$ is a permutation of $\{1, 2, 3, 4, 5\}$. Does there exist a permutation $a_1a_2... a_n$ of $\{1, 2,..., n\}$ such that $i+a_i$ is a perfect square for every $1 \le i \le n$ when a) $n = 6$ ? b) $n = 13$ ? c) $n = 86$ ? Justify your answers. [b]p2.[/b] Circle $C$ and circle $D$ are tangent at point $P$. Line $L$ is tangent to $C$ at point $Q$ and to $D$ at point $R$ where $Q$ and $R$ are distinct from $P$. Circle $E$ is tangent to $C, D$, and $L$, and lies inside triangle $PQR$. $C$ and $D$ both have radius $8$. Find the radius of $E$, and justify your answer. [img]https://cdn.artofproblemsolving.com/attachments/f/b/4b98367ea64e965369345247fead3456d3d18a.png[/img] [b]p3.[/b] (a) Prove that $\sin 3x = 4 \cos^2 x \sin x - \sin x$ for all real $x$. (b) Prove that $$(4 \cos^2 9^o - 1)(4 \cos^2 27^o - 1)(4 cos^2 81^o - 1)(4 cos^2 243^o - 1)$$ is an integer. [b]p4.[/b] Consider a $3\times 3\times 3$ stack of small cubes making up a large cube (as with the small cubes in a Rubik's cube). An ant crawls on the surface of the large cube to go from one corner of the large cube to the opposite corner. The ant walks only along the edges of the small cubes and covers exactly nine of these edges. How many different paths can the ant take to reach its goal? [b]p5.[/b] Let $m$ and $n$ be positive integers, and consider the rectangular array of points $(i, j)$ with $1 \le i \le m$, $1 \le j \le n$. For what pairs m; n of positive integers does there exist a polygon for which the $mn$ points $(i, j)$ are its vertices, such that each edge is either horizontal or vertical? The figure below depicts such a polygon with $m = 10$, $n = 22$. Thus $10$, $22$ is one such pair. [img]https://cdn.artofproblemsolving.com/attachments/4/5/c76c0fe197a8d1ebef543df8e39114fe9d2078.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be an even natural number and let $A$ be the set of all non-zero sequences of length $n$, consisting of numbers $0$ and $1$ (length $n$ binary sequences, except the zero sequence $(0,0,\ldots,0)$). Prove that $A$ can be partitioned into groups of three elements, so that for every triad $\{(a_1,a_2,\ldots,a_n), (b_1,b_2,\ldots,b_n), (c_1,c_2,\ldots,c_n)\}$, and for every $i = 1, 2,\ldots,n$, exactly zero or two of the numbers $a_i, b_i, c_i$ are equal to $1$.