► 35. [М20] Пусть т и п - целые числа и га > 0. Докажите, что равенства

[{х + т)/п\ = [{[х}+т)/п\

выполняется для всех действительных х. (Заметим, что т = О - это очень важный частный случай.) Будет ли справедливо аналогичное равенство для функции "потолок"?

36. [М23] Докажите, что ELiL*/2J = L"V4J; вычислите также сумму Е*=1Г*/21

► 37. [МЗО] Пусть т и га - целые числа, га > 0. Покажите, что

тк + X

0<*;<п

где d - наибольший общий делитель m и га, а х-любое действительное число.

38. [М26] (Е. Буше (Е. Busche), 1909.) Докажите, что для всех действительных чисел х

и у, причем у > 0:

Е U + l = N + Lx + iJ(M-2/)J.

в частности, если у - целое положительное число, то, обозначив его через га, получим важную формулу:

Lxj +

х+ -raj

га-1

= [raxj.

+ ••• +

39. [НМ35] Функция /, для которой /(х) + /(х + ) Н----+ /(х + =) = /(гах), где га -

любое положительное целое число, навывается репликативной функцией. Из предыдущего упражнения следует, что функция [xJ репликативна. Покажите, что репликативны следующие функции:

a) /(x) = x-i;

b) fix) = [х - целое число];

c) fix) = [х - положительное целое число];

d) fix) = [существует рациональное число г и целое т, такие, что х = гтт+т];

e) еще три функции, аналогичные функции из (d), для которых г и/или т рассматриваются только на множестве положительных чисел;

О /(х) = log 2sin7rx, если допускается значение /(х) = -оо;

g) сумма любых двух репликативных функций;

h) произведение репликативной функции на константу;

