Each square of a $10\times 10$ board contains a chip. One may choose a diagonal containing an even number of chips and remove any chip from it. Find the maximal number of chips that can be removed from the board by these operations.

Some frogs, some red and some others green, are going to move in an $11 \times 11$ grid, according to the following rules. If a frog is located, say, on the square marked with # in the following diagram, then [list] [*]If it is red, it can jump to any square marked with an x. [*]if it is green, it can jump to any square marked with an o.[/list] \[\begin{tabular}{| p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | p{0.08cm} | l} \hline &&&&&&\\ \hline &&x&&o&&\\ \hline &o&&&&x&\\ \hline &&&\small{\#}&&&\\ \hline &x&&&&o&\\ \hline &&o&&x&&\\ \hline &&&&&&\\ \hline \end{tabular} \] We say 2 frogs (of any color) can meet at a square if both can get to the same square in one or more jumps, not neccesarily with the same amount of jumps. [list=a] [*]Prove if 6 frogs are placed, then there exist at least 2 that can meet at a square. [*]For which values of $k$ is it possible to place one green and one red frog such that they can meet at exactly $k$ squares?[/list]

Initially given $31$ tuplets $$(1,0,0,\dots,0),(0,1,0,\dots,0),\dots, (0,0,0,\dots,1)$$ were written on the blackboard. At every move we choose two written $31$ tuplets as $(a_1,a_2,a_3,\dots, a_{31})$ and $(b_1,b_2,b_3,\dots,b_{31})$, then write the $31$ tuplet $(a_1+b_1,a_2+b_2,a_3+b_3,\dots, a_{31}+b_{31})$ to the blackboard too. Find the least possible value of the moves such that one can write the $31$ tuplets $$(0,1,1,\dots,1),(1,0,1,\dots,1),\dots, (1,1,1,\dots,0)$$ to the blackboard by using those moves.

Let $G = (V, E)$ be a simple connected graph. Show that there exists a subset of edges $F \subseteq E$ such that every vertex in $H = (V, F)$ has odd degree if and only if $|V |$ is even. Note: A connected graph is a graph such that any two vertices have a sequence of edges connecting one to the other. Note: A simple graph has no loops (edges of the form $(v, v)$) or duplicate edges.

On the plane is give a broken line $ABCD$ in which $AB = BC = CD = 1$, and $AD$ is not equal to $1$. The positions of $B$ and $C$ are fixed but $A$ and $D$ change their positions in turn according to the following rule (preserving the distance rules given): the point $A$ is reflected with respect to the line $BD$, then $D$ is reflected with respect to the line $AC$ (in which $A$ occupies its new position), then $A$ is reflected with respect to the line $BD$ ($D$ occupying its new position), $D$ is reflected with respect to the line $AC$, and so on. Prove that after several steps $A$ and $D$ coincide with their initial positions. (M Kontzewich)

Andrey and Sasha play the game, making moves alternate. On his turn, Andrey marks on the plane an arbitrary point that has not yet been marked. After that, Sasha colors this point in one of two colors: white and black. Sasha wins if after his move it is impossible to draw a line such that all white points lie in one half-plane, while all black points lie in another half-plane with respect to this line. [b]a)[/b] Prove that Andrey can make moves in such a way that Sasha will never win. [b]b)[/b] Suppose that Andrey can mark only integer points on the Cartesian plane. Can Sasha guarantee himself a win regardless of Andrey's moves? [i](N. Naradzetski)[/i]

Let $n$ be a positive integer and let $G$ be a simple undirected graph on $n$ vertices. Let $d_i$ be the degree of its $i$-th vertex, $i = 1, \dots , n$. Denote $\Delta=\max d_i$. Prove that if \[\sum_{i=1}^n d_i^2>n\Delta(n-\Delta),\] then $G$ contains a triangle.

Let set $ T \equal{} \{1,2,3,4,5,6,7,8\}$. Find the number of all nonempty subsets $ A$ of $ T$ such that $ 3|S(A)$ and $ 5\nmid S(A)$, where $ S(A)$ is the sum of all the elements in $ A$.

