«ЗАД АЧИ П О АЛГЕ БР Е, АР И Ф МЕ Т И КЕ И АН АЛИ ЗУ Учебное пособие Москва Издательство МЦНМО 2007 УДК 512.1+517.1+511.1 ББК 22.141+22.161 П70 Прасолов В. В. П70 Задачи по алгебре, арифметике и анализу: Учебное пособие. ...»

Положим в исходном уравнении x = 0. В результате получим а значит, f(y) = Легко проверить, что функция f(x) = acx удовлетворяет данному функциональному уравнению.

34.14. Эквивалентное условие таково: (f2 (x)) = 0, поэтому функция f2 (x) постоянна. Из непрерывности функции f следует, что функция f(x) тоже постоянна.

34.15. Для x = 0 получаем 0 = 26P(0), т. е. P(0) = 0. Для x = 1 получаем P(0) = 25P(1), т. е. P(1) = 0. Далее полагаем x = 2, 3,..., 25 и последовательно получаем 2P(1) = 24P(2),...

..., 25P(24) = P(25). Поэтому P(0) = P(1) =... = P(25) = 0. Значит, P(x) = x(x 1)(x 2)... (x 25)Q(x), где Q(x) — некоторый многочлен. При этом из тождества xP(x 1) = (x 26)P(x) следует, что Q(x 1) = Q(x), т. е. Q(x) = c — постоянное число.

для всех x и t. Рассмотрим многочлен Q(t, x) = P(x, t + x). Он обладает следующим свойством: Q(t, x) = Q(t, x + 1) для всех x.

Поэтому Q(t, x) не зависит от x. Действительно, фиксируем t = t и рассмотрим многочлен g(x) = Q(t0, x). Тогда g(x + 1) g(x) = 0, поэтому g(x) — константа.

34.17. При y = 0 и y = 1 уравнение (1) принимает вид 480 Глава 34. Функциональные уравнения Следовательно, Это равенство выполняется при x = 0, 1, а при чётном n нужно ещё исключить и x = 1/2.

Фиксировав y = 2 и y = 4, аналогичным образом получим равенство которое выполняется при x = 2, 3, 4.

В итоге получаем, что функция h бесконечно дифференцируема, но тогда из (2) и (3) следует, что функция f тоже бесконечно дифференцируема.

Продифференцировав n раз по x равенство (1), получим При фиксированном x из этого равенства следует, что gn (y) — многочлен. Теперь можно продифференцировать равенство (1) по x не n, а n 1 раз и аналогичным образом получить, что gn1 (y) — многочлен, и т. д. В частности, g0,..., gn бесконечно дифференцируемы.

Продифференцируем равенство (1) по y и положим y = 0. В результате получим Из этого равенства следует, что xn1 h(x) — многочлен степени не выше n. А если равенство (1) продифференцировать n раз по y и положить y = 0, то можно показать, что h(x) — многочлен (тоже степени не выше n). Но если h(x) — многочлен, а xn1 h(x) — многочлен степени не выше n, то h(x) = ax + b.

Так как h(x) = ax + b и f(x) бесконечно дифференцируема, то из (2) следует, что f(x) — многочлен степени не выше n + 1.

Поэтому С другой стороны, заменив x на x + y, соотношение (1) можно записать в виде Это означает, что 34.18. Оба утверждения непосредственно следуют из задачи 34.17.

34.19. Дело в том, что если равенство (3) выполняется при всех вещественных x, y, x = y, то Чтобы доказать это, заменим в (3) x на x + y, а y на x y. В результате получим при всех вещественных x, y, y = 0. Положив в (4) x = u + v и x = u v, получаем Заменим теперь в (4) x на u, а y сначала на v y, а потом на y v:

Сравнивая сумму этих двух уравнений с суммой предыдущих уравнений, получаем Положив u + v = x, u v = y, получим требуемое равенство 482 Глава 34. Функциональные уравнения 34.20. а) Если = 1 и f(x) = a0 xn + a1 xn1 +... + an, где a0 = 0, то получаем тождество Такое тождество возможно лишь в том случае, когда a1 = a1 + a0 n, т. е. = 0.

Если = 1, то уравнение f(x + ) = f(x) после замены g(x) = f(x + /2) сводится к уравнению g(x) = g(x), решениями которого служат многочлены вида б) При произвольном сравнение коэффициентов при старшем члене многочлена f(x) = a0 xn +... показывает, что n = 1.

34.21. Достаточно рассмотреть многочлены вида f(x) = xn + j = 1,..., n 1. Доказательство проведём индукцией по j.

Сравнение коэффициентов при xnj для многочленов f(x) и f( x + ) показывает, что поэтому База индукции доказана.

Для доказательства шага индукции (т. е. перехода от j = k к j = k + 1) мы снова воспользуемся соотношением (1) и условием = 1. По предположению индукции as = Cs при s= 1,..., k.

Поэтому Легко проверить, что Cs Ck+1s = Ck+1 Cs. Поэтому Ясно также, что выражение в квадратных скобках равно Следовательно, Учитывая, что = 1, получаем

ЦЕПНЫЕ ДРОБИ

35.1. Определение и основные свойства Рассмотрим бесконечную последовательность натуральных чисел a1, a2,... Пусть a0 — целое число и и т. д. Дробь pk /qk называют подходящей дробью порядка k для рассматриваемой последовательности, а предел lim pk /qk = = [a0 ; a1, a2,...] называют цепной дробью*.

разложение в цепную дробь, т. е. последовательность чисел a0, a1,..., для которой [a0 ; a1, a2,...] =. А именно, a0 = [ ], * Такое название пришло из немецкого языка (Kettenbruchen). Иногда используется название непрерывные дроби, которое пришло из английского языка (continued fractions).

35.1. Докажите, что цепная дробь [0; 1, 1, 1,...] равна отношению меньшего отрезка к большему в золотом сечении, а цепная дробь [1; 1, 1, 1,...] — отношению большего отрезка к меньшему.

35.2. Докажите, что цепные дроби связаны с алгоритмом Евклида следующим образом. Пусть m < n — два натуральных числа. Применим к ним алгоритм Евклида:

35.3. Пусть p0 = a0 и q0 = 1.

а) Докажите, что при k 2 выполняются соотношения pk = ak pk1 + pk2 и qk = ak qk1 + qk2.

б) Докажите, что pk1 qk qk1 pk = (1)k.

в) Докажите, что pk2 qk qk2 pk = (1)k1 ak.

35.4. Докажите, что последовательность pk /qk сходится.

35.5. Решите в натуральных числах уравнение 35.6. Докажите, что Рассмотрим последовательность многочленов K0 = 1, K1 (x1 ) = x1, Согласно задаче 35.3 a) получаем pn = Kn+1 (a0,..., an ) и qn = 35.7. Докажите, что Kn (x1,..., xn ) представляет собой сумму всех мономов, которые получаются из x1 x2... xn вычёркиванием нескольких непересекающихся пар соседних переменных xi xi+1. При этом можно как ничего не вычёркивать, так и вычёркивать всё; в последнем случае считаем, что остаётся моном 1 (Эйлер).

35.8. Докажите, что другое рекуррентное соотношение приводит к той же самой последовательности многочленов.

35.9. Докажите, что количество мономов в Kn (x1,..., xn ) равно числу Фибоначчи Fn+1.

Пусть — положительное число, x и y — целые неотрицательные числа, причём y > 1. Дробь x/y называют наилучшим приближением числа, если для любой другой дроби a/b с меньшим знаменателем выполняется неравенство |a b | > |x y |.

35.10. Докажите, что наилучшими приближениями числа являются подходящие дроби разложения в цепную дробь и только они.

Здесь мы обсудим ещё один подход к построению решений уравнения Пелля, основанный на разложении числа d в цепную дробь.

35.11. Пусть d — натуральное число, свободное от квадратов. Тогда все решения уравнения x2 dy2 = ±1 в натуральных числах находятся среди подходящих дробей разложения числа d в цепную дробь.

Теперь нужно выяснить, какие именно подходящие дроби соответствуют решениям уравнения x2 dy2 = ±1.

Пусть и — корни одного и того же неприводимого квадратного трёхчлена, т. е. и — сопряжённые числа (см. с. 76).

Квадратичную иррациональность называют приведённой, если > 1 и 1 < < 0, т. е. 1/ > 1. Например, квадратичная иррациональность [ d] + d приведённая.

35.12. Докажите, что цепная дробь приведённой квадратичной иррациональности чисто периодическая, т. е. она 35.13. Пусть d = [a0 ; a1,... , ak1, 2a0, a1,...], т. е. число k делится на период. Докажите, что тогда подходящая дробь pk1 /qk1 даёт решение уравнения x2 dy2 = (1)k.

Ясно также, что x > 0. Решая квадратное уравнение и отбрасывая отрицательный корень, получаем требуемое.

Пусть y = [1; 1, 1, 1,...]. Тогда y 1 = 1/y, т. е. y(y 1) = 1.

Ясно также, что y > 0. Решая квадратное уравнение и отбрасывая ys+1 = 0). Действительно, это равенство эквивалентно равенству rk1 = rk ak + rk+1 (нужно положить m = r0 и n = r1 ). Следовательно, ys = [0; as ], ys1 = [0; asa, as ],..., y0 = [0; a0,..., as ], что и требовалось.

35.3. а) Применим индукцию по k. При k = 2 требуемые соотношения легко проверяются. Если a0, a1,... рассматривать как независимые переменные, то имеет место очевидное равенство Поэтому согласно предположению индукции qk+ б) и в) легко следуют из а).

согласно задаче 35.3 в) Поэтому (для иррационального ) приближение числа d.

. Изменив при необходимости знак числа Q = 2a, можно Пусть = [a0 ; a1, a2,...]. Рассмотрим остаточный член k = = [ak ; ak+1, ak+2,...]; при этом = [a0 ; a1,..., ak1, k ].

Ш а г 1. Остаточные члены k принимают лишь конечное число различных значений. В частности, k = l для некоторых Значит, Q > 0 и P > 0. По условию < 0 и > 1, поэтому P < D и Q < P + D < 2 D. Таким образом, при фиксированном D существует лишь конечное число приведённых квадратичных иррациP+ D Покажем, что — приведённая квадратичная иррациональP1 + D где P1 = a0 Q P. Напомним, что P= b, Q= 2a и D = b2 4ac. Поэтому число P2 D = a2 Q2 + 2a0 Q + 4ac делится на Q. Следовательно, ная иррациональность вида, где Pk, Qk — целые числа, ведённых квадратичных иррациональностей такого вида конечно.

Достаточно проверить, что если и 1 — приведённые квадратичные иррациональности, связанные соотношением вида = = a0 + 1, где a0 — натуральное число, то число однозначно этому a0 =. Число a0 однозначно восстанавливается по 1, поэтому число тоже восстанавливается.

35.13. Рассмотрим число где + a0. Это число удовлетворяет квадратному уравk нению Следовательно, pk1 qk2 = 2a0 k1 и pk2 = (d a2 )k1.

Соотношение pk2 k1 k2 pk1 = (1)k1 можно переписать в виде (1)k1 = (d a2 )q2 k1 (k1 2a0 qk1 ) =

ФОРМАЛЬНЫЕ РЯДЫ

И ПРОИЗВОДЯЩИЕ ФУНКЦИИ

Формальным рядом называют выражение вида a0 + a1 x + a2 x2 + + a3 x3 +... При этом ряд может расходиться при всех x = 0; нас интересуют только коэффициенты a0, a1,... Тем не менее, мы будем использовать обозначение f(x) = a0 + a1 x + a2 x2 + a3 x3 +...;

при этом функция f может быть не определена для всех x = 0.

Для формальных рядов f(x) = a0 + a1 x + a2 x2 +... и g(x) = = b0 + b1 x + b2 x2 +... можно определить их сумму и произведение как формальные ряды Формальный ряд, для которого a0 = 1 и ak = 0 при k 1, мы будем обозначать 1.

Будем считать, что f(x) = g(x), если f(x) = a0 + a1 x + a2 x2 +...

