Целые числа a, x₁, x₂, ..., x₁₃ таковы, что  a = (1 + x₁)(1 + x₂)...(1 + x₁₃) = (1 – x₁)(1 – x₂)...(1 – x₁₃).  Докажите, что  ax₁x₂...x₁₃ = 0.

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Цепные (непрерывные) дроби ]

Сложность: 4+ Классы: 10,11

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

Условие

Прибор для сравнения чисел  log_ab  и  log_cd  (a, b, c, d > 1)  работает по правилам: если  b > a  и  d > c,  то он переходит к сравнению чисел  log_a^b/_a  и  log_c^d/_c  если  b < a  и  d < c,  то он переходит к сравнению чисел  log_dc  и  log_ba;  если  (b − a)(d − c) ≤ 0,  то он выдаёт ответ.
  а) Покажите, как прибор сравнит числа  log₂₅75  и  log₆₅260.
  б) Докажите, что любые два неравных логарифма он сравнит за конечное число шагов.

Решение

  а)  (log₂₅75, log₆₅260) → (log₂₅3, log₆₅4) → (log₄65, log₃25) → (log₄⁶⁵/₄, log₃²⁶⁵/₃) → (log₄⁶⁵/₁₆, log₃²⁵/₉) → (log₄⁶⁵/₆₄, log₃²⁵/₂₇).  Итак,  log₂₅75 > log₆₅260.

  б) Переформулируем задачу: Прибор для сравнения чисел  x > 0  и  y > 0  работает по правилам:
    1) если  x > 1  и  y > 1,  то он переходит к сравнению чисел  x − 1  и  y − 1;
    2) если  x < 1  и  y < 1,  то он переходит к сравнению чисел y⁻¹ и x⁻¹;
    3) если  (x − 1)(y − 1) ≤ 0,  то он выдаёт ответ.
  Докажем, что любые два неравных числа он сравнит за конечное число шагов.
  Заметим, что эти правила можно заменить на следующие:
    1') если  [x] = [y],  то он переходит к сравнению чисел ¹/_{x} и ¹/_{y} (запоминая, что при выводе ответ надо изменить на противоположный).
    2') если  [x] ≠ [y],  то он выдаёт ответ.
  Пусть x_i, y_i   – пара чисел, получающихся на i-м шаге этого алгоритма. Очевидно, что  [x₁] +   – цепная дробь числа x₁. Аналогично для числа y₁. Итак, наша задача переформулируется следующим образом: у неравных чисел цепные дроби различны. Это следует, например, из того, что последовательность подходящих цепных дробей числа x сходится к числу x (см. задачу 60607).

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