The function $f : (0,...2005) \rightarrow N$ has the properties that $f(2x+1)=f(2x)$, $f(3x+1)=f(3x)$ and $f(5x+1)=f(5x)$ with $x \in (0,1,2,...,2005)$. How many different values can the function assume?

Nils is playing a game with a bag originally containing $n$ red and one black marble. He begins with a fortune equal to $1$. In each move he picks a real number $x$ with $0 \le x \le y$, where his present fortune is $y$. Then he draws a marble from the bag. If the marble is red, his fortune increases by $x$, but if it is black, it decreases by $x$. The game is over after $n$ moves when there is only a single marble left. In each move Nils chooses $x$ so that he ensures a final fortune greater or equal to $Y$ . What is the largest possible value of $Y$?

Nicholas and Peter are dividing $(2n+1)$ nuts. Each wants to get more. Three ways for that were suggested. (Each consist of three stages.) First two stages are common. 1 stage: Peter divides nuts onto $2$ heaps, each contain not less than $2$ nuts. 2 stage: Nicholas divides both heaps onto $2$ heaps, each contain not less than $1$ nut. 3 stage: 1 way: Nicholas takes the biggest and the least heaps. 2 way: Nicholas takes two middle size heaps. 3 way: Nicholas takes either the biggest and the least heaps or two middle size heaps, but gives one nut to the Peter for the right of choice. Find the most and the least profitable method for the Nicholas.

In the cells of the $4\times N$ table, integers are written, modulo no more than $2024$ (i.e. numbers from the set $\{-2024, -2023,\dots , -2, -1, 0, 1, 2, 3,\dots , 2024\}$) so that in each of the four lines there are no two equal numbers. At what maximum $N$ could it turn out that in each column the sum of the numbers is equal to $23$? [i]G.M.Sharafetdinova[/i]

Sheldon was really annoying Leonard. So to keep him quiet, Leonard decided to do something. He gave Sheldon the following grid $\begin{tabular}{|c|c|c|c|c|c|} \hline 1 & 1 & 1 & 1 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 0 & 0\\ \hline 1 & 1 & 1 & 0 & 0 & 0\\ \hline 1 & 1 & 0 & 0 & 0 & 1\\ \hline 1 & 0 & 0 & 0 & 1 & 0\\ \hline 0 & 0 & 0 & 1 & 0 & 0\\ \hline \end{tabular}$ and asked him to transform it to the new grid below $\begin{tabular}{|c|c|c|c|c|c|} \hline 1 & 2 & 18 &24 &28 &30\\ \hline 21 & 3 & 4 &16 &22 &26\\ \hline 23 &19 & 5 & 6 &14 &20\\ \hline 32 &25 &17 & 7 & 8 &12\\ \hline 33 &34 &27 &15 & 9 &10\\ \hline 35 &31 &36 &29 &13 &11\\ \hline \end{tabular}$ by only applying the following algorithm: $\bullet$ At each step, Sheldon must choose either two rows or two columns. $\bullet$ For two columns $c_1, c_2$, if $a,b$ are entries in $c_1, c_2$ respectively, then we say that $a$ and $b$ are corresponding if they belong to the same row. Similarly we define corresponding entries of two rows. So for Sheldon's choice, if two corresponding entries have the same parity, he should do nothing to them, but if they have different parities, he should add 1 to both of them. Leonard hoped this would keep Sheldon occupied for some time, but Sheldon immediately said, "But this is impossible!". Was Sheldon right? Justify.

Let $n_1,n_2, \cdots, n_{26}$ be pairwise distinct positive integers satisfying (1) for each $n_i$, its digits belong to the set $\{1,2\}$; (2) for each $i,j$, $n_i$ can't be obtained from $n_j$ by adding some digits on the right. Find the smallest possible value of $\sum_{i=1}^{26} S(n_i)$, where $S(m)$ denotes the sum of all digits of a positive integer $m$.

A salesman and a customer altogether have $1999$ rubles in coins and bills of $1, 5, 10, 50, 100, 500 , 1000$ rubles. The customer has enough money to buy a Cat in the Bag which costs the integer number of rubles. Prove that the customer can buy the Cat and get the correct change.