x3 +... Вычислите произведения: а) f(x)f(x); б) f(x)g(x).

36.2. Пусть f(x) = 1 + x + x2 + x3 +... Вычислите формальный ряд g(x), для которого f(x)g(x) = 1.

36.3. Пусть f(x) = a0 + a1 x + a2 x2 +... — формальный ряд, причём a0 = 0. Докажите, что существует единственный формальный ряд g(x) = b0 + b1 x + b2 x2 +..., для которого f(x)g(x) = 1.

494 Глава 36. Формальные ряды и производящие функции вают формальный ряд D(f(x)) = 36.4. Докажите, что формальная производная обладает следующими свойствами обычной производной:

а) D(f(x) + g(x)) = D(f(x)) + D(g(x));

б) D(f(x)g(x)) = f(x)D(g(x)) + g(x)D(f(x));

в) D(f(x)n ) = nf(x)n1 D(f(x)) для любого натурального n;

г) если существует формальный ряд f(x)1, то D(f(x)1 )= =f(x)2 D(f(x)) и D(f(x)n )=nf(x)n1 D(f(x)) для любого натурального n.

д) D(fr ) = rfr1 D(f) для любого рационального числа r и любого формального ряда f = 1 + a1 x + a2 x2 +...

36.5. Для формального ряда f = a0 + a1 x + a2 x2 +... полоxn 36.6. Докажите, что для любого натурального n и любого формального ряда f(x) = 1 + a1 x + a2 x2 +... существует единственный формальный ряд g(x) = 1 + b1 x + b2 x2 +..., для которого g(x)n = f(x).

Ряд g(x) мы будем обозначать 36.7. Докажите, что для любого рационального числа r Назовём формальной экспонентой формальный ряд 36.8. Докажите, что: а) Exp((a + b)x) = Exp(ax) · Exp(bx);

б) Exp(kx) = (Exp(x))k для любого натурального числа k.

36.9. Докажите, что Пусть f = 1 + a1 x + a2 x2 +... — формальный ряд. Формальным логарифмом f называют формальный ряд где g = f 1 = a1 x + a2 x +... Отметим, что формальный ряд Ln(f) корректно определён, поскольку коэффициент при xn полностью определяется конечной суммой g g2 + g3... + (1)n+1 gn.

36.10. Докажите, что D(Ln(f)) = f1 D(f).

36.11. Докажите, что если f = 1 + a1 x + a2 x2 +... и h = 1 + + b1 x + b2 x2 +..., то Ln(fh) = Ln(f) + Ln(h).

36.12. Докажите, что Ln(fr ) = r Ln(f) для любого рационального числа r.

36.13. Докажите, что если Ln(f) = Ln(h), то f = h.

36.14. Докажите, что если g = a1 x + a2 x2 +... и r — любое рациональное число, то 36.15. Бесконечные последовательности a0, a1,.. . и b0, 36.5. Тождества для формальных рядов ствует корректно определённый формальный ряд.

496 Глава 36. Формальные ряды и производящие функции 36.17. Докажите следующие тождества:

36.18. Пусть s(n) — сумма тех делителей d числа n, для которых n/d нечётно (s(n) = 0 при n 0).

D(f) = 2fg.

б) Докажите, что s(n) 2s(n 1) + 2s(n 22 ) 2s(n 32 ) + +... = (1)n+1 n, если n — полный квадрат; в противном случае эта альтернированная сумма равна нулю.

36.19. а) Используя результат задачи 36.18 б), докажите, что любое простое число p вида 4k + 1 можно представить в виде суммы двух квадратов.

б) Докажите, что любое простое число p вида 8k + 3 можно представить в виде суммы трёх квадратов.

Производящей функцией последовательности a0, a1, a2,... называют формальный ряд f(x) = a0 + a1 x + a2 x2 +... Наибольший интерес производящие функции представляют в том случае, когда им соответствуют ряды, сходящиеся хотя бы на каком-то интервале.

36.20. Докажите, что производящая функция последовательности ak = Ck, k = 0, 1,..., n, равна (1 + x)n.

36.21. Пусть f(x) = последовательности чисел Каталана, т. е. c1 = 1, c2 = c1 c и ck = c1 ck1 + c2 ck2 +... + ck1 c1 при k 3.

а) Докажите, что (f(x))2 = f(x) x.

Согласно задаче 36.3 формальный ряд определён однозначно. Запишем этот формальный ряд в виде x.

Числа Bn называют числами Бернулли. Непосредственно из определения видно, что B0 = 1.

Многочлены Бернулли определяются равенством Bn (z) = Cn Bnk zk. Это равенство можно формально записать в виде Bn (z) = (B + z)n, где подразумевается, что вместо Bk мы пишем Bk.

Равенство из задачи 36.22 формально можно записать в виде (B + 1)k = Bk, где подразумевается, что вместо Bp мы пишем Bp.

36.23. Докажите, что Bn (0) = Bn (1) = Bn.

36.24. С помощью тождества из задачи 36.22 вычислите 36.25. Докажите, что B2k+1 = 0 для всех натуральных k.

36.26. а) Докажите, что Bn (z+1)Bn(z)=nzn1 при n 2.

б) Докажите, что при n 36.27. Докажите, что B (z) = nBn1 (z).

Пусть p(n) — количество способов, которыми можно представить число n в виде суммы натуральных слагаемых (слагаемые могут быть одинаковыми; два представления, которые отличаются лишь порядком слагаемых, считаются одинаковыми).

Число p(n) называют числом разбиений.

Например, p(1) = 1, p(2) = 2 (1 + 1; 2), p(3) = 3 (1 + 1 + 1;

498 Глава 36. Формальные ряды и производящие функции 36.28. Докажите, что 36.29. Докажите, что (тождество Эйлера).

36.30. Докажите, что (предполагается, что p(0) = 1 и p(m) = 0 при m < 0).

36.31. Пусть d(n) — количество разбиений числа n на различные слагаемые, l(n) — количество разбиений числа n на нечётные слагаемые. Докажите, что d(n) = l(n) (Эйлер).

Пусть 1,..., n — элементарные симметрические многочлены 36.26. а) По определению Выражение в правой части не содержит z для p > n 1. Кроме того, коэффициент при zn1 равен Cn Cn = n. Остаётся доказать, что для фиксированного p, 0 p n 2, Cn Ck Bnk = 0. Поk=p+ ложим m = n k. Тогда требуемое равенство перепишется в виде np Остаётся заметить, что np б) Складывая равенства получаем требуемое.

36.28. Ясно, что (1 x ) количеству представлений числа m в виде a1 + 2a2 +... + kak, где a1, a2,..., ak — неотрицательные целые числа. Такое представление можно записать следующим образом:

Поэтому количество представлений числа m в таком виде равно 36.29. Бесконечному произведению формальный ряд, в котором коэффициент при xm получается следующим образом. Рассмотрим все представления числа m в виде m = n1 + n2 +... + nk, где n1 < n2 <... < nk — различные натуральные числа, и каждому такому представлению сопоставим число (1)k.

Сумма всех этих чисел и есть коэффициент при xm.

Фиксируем число m и рассмотрим все его представления в виде m = n1 + n2 +... + nk, где n1 < n2 <... < nk. Пусть s — наибольшее число, для которого s чисел nks+1, nks+2,..., nk идут подряд, т. е. nk nks+1 = s 1.

Предположим, что n1 s, но исключим случай, когда n1 = s = k.

Сопоставим набору (n1, n2,..., nk ) набор если k = n1, то сопоставляемый набор имеет вид (n2 + 1,..., nk + 1).

Новый набор тоже соответствует некоторому представлению числа m. Неравенство n1 s гарантирует, что числа nkn1 +1 + 1,...

..., nk + 1 идут подряд. Ясно также, что (nkn1 +1 + 1) nkn1 > 1, поэтому в новом наборе подряд идут ровно n1 < n2 чисел.

Предположим, что n1 s, но исключим случай, когда n1 = s + и s = k. Сопоставим набору (n1, n2,..., nk ) набор если k=s, то сопоставляемый набор имеет вид (s, n1 1,..., nk 1).

Неравенство nks < nks+1 обеспечивается тем, что подряд идут 508 Глава 36. Формальные ряды и производящие функции только числа nks+1,..., nk. Мы получаем новый набор, который тоже соответствует представлению числа m. В новом наборе подряд идут по крайней мере s чисел.

Мы построили взаимно обратные соответствия между некоторыми представлениями числа m: каждому представлению, для которого n1 s, соответствует представление для которого n1 >s, но при этом некоторые представления исключены. Друг другу соответствуют представления, в которых число слагаемых отличаются на 1. Вклады таких представлений в коэффициент при xm взаимно сокращаются. Поэтому остаются только исключённые представления (k, k + 1,..., 2k 1) и (k + 1, k + 2,..., 2k). Им соответствуют члены (1)k xa и (1)k xb, где a = k + (k + 1) +... + (2k 1) = Далее, согласно задаче 36. Запишем тождество и раскроем скобки. Приравнивая в левой части коэффициент при xn, n 1, нулю, получаем требуемое.

36.31. Для d(n) производящая функция равна а для l(n) производящая функция равна Ясно, что В правой части все числители сокращаются со всеми знаменателями вида 1 x2k, поэтому остаются только знаменатели вида 1 x2k+1.

36.32. Рассмотрим формальные ряды (Их можно рассматривать как формальные ряды от переменных xi /x.) Складывая эти формальные ряды, получаем С другой стороны, Сравнивая коэффициенты при k, получаем требуемое.

36.33. Рассмотрим формальный ряд Взяв формальную экспоненту, получим С другой стороны, Сравнив коэффициенты при k, получаем требуемое.

ИСЧИСЛЕНИЕ КОНЕЧНЫХ РАЗНОСТЕЙ

37.1. Свойства конечных разностей Пусть x0, x1, x2,... — последовательность чисел. Ей можно сопоставить последовательность первых разностей x0, x1, x2,..., где xk = xk+1 xk. Повторив эту операцию, получим последовательность вторых разностей 2 xk = xk+1 xk и т. д.

Последовательности разностей обычно рассматривают для xk = f(x + hk), где f — некоторая функция, h — постоянное число, которое мы будем обозначать x. Число k x0 будем при этом обозначать k f(x).

37.3. Докажите, что если f(x) — многочлен степени n, то его n-е разности постоянны, а именно, они равны n! an hn, где an — старший коэффициент многочлена.

37.4. Докажите, что 37.5. Докажите, что n apx+q = apx+q (apx 1)n.

37.6. Докажите, что 37.9. Пусть функция (x) такова, что f(x) = (x) для некоторой функции f(x). Докажите, что 37.10. Докажите, что Легко видеть, что Это выражение, вообще говоря, не равно kxk1 h. В исчислении конечных разностей роль xk играет обобщённая степень x 37.11. Докажите, что x(k) = khx(k1).

При h = 1 мы обозначаем обобщённую степень x(k). Формула x(k) = kx(k1) является аналогом формулы дифференцирования xk. n1 n(k) 37.13. Пусть функция f(x) непрерывно дифференцируема на отрезке [1, n]. Докажите, что где B1 (z) = z 1/2 — многочлен Бернулли.

512 Глава 37. Исчисление конечных разностей 37.14. Пусть функция f(x) непрерывно дифференцируема m раз на отрезке [1, n]. Докажите, что k= где Rmn = 37.1. Применим индукцию по n. При n = 1 утверждение верно.

Предположим, что оно верно для некоторого n. Тогда 37.2. Применим индукцию по n. При n = 1 получаем x1 = = (x1 x0 ) + x0 = 1 x0 + 0 x0. Предположим, что требуемое равенство верно для некоторого n. Тогда 37.3. Равенство (x+(k+1)h)m (x+kh)m =C1 h(x+kh)m1 +C2 h2 (x+kh)m2 +...

показывает, что первые разности для последовательных значений xm являются последовательными значениями некоторого многочлена степени m 1 со старшим коэффициентом C1 h = mh.

