олимпиада - Покрыть точки монетами

Решение Пусть $% R^2 $% – плоскость, $% r()$% – метрика в $% R^2 $%, радиус монет примем за 1, покрываемые точки обозначим $% x_1, x_2,…,x_{10} \in R^2. $% Под областью расположения точек будем понимать множество $% X=\lbrace x \in R^2| $% для некоторого $% j: r(x ,x_j) \le 1 \rbrace . $% На часть плоскости, включающую область X, нанесем гексоидальную разметку с радиусом $% 2 / \sqrt 3 $% (упакованные на плоскости правильные шестиугольники с длиной стороны, равной $% 2/\sqrt 3 $%). В каждый такой шестиугольник впишем круг радиуса 1. Покажем, что существует такой сдвиг разметки, при котором все точки $% x_1, x_2,…,x_{10} $% попадут в какой-нибудь круг. Такое расположение разметки будет соответствовать решению задачи. $%$%
Чтобы это показать, нанесем на область X квадратную (для простоты) $% \epsilon-сеть $% и осуществим по этой сети сдвиги исходной разметки так, чтобы центральная точка шестиугольника не выходила в результате сдвига за пределы этого шестиугольника в исходном состоянии (такие сдвиги далее называем допустимыми). Обозначим: s – площадь квадратной ячейки, N – число допустимых сдвигов, $% I_{ij}\in \lbrace 0,1 \rbrace $% - индикатор не попадания i-й точки в какой-либо единичный круг при j-м сдвиге решетки, $%I_i = \sum_{j} I_{ij}, S= 2 \sqrt 3 $% – площадь шестиугольника, $%\pi $% – площадь круга, $% S- \pi = S_0. $% Для полного множества всех допустимых сдвигов число непопаданий какой-либо точки в единичный круг равно $% N_0=N(I_1=1 \vee I_2=1,…, \vee I_{10}=1) \le \sum_{i} I_{i} =10 I_1. $% Учитывая, что $% lim_{\epsilon \to 0 } \sum_j I_{1j}s =S_0< S/10 $% и $% lim_{\epsilon \to 0 } Ns =S, $% можно подобрать такое значение $% \epsilon, $% для которого $% \sum_{i} I_i /N < 1/10 $% и, следовательно, $% N_0< N. $%