|
|
 |
Условие
Прибор для сравнения чисел 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 (см. задачу 60607).