Поэтому первые разности для последовательности xk = f(x + kh) имеют вид f1 (x + kh), где f1 — многочлен степени n 1 со старшим коэффициентом nhan. Значит, вторые разности имеют вид f2 (x + kh), где f2 — многочлен степени n 2 со старшим коэффициентом n(n 1)h2 an. Продолжая аналогично, получаем, что n-е разности — это константа n(n 1) ·... · 2 · 1 · hn an.

37.4. Пусть xk = km. Согласно задаче 37.3 m xk = m! и n xk = при n > m. С другой стороны, согласно задаче 37. При k = 0 получаем требуемое.

З а м е ч а н и е. По поводу других доказательств см. задачи 10.34 и 36.9.

37.5. Требуемое равенство достаточно доказать при n = 1. Ясно, что 37.6. Требуемые равенства достаточно доказать при n = 1. Для синуса получаем sin(ax + b) = sin(ax + b + ax) sin(ax + b) = Для косинуса вычисления аналогичны.

37.8. Если y = arctg(x + x) arctg x, то по формуле для тангенса разности двух углов 37.9. По условию (x) = f(x + h) f(x), (x + h) = f(x + 2h) f(x+ h),..., (x+ (n 1)h) = f(x+ nh) f(x+ (n 1)h). Складывая эти равенства, получаем требуемое.

37.10. Применим формулу из задачи 37.9 к тождествам из задач 37.6 и 37.8. В случае арктангенса мы полагаем x = 1.

37.11. Ясно, что 514 Глава 37. Исчисление конечных разностей h = 1. Применяя формулу из задачи 37.9, получаем требуемое.

37.13. Интегрируя по частям, получаем k+1“ Запишем такие равенства для k = 1, 2,..., n 1 и сложим их.

В результате получим требуемое.

37.14. Напомним, что B (x) = mBm1 (x) (задача 36.27). Поэтоm му при m 1 интегрирование по частям даёт Напомним также, что Bm+1 (1) = Bm+1 (0) = Bm+1 согласно задаче 36.23. Запишем тождество из задачи 37.13 и будем последовательно применять только что доказанное тождество. В результате получим требуемое.

КРИВЫЕ НА ПЛОСКОСТИ

Представление кривой в виде графика функции не всегда бывает удобно. Такое представление возможно лишь в достаточно специальных случаях. Например, так нельзя представить даже обычную окружность. Более широкий класс кривых можно получить с помощью параметризации кривой или задания кривой уравнением. Под параметризацией подразумевается представление кривой в виде (x(t), y(t)), где x(t) и y(t) — некоторые функции от t. Например, окружность можно представить в виде (cos t, sin t).

38.1. Предположим, что x (t) = 0 и y (t) = 0. Докажите, что касательная к кривой (x(t), y(t)) в точке (x(t0 ), y(t0 )) задаётся уравнением Чтобы записать уравнение касательной к кривой, заданной уравнением f(x, y) = 0, нужно понятие частной производной:

Другими словами, частная производная по x — это обычная производная функции f(x, y0 ), где y0 фиксировано, а частная производная по y — это обычная производная функции f(x0, y), где x0 фиксировано.

Докажите, что касательная в точке (x0, y0 ) к кривой, заГлава 38. Кривые на плоскости данной уравнением f(x, y) = 0, задаётся уравнением Положение точки X в полярных координатах задаётся расстоянием r до начала координат O и углом между лучом OX и осью Ox. Полярные координаты (r, ) связаны с прямоугольными координатами (x, y) следующим образом:

Лемниската — это множество всех точек, для которых произведение расстояний от точек (a, 0) и (a, 0) равно a2.

38.3. Найдите уравнение лемнискаты: а) в прямоугольных координатах; б) в полярных координатах.

Мы говорим, что две кривые на плоскости касаются в некоторой точке, если их касательные в этой точке совпадают.

Пусть на плоскости с координатами x, y задано семейство кривых C, зависящих от параметра. Огибающей семейства кривых C называют кривую C, которая в каждой своей точке касается одной из кривых C, причём она касается каждой из кривых C. Огибающая семейства кривых может состоять из нескольких связных компонент. Например, огибающая семейства окружностей фиксированного радиуса r с центрами на данной прямой l состоит из двух прямых, параллельных прямой l и удалённых от неё на расстояние r.

Мы будем предполагать, что кривые C заданы уравнениями вида f(x, y, ) = 0, где f — дифференцируемая функция.

Найдём уравнение огибающей C, предполагая, что она задаётся параметрически: x = ( ), y = ), причём кривая C в точке (x0, y0 ) задаются уравнениями Эти прямые совпадают, значит, Точка ( ( ), )) лежит на кривой C, поэтому для всех. Дифференцируя это равенство, получаем Теперь, учитывая (38.2), получаем =0. Таким образом, огибад ющая (если она существует и задаётся параметрически указанным способом) находится исключением параметра из системы уравнений Чтобы уравнения (38.1) действительно задавали касательдf дf не обращались в нуль одновременно. Если это условие выполнено, то рассуждения можно обратить; в таком случае кривая, найденная как решение системы (38.4), действительно будет огибающей.

Довольно часто огибающую можно найти при помощи следующих геометрических соображений. Предположим, что каждая пара кривых C 1 и C 2 ( 1 = 2 ) пересекается в одной точке, причём эти точки пересечения стремятся к некоторой точке (x( ), y( )) при 1 и 2. Тогда эта точка (x( ), y( )) лежит на огибающей. Действительно, если f(x, y, 1 ) = и f(x, y, 2 ) = 0, то (x( ), y( )) имеют место равенства а значит, эта точка лежит на огибающей.

38.4. Найдите огибающую семейства прямых, отсекающих от данного прямого угла треугольник площади a2 /2.

38.5. На сторонах угла с вершиной O фиксированы точки A и B. На отрезках OA и OB выбираются точки A1 и B так, что OB1 : B1 B = AA1 : A1 O. Докажите, что огибающая семейства прямых A1 B1 — дуга параболы.

38.6. Найдите в фиксированной вертикальной плоскости огибающую траекторий материальной точки, выбрасываемой из начала координат со скоростью v0.

Кривую из задачи 38.6 называют параболой безопасности.

38.7. Докажите, что огибающая семейства прямых, высекающих на координатных осях отрезок постоянной длины l (рис. 38.1), задаётся уравнением Траекторию отмеченной точки окружности радиуса r, которая катится по неподвижной окружности радиуса R, причём окружность радиуса r расположена внутри окружности радиуса R, называют гипоциклоидой.

Траекторию отмеченной точки окружности радиуса r, которая катится по неподвижной окружности радиуса R, причём окружность радиуса r расположена вне окружности радиуса R, называют эпициклоидой.

Если число r/R рационально, то соответствующие гипои эпициклоиды являются замкнутыми кривыми с конечным числом особых точек (точек возврата). Некоторые из них имеют специальные названия. Например, эпициклоиду с одной точкой возврата называют кардиоидой (по форме она напоминает сердце), а эпициклоиду с двумя точками возврата называют нефроидой (по форме она напоминает почку). Гипоциклоида с четырьмя точками возврата — это астроида.

38.9. а) Фиксируем число k = 0, ±1 и рассмотрим семейство прямых, каждая из которых соединяет точки ei и eik.

Докажите, что огибающая этого семейства прямых — гипоили эпициклоида.

б) Для каждого целого числа k = 0, ±1 найдите число точек возврата.

38.10. Докажите, что огибающая семейства прямых, являющихся отражениями от кругового зеркала пучка параллельных лучей, — нефроида (точнее говоря, половина нефроиды, см. рис. 38.2).

38.11. Рассмотрим окружность S и выберем на ней точку A. Из точки A выпускаются лучи света и отражаются от окружности. Докажите, что огибающая отражённых лучей — кардиоида (рис. 38.3).

Пусть (t) = (x(t), y(t)) — параметризованная кривая. Мы будем предполагать, что v(t) = (t) = 0 при всех t.

Параметр t удобно заменить на так называемый натуральt ный параметр s = s(t) = |v()| d. Для натурального параметра Конец вектора v(s)= движется по единичной окружносds ти, поэтому v. Пусть n — единичный вектор на плоскости, ортогональный вектору v. Тогда = k(s)n. Число |k(s)| называds ют кривизной кривой в данной точке.

38.12. Докажите, что кривизна окружности радиуса R равна 1/R.

38.13. Докажите, что для кривой (t) = (x(t), y(t)) с произвольной параметризацией t кривизна вычисляется по формуле 38.14. Вычислите кривизну эллипса 2 + 2 = 1 в каждой точке.

38.4. Соприкасающаяся окружность Рассмотрим на плоскости две кривые, заданные уравнениями y = f(x) и y = g(x). Эти кривые пересекаются, если f(x0 ) = g(x0 ).

В точке пересечения кривые касаются (имеют соприкосновение порядка 1), если f (x0 ) = g (x0 ). Касающиеся кривые имеют соприкосновение порядка n, если f(x0 ) = g(x0 ), f (x0 ) = g (x0 ),...

..., f(n) (x0 ) = g(n) (x0 ). Кривые, имеющие соприкосновение порядка 2, называют соприкасающимися.

Если кривизна кривой в некоторой точке отлична от нуля, то однозначно определена окружность, соприкасающаяся с кривой в этой точке (соприкасающаяся окружность). Уравнение соприкасающейся окружности в случае, когда кривая задана уравнением y = f(x), находится следующим образом. Пусть y = g(x) — функция, локально задающая окружность радиуса R с центром (a, b), т. е. g удовлетворяет соотношению Дифференцируя это соотношение, последовательно получаем Если кривая y = f(x) соприкасается с указанной окружностью в точке (x0, y0 ), то где y = f (x0 ) и y = f (x0 ). Более того, если эта система уравнений для a, b, R имеет решение, то верно и обратное: кривая соприкасается с окружностью. Легко видеть, что если y = 0, то эта система уравнений имеет единственное решение. Например, если y = 0 (а этого всегда можно добиться подходящим выбором системы координат), то a = x0, b = y0 + Центр соприкасающейся окружности называют центром кривизны кривой. Согласно задаче 38.13 в рассматриваемой сиy ) лежит на нормали к кривой в данной точке и удалён от этой точки на расстояние ±1/k.

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

Пусть (s) = (x(s), y(s)) — кривая с натуральной параметризацией. Фиксируем на плоскости точку q = (x0, y0 ) и рассмотрим функцию F(s) = | (s) q|2. Точку s0 называют критической точкой функции F, если F (s0 ) = 0. Критическую точку называют вырожденной, если F (s0 ) = 0. Ясно, что (число k и вектор n определяются на с. 520.) Поэтому точка s является критической точкой функции F тогда и только тогда, когда вектор (s0 )q ортогонален кривой в точке (s0 ), а критическая точка s0 является вырожденной тогда и только тогда, когда k(s0 ) = 0 и (s0 )q = точкой кривой имеет вырожденную критическую точку. В таком случае, если s0 — вырожденная критическая точка, то точка q однозначно определяется равенством (s0 )q = n. С геометрической точk(s0 ) ки зрения это означает, что точка q является центром окружности, соприкасающейся с кривой в точке (s0 ). Таким образом, q — предельное положение точки пересечения нормалей к кривой в точках (s1 ) и (s2 ), когда s1 s0 и s2 s0. Отметим, в частности, что фокальная точка не зависит от выбора параметризации.

Эволютой кривой называют множество всех её фокальных точек. Учитывая, что фокальные точки являются предельными положениями точек пересечения близких нормалей к кривой, приходим к другому определению: эволюта — огибающая семейства всех нормалей к кривой.

38.16. Для эллипса 2 + 2 = 1 найдите фокальную точку, соответствующую точке (a cos t0, b sin t0 ); найдите радиус кривизны эллипса в этой точке.

38.17. Найдите уравнение эволюты эллипса.

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

38.18. Докажите, что эволютой циклоиды является такая же циклоида (полученная из исходной кривой параллельным переносом).

