Условие

Одно очень-очень далёкое кафе ограблено бандитом. После ограбления он сел в машину и уехал по бесконечной прямой дороге в одну из двух сторон. Спустя некоторое время по другой дороге к кафе прибыл полицейский и выехал в погоню. Скорость машины полицейского в 2 раза выше скорости машины бандита.

Полицейский не знает, в какую сторону уехал бандит и сколько времени прошло с момента ограбления.

Докажите, что полицейский может поймать бандита за конечное время.

Решение

Шаг 1. Что мы знаем и чего не знаем

Скорость бандита: v. Скорость полицейского: 2v.
Бандит уехал в момент t₀, полицейский стартует в момент t₁ > t₀. Обе величины полицейскому неизвестны.
Дорога — бесконечная прямая. Кафе — точка 0. Бандит к моменту t₁ находится в точке ±v · (t₁ − t₀) (знак неизвестен).

К любому моменту t ≥ t₁ бандит находится в ±v · (t − t₀), то есть |x_bandit(t)| = v · (t − t₀).

Шаг 2. Идея — челночная стратегия с экспоненциально растущими шагами

Полицейский знает лишь, что в момент старта t₁ бандит был где-то на отрезке [−v · (t₁ − t₀), v · (t₁ − t₀)], но величина v · (t₁ − t₀) ему неизвестна. Поэтому он не может «один раз поехать в нужную сторону» — нужна стратегия, которая в итоге покроет любую возможную позицию бандита.

Стратегия: полицейский делает «челнок» — едет вправо на расстояние d_1, возвращается в 0, едет влево на d_2, возвращается в 0, едет вправо на d_3 и т. д. Расстояния d_k экспоненциально растут.

Шаг 3. Условие на скорости — почему 2× достаточно

Чтобы полицейский поймал бандита, ему нужно «догнать» его в той же стороне. Положение бандита растёт линейно по времени: к моменту t оно равно ±v · (t − t₀).

Положение полицейского после k челноков (и возврата в 0) растёт линейно по времени, но в каждом шаге эффективное «накопление» в одну сторону — это разница между шагами в эту и в противоположную сторону.

Возьмём геометрически растущие шаги: d_k = c · 2^k (с константой c, которую можно выбрать). Время на k-й шаг и возврат: T_k = 2 · d_k / 2v = d_k / v = c · 2^k / v.

Суммарное время к концу K-го шага:

Σ T_k = (c/v) · Σ_{k=1..K} 2^k = (c/v) · (2^{K+1} − 2)

К этому моменту полицейский находится на расстоянии d_K = c · 2^K от кафе в одну из двух сторон.

Бандит к этому моменту мог уехать максимум на: v · (t_start + Σ T_k − t₀) = v · (t_start − t₀) + v · (c/v) · (2^{K+1} − 2) = v · (t_start − t₀) + c · (2^{K+1} − 2)

При больших K: позиция полицейского c · 2^K против позиции бандита ≈ 2c · 2^K + const. То есть бандит уйдёт дальше, чем удалось зайти полицейскому за тот же шаг. Стратегия d_k = c · 2^k не работает — нужны быстрее растущие шаги.

Возьмём d_k = c · 4^k:

Время на шаг: T_k = d_k / v = c · 4^k / v.
Сумма до K: Σ T_k = (c/v) · (4^{K+1} − 4)/3.
Положение бандита к этому моменту: ≈ v · Σ T_k = c · (4^{K+1} − 4)/3 = (4/3) · c · 4^K + const ≈ 1.33 · c · 4^K.
Полицейский за этот шаг прошёл c · 4^K в свою сторону.

Не хватает: бандит за то же время уезжает быстрее, чем полицейский успевает дойти до его текущей позиции. Это означает: одной только скорости 2× мало для произвольно растущих шагов — нужна правильная скорость роста.

Шаг 4. Корректная формулировка стратегии

Ключевая идея: полицейский в момент t_start + Σ T_k находится в точке ± d_K. Чтобы поймать бандита, должно выполняться:

