27. [М22] (Д. Зейлбергер (D. Zeilberger).) Найдите рекуррентную формулу, аналогичную (9), для вычисления коэффициентов W{z) = V{z)V{qz)... V{q"~z) при заданных q и тп и коэффициентов V{z) = 1 + Viz + Vzz + . Предполагается, что q не равно корню из единицы.

► 28. [НМ26] Ряд Дирихле - это сумма вида V{z) = Vi/V +v2/2 +V3/3 + ; произведение U{z)V{z) двух таких рядов - это ряд Дирихле W{z), у которого

Обычные степенные ряды - частный случай рядов Дирихле, так как Vo + Viz + Vz + ViZ + = Vo/V + Vil2 4- 1/2/4" + Vs/S" + когда z = 2~ Ha самом деле ряды Дирихле эквивалентны степенным рядам вида V{zi,Z2,...) с произвольным множеством переменных, где z = Pk и р - fe-e простое число.

Найдите рекуррентное соотношение, с помощью которого можно обобщить (9) и формулу из упр. 4, если предположить, что задан ряд Дирихле V(z) и что нужно вычислить (а) W(z) = V{zY, когда Vi = 1; (b) W{z) = ехрТ/(г), когда Vi = 0; (с) W{z) = \nV{z), когда Vi = 1. [Указание. Пусть t(n)-общее число простых множителей п, включая кратные, и пусть о . п "

/п* = ]Сп *(")"/" Покажите, что операция 5 - аналогична производной, например <$е,* = e-SViz)]

"Это, безусловно, мысль,-с некоторым интересом

произнес Пуаро. -

Да, да, я играю роль компьютера, который питается информацией."

"И, предположим, вы получаете все неправильные ответы",-сказала миссис Оливер.

"Это невозможно,-возразил Эркюль Пуаро.- Компьютеры всего лишь сортируют факты."

"Это не предполагается,-сказала миссис Оливер,- но следует удивляться вещам, которые иногда происходят."

- АГАТА КРИСТИ (AGATHA CHRISTIE), Прием в честь дня всех святых (1969)

Кажется невозможным, что некоторый факт становится реальным после ряда фактов без той власти, которая впервые их создала.

ЭДВАРД СТИЛЛИНГФЛИТ (EDWARD STILLINGFLEET),

Начала таинства, 2:3:2 (1662)

ОТВЕТЫ К УПРАЖНЕНИЯМ

Это единственная ветвь математики, я полагаю, в которой хорошие авторы неоднократно получали совершенно ошибочные результаты. . Сомневаюсь, что есть хотя бы один пространный трактат о вероятностях, существующих в природе, который не содержал бы решений, абсолютно недоказуемых.

- Ч. С. ПИРС (С. S. PEIRCE), Popular Science Monthly (1878)

ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ

1. Задача средней сложности для читателей с математическим уклоном,

3. (Решение Роджера Фрея (Roger Frye), полученное после около 110 часов вычислений на Connection Machine в 1987 году): 95800 + 217519" + 414560" = 422481".

4. Один из читателей рукописи этой книги сообщил, что нашел поистине замечательное доказательство. Но, к сожалению, размер его заметки был слишком мал, чтобы вместить его.

РАЗДЕЛ 3.1

1. (а) Вообще говоря, вы потерпите неудачу, так как владельцы телефонов по возможности выбирают "круглые" номера. Вероятно, в некоторых районах телефонные номера устанавливаются случайным образом. Но в любом случае было бы ошибкой пытаться получить несколько последовательных случайных чисел на одной и той же странице, так как один и тот же телефонный номер часто вносится в список несколько раз подряд.

(b) Вы воспользуетесь левой или правой страницей? Допустим, вы выберете номер на левой странице, разделите его на 2 и возьмете правую цифру. Общему числу страниц стедовало бы быть кратным 20, но даже если это так, данный метод все равно обладает определенными недостатками.

(c) Маркировка на гранях кости несколько нарушает симметрию игральной кости, но для практических целей этот метод вполне удовлетворителен (и был использован автором при подготовке нескольких примеров для этой книги). См. Math. Сотр. 15 (1961), 94-95, где обсуждаются игральные кости в виде икосаэдра.

(d) (Этот сложный вопрос включен в качестве сюрприза.) Число не вполне равномерно распределено. Если среднее число зарегистрированных частиц в минуту равно ш, вероятность того, что счетчик зарегистрирует к частиц, равна е~"т/к\ (пуассоновское распределение); так что цифра "О" выпадает с вероятностью е~к>о т"/{10к)\ и т. д. В частности, младшая цифра будет четной с вероятностью e~"cosh7n = f -Ь fe" и она никогда не равна j (хотя ошибка пренебрежительно мала, когда т велико).

Однако совершенно законно взять десять наблюдений (то,.. • .mg) и затем выбрать то j, для которого rrij строго меньше, чем пц для всех i ф j; повторить операцию, если минимальное значение появляется более одного раза (см. (h)).

(е) Окей; подходит, если время, прошедшее с момента выбора цифры, случайно. Тем не менее возможны искажения в граничных случаях.

(f, g) Нет. Люди обычно выбирают определенные цифры с большей вероятностью (см. 7).

(h) Окей; при таком распределении номеров вероятность того, что заданная цифра присвоена выигравшей лошади, равна j.

2. Число таких последовательностей равно полиномиальному коэффициенту 1000000! / (100000!)°; таким образом, искомая вероятность равна этому числу, деленному на ю""""", число всех последовательностей, содержащих миллион цифр. Используя формулу Стирлинга, найдем, что вероятность близка к 1/(1б7г10\/27г) ~ 2.56 х 10~®. Грубо говоря, это происходит в одном случае из 4 х 10.

3. 3040504030.

4. (а) На шаг К11 мы попадаем только после шага К10 или К2, и в любом случае легко обнаружить, что X не может равняться нулю. Если бы X мог принимать значение "нуль" на этом шаге, то алгоритм никогда бы не закончился (программа зациклилась бы).

(Ь) Если X установлено равным 3830951656, то вычисления подобны таким же вычислениям шагов из табл. 1. Разница состоит в том, что мы попадаем в состояние К11 У -I- 1 = 7 раз вместо У --1 = 4 раз; следовательно, 3830951656 5870802097. Аналогично 5870802097 -> 1226919902 -> 3172562687 -> 3319967479 6065038420 -> 6065038420 •.

5. Существует только 10" десятизначных чисел; некоторые значения X должны повториться на первых Ю" -I- 1 шагах. И коль скоро какое-нибудь значение повторится, последовательность повторит свое прежнее поведение (появится периодичность).

6. (а) Используя те же аргументы, что и в предыдущем случае, легко показать, что в последовательности должно в конечном счете повториться одно из значений. Пусть в первый раз такое повторение произойдет на шаге ц + X, где Х+л - Х. (Это условие определяет /i и А.) Мы получим 0</х<т, 0<Л<т, /х4-Л<т. Значения /х = О, \ = т достигаются тогда и только тогда, когда / является циклической перестановкой; и/х = 7гг - 1,Л = 1 встретится, например, если Ао = О, /(ж) = х + 1 для ж < m - 1 и /(ш- 1) = тп - 1.

(b) Для г > п имеем Хг = А„ тогда и только тогда, когда г - п кратно Л и п > /х. Значит, Xin = Хп тогда и только тогда, когда п кратно Л и п > /х. Ожидаемые результаты следуют теперь незамедлительно. [Замечание. Это, в сущности, доказательство известного математического утверждения: "Степени элемента конечной полугруппы включают единственный идемпотентный элемент: возьмите Xi = а, /(х) = ах".]

(c) Как только п найдено, генерируем Xi и Xn+i для г > О до тех пор, пока найдется первое Xi = Хп+С, тогда /х = г. Если ни одно из значений Xn+i при О < г < /х не равно А„, значит, \ - п, иначе Л - наименьшее из таких г.

7. (а) Наименьшее значение п > О, такое, что п - {£{п) - 1) кратно Л и £{п) - 1 > /х, равно п = 28™»(+1)1 1 -I- л. [Это можно сравнить с наименьшим и > О, при котором Х2п = Хп, т. е. Л(Г/х/Л] 4-<$о).]

(Ь) Начните со значения X = Y = Хо, к = т = 1. (На ключевом месте в этом алгоритме получим X = X2m-k-i, Y = Xm-i и тп = £{2т - к).) Для генерирования следующего случайного числа выполним такие шаги. Установим X <- f{X) и fe <- fe - 1. Если X = Y, остановка (длина периода Л равна т - к). Если fe = О, установим У <- А, тп ч- 2тп, к т. Получим X.