Let [i]n[/i] $\ge$ 3 be an integer and let ([i]$p_1$[/i], [i]$p_2$[/i], [i]$p_3$[/i], $\dots$, [i]$p_n$[/i]) be a permutation of {1, 2, 3, $\dots$ [i]n[/i]}. For this permutation we say that [i]$p_t$[/i] is a [i]turning point[/i] if 2$\le$ [i]t[/i] $\le$ [i]n[/i]-1 and ([i]$p_t$[/i] - [i]$p_{t-1}$[/i])([i]$p_t$[/i] - [i]$p_{t+1}$[/i]) > 0 For example, for [i]n[/i] = 8, the permutation (2, 4, 6, 7, 5, 1, 3, 8) has two turning points: [i]$p_4$[/i] = 7 and [i]$p_6$[/i] = 1. For fixed [i]n[/i], let [i]q[/i]([i]n)[/i] denote the number of permutations of {1, 2, 3, $\dots$ [i]n[/i]} with exactly one turning point. Find all [i]n[/i] $\ge$ 3 for which [i]q[/i]([i]n)[/i] is a perfect square.

Aladdin has a set of coins with weights $ 1, 2, \ldots, 20$ grams. He can ask Genie about any two coins from the set which one is heavier, but he should pay Genie some other coin from the set before. (So, with every question the set of coins becomes smaller.) Can Aladdin find two coins from the set with total weight at least $ 28$ grams?

A set of $n$ distinct integer weights $w_1,w_2,\ldots, w_n$ is said to be [i]balanced[/i] if after removing any one of weights, the remaining $(n-1)$ weights can be split into two subcollections (not necessarily with equal size)with equal sum. $a)$ Prove that if there exist [i]balanced[/i] sets of sizes $k,j$ then also a [i]balanced[/i] set of size $k+j-1$. $b)$ Prove that for all [i]odd[/i] $n\geq 7$ there exist a [i]balanced[/i] set of size $n$.

Let $S$ be the set of natural numbers whose digits are different and belong to the set $\{1, 3, 5, 7\}$. Calculate the sum of the elements of $S$.

There are arbitrary 7 points in the plane. Circles are drawn through every 4 possible concyclic points. Find the maximum number of circles that can be drawn.

Clarabelle wants to travel from $(0,0)$ to $(6,2)$ in the coordinate plane. She is able to move in one-unit steps up, down, or right, must stay between $y=0$ and $y=2$ (inclusive), and is not allowed to visit the same point twice. How many paths can she take? [i]Proposed by Connor Gordon[/i]

On a board with $64$ ($8 \times 8$) squares, find a way to arrange $9$ queens and $ 1$ king so that every queen cannot capture another queen.

Let $f(k)$ denote the number of triples $(a, b, c)$ of positive integers satisfying $a + b + c = 2020$ with $(k - 1)$ not dividing $a, k$ not dividing $b$, and $(k + 1)$ not dividing $c$. Find the product of all integers $k$ in the range 3 \le k \le 20 such that $(k + 1)$ divides $f(k)$.

Sunn and Tacks play a game alternately choosing a word among the following (German) words: ”bad”, ”binse”, ”kafig”, ”kosewort”, ”maitag”, ”name”, ”pol”, ”parade”, ”wolf”. Two words are said to compatible if they have exactly one consonant in common. In the first round, Sunn selects a word for herself and one for Tacks. In every consequent round, each player selects a word that is compatible with the one they chose in the previous round. Tacks wins the game if the two players successively select the same word. (a) Prove that Tacks can always win. How many rounds are necessary for that? (b) Upon Sunn’s desire, the word ”kafig” was replaced with the word ”feige”. Prove that Sunn can prevent Tacks from winning.

A graph $G$ is called $\textit{divisibility graph}$ if the vertices can be assigned distinct positive integers such that between two vertices assigned $u, v$ there is an edge iff $\frac{u} {v}$ or $\frac{v} {u}$ is a positive integer. Show that for any positive integer $n$ and $0 \leq e \leq \frac{n(n-1)}{2}$, there is a $\textit{divisibility graph}$ with $n$ vertices and $e$ edges. [hide=Remark on source of 10.3] It appears to be Kvant 2022 Issue 10 M2719, so it will not be posted; the same problem was also used as 9.4.