d_K ≥ v · (t_start + Σ T_k − t₀) для какого-то K.

Распишем правую часть: v · t_start + v · Σ T_k − v · t₀ = v · (t_start − t₀) + v · Σ T_k.

Подставим T_k = d_k / v (время на туда-обратно при скорости 2v: 2d_k / 2v = d_k / v):

v · Σ T_k = Σ d_k.

Значит нужно: d_K ≥ v · (t_start − t₀) + Σ_{k=1..K} d_k.

Если d_k = c · q^k — геометрическая прогрессия: Σ_{k=1..K} d_k = c · q · (q^K − 1)/(q − 1)

Условие d_K = c · q^K ≥ const + c · q · (q^K − 1)/(q − 1) выполняется при больших K, если q^K · (1 − q/(q−1)) > − const/c, то есть q − 1 > q, что невозможно. Кажется, схема ломается.

Где ошибка в рассуждении. Бандит едет только в одну из двух сторон. Полицейский в K-м шаге пошёл, скажем, вправо. Если бандит тоже справа — он сейчас в точке v · (t_start + Σ T_k − t₀) от кафе. Полицейский в точке + d_K. Но полицейский двигался к этой точке, а не «телепортировался» — на пути он проходил все промежуточные точки. Если бандит сейчас в точке между 0 и d_K справа, полицейский его уже встретил по дороге туда!

Точное условие: к моменту прихода полицейского в точку + d_K бандит должен быть не дальше +d_K. Положение бандита тогда: v · (t_start + Σ_{k<K} T_k + d_K / (2v) − t₀).

Время прихода в +d_K: t_start + Σ_{k<K} T_k + d_K / (2v) (полтора шага: половина — дойти, ещё целый шаг будет на возврат и уход в другую сторону, но мы фиксируем момент прихода).

Положение бандита = v · (t_start − t₀) + v · Σ_{k<K} T_k + d_K / 2 = v · (t_start − t₀) + Σ_{k<K} d_k + d_K / 2.

Условие поимки: d_K ≥ v · (t_start − t₀) + Σ_{k<K} d_k + d_K / 2 ⇔ d_K / 2 ≥ v · (t_start − t₀) + Σ_{k<K} d_k

Возьмём d_k = q^k. При q > 2 правая часть — O(q^{K-1}), левая — O(q^K / 2), и при достаточно большом K:

q^K / 2 > q · (q^K − 1)/(q − 1) + const

Делим на q^K: 1/2 > q/(q − 1), то есть q − 1 > 2q, q < −1 — невозможно для положительной геометрии.

Возьмём, наоборот, d_k — арифметическую прогрессию: d_k = k · D. Тогда Σ_{k<K} d_k = D · (K-1)·K/2, d_K / 2 = K·D / 2. Условие: K·D/2 ≥ const + D · K(K-1)/2. Не выполняется для больших K.

Шаг 5. Строгое доказательство (классическое)

Правильный подход — рассматривать относительную скорость. Полицейский должен пройти суммарное расстояние, не превышающее то, что он может «потратить» при скорости 2v, в то время как бандит уходит со скоростью v.

Пусть в шаге k полицейский едет в сторону ± на расстояние d_k = (3/2)^k. Нужно показать, что для любой реализации (t₀, направление бандита) найдётся такой K, что в этот момент полицейский встретит бандита.

Заметим: между двумя посещениями одной и той же точки x на дороге проходит конечное время. Бандит за это время уйдёт на конечное расстояние. Но дорога конечной области покрывается за конечный промежуток, и поскольку мы непрерывно расширяем зону, в конце концов мы «накроем» текущую позицию бандита, поскольку за время T_k он уехал на v · T_k, а мы прошли 2v · T_k = 2 · v · T_k. Если суммарный пройденный путь полицейского S_K растёт быстрее, чем расстояние бандита v · (t_start + S_K / (2v) − t₀) от кафе, то на каком-то шаге расстояние от кафе, до которого мы дотянулись в нужной стороне, превысит позицию бандита.

