Интернет-журнал 'Домашняя лаборатория', 2007 №1 - Цыбанова

1/q2n < ε => qn > 1/√ε

Остается получить оценку сверху для qn, причем требуется оценить qn величиной, связанной с Ic. Сделаем это.

Для знаменателей qn подходящих дробей справедливо рекуррентное соотношение (см. [1], стр. 11, формула (7))

qк = aкqк-1 + aкqк-2,

причем по определению полагается q-1 = 0, q0 = 1. Тогда q1 = а1, q2 = a2a1 + 1, q3 = a3a2a1 + a3 + a1 и т. д.

Лемма. Для знаменателей qn верна оценка qn <= 2n-1πn, где πn= Пn i=1= ai.

Доказательство (методом мат. индукции). Для n = 1 утверждение верно, ибо q1 = а1. Предположим, что оценка верна для всех k и n. Тогда

поскольку выражение в круглых скобках не превосходит единицы ибо аn >= 1, аn+1 >= 1. Лемма доказана.

Опираясь теперь на лемму, заключаем, что для аппроксимации числа α с точностью ε должно быть:

1/√ε < qn =< 2n-1Пni-1 ai

Следовательно, используя (2), находим:

Таким образом, учитывая (1), получаем соотношение:

Ic(ε) >= (1/2)∙I2(ε) - n + 3/2

Впрочем, данная оценка довольно груба. Ее можно немного усилить.

С другой стороны, очевидно, qn >= Пn i=1 ai (доказывается тоже индукцией), поэтому если

1/q2n < ε < 1/q2n-1

то

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" или "ах принадлежит тому же классу вычетов по модулю Ь, что и с". Т. е. мы свели уравнение с двумя неизвестными (х и у) к уравнению с одним неизвестным, поскольку ясно,