Назовём белыми числа вида $\sqrt{a+b\sqrt{2}}$, где $a$ и $b$  — целые, не равные нулю. Аналогично, назовём чёрными числа вида $\sqrt{c+d\sqrt{7}}$, где $c$ и $d$  — целые, не равные нулю. Может ли чёрное число равняться сумме нескольких белых?

   Решение

Темы:    [ Теория игр (прочее) ] [ Наибольшая или наименьшая длина ] [ Рекуррентные соотношения (прочее) ] [ Процессы и операции ]

Сложность: 5 Классы: 9,10,11

Прислать комментарий

Условие

Три прямолинейных коридора одинаковой длины l образуют фигуру, изображённую на рисунке. По ним бегают гангстер и полицейский. Максимальная скорость полицейского в 2 раза больше максимальной скорости гангстера. Полицейский сможет увидеть гангстера, если он окажется от него на расстоянии, не большем r. Доказать, что полицейский всегда может поймать гангстера, если:   а)  r > ^l/₃;   б)   r > ^l/₄;   в)   r > ^l/₅;   г)   r > ^l/₇.

Решение

  Договоримся, что полицейский всегда движется с максимальной скоростью. Сначала он "прочёсывает" коридор OC. Убедившись, что гангстера там нет, полицейский удаляется в коридор OA на расстояние 2r и затем возвращается в точку O. Пусть отсюда он не увидел гангстер. Заметим, что тогда он не может находиться в коридоре OC: если бы он за время отсутствия полицейского в точке O попытался перебежать из коридора OB в коридор OC, то к моменту возвращения полицейского в точку O расстояние от гангстера до O было бы не больше, чем r.

  а) Если  l ≤ 3r,  то гангстер не может находиться и в коридоре OA, и полицейский ловит его, "прочесав" коридор OB.

  б) Пусть  3r < l ≤ 4r.  Тогда гангстер может находиться в коридоре OA, но на расстоянии от O , большем 2r.
  Теперь полицейский отправляется в коридор OB на расстояние 3r. Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OB гангстера нет. Но и в коридоре OC гангстера нет (если гангстер находился в коридоре OA, то на расстоянии от O, большем 2r, и потому до возвращения полицейского в точку O, гангстер не сможет перебежать в коридор OC так, чтобы при этом оказаться от O на расстоянии, большем r). Осталось "прочесать" коридор OA.

  в) Пусть  4r < l < 5r.  Тогда гангстер может находиться в коридоре OB, но на расстоянии от O, большем  (3r + r) – ^3r/₂ = ^5r/₂.
  Дальнейшие действия полицейского заключаются в том, чтобы углубляться то в коридор OB, то в коридор OA на все большие расстояния, но так, чтобы гангстер не смог перебежать в коридор OC. Каждое такое "углубление" вместе с последующим возвратом в точку O будем называть циклом. Два первых цикла уже описаны.
  Пусть после n-го цикла полицейский знает, что в коридоре OC гангстера нет, а в коридоре OX (где  X = A  при нечётном n и  X = B  при чётном n) гангстер может находиться только на расстоянии от O, большем y_n. Тогда в следующем цикле полицейский отправляется в другой коридор на расстояние  y_n + r.  Вернувшись в точку O, полицейский знает, что в коридоре OC гангстера нет, а в только что исследованном коридоре гангстер может находиться только на расстоянии от O, большем  y_n+1 = (½ (y_n + r) + r) = ½ (y_n + 3r).  Если же  y_n + r ≥ l – r,  то в исследованном коридоре гангстера вообще нет.
  Так как  3r – y_n+1 = ½ (3r – y_n),  то  3r – y_n = 2^1–n(3r – y₁) = 2^1–nr,  то есть  y_n = 3r – 2^1–nr.  Гангстер ловится, если  y_n + r ≤ l – r  при каком-нибудь n, то есть если  2^1–nr ≤ 5r – l.  Поскольку  l < 5r,  то после достаточно большого числа циклов гангстер ловится.

  г) Пусть  5r ≤ l < 7r.  Положим  ε = ½ (7r – l).  Полицейский действует так, как описано в п. в), пока при каком-то не окажется, что  y_n ≥ 3r – ε  (из формулы для y_n следует, что когда-то это произойдёт). После этого полицейский углубляется в очередной коридор (скажем, OA) на расстояние  l – r.
  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OA гангстера нет, а в коридоре OC гангстер не может находиться от O на расстоянии, большем   (l – r) – (3r – ε) = 3r – ε.  Затем полицейский углубляется в коридор OC на расстояние  4r – 2ε.  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OC гангстера нет (в противном случае гангстер был бы пойман, оказавшись в коридоре OC от полицейского на расстоянии, меньшем  (3r – ε) + ½ (4r – 2ε) – (4r – 2ε) = r),  а в коридоре OA гангстер не может находиться на расстоянии от O, большем
(4r – 2ε) – r = 3r – 2ε.  Затем полицейский идёт в коридор OA на расстояние  4r – 4ε,  затем в коридор OC на расстояние  4r – 8ε,  снова в коридор OA на расстояние  4r – 16ε  и т. д. Когда окажется, что надо идти на отрицательное расстояние, полицейский понимает, что гангстер находится в коридоре OB.

Источники и прецеденты использования