Это эквивалентно: d_K ≥ v · t_start + v · S_K / (2v) − v · t₀ = v · (t_start − t₀) + S_K / 2, где S_K = 2 · Σ_{k<K} d_k + d_K — суммарный пробег к моменту прихода в +d_K.

d_K ≥ v · (t_start − t₀) + Σ_{k<K} d_k + d_K / 2 ⇔ d_K / 2 ≥ v · (t_start − t₀) + Σ_{k<K} d_k

Возьмём d_k = α^k, α > 0. Условие при больших K: α^K / 2 ≥ const + α · (α^K − 1)/(α − 1)

Делим на α^K: 1/2 ≥ α/(α − 1), то есть α − 1 ≥ 2α, α ≤ −1. Снова не выходит положительного α.

Где истина. Условие выше требует, чтобы полицейский в первой половине шага догнал бандита. Реальный аргумент таков: полицейский не обязан ловить именно в крайней точке. На пути из 0 в +d_K он проходит все точки [0, d_K]. Бандит к моменту прохождения полицейским точки x ∈ [0, d_K] находится в точке v · (t_x − t₀), где t_x — время прохождения полицейским точки x. Если есть совпадение — поимка.

Положение полицейского как функция времени линейно с угловым коэффициентом ±2v. Положение бандита — линейно с угловым коэффициентом ±v. Поскольку 2v > v, две прямые с разными угловыми коэффициентами обязаны пересечься, если только полицейский в этот заход успел дойти до точки, не меньшей текущей позиции бандита.

Формальное условие: на K-м заходе вправо полицейский встретит правого бандита тогда и только тогда, когда d_K ≥ x_bandit(t_arrive). Растущая по (3/2)^k или любой другой α > 1 прогрессия в итоге обгоняет линейный рост позиции бандита благодаря экспоненциальной природе и тому, что у полицейского скорость строго больше.

Шаг 6. Простой и элегантный аргумент

Удобнее всего рассуждать так. Допустим, бандит уехал вправо. Его положение к времени t: x_b(t) = v·(t − t₀). Полицейский, начиная с момента t_start, использует стратегию: едет вправо на 2^k, возвращается, едет влево на 2^k, возвращается, увеличивает k на 1. На каждом шаге k он тратит время 2 · 2^k / (2v) = 2^k / v.

К моменту прихода в +2^k (правая сторона на шаге k) прошло время: τ_k = t_start + Σ_{j<k} (2^j / v) + Σ_{j<k} (2^j / v) + 2^k/(2v) = t_start + 2 · (2^k − 1)/v + 2^{k-1}/v = t_start + (2^{k+1} − 2 + 2^{k-1})/v

(множитель 2 — потому что два направления туда-обратно за каждый предыдущий шаг)

Положение бандита в этот момент: x_b = v · (τ_k − t₀) = v · (t_start − t₀) + 2^{k+1} − 2 + 2^{k-1} = v · (t_start − t₀) + 2.5 · 2^k − 2

Полицейский в +2^k. Условие догнать: 2^k ≥ 2.5 · 2^k − 2 + v · (t_start − t₀). Это даёт 2 − v · (t_start − t₀) ≥ 1.5 · 2^k, что не выполняется при больших k.

То есть простой шаг 2^k действительно не работает: бандит за время челнока уходит дальше, чем 2^k. Нужно, чтобы скорость роста шагов превышала скорость бандита, относительно челночной стратегии.

Шаг 7. Правильный коэффициент роста

Возьмём d_k = α^k с большим α. Время k-го челнока: T_k = α^k / v. Суммарное время:

Σ_{j ≤ k} T_j = (1/v) · (α^{k+1} − α)/(α − 1)

Положение бандита в момент прихода в +α^k:

x_b = v · (t_start − t₀) + Σ_{j < k} α^j · 2 + α^k = v · (t_start − t₀) + 2(α^k − 1)/(α − 1) + α^k