i) функция д(х) = /(х - [xJ), где /(х) репликативна.

40. [НМ46] Исследуйте класс репликативных функций; определите все репликативные функции специального типа. Например, является ли функция из п. (а) в упр. 39 единственной непрерывной репликативной функцией? Интересно рассмотреть также более общий класс функций, для крторых

fix) + f(x++-+f(x + ~ =а„/(гах)+Ь„

Здесь а„ и Ь„ -это числа, которые зависят от га, но не зависят от х. Производные и интегралы от данных функций (если Ьп = 0) относятся к этому же типу. Если мы потребуем, чтобы Ьп = О, то получим, например, многочлены Бернулли, тригонометрические функции cotTfx и cscTfx, а также обобщенную дзета-функцию Гурвица C(s,x) = X]fc>o /( + где S фиксировано. При Ьп / О получим другие хорошсКдавестные функции, например пси-функцию.

41. [М23] Пусть 01, а2, аз,.. - -последовательность 1, 2, Т, 3, 3, 3, 4, 4, 4, 4, .... Выразите а» как функцию от га с помощью функций "пол" и/или "потолок".

42. [М24] (а) Докажите, что

п п- 1

ок - па„ - к(ак+1 - ак), если тг > 0.

(Ь) Предыдущая функция используется для вычисления сумм, в которых присутствует функция "пол". Докажите, что если b - целое число и Ь > 2, то

X:Liogb fcj = (п + 1) Llogb nj - (ь-ь "J+1 - - 1).

43. [MS5] Вычислите сумму 53i[\/fcJ.

44. [М24] Покажите, что ]Ct>o ]Ci<j<b L(" + jb*)/b*""ij = n, если Ь и n-целые числа, п > О и Ь > 2. Чему равна эта сумма при п < О?

► 45. Результат упр. 37 несколько удивляет, так как из него следует, что

0<*<г.

тк + X п

0<к<т

пк + X

Это "соотношение взаимности" -только один пример из множества подобных формул (см. раздел 3.3.3), Покажите, что для любой функции /

Е /(?) = Е fSl(/(-!)-/И)+n/(m-i).

0<j<n J 0<r<m

В частности, докажите, что

0<j<n 0<j<m

[Указание. Выполните замену переменных г = [mj/nj. Биномиальные коэффициенты () обсуждаются в разделе 1.2.6.]

46. [М29] (Обобщенный закон взаимности.) Обобщите формулу из упр. 45 таким образом, чтобы получить выражение для суммы ]Co<j<an/(Lj/J) ""Д® - любое положительное действительное число.

► 47. [М31] Пусть р - нечетное простое число. Определим символ Лежандра, (~), считая его равным +1, О или -1, в зависимости от того, чему равно q-f~ modp: 1, О или р-1. (См. упр. 26.)

a) Пусть q не кратно р. Покажите, что числа

( jl2t,/pj(2fcgniodp), 0<fc<p/2,

сравнимы по модулю с числами 2, 4, р - 1, взятыми в определенном порядке. Следовательно, (j) = (-1)", где а = Eo<*<p/2L2fe9/pJ-

b) Используйте результат (а) для вычисления ().

c) Пусть q - нечетное число. Покажите, что

Eo<*<p/2L2fe9/iPj =Eo<k<p/2[l<l/pi (по модулю 2).

[Указание. Рассмотрите величину [(р-1 - 2k)q/p\.]

d) Воспользуйтесь общей формулой взаимности из упр. 46, чтобы получить закон квадратичной взаимности: (f)(f) " (-!)")("/*, если р и q - различные нечетные простые числа.

48. [М26] Пусть m и п-целые числа. Докажите или опровергните следующие тождества:

т + п - 1

49. [M3ff] Предположим, что целочисленная функция /(х) удовлетворяет следующим двум простым условиям; (i) /(х + 1) = /(х) -+ 1; (ii) для всех положительных целых п /(х) = f{f{nx)/n). Докажите, что для всех рациональных х либо /(х) = [xJ, либо /(х) = fx].

1.2.5. Перестановки и факториалы

Перестановкой п объектов называется способ последовательного расположения п различных объектов с учетом порядка. Например, для трех объектов {а, Ь, с} существует шесть перестановок:

обе, асЪ, Ьас, be а, cab, cba. (1)

Свойства перестановок играют очень важную роль в анализе алгоритмов; далее в этой книге мы установим много интересных фактов, касающихся перестановок (permutation)*. А пока наша задача - просто сосчитать их, т. е. выяснить, сколько имеется возможных перестановок для п объектов. Существует п способов выбора крайнего объекта слева (первого); после того как этот выбор сделан, существует п-1 способ выбора следующего за ним объекта. Таким образом, получаем п(п - 1) способов выбора объектов для первых двух позиций. Аналогично третий объект можно выбрать п - 2 способами, что в итоге дает п{п - 1)(п - 2) возможных способов выбора первых трех объектов. В общем случае, обозначив через Рпк количество способов выбора А; объектов из п с учетом порядка, получим

Рпк=п(п-1)...{п-к + 1). (2)

Отсюда вытекает, что общее число перестановок выражается формулой

Рпп = п(п - 1) ... (1).

Для наших прикладных целей очень важное значение имеет процесс построения всех перестановок из п объектов методом индукции в предположении, что все перестановки из п - 1 объектов уже построены. Давайте перепишем (1), заменив буквы {а, 6,с} цифрами {1,2,3}; тогда получим следующие перестановки:

12 3, 13 2, 213, 2 3 1, 3 1 2, 3 21. (3)

А теперь давайте подумаем, как из этого набора получить все возможные перестановки из четырех цифр {1,2,3,4}. Существует два основных метода перехода от перестановок из п - 1 объектов к перестановкам из п объектов.

Метод 1. Для каждой перестановки oi ог ... a„ i из {1,2,...,п-1} объектов построим еще п перестановок, помещая число п на все возможные места, в результате чего получим

noi 02 ... а„ 1, Ol пог ... а„ 1, 0102 ..na„ i, oj 02 ... a„ i п.

* В связи с чрезвычайной важностью перестановок Вогад Пратт (Vaughan Pratt) предложил для краткости называть их "perms". Как только предложение Пратта будет принято, учебники по прогпаммипованию немного "похудеют (и, возможно, подешевеют).