38.1. Искомая касательная задаётся уравнением y y(t0 ) = = k(x x(t0 )), где 38.2. Мы будем предполагать, что в достаточно малой окрестности точки (x0, y0 ) рассматриваемая кривая является графиком функции y = (x), хотя в действительности при сделанных предположениях о том, что частные производные не обращаются в нуль, это можно было бы доказать.

По теореме о конечных приращениях где число заключено между x0 и x1, а число заключено между y0 и y1. Поэтому если точка (x1, y1 ) тоже лежит на рассматриваемой кривой, то Искомая касательная задаётся уравнением y y0 = k(x x0 ), где 38.3. а) О т в е т: (x2 + y2 )2 = 2a2 (x2 y2 ). Непосредственно из определения видно, что лемниската задаётся уравнением т. е. x4 + a4 + y4 2a2 x2 + 2a2 y2 + 2x2 y2 = a4. После несложных преобразований получаем уравнение, указанное в ответе.

б) О т в е т: r2 = 2a2 cos2 2. Выразив прямоугольные координаты через полярные, получим для лемнискаты уравнение Остаётся заметить, что cos sin = cos 2.

38.4. Введём систему координат, направив оси по сторонам данного прямого угла. Интересующие нас прямые пересекают оси координат в точках ( a, 0) и (0, a/ ), где > 0. Прямая, соответствующая параметру, задаётся уравнением x + 2 y = a.

Две прямые, соответствующие параметрам 1 и 2, пересекаются то мы получаем точку,. Такие точки лежат на гиперболе xy = a2 /4.

38.5. Можно считать, что O — начало координат, A = (1, 1) и B = (1, 1). Тогда A1 = (1, 1 ) и B1 = (, ) для некоторого [0, 1]. Прямая, проходящая через точки A1 и B1, задаётся уравнением (2 1)x + y = 2 (1 ). Легко проверить, что если (x0, y0 ) — точка пересечения прямых, соответствующих параметрам 1 и 2, то x0 = 1 1 2. Если 1 и 2, то x0 1 2.

38.6. Направим ось Oy вертикально вверх, а ось Ox направим по горизонтальной составляющей скорости v0. Тогда в момент времени t материальная точка имеет координаты x(t) = v0 cos · t, y(t) = v0 sin · t, где — угол, под которым она была выброшена. Например, если точка выбрасывается вертикально вверх, этом y(t) =. Если предположить, что огибающая является параболой, то она должна задаваться уравнением y = Чтобы найти k, вычислим наибольшую возможную координату пересечения траектории с осью Ox (наибольшую дальность выстрела равна. Соответственно, для k получаем уравнение y = 0 k 0 = 0, откуда находим k = 2.

является огибающей рассматриваемого семейства траекторий. Для этого достаточно доказать, что любая траектория лежит ниже этой параболы и имеет с ней одну общую точку, т. е. для всех t имеет место неравенство причём для некоторого t оно обращается в равенство. Заменив cos2 на 1 sin2, переходим к неравенству 38.7. Пусть отрезок с концами (a1, 0) и (0, b1 ) имеет длину l и отрезок с концами (a2, 0) и (0, b2 ) тоже имеет длину l. Если для некоторых и. Из соотношения (a + )2 + (b )2 = (a )2 + + (b + )2 получаем a = b.

Найдём координаты точки пересечения рассматриваемых отрезков (предполагается, что a1 и a2 одного знака и b1 и b2 тоже одного знака). Прямые, на которых лежат эти отрезки, задаются уравнениями Рассматривая сумму и разность этих уравнений, получаем Если учесть соотношение a = b, то последнее равенство можно ние в первое равенство, находим Нас интересует предел при 0, 0. Ясно, что предельные выражения такие: x = a3 /l2 и y = b3 /l2. Тогда 38.8. П е р в о е р е ш е н и е. Выведем параметрическое представление траектории отмеченной точки в общем случае, когда окружность радиуса r катится внутри окружности радиуса R. Это движение отмеченной точки можно представить как вращение центра меньшей окружности по окружности радиуса r1 = R r с угловой скоростью 1 и вращение меньшей окружности радиуса r2 = r с угловой скоростью 2. При этом 1 и 2 имеют разные знаки и связаны соотношением (r1 + r2 )1 = r2 (2 + 1 ), которое выражает равенство дуг неподвижной окружности радиуса R = r1 + r2 и подвижной окружности радиуса r = r2 (качение без скольжения). После сокращения это соотношение записывается в виде r1 1 = r2 2.

Траектория отмеченной точки параметрически задаётся так:

В случае, когда R = 4r, получаем r1 = 3r, r2 = r и = 31. Положив 1 = 1, получим а значит, x2/3 + y2/3 = (4r)2/3 = R2/3.

З а м е ч а н и е. Точно такое же параметрическое представление траектории получается и в случае, когда окружность радиуса r катится по внешней части круга радиуса R. Тогда движение отмеченной точки можно представить как вращение центра окружности радиуса r2 = r по окружности радиуса r1 = R + r с угловой скоростью 1 и вращение окружности радиуса r2 = r с угловой скоростью 2. При этом 1 и 2 имеют одинаковые знаки и связаны соотношением (r1 r2 )1 = r2 (2 1 ). После сокращения это соотношение записывается в виде r1 1 = r2 2.

В т о р о е р е ш е н и е. Рассмотрим окружность радиуса l = 4r с центром в начале координат O. Пусть окружность радиуса r катится внутри её, причём в начальный момент отмеченная точка совпадает с точкой P = (l, 0). Пусть через некоторое время отмеченная точка переместилась в точку X, а окружности теперь касаются в точке A. Тогда дуги AP и AX равны, поэтому центральный угол, опирающийся на дугу AX, равен 4AOP, а вписанный угол равен 2AOP. Пусть B — середина отрезка OA, а M и N — точки пересечения прямой BX с координатными осями. Треугольники OBM и OBN равнобедренные, поскольку в них внешний угол при вершине B вдвое больше внутреннего угла при вершине O. Поэтому MN = 2OB = OA = l.

Прямая MN касается траектории отмеченной точки в точке X.

Действительно, прямая MN перпендикулярна прямой AX, а вектор скорости движения точки X перпендикулярен AX, поскольку точка A является мгновенным центром вращения точки X. Таким образом, траектория точки X является огибающей семейства прямых, высекающих на координатных осях отрезок постоянной длины l.

Пусть, далее, C — предельное положение точки пересечения прямых AB и A B при 0. Ясно, что если k > 0, то точка C лежит на отрезке AB, а если k < 0, то точка C лежит вне этого отрезка. Покажем, что AC : CB = 1 : |k|. Действительно, AC : CB = sin B : sin A = динаты Как видно из первого решения задачи 38.8, точки с такими координатами образуют гипо- или эпициклоиду.

б) О т в е т: |k 1|. Точки возврата соответствуют положениям, когда точки ei и eik диаметрально противоположны, т. е. ei + eik = 0. После сокращения на ei получаем уравнение ei(k1) = 1. Оно имеет |k 1| решений.

38.10. Будем считать, что лучи параллельны оси Ox и отражаются от единичной окружности. Пусть луч попадает в точку A = ei. После отражения этот луч попадает в точку A1, которая получается следующим образом. Пусть A — исходная точка луча света, т. е. точка, симметричная точке A относительно оси Oy.

Тогда точка A1 симметрична точке A относительно диаметра AB.

В результате мы оказываемся в ситуации задачи 38.9 для k = 3, что соответствует эпициклоиде с двумя точками возврата.

38.11. Будем считать, что окружность единичная, а A = (1, 0).

Тогда луч, попадающий в точку ei, после отражения попадает в точку ei(2+). Положим = +. Тогда 2 + = 2 + 2 + = = 2 + для =. В результате мы оказываемся в ситуации задачи 38.9 для k = 2, что соответствует эпициклоиде с одной точкой возврата.

38.12. Окружность радиуса R параметрически можно задать Пусть = 1/R. Тогда |v(t)| = 1, т. е. t — натуральный параметр.

Дифференцируя это равенство по t, получаем Возведём это равенство в квадрат. Учитывая, что 2 = k Последнее выражение легко преобразуется к требуемому виду.

38.14. Рассмотрим следующую параметризацию эллипса: x(t) = = a cos t, y(t) = b sin t. Тогда Поэтому согласно задаче 38. З а м е ч а н и е. Другим способом кривизна эллипса вычисляется в задаче 38.16.

38.15. Можно считать, что кривая задаётся уравнением y=f(x), причём f (0) = 0. При этом нас интересует центр кривизны для точки (0, f(0)). Нормаль к кривой в точке (, f( )) задатся уравнением (x ) + f ( )(y f( )) = 0; нормаль в точке (0, f(0)) — это координатная” ось Ox. Пересечение этих нормалей — точка 0, f( ) +. При 0 получаем точку 0, f(0) +. Это как раз и есть центр кривизны.

38.16. Для фиксированной точки (x0, y0 ) рассмотрим на эллипсе функцию F(t) = (x0 a cos t)2 + (y0 b sin t)2. Нас интересует точка (x0, y0 ), для которой F (t0 ) = 0 и F (t0 ) = 0, т. е.

Решая эту систему уравнений, находим Теперь радиус кривизны R вычисляется по формуле 38.17. Выражения для фокальных точек, полученные в решении задачи 38.16, показывают, что они лежат на кривой 38.18. Пусть фиксированная прямая — это ось Ox, а в начальный момент фиксированная точка совпадает с началом координат O. Будем также предполагать, что окружность имеет радиус и катится она в верхней полуплоскости. Пусть через некоторое время фиксированная точка сместилась в точку X; при этом катящаяся окружность S1 касается оси Ox в точке P (рис. 38.4).

Тогда длина отрезка OP равна длине дуги PX. Пусть PQ — диаметр окружности S1 и O1 — точка (, 0), т. е. середина отрезка с концами в первом и втором положении фиксированной точки на оси Ox. Тогда длина отрезка O1 P равна длине дуги QX. Поэтому если мы рассмотрим окружность S, симметричную S1 относительно точки P, и рассмотрим на ней точки X и Q, симметричные X и Q, то длина дуги Q X равна длине отрезка Q1 P. Рассмотрим прямую l, которая проходит через точку Q параллельно исходной фиксированной прямой. Пусть O — проекция точки O1 на эту прямую. Тогда длина отрезка O1 P равна длине отрезка Q O.

Поэтому длина дуги Q X равна длине отрезка Q O, т. е. точка X расположена на циклоиде, которая получается, когда окружность радиуса 1 катится по прямой l навстречу исходной окружности, причём в начальный момент фиксированная точка расположена в точке O.

Покажем, что прямая XX одновременно является нормалью к первой циклоиде и касательной ко второй циклоиде. Точка P является мгновенным центром вращения точки X, поэтому прямая PX является нормалью к первой циклоиде. Точка Q является мгновенным центром вращения точки X, поэтому прямая Q X является нормалью ко второй циклоиде, а прямая PX является касательной.

ТЕОРИЯ МНОЖЕСТВ

39.1. Дано непустое конечное множество. Докажите, что количество его подмножеств, содержащих чётное число элементов, равно количеству подмножеств, содержащих нечётное число элементов.

39.2. Операции над множествами В теории множеств приняты следующие обозначения:

x X: x — элемент множества X (x принадлежит множеству X);

x X: x не принадлежит X;

A X: A — подмножество X, т. е. каждый элемент множества A принадлежит X;

A B — объединение множеств A и B; оно состоит из тех элементов, которые являются элементами множества A или множества B;

A B — пересечение множеств A и B; оно состоит их тех элементов, которые одновременно являются элементами множества A и элементами множества B.

В том случае, когда фиксировано некоторое множество U, используют обозначение A — дополнение множества A; оно состоит из тех элементов множества U, которые не являются элементами множества A.

39.2. а) Докажите, что A (B C) = (A B) (A C).

де Моргана).

Тождества, подобные тем, которые доказываются в задачах 39. и 39.3, удобно доказывать с помощью так называемых диаграмм Венна, на которых рассматриваемые множества изображаются в виде пересекающихся кругов. В случае n множеств берутся n выпуклых фигур (кругами не всегда можно обойтись), границы которых разбивают плоскость на 2n частей. Если все рассматриваемые множества лежат в фиксированном множестве U, то это множество U можно изобразить в виде круга, содержащего все остальные фигуры.

39.4. Решите задачи 39.2 и 39.3, нарисовав соответствующие диаграммы Венна.

Два множества X и Y называют равномощными, если существует отображение f : X Y, которое является взаимно однозначным, т. е. для любого элемента y Y существует ровно один элемент x X, для которого f(x) = y. Другими словами, между элементами множеств X и Y установлено соответствие, при котором каждому элементу одного множества соответствует ровно один элемент другого множества.

Мы будем использовать следующие обозначения и терминологию:

• отрезок [a, b] состоит из точек x, удовлетворяющих неравенствам a x b;

• интервал (a, b) состоит из точек x, удовлетворяющих неравенствам a < x < b;

• полуинтервал [a, b) состоит из точек x, удовлетворяющих неравенствам a x < b; полуинтервал (a, b] состоит из точек, удовлетворяющих неравенствам a < x b.

39.5. Докажите, что отрезки [0, 1] и [0, a] равномощны для любого положительного числа a.

39.6. Докажите, что интервал (0, 1) и луч (1, +) равномощны.

39.7. Докажите, что интервал (1, 1) равномощен множеству всех действительных чисел.

39.8. Докажите, что множество всех бесконечных последовательностей a1, a2,..., где ai = 0 или 1 для всех i, равномощно множеству всех подмножеств натуральных чисел.

39.9. Докажите, что отрезок [0, 1] равномощен полуинтервалу [0, 1).

Множество называют счётным, если оно равномощно множеству натуральных чисел.

39.10. Докажите, что множество целых чисел счётно.

39.11. Докажите, что множество рациональных чисел счётно.

39.12. Докажите, что любое подмножество счётного множества либо конечно, либо счётно.

39.13. Докажите, что объединение счётного множества счётных множеств счётно.

39.14. Докажите, что для каждого натурального n множество всех последовательностей из n натуральных чисел счётно.

39.15. Докажите, что множество всех конечных последовательностей натуральных чисел счётно.

39.16. Докажите, что множество всех алгебраических чисел счётно.

39.17. Докажите, что множество попарно не пересекающихся отрезков на прямой конечно или счётно.

39.18. Докажите, что множество попарно не пересекающихся кругов на плоскости конечно или счётно.

39.19. Докажите, что если множество X бесконечно, а множество Y конечно или счётно, то множество X Y равномощно X.

Говорят, что множество имеет мощность континуума, если оно равномощно множеству действительных чисел.

39.20. а) Докажите, что множество точек интервала (0, 1) имеет мощность континуума.

б) Докажите, что множество точек отрезка [0, 1] имеет мощность континуума.

39.21. а) Докажите, что множество всех бесконечных последовательностей a1, a2,..., где ai = 0 или 1, имеет мощность континуума.

б) Докажите, что множество всех подмножеств множества натуральных чисел имеет мощность континуума.

39.22. Докажите, что множество всех точек квадрата имеет мощность континуума.

39.23. Докажите, что никакое множество X не равномощно множеству P(X) всех своих подмножеств (Кантор).

39.24. Докажите, что если множество имеет мощность континуума, то оно не счётно.

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

является элементом самого себя*, либо является. Пусть Y — множество, элементами которого являются все те множества X, которые не являются элементами самого себя.

Попробуем выяснить, что верно: Y Y или Y Y? Если Y Y, то по определению множество Y не является элементом Y, а если Y Y, то по определению множество Y является элементом Y.

множеств, P(M) — множество всех его подмножеств. Из определения M видно, что P(M) содержится в M. С другой стороны, по теореме Кантора (задача 39.23) множество * Именно такими являются множества, с которыми обычно имеют дело в математике: множество натуральных чисел, множество действительных чисел и т. п.

P(M) имеет строго большую мощность, чем M, поэтому оно не может содержаться в M.

Чтобы избежать парадоксов такого рода, в аксиоматической теории множеств вводится так называемая аксиома фундирования: не существует бесконечной последовательности множеств X1 X2, X2 X3, X3 X4,... В частности, никакое множество не может быть элементом самого себя. Тогда парадокс Рассела разрешается так, что описанный указанным образом объект Y не существует (не является множеством).

39.1. Фиксируем в данном множестве один элемент x. Подмножества данного множества можно разбить на пары следующим образом: берём произвольное подмножество, не содержащее x, и в качестве второго множества пары берём то же самое подмножество и добавляем к нему элемент x. В каждой паре одно множество состоит из чётного числа элементов, а другое — из нечётного.

39.4. Требуемые диаграммы изображены на рис. 39.1.

39.5. Взаимно однозначное отображение [0, 1] [0, a] задаётся формулой x ax.

39.6. Взаимно однозначное отображение (0, 1) (1, +) задатся формулой x 1/x. “ x ” 39.7. Функция f(x) = tg задаёт взаимно однозначное отображение интервала (1, 1) на множество всех действительных чисел.

39.8. Сопоставим последовательности a1, a2,... множество, состоящее из тех натуральных чисел n, для которых an = 1. В результате получим взаимно однозначное соответствие между последовательностями указанного вида и множествами натуральных чисел.

39.9. Выберем бесконечную последовательность попарно различных чисел a1, a2,..., заключённых строго между 0 и 1. Построим отображение f : [0, 1] [0, 1) следующим образом: f(1) = a1, f(ai ) = ai+1 и f(x) = x, если x отлично от 1 и от ai для всех i. Ясно, что отображение f взаимно однозначно. Действительно, обратное отображение f1 : [0, 1) [0, 1] устроено следующим образом:

f1 (a1 ) = 1, f1 (ai ) = ai1 при i 2 и f(x) = x, если x отлично от ai для всех i.

39.10. В последовательности 0, 1, 1, 2, 2, 3, 3,... каждое целое число встречается ровно один раз.

последовательности для k = 1, 2, 3,... После этого будем идти по полученной последовательности и вычёркивать все те числа, которые уже встретились нам ранее. В результате получим последовательность, в которой каждое рациональное число встречается ровно один раз.

З а м е ч а н и е. По поводу другого доказательства см. задачу 4.13.

39.12. Занумеруем элементы данного счётного множества, и пусть элементы данного подмножества имеют номера i1 < i2 < < i3 <... Множество этих номеров либо конечно (тогда данное подмножество конечно), либо бесконечно (тогда данное подмножество счётно).

39.13. Пусть k-е счётное множество состоит из элементов ak1, ak2, ak3,... Тогда последовательность элементов a11 ; a12, a21 ; a13 , a22, a31 ; a14, a23, a32, a41 ;... содержит все элементы данных множеств. Нужно только вычеркнуть из неё повторяющиеся элементы.

39.14. Множество упорядоченных пар натуральных чисел можно представить как объединение счётного множества счётных множеств (первое число пары можно рассматривать как номер множества). Значит, это множество счётно (задача 39.13). Занумеруем пары натуральных чисел. Тройку натуральных чисел можно рассматривать как пару натуральных чисел и ещё одно натуральное число. Поэтому множество троек натуральных чисел является объединением счётного множества счётных множеств и т. д.

39.15. Непосредственно следует из задач 39.13 и 39.14.

39.16. Множество всех многочленов с целыми коэффициентами, имеющих данную степень n, счётно. Каждый из них имеет не более n различных корней, поэтому множество корней многочленов степени n с целыми коэффициентами счётно (многочлены вида pxn qxn1 показывают, что оно бесконечно). Поэтому множество алгебраических чисел является объединением счётного множества счётных множеств.

39.17. Каждый из отрезков содержит рациональную точку, причём для непересекающихся отрезков эти точки разные.

39.18. Каждый из кругов содержит точку, обе координаты которой рациональны, причём для непересекающихся кругов эти точки разные.

39.19. Можно считать, что X и Y не пересекаются. Действительно, вместо Y можно взять множество Y, состоящее из тех элементов Y, которые не принадлежат X. Множество Y является подмножеством Y, поэтому оно конечно или счётно.

Пусть X1 — счётное подмножество в X, а X2 — дополнение к X в X. Множество X1 Y равномощно X1, поскольку объединение счётного множества с конечным или счётным счётно. Установим взаимно однозначное соответствие множеств X1 Y и X1. Вместе с естественным взаимно однозначным соответствием множеств X2 и X2 (каждый элемент соответствует самому себе) оно даёт требуемое взаимно однозначное соответствие множеств X Y и X.

39.20. а) Это легко выводится из задач 39.5 и 39.7.

б) Можно воспользоваться такими же рассуждениями, как и при решении задачи 39.9.

39.21. а) Достаточно доказать, что множество точек отрезка [0, 1] равномощно множеству всех бесконечных последовательностей a1, a2,..., где ai = 0 или 1. Сопоставим такой последовательa1 a2 a ности число + 2 + 3 +... Это представление числа из [0, 1] неоднозначно. Например, двоичные дроби 0,01111... и 0,1000...

представляют одно и то же число. Но если мы отбросим все двоГлава 39. Теория множеств ичные дроби с единицей в периоде, кроме дроби 0,1111..., то оставшиеся дроби будут находиться во взаимно однозначном соответствии с точками отрезка [0, 1]. Выброшенные дроби образуют счётное множество, поскольку каждая из них задаётся конечной последовательностью из нулей и единиц.

Пусть X — множество оставшихся дробей, Y — множество выброшенных дробей. Тогда X имеет мощность континуума, поэтому согласно задаче 39.19 рассматриваемое множество X Y тоже имеет мощность континуума.

б) Следует из задачи а) и задачи 39.8.

39.22. Точку квадрата можно представить как пару точек отрезка. Согласно задаче 39.21 множество точек отрезка равномощно множеству бесконечных последовательностей a1, a2,..., где ai = 0 или 1. Поэтому достаточно доказать, что множество упорядоченных пар таких последовательностей равномощно множеству таких последовательностей. Сопоставим паре последовательностей a1, a2, a3,... и b1, b2, b3,... последовательность a1, b1, a2, b2, a3, b3,... В результате получим требуемое взаимно однозначное соответствие.

39.23. Предположим, что удалось установить взаимно однозначное соответствие : X P(X). Пусть Y — множество тех элементов x X, для которых x (x). Докажем, что этому подмножеству не соответствует никакой элемент множества X. Действительно, предположим, что Y = (y). Тогда Первая эквивалентность вытекает из определения множества Y, а вторая — из того, что (y) = Y.

З а м е ч а н и е. Обратите внимание, что если X =, то множество P(X) = {} состоит из одного элемента.

39.24. Согласно задаче 39.21 б) множество P(X) всех подмножеств счётного множества X имеет мощность континуума. Согласно теореме Кантора P(X) не равномощно X, т. е. множество, имеющее мощность континуума не равномощно счётному множеству.

ДОПОЛНЕНИЕ

1. Рациональная параметризация окружности Чтобы найти все точки окружности x2 + y2 = 1, обе координаты которых рациональны, можно воспользоваться следующей конструкцией. Возьмём на окружности произвольную точку A с рациональными координатами и проведём через неё всевозможные прямые. Например, в качестве точки A можно взять точку (1, 0) или точку (3/5, 4/5).

Мы проведём вычисления для точки (1, 0), хотя для любой другой точки с рациональными координатами вычисления будут аналогичны.

Прямая, проходящая через точку (1, 0), задаётся либо уравнением y = t(x 1), либо уравнением x = 1 (уравнение x = 1 можно получить из уравнения y = t(x 1), положив t = ; поэтому удобно считать, что t принимает также значение ). Чтобы найти точки пересечения прямой y = t(x 1) и окружности x2 + y2 = 1, нужно решить квадратное уравнение x2 + t2 (x 1)2 = 1, т. е.

Одна точка пересечения прямой и окружности, соответствующая x = 1, известна. Поэтому координату x второй точки пересечения можно найти с помощью теоремы Виета. В результате получим Таким образом, точка пересечения окружности x2 + y2 = и прямой y = t(x 1) имеет координаты Это означает, что точка окружности имеет рациональные координаты тогда и только тогда, когда она соответствует рациональному значению параметра t. В самом деле, если нальны. А если числа x и y рациональны, то число t = тоже рационально. Значение t =, соответствующее точке (1, 0), удобно при этом тоже считать рациональным.

С помощью рациональной параметризации окружности можно получить описание пифагоровых троек, т. е. таких троек натуральных чисел (a, b, c), что a2 +b2 =c2. А именно, (a, b, c) — пифагорова тройка тогда и только тогда, когда существуют такие натуральные числа m и n, что a = m2 n2, Доказательство этого утверждения начнём с того, что избавимся от общих делителей. Если два из трёх чисел a, b, c делятся на d, то третье число тоже делится на d. Поэтому можно считать, что a/c и b/c — несократимые дроби. Точка (a/c, b/c) лежит на окружности x2 + y2 = 1 и обе координаты этой точки рациональны. Следовательно, где t — рациональное число. Пусть t = m/n — несократимая дробь. Тогда Дробь m/n несократимая, поэтому числа m и n не могут быть оба чётными. Если одно из этих чисел чётно, а другое 1. Рациональная параметризация окружности оба числа m и n нечётны, т. е. m = 2p + 1 и n = 2q + 1, то, как легко проверить, где m1 =p+q+1 и n1 =pq. Мы получаем несократимые дроби, так как одно из чисел m1 и n1 чётно, а другое нечётно.

Как мы уже говорили, взяв любую другую рациональную точку окружности, можно повторить аналогичные вычисления и получить аналогичную параметризацию окружности параметром t, причём рациональным значениям параметра будут соответствовать рациональные точки окружности. Более того, аналогичным образом можно параметризовать произвольную кривую второго порядка Для этого нужно взять произвольную точку кривой и провести через неё всевозможные прямые.

Предположим, что выполняются следующие условия:

• коэффициенты a, b,..., f рациональны;

• выбранная точка кривой имеет рациональные координаты;

• кривая (1) содержит бесконечно много точек.

Тогда в результате получим такую параметризацию кривой (1), что рациональным значениям параметра t соответствуют точки кривой, обе координаты которых рациональны. Напомним, что мы пользовались тем, что кривая (1) содержит хотя бы одну точку с рациональными координатами. Но такая точка есть не всегда. Самый простой пример — кривая x2 + y2 = 1.

Более интересен пример кривой 2x2 + 5y2 = 1. Проверим, что на ней нет рациональных точек. Предположим, что (x, y) — рациональная точка этой кривой. Можно считать, что x = p1 /q и y = p2 /q, причём у чисел p1, p2, q нет общего делителя (т. е. нет числа d, на которое делятся все эти три числа).

Числа p1, p2, q удовлетворяют соотношению 2p2 + 5p2 = = q2. Поэтому числа 2p2 и q2 при делении на 5 дают одинаковые остатки. Но число a2 при делении на 5 может давать лишь остатки ±1 и 0. Поэтому число 2p2 при делении на даёт остаток ±2 или 0, а число q2 даёт остаток ±1 или 0.

Следовательно, оба числа 2p2 и q2 делятся на 5, а значит, они делятся на 25. Но тогда число 5p2 делится на 25, а значит, число p2 делится на 5. В результате получаем, что числа p1, p2, q делятся на 5, а это противоречит предположению.

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

В этом случае P(x) = x(x + a)(x b), где a и b — рациональные числа, и P (x) = 3x2 + 2(a b)x ab. Требуется, чтобы дискриминант D = 4((a b)2 + 3ab) = 4(a2 + b2 + ab) был квадратом рационального числа. Эквивалентное условие таково:

a2 + b2 + ab = c2, где c — рациональное число.

Положим x = a/c и y = b/c. Нас интересуют точки с рациональными координатами на кривой x2 + y2 + xy = 1. Одна такая точка очевидна: x = 1 и y = 0. Проведём через неё всевозможные прямые y = t(x 1). Подставим это выражение для y в уравнение кривой:

У этого квадратного уравнения есть корень x = 1. Нас интеt следующим образом. Пусть c и t — произвольные рациоt2 1 t2 + 2t метим, что если мы возьмём a = t2 1 и b = (t2 + 2t), где t — целое число, то получим кубический многочлен, у которого корни как самого многочлена, так и корни его производной, — целые числа.

Нетрудно доказать, что любой многочлен p(x) с действительными коэффициентами, принимающий неотрицательные значения при всех действительных x, можно представить в виде суммы квадратов двух многочленов с действительными коэффициентами. Прежде всего заметим, что если p(z) = 0 и p — многочлен с действительными коэффициентами, то p(z)=p(z)=0, т. е. z — тоже корень многочлена p.

Поэтому корни многочлена с действительными коэффициентами разбиваются на действительные корни и пары комплексных корней. Следовательно, где числа k действительные.

Предположим теперь, что p(x) 0 при всех действительных x. Если x — достаточно большое положительное число, то поэтому a > 0. Кроме того, все числа mk чётны. В самом деле, пусть некоторые из чисел mk нечётны. Можно считать, что нечётны лишь числа m1,..., ms и при этом 1 <... < s.

Тогда при s1 < x < s выполняется неравенство т. е. p(x) < 0. (Если s = 1, то это неравенство выполняется при всех x < s.) Таким образом, действительные корни тоже разбиваются на пары. Следовательно, где некоторые из чисел zj могут быть действительными.

Пусть где q и r — многочлены с действительными коэффициентами. Тогда В итоге получаем p(x) = (q(x))2 + (r(x))2.

Но для многочленов от нескольких переменных аналогичное утверждение уже не всегда верно, т. е. существуют неотрицательные многочлены (так мы будем называть многочлены с действительными коэффициентами, которые при всех действительных значениях переменных принимают неотрицательные значения), которые нельзя представить в виде суммы квадратов многочленов с действительными коэффициентами. Первым это доказал немецкий математик Давид Гильберт в 1888 г., но он не привёл явный пример такого многочлена. Первый простой пример привёл Т. Моцкин в 1967 г. А именно, он показал, что многочлен неотрицателен, но его нельзя представить в виде суммы квадратов многочленов с действительными коэффициентами. Основная трудность заключалась, конечно, в том, чтобы найти этот многочлен, а само доказательство его свойств, как мы сейчас увидим, несложно.

Неотрицательность многочлена F следует из того, что Предположим теперь, что F(x, y) = fj (x, y)2, где fj — многочлены с действительными коэффициентами. Тогда fj (x, 0)2 = F(x, 0) = 1. Если хотя бы один из многочленов fj (x, 0) от переменной x отличен от константы, то fj (x, 0)2 — многочлен, степень которого в два раза больше наибольшей из степеней многочленов fj (x, 0). Следовательно, fj (x, 0) = cj — некоторая константа, а значит, fj (x, y) = cj + ygj (x, y). Аналогичные рассуждения показывают, что fj (x, y)=c +xgj (x, y). Ясно, что cj =c и fj (x, y)=cj + + xyhj (x, y), причём здесь deg f — степень многочлена f. Таким образом, т. е.

Все одночлены, встречающиеся в правой части этого равенства, имеют степень не больше 3, а все одночлены, встречающиеся в левой части этого равенства, имеют степень не меньше 4. Следовательно, x2 y2 (x2 y2 3) x2 y2 h2 = 0, а значит, x2 + y2 3 = h2. Получено противоречие, так как Мы обсудили здесь лишь наиболее простые из известных фактов о суммах квадратов. Сейчас на эту тему известно весьма многое, но многие вопросы остаются пока без ответа. Гильберт высказал предположение, что любой неотрицательный многочлен от многих переменных можно представить в виде суммы квадратов не многочленов, а рациональных функций. Вопрос о том, верно это или нет, он включил под номером 17 в свой знаменитый список 23 проблем. Семнадцатая проблема Гильберта была решена в 1927 г. Э. Артином. Он доказал, что любой неотрицательный многочлен можно представить в виде суммы квадратов некоторого количества рациональных функций. В 1967 г.

А. Пфистер уточнил теорему Артина; он доказал, что любой неотрицательный многочлен от n переменных можно представить в виде суммы 2n квадратов рациональных функций. Но до сих пор не известно, можно ли заменить 2n на меньшее число. Лишь при n = 2 известно, что число 2n = в данном случае минимально. А именно, в 1971 г. Касселс, Эллисон и Пфистер показали, что тот самый многочлен F(x, y), который мы рассмотрели выше, нельзя представить в виде суммы квадратов трёх рациональных функций. Их доказательство весьма сложно; оно опирается на глубокие результаты из теории эллиптических кривых.

3. Представление чисел в виде суммы двух квадратов В одном из своих писем Пьер Ферма в 1658 г. сообщал, что он получил «неопровержимые доказательства» того, что любое простое число вида 4k + 1 является суммой двух квадратов, а любое число является суммой не более чем четырёх квадратов. Никаких записей этих доказательств Ферма не оставил. Прошло почти сто лет, и этими теоремами заинтересовался Леонард Эйлер. Первую из них он доказал в 1747 г., а через два года он нашёл другое изящное и сравнительно простое доказательство той же теоремы. Вторая теорема была доказана лишь в 1770 г. Лагранжем, после чего Эйлер сумел значительно упростить его доказательство.

В дальнейшем были найдены другие интересные доказательства теоремы о представлении простых чисел p = 4k + в виде суммы двух квадратов; некоторые из них приведеПредставление чисел в виде суммы двух квадратов ны в решениях задач 31.53– 31.55 и 36.19 а). Но все они, как и доказательство Эйлера, были не вполне элементарны. И лишь совсем недавно* было получено очень изящное и вполне элементарное доказательство этой теоремы.

Центральное место в этом доказательстве занимает простое, но важное понятие инволюции. Пусть M — некоторое множество. Отображение если = m для любого элемента m множества M.

Примером инволюции служит любая симметрия. Инволюция позволяет разбить точки (элементы множества M) на пары {m, «симметричных» точек. Для элемента получается та же самая пара, что и для элемента m, так как = m. Пара элементов не возникает лишь в том (m)=m (такие точки m называют неподвижслучае, когда ными). Поэтому если на конечном множестве M задана инволюция, то чётность количества элементов M совпадает с чётностью количества неподвижных точек инволюции (остальные элементы разбиваются на пары, поэтому их количество чётно).

Общая схема доказательства такова. Рассмотрим множество всех решений уравнения x2 + 4yz = p в натуральных числах. Достаточно доказать, что если p = 4k + 1, то у этого уравнения есть решение, для которого y = z. В самом деле, тогда p = x2 + (2y)2. Решение, для которого y = z, — это неподвижная точка инволюции y, z) = (x, z, y). Поэтому достаточно доказать, что общее количество решений нечётно. Для этого строится совсем другая инволюция имеющая ровно одну неподвижную точку. Вот эта инволюция:

(x, * D. Z a g i e r. A one-sentence proof that every prime p 1 (mod 4) is a sum of two squares // Amer. Math. Monthly. 1990. V. 97. P. 114.

Отметим сначала, что x = 2y и x = y z, так как иначе p = x2 + 4yz = 4(y2 + yz) или p = (y z)2 + 4yz = (y + z)2.

Проверим, далее, что любое решение уравнения x2 + 4yz = p инволюция действительно переводит в решение. Это следует из тождеств > 2z = 2y, т. е. точка типа (1) переходит в точку типа (3).

Аналогично проверяется, что точка типа (3) переходит в точку типа (1), а точка типа (2) — в точку типа (2). После этого уже легко проверить, что — инволюция.

Точка типа (1) не может быть неподвижной, так как x = x + 2z > x; для точки типа (3) x = x 2y < x. Поэтому неподвижной может быть лишь точка типа (2), причём для неё должно выполняться соотношение z = z = x y + z, т. е. x = y. В таком случае p = x2 + 4yz = x(x + 4z), а значит, x = y = 1 (здесь мы используем простоту числа p). Если p = 4k + 1, то (1, 1, k) — неподвижная точка (здесь мы используем то, что число p имеет вид 4k + 1). Доказательство завершено.

Сделаем ещё некоторые замечания по поводу представления чисел в виде суммы двух квадратов. Прежде всего отметим, что простое число вида 4k + 3 нельзя представить в виде суммы двух квадратов. В самом деле, квадрат числа 2m + 1 равен 4(m2 + m) + 1, поэтому остаток от деления его на 4 равен 1. Следовательно, остаток от деления суммы двух квадратов на 4 равен 0, 1 или 2, но никак не 3.

Условие простоты числа p = 4k + 1 тоже существенно.

Например, число 21 нельзя представить в виде суммы двух квадратов.

Отметим также, что если m = a2 + b2 и n = c2 + d2, то mn = (ac + bd)2 + (ad bc)2 — тоже сумма двух квадратов.

Поэтому произведение простых чисел вида 4k + 1 можно представить в виде суммы двух квадратов. Если же в какое-то натуральное число простой множитель вида 4k + входит в нечётной степени, то это число нельзя представить в виде суммы двух квадратов. Это следует из того, что если a2 + b2 делится на простое число p = 4k + 3, то оба числа a и b делятся на p (задача 31.2).

4. Построение правильного 17-угольника В Древней Греции геометры использовали для построений разные инструменты, но основными инструментами были циркуль и линейка. А в самом знаменитом древнегреческом учебнике геометрии, «Началах» Евклида, никакие другие инструменты вообще не встречаются. Поэтому под геометрическими построениями обычно подразумевают построения циркулем и линейкой. Циркуль позволяет построить окружность данного радиуса с центром в данной точке, а линейка позволяет построить прямую, проходящую через две данные точки.

Построению правильных многоугольников в «Началах»

Евклида уделено большое внимание. Построение правильного треугольника описано в Предложении 1 Книги I, а почти вся Книга IV посвящена построению других правильных многоугольников: квадрата, пятиугольника, шестиугольника, пятнадцатиугольника. Но ничего существенно нового геометры не могли добавить очень долго, вплоть до 1796 г., когда 19-летний Гаусс показал, что с помощью циркуля и линейки можно построить правильный 17-угольk ник. Впоследствии он доказал, что если число n = 22 + простое, то с помощью циркуля и линейки можно построить правильный n-угольник. Гаусс утверждал также, что он умеет доказывать, что правильный n-угольник можно построить лишь в том случае, когда n = 2m p1... ps, где p1,..., ps — различные простые числа вида 22 + 1. Но ни в одной из его работ нет доказательства этого утверждения.

Построение правильного 17-угольника в большей степени относится не к геометрии, а к алгебре. Формула Муавра показывает, что корни уравнения xn 1 = 0 имеют вид cos + i sin. На комплексной плоскости эти точки являются вершинами правильного n-угольника. Таким образом, построение правильного n-угольника тесно связано с решением уравнения xn 1 = 0. Это уравнение имеет очевидный корень x = 1. Чтобы избавиться от него, поделим многочлен xn 1 на x 1. В результате получим многочлен xn1 + xn2 +... + x2 + x + 1. Именно его мы будем рассматривать в дальнейшем.

Будем говорить, что комплексное число a + ib можно построить, если можно построить отрезки длин a и b, т. е. можно построить точку a + ib на комплексной плоскости. Если задан отрезок единичной длины, то по данным отрезкам a и b можно построить отрезки a ± b, ab, a/b, a.

Несложно проверить, что Поэтому если отрезки a и b можно построить, то число a + ib тоже можно построить. В итоге получаем, что если числа u и v можно построить, то корни уравнения x2 + ux + v = 0 тоже можно построить.

Разберём для начала с этой точки зрения построение правильных n-угольников при n = 3 и n = 5. При n = 3 получаем уравнение x2 + x + 1 = 0. Это уравнение квадратное, поэтому его корни можно построить.

При n = 5 получаем уравнение x4 + x3 + x2 + x + 1 = 0.

Положим u = x + x1. Легко проверить, что u2 + u 1 = 0.

Корни u1 и u2 этого уравнения можно построить. С их помощью можно построить корни уравнений x2 u1 x + 1 = и x2 u2 x + 1 = 0. Эти корни являются корнями исходного уравнения.

Теперь можно непосредственно заняться построением правильного 17-угольника. Для этого, как мы убедились, достаточно доказать, что корни уравнения x16 + x15 +...

... + x + 1 = 0 можно получить, последовательно решая квадратные уравнения. Достаточно даже получить один, 3,..., 16. Доказательство Гаусса основано на специальной нумерации этих корней. Он нумерует корни таким образом, чтобы при фиксированном l переход от k (корня с номером k) к k+l происходил по одному и тому же правилу, а именно, чтобы при таком переходе число k возводилось в некоторую фиксированную степень. Такую нумерацию можно получить, положив k = g, где числа 1, g, g2, g3,..., g15 дают разные остатки при делении на 17.

В самом деле, в таком случае В качестве g можно взять, например, число 3. При этом Рассмотрим сначала квадратное уравнение с корнями По теореме Виета проверить, что где = 2/17. Воспользовавшись формулой получим Таким образом, x1 и x2 удовлетворяют квадратному уравнению x2 + x 4 = 0 с целыми коэффициентами. Следовательно, x1 и x2 можно построить.

Рассмотрим теперь квадратные уравнения с корнями Легко проверить, что y1 + y2 = x1 и Таким образом, y1 и y2 — корни квадратного уравнения y2 x1 y + 1 = 0. Аналогично доказывается, что являются корнями квадратного уравнения y2 x2 y + 1 = 0.

Следовательно, y1, y2, y3 и y4 можно построить.

Рассмотрим, наконец, квадратное уравнение с корнями Ясно, что z1 +z2 =y1 и z1 z2 =2(cos 5 +cos 3 )=y3. Таким образом, z1 и z2 — корни квадратного уравнения z2 y1 z+y3 =0.

Поэтому число z1 = 2 cos можно построить, а значит, можно построить и число = cos + i sin. Но тогда можно построить и правильный 17-угольник.

5. Построения циркулем и линейкой Здесь мы докажем, что с помощью циркуля и линейки нельзя выполнить некоторые построения, например, нельзя построить отрезок 3 2a, если задан отрезок длины a, и нельзя разделить произвольный угол на три равные части. Первая из этих задач называется удвоением куба, потому что она эквивалентна задаче о построении ребра куба в 2 раза большего объёма, чем куб с данным ребром. Вторая задача называется трисекцией угла. Кроме того, мы докажем, что с помощью циркуля и линейки нельзя построить треугольник по длинам его биссектрис.

Сначала нужно точно сформулировать, что такое построение циркулем и линейкой. В задаче на построение циркулем и линейкой обычно бывает задан некоторый набор точек. Окружность и прямую можно задать двумя точками, поэтому включать в набор исходных данных окружности и прямые нет необходимости. В некоторых задачах набор исходных данных может быть пустым множеством; например, в задаче о построении правильного треугольника или пятиугольника исходного набора данных нет. Задача на построение заключается в том, чтобы добавить к исходному набору точек некоторые другие точки так, чтобы при этом в новом наборе содержались некоторые требуемые точки. К исходным данным разрешается добавлять следующие точки, прямые и окружности:

1) прямую, проходящую через две данные точки;

2) окружность с данным центром, проходящую через данную точку;

3) точку пересечения двух данных прямых, двух данных окружностей или данной прямой и данной окружности;

4) произвольную точку.

Добавление произвольной точки требует пояснений. Подразумевается, что конечный результат должен не зависеть от выбора этой точки. Точнее говоря, если вместо выбранной произвольной точки мы возьмём любую другую достаточно близкую к ней точку, то при этом конечный результат не должен измениться. Отметим, что операция выбора произвольной точки на данной прямой l или данной окружности S не даёт ничего нового. Действительно, вместо этого можно выбрать две произвольные точки A и B и построить точку пересечения прямой AB с прямой l или с окружностью S.

Выясним, по каким алгебраическим правилам координаты добавляемых точек получаются из координат исходных точек. Введём на плоскости прямоугольную систему координат Oxy. Каждая точка плоскости имеет две координаты.

Рассмотрим набор всех численных значений координат исходных точек, не различая координаты x и y.

Т е о р е м а 1. Предположим, что к набору точек с координатами t1,..., tn в процессе построений циркулем и линейкой добавилась ровно одна точка с координатами s1 и s2.

Тогда либо число si (i = 1, 2) рационально, либо оно получается из чисел t1,..., tn применением операций сложения, вычитания, умножения, деления и извлечения квадратного корня.

Д о к а з а т е л ь с т в о. Разберём все возможные варианты добавления одной точки.

а) Добавление произвольной точки. Для любой точки найдётся сколь угодно близкая к ней точка, обе координаты которой рациональны. Поэтому в качестве произвольной точки всегда можно выбрать точку с рациональными координатами.

б) Добавление точки пересечения двух прямых. Прямая, проходящая через точки с координатами (a1, b1 ) и (a2, b2 ), задаётся уравнением т. е. (b2 b1 )x + (a1 a2 )y = a1 b2 a2 b1. Коэффициенты этого уравнения получаются из координат исходных точек применением операций умножения и вычитания.

Точка пересечения прямых, заданных уравнениями имеет координаты Эти числа получаются из коэффициентов уравнений применением операций вычитания, умножения и деления. Следовательно, координаты точки пересечения двух прямых, проходящих через две пары данных точек, можно получить из координат этих четырёх данных точек, применяя операции вычитания, умножения и деления.

Операция извлечения квадратного корня пока не использовалась. Она нужна лишь для нахождения координат точек пересечения прямой и окружности или двух окружностей.

в) Добавление точки пересечения прямой и окружности.

Окружность с центром (a1, b1 ), проходящая через точку (a2, b2 ), имеет уравнение Для нахождения координат точек пересечения прямой px + qy = r и окружности x2 2ax + y2 2by = c нужно решить систему уравнений Одно из чисел p и q отлично от нуля. Будем для определённости считать, что q = 0. Тогда из первого уравнения можно получить выражение для y через x:

Подставив это выражение в уравнение окружности, получим квадратное уравнение Корни x1 и x2 этого уравнения выражаются через его коэффициенты с помощью операций сложения, вычитания, умножения и извлечения квадратного корня. Соответствующие выражения для y1 и y2 можно получить по формуле (1).

г) Добавление точки пересечения двух окружностей.

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

Удвоение куба Отрезок a можно выбрать в качестве отрезка (1, 0) на оси Ox. Таким образом, в задаче удвоения куба требуется построить точку с координатами ( 3 2, 0). Предположим, что эту точку можно построить с помощью циркуля и линейки. Тогда согласно теореме 1 число 3 2 можно получить из рациональных чисел, используя операции сложения, вычитания, деления, умножения и извлечения квадратного корня, т. е., как мы будем для краткости говорить, это число можно выразить в квадратных радикалах. Для доказательства неразрешимости задачи удвоения куба помощью циркуля и линейки нужно доказать, что число 2 не выра- жается в квадратных радикалах. Напомним, что число иррационально (задача 31.2 а).

Т е о р е м а 2. Предположим, что один из корней уравнения x3 + Ax2 + Bx + C = 0, где A, B, C — рациональные числа, выражается в квадратных радикалах. Тогда это уравнение имеет рациональный корень.

Д о к а з а т е л ь с т в о. Отметим прежде всего, что любое число, полученное из чисел u1,..., un применением операций сложения, вычитания, умножения и деления, можно представить в виде где P и Q — многочлены с рациональными коэффициентами, т. е. выражения, полученные без использования операции деления. В самом деле, Для любого числа, выражающегося в квадратных радикалах, можно определить его ранг как наибольшее число расположенных один внутри другого квадратных радикалов в выражении для числа. Это определение нужно сфорболее аккуратно. Например, (1 + 2)2 = 3 + 2 2, т. е. 3 + 2 2 = 1 + 2. Тем самым, одно выражение числа 1 + 2 имеет ранг 1, а другое выражение того же числа имеет ранг 2. Поэтому нужно сначала определить ранг выражения, а в качестве ранга самого числа взять наименьший из рангов всех его выражений.