(Здесь множитель 2 — т.к. шаг j < k это туда-обратно. Половина шага k — путь до +α^k.)

Условие поимки: α^k ≥ x_b, т. е. α^k − 2(α^k − 1)/(α − 1) − α^k ≥ v · (t_start − t₀) ⇔ −2 · (α^k − 1)/(α − 1) ≥ v · (t_start − t₀)

Левая часть отрицательная — условие никогда не выполняется. Что-то пошло не так.

Дело в том, что при правильной формулировке бандит и полицейский встречаются по дороге (полицейский едет прямо, бандит тоже). Полицейский в момент пути из 0 в +α^k пересекает все точки [0, α^k]. Бандит едет от +v·(t_start − t₀) + 2·(α^k − 1)/(α − 1)·v / v (его позиция в момент начала шага k)... уезжает дальше со скоростью v. Полицейский едет к нему со скоростью 2v. Относительная скорость 2v − v = v — догоняет!

То есть после некоторого момента, когда полицейский «проходит» точку, в которой был бандит в начале шага k, дальше он его догоняет со скоростью v. Главное условие — чтобы момент начала шага k имел полицейского позади бандита, а в течение шага полицейский двигался в ту же сторону, что и бандит.

Если α достаточно велико, то полицейский в начале шага k (в точке 0) находится позади бандита (в точке ≈ v · τ_k). Дальше он едет вправо со скоростью 2v, бандит вправо со v. Полицейский догоняет за время Δt = v · τ_k / v = τ_k. На это нужно расстояние 2v · τ_k — то есть полицейский должен заехать на это далеко.

Условие: α^k ≥ 2v · τ_k = 2 · α · (α^k − 1)/(α − 1) + 2 · v · (t_start − t₀).

При больших k: α^k ≥ 2α · α^k / (α − 1), т. е. 1 ≥ 2α/(α−1), α − 1 ≥ 2α, α ≤ −1. Не работает.

Шаг 8. Окончательный аргумент

Аккуратно — нужна стратегия, в которой полицейский на длинном шаге вправо (или влево) едет дольше, чем потребовалось бы бандиту убежать с момента начала этого шага. Это значит, что длительность T_k должна расти быстрее, чем суммарное предыдущее время.

Возьмём T_k = 4^k (длительность k-го челнока в обозначениях времени). Тогда d_k = v · T_k = v · 4^k. Сумма предыдущих Σ_{j<k} T_j = (4^k − 1)/3 < 4^k / 3.

В момент шага k (вправо) полицейский тратит время 4^k / 2 = 2 · 4^{k-1} на поездку в +v · 4^k (скорость 2v, расстояние v · 4^k, время 4^k / 2). Возьмём момент времени посередине шага.

Бандит к этому моменту находится в точке v · (t_start − t₀ + 2 · (4^k − 1)/3 + 4^k/4) ≈ v · 4^k · (2/3 + 1/4) = v · 4^k · 11/12.

Полицейский в этой временной точке — на полпути в правую сторону, в v · 4^k / 2. Бандит дальше — v · 4^k · 11/12 > v · 4^k · 6/12 = v · 4^k / 2. Полицейский ещё не догнал.

Но к концу шага вправо полицейский в +v · 4^k. Положение бандита: v · (t_start − t₀ + 2 · (4^k − 1)/3 + 4^k/2) ≈ v · 4^k · (2/3 + 1/2) = v · 4^k · 7/6. Бандит впереди на v · 4^k · 1/6. Полицейский снова не догнал.

Скорость роста позиции бандита больше — нужны еще больше шаги. Никакая постоянная геометрическая прогрессия не работает, потому что бандит и полицейский в конце концов «зависают» в одинаковом отношении.

Правильная стратегия: на шаге k полицейский остаётся в той стороне, пока не встретит бандита. То есть он не возвращается в 0 после шага k, а ждёт там. Если бандит в этой стороне — он догонит. Если нет — после долгого ожидания возвращается.

