Назад
Задача

Прибор для сравнения чисел  logab  и  logcd  (a, b, c, d > 1)  работает по правилам: если  b > a  и  d > c,  то он переходит к сравнению чисел  logab/a  и  logcd/c  если  b < a  и  d < c,  то он переходит к сравнению чисел  logdc  и  logba;  если  (b − a)(d − c) ≤ 0,  то он выдаёт ответ.

  а) Покажите, как прибор сравнит числа  log2575  и  log65260.

  б) Докажите, что любые два неравных логарифма он сравнит за конечное число шагов.

Решение

  а)  (log2575, log65260) → (log253, log654) → (log465, log325) → (log465/4, log3265/3) → (log465/16, log325/9) → (log465/64, log325/27).  Итак,  log2575 > log65260.   б) Переформулируем задачу: Прибор для сравнения чисел  x > 0  и  y > 0  работает по правилам:

    1) если  x > 1  и  y > 1,  то он переходит к сравнению чисел  x − 1  и  y − 1;

    2) если  x < 1  и  y < 1,  то он переходит к сравнению чисел y−1 и x−1;

    3) если  (x − 1)(y − 1) ≤ 0,  то он выдаёт ответ.

  Докажем, что любые два неравных числа он сравнит за конечное число шагов.

  Заметим, что эти правила можно заменить на следующие:

    1') если  [x] = [y],  то он переходит к сравнению чисел 1/{x} и 1/{y} (запоминая, что при выводе ответ надо изменить на противоположный).

    2') если  [x] ≠ [y],  то он выдаёт ответ.

  Пусть xi, yi   – пара чисел, получающихся на i-м шаге этого алгоритма. Очевидно, что  [x1] +   – цепная дробь числа x1. Аналогично для числа y1. Итак, наша задача переформулируется следующим образом: у неравных чисел цепные дроби различны. Это следует, например, из того, что последовательность подходящих цепных дробей числа x сходится к числу x (см. задачу 160607).

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет