Problem 1772

Let $A_i \subset \{1, 2, \dots, 10\}$ be the set of the positions of the tokens in the $i$$-$th line of the board, $1 \le i \le 10$. The problem is equivalent to finding $A_1, A_2, \dots, A_{10}$ such that $|A_i \cap A_j| \le 1$ for $i \ne j$ and $|A_1| + |A_2| + \dots + |A_{10}|$ is maximum. Let $k_i$ be $|A_i|$. The $\binom{k_i}{2}$ subsets of $A_i$ with 2 elements must not be contained in any other $A_j, j \ne i$. Hence $$\sum_{1 \le i \le 10} \binom{k_i}{2} \le \binom{10}{2} \Leftrightarrow \sum_{1 \le i \le 10} (2k_i - 1)^2 \le 370$$ By Cauchy's inequality, $$ENV0$$$$\begin{aligned} & \sum_{1 \le i \le 10} 1^2 \cdot \sum_{1 \le i \le 10} (2k_i - 1)^2 \ge \left( \sum_{1 \le i \le 10} (2k_i - 1) \right)^2 \\ \Rightarrow & \sum_{1 \le i \le 10} (2k_i - 1) \le \sqrt{10 \cdot 370} \\ \Leftrightarrow & \sum_{1 \le i \le 10} k_i \le 35 \end{aligned}$$
The equality holds if and only if 5 of the $k_i$'s equal 4 and the other 5 equal 3. In this case, $\sum_{1 \le i \le 10} \binom{k_i}{2} = \binom{10}{2}$ and hence each subset of $\{1, 2, \dots, 10\}$ with 2 elements should be in exactly one $A_i$.

Therefore if it were possible to construct an instance with 35 tokens, each element of $\{1, 2, \dots, 10\}$ would either be in 3 subsets with 4 elements or
in 1 subset with 4 elements and 3 subsets with 3 elements. Since there are 5 subsets with 4 elements, there must be elements which belong to 3 subsets with 4 elements. We may thus suppose wlog that $A_1 = \{1, 2, 3, 4\}$, $A_2 = \{1, 5, 6, 7\}$, $A_3 = \{1, 8, 9, 10\}$. However any other subset with 4 elements would be contained in $\{2, 3, \dots, 10\}$ and therefore its intersection with one of $A_1$, $A_2$ or $A_3$ would have at least 2 elements. We conclude that it is impossible to have $\sum_{1\le i\le 10} k_i = 35$.

On the other hand, there exist instances with 34 tokens: