8. Anya and Borya are playing "battleship" with the following rules: 29 different points are chosen on a circle, numbered clockwise with natural numbers from 1 to 29. Anya draws a ship - an arbitrary triangle with vertices at these points. We will call a "shot" the selection of two different natural numbers $k$ and $m$ from 1 to 29. If the segment with endpoints at points numbered $k$ and $m$ has at least one common point with Anya's triangle, the ship is considered "wounded." Borya fires a "salvo" - several shots simultaneously. Anya drew a ship and showed it to Borya. And then they noticed that any "salvo" of K different shots will definitely wound Anya's ship. Indicate any position of Anya's ship for which the value of $K$ will be minimal.
Solution. The vertices of Anya's triangle divide the circle into three arcs (see figure). Let $x, y$, and $26-x-y$ be the number of points on these arcs (see figure), excluding the vertices of the triangle itself. For a "shot" with endpoints at points $k$ and $m$ to not hit the ship, both these points must lie on one of the arcs. Clearly, two different points can be chosen on the arc containing $x$ points in $C_{x}^{2}$ ways. The same applies to the other arcs. Therefore, the number $N$ of "safe" shots is the sum $N=C_{x}^{2}+C_{y}^{2}+C_{26-x-y}^{2}$. Then the next shot will definitely "hit" the ship, so $K=N+1$.

Thus, we need to find such non-negative integers $x, y$ that satisfy the condition $x+y \leq 26$, for which the value of $N$ is minimal.

![](https://cdn.mathpix.com/cropped/2024_05_06_216317514e8812a39ee1g-4.jpg?height=363&width=349&top_left_y=2037&top_left_x=1593)
Let's write the expression for $N$ in expanded form:

$$
N=\frac{x(x-1)}{2}+\frac{y(y-1)}{2}+\frac{(26-x-y)(25-x-y)}{2}
$$

Expanding the brackets and combining like terms, we get

$$
N=x^{2}-x(26-y)+y^{2}-26 y+325
$$

www.v-olymp.ru

Interregional Olympiad for Schoolchildren Based on Departmental Educational Organizations in Mathematics

For each fixed $y$ from 0 to 26, we will find such a value of $x$ that satisfies the inequality

$$
0 \leq x \leq 26-y
$$

for which the value of $N$ is minimal. If $y$ is fixed, then the right-hand side (1) takes its minimum value at

$$
x=\frac{26-y}{2}
$$

(the vertex of the parabola, belonging to the interval (2)). This minimum value is $13 y+156$. It, in turn, is minimal at $y=\frac{26}{3} \approx 8.6$. From (3), we then find $x=\frac{26}{3}$. Among the points with integer coordinates $(8,8),(8,9),(9,8),(9,9)$ - the nearest integer neighbors of the point of minimum $\left(\frac{26}{3}, \frac{26}{3}\right)$ - we choose the one for which the value of $N$ is the smallest. These are the points $(8,9),(9,8),(9,9)$. For them, $N=100$.

Answer: The ship should be placed such that on the three arcs into which the vertices of the ship divide the circle, there are 8, 9, and 9 points (excluding the vertices of the ship itself).