РЕШУ ОЛИМП — математика

Задания

На плоскости дан выпуклый многоугольник с вершинами в целых точках, содержащий внутри начало координат O. Пусть V₁  — множество векторов, идущих из O в вершины многоугольника, а V₂  — множество векторов, идущих из O во все целые точки, содержащиеся внутри и на границе многоугольника (таким образом, V₁ содержится в V₂). Два кузнечика прыгают по целым точкам: каждый прыжок первого кузнечика смещает его на вектор из множества V₁, а второго  — из V₂. Докажите, что для некоторого числа c верно следующее утверждение: если оба кузнечика могут допрыгать из O до некоторой точки A, причем второму понадобится для этого n прыжков, то первый сможет сделать это не более чем за n + c прыжков.

(А. Акопян)

Решение. Пусть $\vecv принадлежит дробь: числитель: V_2 , знаменатель: V_1 конец дроби ,$ тогда $\vecv$ лежит в треугольнике с вершинами $\veca,$ $\vecb,$ $\vecc$ из $V_1,$ и, значит, $\vecv= альфа \veca плюс бета \vecb плюс гамма \vecc,$ где α, β, γ — неотрицательные рациональные числа с суммой 1 (они пропорциональны площадям треугольников vbc, vac, vab соответственно). Если $N=N левая круглая скобка \vecv правая круглая скобка$   — общий знаменатель чисел α, β, γ, то N прыжков на вектор $\vecv$ можно заменить на $альфа N$ прыжков на вектор $\veca,$ $бета N$ прыжков на вектор $\vecb,$ $гамма N$ прыжков на вектор $\vecc.$ Таким образом, можно считать, что второй кузнечик использует прыжок на вектор $\vecv$ менее чем $N левая круглая скобка \vecv правая круглая скобка$ раз.

Предположим, что утверждение задачи неверно, тогда имеется последовательность точек $x_i,$ такая что $f левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_i правая круглая скобка arrow бесконечность ,$ где $f левая круглая скобка x правая круглая скобка$ и $g левая круглая скобка x правая круглая скобка$ обозначают количества прыжков, необходимых первому и второму кузнечикам соответственно, чтобы достичь точки x . Переходя к подпоследовательности, можем считать, что набор использованных вторым кузнечиком прыжков из $дробь: числитель: V_2, знаменатель: V_1 конец дроби$ всегда один и тот же  — ведь мы добились того, что количество возможных таких наборов конечно. Еще несколько раз переходя к подпоследовательности, можем считать, что для каждого вектора $\veca принадлежит V_1$ количество $n_i левая круглая скобка \veca правая круглая скобка$ прыжков на вектор $\veca$ у второго кузнечика для достижения точки $x_i$ стабилизируется или же возрастает к бесконечности. Это позволяет считать, что при $i больше j$ точка $x_i$ достигается вторым кузнечиком через промежуточную точку $x_j,$ причем все прыжки из $x_j$ в $x_i$ лежат в $V_1$ и их количество равно $g левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_j правая круглая скобка .$ Но тогда первый кузнечик может попасть в $x_i$ за

$f левая круглая скобка x_j правая круглая скобка плюс g левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_j правая круглая скобка =g левая круглая скобка x_i правая круглая скобка плюс c$

прыжков. Противоречие.

Ключ