Страница 139 из 150
qn-1 < 1/√ε < qn
(5)
и, значит
Поэтому,
Ic(ε) <= 1/2∙I2(ε) + 1/2 + log2 an
Если принять, что 1/q2n < ε, то оценка упрощается:
Ic(ε) <= 1/2∙I2(ε) + 1/2
Таким образом видим, что теоретическая нижняя граница для Ic(ε) — объема данных, потребных для хранения вещественного числа а, оценена нами как сверху (формулы (6) и (6’)), так и снизу (формула (4)). Поэтому в случае больших объемов информации (Ic(ε) —> оо) представление числа в виде цепной дроби требует примерно вдвое меньшего количества бит, т. е. достигаемое сжатие — порядка 50 %.
3. Оценку (6) можно несколько улучшить. Для этого достаточно вместо (3) использовать более точную оценку приближения произвольного числа а подходящими дробями. Именно, ([1]. стр. 30) имеют место неравенства:
(7)
Поэтому если дробь pn/qn — первая из последовательности подходящих дробей, которая приближает число а с точностью ε, то, очевидно, имеют место неравенства:
и в тоже время
Из последнего неравенства вытекает
qn-1qn <= 1/ε (8)
Но
qn-1qn = qn-1(anqn-1 + qn-2) >= anq2n-1
Поэтому (8) превращается в неравенство
каковая оценка является просто уточнением первого из неравенств (5). Поэтому точно так же, как и раньше получаем уточненную оценку для Ic(ε):
Список литературы
[1] А. Я. Хинчин. Цепные дроби. Государственное изд-во физ. — мат. лит-ры. М., 1961.
Задача: Три рыбака ловили рыбу и после ловли заночевали на берегу. Двое рыбаков заснули, а третий решил уехать домой со своей частью улова. Он разделил рыбу на 3 равные части, но при этом одна рыбина оказалась лишней. Он швырнул ее в воду, забрал свою треть и ушел.
Среди ночи проснулся второй рыбак и тоже решил уехать. Не зная, что первый рыбак уже ушел, он тоже поделил всю рыбу на 3 равные части, одна рыбина снова оказалась лишней, он ее тоже выкинул и ушел.
То же произошло и с последним рыбаком: проснувшись, он тоже разделил оставшийся улов на 3 равные части, выкинул одну рыбину и ушел.
Вопрос: какое наименьшее количество рыб могло быть у рыбаков?
Решение П. А. М. Дирака: Рыб было (-2). После того, как первый рыбак выкинул одну рыбину в воду, их осталось (-2) — 1 = -3. Потом он ушел, унося (-1) рыбу. Рыб стало (-3) — (-1) = -2. Второй и третий рыбаки просто повторили поступок своего товарища.
Из книги "Физики продолжают шутить".
На самом деле решение Дирака, хоть и остроумно, но, строго говоря, неверно, и во всяком случае неполно. Приведем полное, "математическое" решение, т. е. найдем ВСЕ решения.
Решение.
Пусть в начале рыб было n0 (количество, после того, как уехало 0 рыбаков). Первый рыбак выбросил одну (лишнюю) рыбину (n0 — > n0 — 1), после чего количество рыбин стало делиться на 3, и взял 1/3 оставшегося улова, и после себя он оставил n1 = (2/3)∙(n0 — 1) рыбин. Аналогичным образом действовали и остальные рыбаки, так что после отъезда 2-го рыбака рыб осталось n2 = (2/3)∙(n1 — 1), а после отъезда 3-го — n3 = (2/3)∙(n2 — 1). Подставляя в последнее равенство выражения для n2 и n1, получаем:
В итоге получаем уравнение, требующее разрешения в целых числах:
8n0 — 27n3 = 38.
Для упрощения расчетов имеет смысл уменьшить входящие в уравнение числа перейдя к новым переменным n0 = n0 + k, n3 = n3. Если взять k = 5, то уравнение превратится в
27n3 — 8n0 = 2. (1)
Это уравнение имеет вид
ах — by = с (1')
т. е. является диофантовым уравнением, и нужно найти все решения данного уравнения. Как это сделать?
Взглянем на уравнение (1') с точки зрения теории сравнений. В самом деле, требуется найти такое число х, что ах отличается от заданного числа с на слагаемое, кратное Ь. Иными словами, разность ах — с делится на Ь, т. е. (ах — с) = ()(mod b) или
ах = c(mod Ь). (1")
То же самое можно выразить словами: "ах сравнимо с с по модулю b" или "ах принадлежит тому же классу вычетов по модулю Ь, что и с". Т. е. мы свели уравнение с двумя неизвестными (х и у) к уравнению с одним неизвестным, поскольку ясно, что из (1'), зная х, сразу же можно найти у. Однако х все же не произволен, а именно — удовлетворяет (1").
Кроме того, можно усмотреть следующее. Уравнение (1') (или (1")) — это неоднородное сравнение первой степени (т. е. линейное сравнение). Согласно общей теории, общее решение неоднородного сравнения есть сумма частного решения неоднородного сравнения и общего решения однородного сравнения ах = ()(mod b). Таким образом, задача разбилась на две.
Займемся сначала неоднородным сравнением (1") — Рассматривая эквивалентное уравнение (1'), замечаем (стандартное рассуждение — см. [1]), что если числа а и b делятся на число k, то на это же число должно делиться и с. Поскольку это верно для любого общего делителя а и Ь, то это верно и для их наибольшего общего делителя (а, Ь) =< 1. Таким образом, делимость с на <1 — необходимое условие разрешимости сравнения (1").
В нашем случае а = 27, b = 8, (а, Ь) = 1, т. е. числа а и b взаимно просты, поэтому сравнение (1") разрешимо при любом с.
Из приведенного рассуждения следует и способ решения сравнения (1") — Если мы умеем решить уравнение ах0 — by0 =< d, то умножив его на целое число c/d (поскольку необходимо с делится на d), мы получим решение уравнения (1').
В нашем случае d = 1, и кратчайший способ решения уравнения ах0 — by0 = 1 дается в [2]. Именно, надо разложить число a/b в цепную дробь, и если а = рn, b = qn то положить х = (-1)n-1qn-1, y = (-1)n-1pn-1.Это следует просто из того, что qn_1pn — qnpn-1 = (-1)n-1.