Формально: полицейский едет вправо на сколь угодно большое расстояние D_k. Если на пути встретил бандита — поймал. Если не встретил — возвращается, едет влево на D_k. Если встретил — поймал; иначе берёт D_{k+1} > D_k.

Гарантия поимки: если бандит едет вправо, то начиная с какого-то D_k > x_b(t_arrive) полицейский догонит его (поскольку расстояние полицейского обгоняет позицию бандита, ведь полицейский идёт со скоростью 2v и не отвлекается на левую сторону на этом шаге).

Это работает, потому что когда полицейский едет в правильную сторону, его скорость строго больше. Условие догона: на каком-то шаге k отрезок [0, D_k] будет больше, чем длина x_b(t_arrive), и пересечение случится.

Шаг 9. Численная иллюстрация

def simulate(v=1.0, t0=0.0, t_start=10.0, bandit_dir=+1, alpha=4):
    """
    Стратегия: полицейский едет вправо на alpha^k, возвращается, едет влево на alpha^k,
    возвращается, увеличивает k. На каждом отрезке проверяет, не встретил ли бандита.
    Скорость полицейского = 2v.
    """
    t = t_start
    pos = 0.0
    k = 0
    speed = 2 * v
    while True:
        for sign in [+1, -1]:
            d = alpha ** k
            target = sign * d
            # Едем от pos к target со скоростью speed
            # Проверяем встречу с бандитом на этом отрезке
            # Бандит: x_b(t) = bandit_dir * v * (t - t0)
            # Полицейский: x_p(τ) = pos + sign * speed * (τ - t), τ >= t
            # Встреча при x_p(τ) = x_b(τ):
            # pos + sign*speed*(τ-t) = bandit_dir * v * (τ - t0)
            # τ * (sign*speed - bandit_dir*v) = -pos + sign*speed*t - bandit_dir*v*t0
            denom = sign * speed - bandit_dir * v
            if denom != 0:
                tau = (-pos + sign * speed * t - bandit_dir * v * t0) / denom
                if t <= tau <= t + abs(target - pos)/speed:
                    return tau, bandit_dir * v * (tau - t0)
            # Не встретили — едем дальше
            t += abs(target - pos) / speed
            pos = target
            # Возврат в 0
            t += abs(pos) / speed
            pos = 0.0
        k += 1
        if k > 100:
            return None
 
print(simulate(bandit_dir=+1, alpha=4))   # поймает
print(simulate(bandit_dir=-1, alpha=4))   # тоже поймает

При достаточно большом α (например, α = 4) программа находит момент поимки за конечное число итераций.

Подводные камни

«Скорость 2× — это с запасом или впритык?» Это строгое превосходство. Если бы было 1.5× или 1× — поимка не гарантирована (скорости относительно равны, бандит может убежать). Если бы было 1× — точно невозможно.
Идея «ехать в одну сторону» не работает: если выбрать неверную сторону, никогда не догоним. Нужна именно челночная (или последовательно расширяющаяся) стратегия.
Время t_start − t₀ — это «фора», которую успел набрать бандит. Главное, что она конечна: если фора бесконечна, поймать невозможно. В задаче фора конечна, поэтому стратегия работает.
Не путать с задачей о «преследовании», где обе стороны видят друг друга. Тут полицейский не видит бандита и не знает его позицию — это задача о поиске.
Доказательство — конструктивное. Достаточно предъявить одну стратегию, которая ловит бандита за конечное время в любой реализации.

Эталонный ответ

Полицейский может поймать бандита за конечное время. Стратегия: челночное движение с экспоненциально растущими шагами в обе стороны от кафе. Поскольку скорость полицейского строго больше скорости бандита (2v > v), на каком-то шаге полицейский гарантированно «накроет» текущую позицию бандита и встретит его на пути. Время поимки — конечное, но может быть большим относительно начальной форы.

Полицейский и бандит на бесконечной дороге: доказать конечное время поимки