Для числа ранга n можно определить его порядок следующим образом. Рассмотрим для числа все его выражения ранга n. В каждое такое выражение входит несколько радикалов вида R, где ранг выражения R равен n 1;

пусть k — количество таких радикалов. Наименьшее из всех таких чисел k будем называть порядком числа.

Кубическое уравнение x3 + Ax2 + Bx + C = 0 имеет три корня x1, x2, x3 (не обязательно различных), для которых выполняется соотношение В частности, x1 + x2 + x3 = A.

Предположим, что один из корней этого кубического уравнения выражается в квадратных радикалах. Остальные корни могут выражаться в квадратных радикалах, а могут и не выражаться. Возьмём все корни, которые выражаются в квадратных радикалах, и выберем среди них все корни с наименьшим рангом. Затем среди этих корней выберем корни с наименьшим порядком. Если такой корень один, то выберем его, а если их несколько, то выберем любой из них.

Пусть при этом выбран корень x1 с рангом n и порядком k.

Требуется доказать, что n = 0, т. е. число x1 рационально.

Предположим, что n 1. Рассмотрим для числа x1 какое-нибудь выражение ранга n и порядка k. Пусть R — одно из выражений ранга n, входящих в это выражение. Тогда x1 можно представить в виде где выражения a, b, c и d содержат не более k 1 радикалов ранга n и содержат радикалов большего ранга. Докажем, что c d R = 0. Если d = 0, то c = 0. Если же d = 0, то из равенства c d R = 0 следовало бы, что R = c/d. Подставляя это значение числа R в формулу (2), можно получить для x1 выражение ранга не более n, содержащего не более k 1 радикалов ранга n. Это противоречит тому, что ранг числа x1 равен n, а порядок равен k. Следовательно, c d R = 0, а значит, Подставив значение x1 = p + q R в кубическое уравнение, получим где выражения M и N содержат не более k 1 радикалов ранга n ине содержат радикалов большего ранга. Если N = 0, то R = M/N, а выше было показано, что такого быть не может. Следовательно, M = N = 0. Непосредственные вычисления показывают, что т. е. x2 = p q R — другой корень кубического уравнения.

Наибольший ранг радикалов, входящих в это выражение числа x3, не превосходит n, причём радикалов ранга n не более k1. Это противоречит выбору корня x1 как корня наименьшего ранга n и при этом наименьшего порядка k.

С помощью теоремы 2 легко доказать, что число нельзя выразить в радикалах. Действительно, рассмотрим кубическое уравнение x3 2 = 0. него есть лишь один вещественный корень, а именно, 3 2. Число 3 2 не рационально, поэтому уравнение x3 2 = 0 не имеет рациональных корней. Следовательно, у этого уравнения нет корней, выражающихся в квадратных радикалах.

Трисекция угла Чтобы доказать, что не существует общего способа построений, позволяющего разделить на три равные части любой угол, достаточно доказать, что с помощью циркуля и линейки нельзя разделить на три равные части угол в 30.

Введём систему координат Oxy, выбрав в качестве начала координат вершину данного угла AOB и направив ось Ox по стороне OA. Можно считать, что точки A и B удалены от точки O на расстояние 1. Тогда в задаче трисекции угла требуется по точке с координатами (cos 3, sin 3 ) построить точку с координатами (cos, sin ). В случае, когда = 10, исходная точка имеет координаты,. Обе её координаты выражаются в квадратных радикалах. ПоДополнение этому достаточно доказать, что число sin 10 не выражается в квадратных радикалах.

то число x = sin 10 удовлетворяет кубическому уравнению 3x 4x3 = 1/2, т. е.

Согласно теореме 2 достаточно доказать, что у этого уравнения нет рациональных корней. Положим 2x = p/q, где p и q — целые числа, не имеющие общих делителей. Тогда p3 3pq2 + q3 = 0, т. е. q3 = p(3q2 p2 ). Следовательно, число q делится на p, а значит, p = ±1. Поэтому ±1 3q2 + q3 = 0, т. е. q2 (q ± 3) = ±1. Число 1 делится на q, поэтому q = ±1.

В итоге получаем, что x = ±1/2. Легко проверить, что значения ±1/2 не являются корнями уравнения (3). Получено противоречие, поэтому уравнение (3) не имеет рациональных корней, а значит, число sin 10 не выражается в квадратных радикалах.

Построение треугольника по биссектрисам Если заданы длины медиан треугольника или длины его высот, то треугольник можно построить циркулем и линейкой. Но если заданы длины биссектрис треугольника, то нет общего способа, позволяющего построить сам треугольник циркулем и линейкой. Чтобы это доказать, достаточно доказать, что треугольник, длины биссектрис которого равны 3, 1 и 1, нельзя построить циркулем и линейкой.

Нам потребуются два геометрических факта, доказательства которых можно найти в книге В. В. П р а с о л о в. Задачи по планиметрии. 6-е изд. М.: МЦНМО, 2007. Прежде всего заметим, что треугольник, у которого две биссектрисы равны, равнобедренный (задача 5.55 из указанной книги), поэтому в рассматриваемом треугольнике =, т. е. =. Далее, согласно задаче 12.37 г) из указанной книги Поэтому Если рассматриваемый треугольник можно было бы построить циркулем и линейкой, то число x=sin( /2) выражалось бы в квадратных радикалах. Ясно, что sin(3 /2) = 3x 4x и cos = 1 2x2. Поэтому для x мы получаем уравнение 4x3 12x2 3x + 6 = 0. После замены y = 2x 2 перейдём к уравнению y3 15y 10 = 0. Согласно теореме 2 достаточно проверить, что это уравнение не имеет рациональных корней. Предположим, что число p/q, где p и q — взаимно простые целые числа, является корнем этого уравнения.

Тогда p3 = 5q2 (3p + 2q), поэтому p = 5r, где r — целое число.

В таком случае 25r3 = q2 (15r + 2q). Следовательно, число q тоже делится на 5, чего не может быть.

6. Хроматический многочлен графа Рассмотрим в пространстве систему из нескольких точек и отрезков, соединяющих некоторые из этих точек. При этом нас будет интересовать лишь то, какие именно пары точек соединены отрезками. Более того, эти отрезки можно считать не прямолинейными, а криволинейными. Такую систему точек называют графом; сами точки называют вершинами графа, а отрезки — рёбрами графа.

Граф называют планарным, если его можно расположить на плоскости так, чтобы его рёбра попарно не пересеДополнение кались. Например, граф, изображённый на рис. 1, не планарный. Это следует из решения известной задачи о трёх домах и трёх колодцах: «Можно ли каждый из трёх домов го была популярна задача четырёх красок: «Любой ли планарный граф можно раскрасить в 4 цвета?». (Под раскраской графа здесь и далее подразумевается такая раскраска вершин графа, что концы любого ребра разноцветные.) Лишь в 1977 г. было доказано, что любой планарный граф можно раскрасить в 4 цвета. Это доказательство опиралось на перебор огромного количества различных вариантов, выполненный с помощью компьютера.

С раскрасками графов связано одно интересное явление, которое мы сейчас обсудим. Пусть G — некоторый граф, а f(G, x) — количество раскрасок этого графа в x цветов.

Удивительным образом оказывается, что f(G, x) — многочлен степени n, где n — число вершин графа. Прежде чем доказывать это утверждение, разберём два простых примера.

Наиболее прост тот случай, когда у графа G нет вообще никаких рёбер, а есть только n вершин. В этом случае каждую вершину можно окрасить любым цветом, независимо от остальных вершин. Поэтому f(G, x) = xn.

Другой крайний случай — граф G с n вершинами, любые две из которых соединены ребром. В этом случае все вершины должны быть разноцветными, поэтому В обоих случаях f(G, x) — многочлен степени n. Как мы сейчас убедимся, из этого уже следует, что f(G, x) — многочлен степени n для любого графа G с n вершинами.

Рассмотрим граф G+ с n вершинами, в котором две верn шины A и B соединены ребром. Сопоставим ему граф G, n в котором все вершины и рёбра те же самые, за исключением того, что в нём нет ребра, соединяющего вершины A и B. Сопоставим графу G+ также граф Gn1, в котором все вершины и рёбра такие же, как у графов G+ и G, за исключением того, что в нём вершины A и B отождествлены друг с другом (при этом могут возникнуть двойные рёбра, но мы их заменяем на обычные рёбра). Примеры графов G, G+ и Gn1 приведены на рис. 2. При этом двойное ребро, соединяющее вершины A = B и D, заменено на обычное (однократное) ребро.

Любая раскраска графа G с одноцветными вершинами A и B соответствует определённой раскраске графа Gn1, а любая раскраска того же графа с разноцветными вершинами A и B — раскраске графа G+. Поэтому С помощью формулы (1) несложно доказать, что если Gn — граф с n вершинами, то f(Gn, x) — многочлен степени n. Применим для этого индукцию по n. При n = 1 граф состоит из одной точки, поэтому f(G1, x) = x. ПредполоДополнение жим, что для любого графа Gn1 с n 1 вершиной функция f(Gn1, x) представляет собой многочлен степени n.

Возьмём произвольный граф G с n вершинами. Применив несколько раз формулу (1), можно перейти от графа G n к графу с n вершинами, любые две из которых соединены ребром. Хроматический многочлен полученного графа равен x(x 1)... (x n + 1), поэтому где f1,..., fk — хроматические многочлены графов с n вершиной, т. е. многочлены степени n 1.

При доказательстве мы воспользовались тем, что хроматический многочлен графа, все вершины которого соединены рёбрами, равен x(x 1)... (x n + 1). Но можно воспользоваться и тем, что хроматический многочлен графа, у которого вообще нет рёбер, равен xn. Для этого формулу (1) нужно записать в виде Применив такую формулу несколько раз, можно перейти от графа G+ к графу с n вершинами, у которого вообще нет рёбер. Поэтому где g1,..., gl — хроматические многочлены графов с n вершиной.

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

Т е о р е м а 1. Хроматический многочлен графа с n вершинами имеет вид Эту теорему сформулировал и доказал в 1932 г. американский математик Хасслер Уитни.

Т е о р е м а 1. Число e трансцендентно.

Д о к а з а т е л ь с т в о. Предположим, что число e алгебраическое. Тогда выполняется равенство где a0, a1,..., am — целые числа.

Согласно задаче 29.14 а) для любого многочлена f(x) степени d имеет место равенство где F(x) = f(x) + f (x) +...+ f(d) (x). В частности, для каждого целого неотрицательного числа k имеет место равенство т. е.

торое натуральное число (выбрав n подходящим образом, мы вскоре придём к противоречию); степень d этого многочлена равна (m + 1)n 1. Запишем равенство (2) для k = 0, 1,..., m, умножим каждое из таких равенств на соответствующее ak и сложим их. Из равенства (1) следует, что Покажем, что n можно выбрать так, что в левой части равенства (3) стоит целое ненулевое число, а в правой части — число, абсолютная величина которого меньше 1.

Легко видеть, что f(0)=f (0)=...=f(n2) (0)=0, f(n1) (0)= = (1)mn (m!)n и f(l) (k) = 0 при 0 l n 1 и 1 k m. Согласно задаче 28.19 коэффициенты производной порядка l многочлена xn1 ((x 1)... (x m))n делятся на l!. Поэтому все производные f(l) (x) при l n имеют целые коэффициенты, делящиеся на n. Значит, Здесь A и Bk — целые числа.

Пусть n — простое число, которое одновременно больше m и |a0 |. Тогда в левой части равенства (3) слагаемое a0 F(0) не делится на n, а слагаемые ak F(k), 1 k m, нулю. В частности, его абсолютная величина не меньше 1.