Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
Решения 22.1. Пусть v — произвольная вершина графа с шестью вершинами. Среди оставшихся пяти вершин есть либо три вершины, соединённые рёбрами с v, либо три вершины, не соединённые рёб- рами с v. Пусть v 1 , v 2 , v 3 — вершины, соединённые рёбрами с Если вершины v 1 , v 2 , попарно не соединены рёбрами друг с другом, то они образуют искомую тройку вершин. Если какие-то две из вершин v 1 , v 2 , соединены ребром, то вместе с вершиной v они образуют искомую тройку. Для вершин v 1 , v 2 , v 3 , не соединённых рёбрами с вершиной v, рассуждения аналогичны. Вычислим двумя способами количество пар, состоящих из ребра и одного из его концов. С одной стороны, это количество равно удвоенному числу рёбер; в частности, оно чётно. С другой стороны, оно равно сумме чисел рёбер, выходящих из всех вершин. Эта сумма чётна, поэтому вне входит чётное число нечёт- ных слагаемых. А нечётные слагаемые соответствуют как раз тем вершинам, из которых выходит нечётное число рёбер. 22.3. Ответ да, может. При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно 4k + 1. При k = 250 получаем нужное число свободных концов Глава 22. Графы. а) Применим индукцию по числу рёбер графа. Для графа с двумя рёбрами утверждение очевидно. Возьмём теперь произвольный граф и будем идти по его рёбрам, выйдя из некоторой вершины и не проходя дважды по одному и тому же ребру. Из каждой вершины выходит чётное число рёбер, поэтому мы можем продолжать обход до тех пор, пока не попадём в вершину, в которой уже побывали (эта вершина необязательно та, из которой мы вышли. В результате получится некоторый цикл. Выбросив все рёбра, входящие в этот цикл, мы получим граф с меньшим числом рёбер, в котором снова из каждой вершины выходит чётное число рёбер. По предположению индукции этот граф можно разбить на непересекающиеся циклы. б) Будем действовать также, как ив задаче а, но только теперь будем выходить из вершины, из которой выходит нечётное число рёбер. На этот разу нас либо получится цикл, либо получится несамопересекающийся путь, соединяющий две вершины, из которых выходит нечётное число рёбер. Можно выбросить этот цикл или путь и к полученному графу применить предположение индукции. Из каждой вершины графа, отличной от начала или конца обхода, выходит чётное число рёбер. 22.6. Согласно задаче 22.4 данный граф можно представить в виде объединения непересекающихся циклов и, возможно, одного несамопересекающегося пути. Если граф состоит только из несамопересекающегося пути или только из цикла, то всё ясно. Если есть несамопересекающийся путь, то возьмём его, а если несамопересекающегося пути нетто возьмём произвольный цикл. Предположим, что помимо выбранного пути (цикла) есть ещё ка- кие-то дополнительные циклы. Из связности графа следует, что есть дополнительный цикл, одна из вершин которого лежит на несамопересекающемся пути (выбранном цикле. Если выбросить этот дополнительный цикл, то получится граф, для которого обход существует по предположению индукции. Поэтому можно поступить следующим образом. Будем обходить полученный граф до тех пор, пока не дойдём до вершины, принадлежащей дополнительному циклу. После этого совершим обход дополнительного цикла, а затем продолжим обход полученного графа. В результате получим обход исходного графа. Сначала ориентируем граф произвольно. Рассмотрим все вершины, из которых выходит нечётное число рёбер. Их число чётно. Действительно, сумма чисел рёбер, выходящих из всех вершин, равна числу рёбер, поэтому она чётна. Таким образом, если Решения задач 273 есть хотя бы одна вершина v 1 , из которой выходит нечётное число рёбер, то есть ещё хотя бы одна такая же вершина v 2 . Пользуясь связностью, соединим их набором рёбер. Среди всех таких наборов возьмём тот, в котором число рёбер наименьшее (тогда в нём не будет циклов. Изменим ориентации всех рёбер этого набора на противоположные, а ориентации всех остальных рёбер оставим без изменений. После такой операции из вершин и будет выходить чётное число рёбер, а из всех остальных вершин будет выходить столько же рёбер, сколько и раньше. Несколькими такими операциями мы уничтожим все вершины, из которых выходит нечётное число рёбер. 22.8. Предположим сначала, что в графе есть путь, обладающий указанными свойствами. Изначальной и конечной точек этого пути выходят рёбра, не принадлежащие паросочетанию, поэтому путь состоит из нечётного числа рёбер v 1 v 2 , v 2 v 3 , . . . , Построим новое паросочетание, выбросив рёбра v 2 v 3 , v 4 v 5 , . . . и добавив рёбра v 1 v 2 , v 3 v 4 , . . . Это можно сделать, потому что из вершин и по условию не выходят рёбра паросочетания.) Новое паросочетание содержит на одно ребро больше, чем старое, что противоречит максимальности. Предположим теперь, что есть два паросочетания M и M ′ , прич м содержит больше рёбер, чем M. Построим для паросоче- тания M путь, обладающий требуемыми свойствами. Рассмотрим только тер бра, которые входят ровно водно из паросочетаний M и M ′ . Любой путь, идущий по таким рёбрам, обладает свойством, поскольку если из какой-то вершины выходят два из рассматриваемых рёбер, то одно из них принадлежит M, а другое принадлежит и не принадлежит M. Рассмотрим все пути, которые максимальны в том смысле, что их нельзя увеличить. Среди них обязательно найдётся путь, у которого рёбер паросо- четания больше, чем рёбер паросочетания M; это следует из того, что паросочетание содержит больше рёбер, чем M. Этот путь, очевидно, обладает свойством 3). Легко убедиться, что он обладает и свойством 2). Действительно, пусть v — конец или начало этого пути. Из v выходит ребро паросочетания M ′ . Из максимальности пути следует, что из v не выходит ребра, которое принадлежит M и не принадлежит M ′ . Но ребро, которое одновременно принадлежит M и M ′ , тоже не может выходить из v, потому что изнемогут выходить два ребра паросочета- ния M ′ 22.9. В одну сторону утверждение очевидно если паросочета- ние существует, то количество вершин из множества Y, соединён- Глава 22. Графы ных с выделенными вершинами даже только рёбрами паросочета- ния, уже равно количеству выделенных вершин. Предположим теперь, что указанное условие выполняется, но нужного паросочетания не существует. Чтобы прийти к противоречию, возьмём максимальное паросочетание M. По предположению весть вершина x, из которой не выходит рёбер па- росочетания M. Рассмотрим все пути, идущие из вершины x, рёбра которых поочерёдно то лежат в M, тоне лежат. Пусть и Y ′ — множества концов этих путей, лежащих в X и Y. Согласно задаче 22.8 из максимальности M следует, что из каждой вершины множества выходит ребро паросочетания M; очевидно также, что из каждой вершины множества X ′ , кроме вершины выходит ребро паросочетания M. Пусть X ′′ — это множество без вершины Вершины множеств и разбиты на пары — концы рёбер паросочетания M. В частности, и состоят из одинакового числа вершин. Кроме того, вершины множества соединены рёбрами только с вершинами множества Y ′ . Действительно, если вершина y соединена с некоторой вершиной множества X ′ , то вершина соединена с вершиной x путём, рёбра которого поочерёдно то лежат в M, тоне лежат. Нов таком случае вершина y лежит в Y ′ . В результате получаем, что количество вершин, соединённых рёбрами с вершинами множества X ′ , на 1 меньше количества вершин множества X ′ . Приходим к противоречию. Прежде всего покажем, что юношей пришло ровно столько же, сколько девушек. Пусть количество юношей равно a, количество девушек равно b, а количество всех пар знакомых друг с другом юношей и девушек равно n. Тогда ka = n = kb, поэтому Выберем произвольную группу из юношей. Пусть количество тех девушек, которые знакомы хотя бы с одним из этих юношей, равно b 1 . Пусть, далее, n 1 — количество пар знакомых юношей и девушек, в которых юноша — один из выбранных юношей количество пар знакомых юношей и девушек, в которых девушка — одна из выбранных девушек. Ясно, что n 2 > n 1 , n 1 = и n 2 = kb 1 . Поэтому b 1 > a 1 . Это неравенство позволяет воспользоваться результатом задачи 22.9. ГЛАВА КОМПЛЕКСНЫЕ ЧИСЛА Комплексным числом называют выражение вида a + bi, где и b — вещественные числа, а i — символ, удовлетворяющий соотношению i 2 = −1. Если z = a + bi, то числа a и b называют соответственно вещественной и мнимой частью числа z обозначение, а комплексное число a − bi называют числом, сопряжённым к числу z обозначение z). Перемножают комплексные числа по обычным правилам раскрытия скобок и приведения подобных членов, заменяя каждый раз нате+ Каждое вещественное число a можно рассматривать как комплексное число a + Если на плоскости выбрать систему координат, то можно установить взаимно однозначное соответствие между комплексными числами и точками плоскости, при котором числу a + соответствует точка с координатами (a, b). При этом умножение на комплексное число z приобретает следующую геометрическую интерпретацию. Пусть r — расстояние от нуля до z, f — угол, на который нужно повернуть вокруг нуля луч, содержащий положительные вещественные числа, чтобы получить луч Oz. Тогда умножение на число z — это композиция гомотетии с коэффициентом r с центром в нуле) и поворота на угол Числа r и называют соответственно модулем и аргументом числа z обозначение r = |z|, f = arg z). По-другому геометрическую интерпретацию произведения комплексных чисел можно сформулировать так приумножении комплексных чисел их модули перемножаются, а аргументы складываются. Зная геометрическую интерпретацию комплексных чисел, легко научиться их делить для этого нужно делить модули и вычитать аргументы. Деление можно ввести также и чисто Глава 23. Комплексные числа алгебраически. Для каждого комплексного числа z = a + bi имеет место очевидное равенство (a + bi)(a − bi) = a 2 − b 2 i 2 = a 2 + b 2 = Поэтому w/z = wz/|z| 2 23.1. Тождества и неравенства для комплексных чисел. Пусть a и b — комплексные числа. Докажите, что) = Re(ab). 23.2. Пусть a и b — комплексные числа. Докажите, что + b| 2 − |a − b| 2 = 4 Re(ab). 23.3. Пусть z и w — комплексные числа. Докажите, что + w| 2 + |z − w| 2 = 2|z| 2 + 2|w| 2 23.4. Пусть a, b и c — комплексные числа. Докажите, что следующие неравенства эквивалентны) Re[(a − c)(c − b)] > 0; 2) c − a + b 2 6 1 2 |a − b|. 23.2. Формула Муавра 23.5. Докажите, что (cos f + i sin f ) n = cos n f + i sin n f для любого натурального n формула Муавра). 23.6. а) Докажите, что числа sin 2 p 2n + 1 , sin 2 2 p 2n + 1 , . . . . . . , sin 2 n p 2n + являются корнями многочлена 2n+1 (1 − x) n − C 3 2n+1 (1 − x) n −1 x + C 5 2n+1 (1 − x) n −2 x 2 − . . . . . . + б) Докажите, что числа ctg 2 p 2n+1 , ctg 2 2 p 2n+1 , . . ., являются корнями многочлена 2n+1 x n − C 3 2n+1 x n −1 + C 5 2n+1 x n −2 − . . . + (−1) n Условия задач. Используя результат задачи 23.6, вычислите следующие суммы и произведения: а) ctg 2 p 2n + 1 + ctg 2 2 p 2n + 1 + . . . + ctg 2 n p 2n + б + 1 + 1 sin 2 2 p 2n + 1 + . . . + 1 sin 2 n p 2n + в) sin p 2n + 1 sin 2 p 2n + 1 . . . sin n p 2n + 1 23.3. Корни из единицы Корнем й степени из единицы называют комплексное число для которого e n = 1. Примитивным корнем й степени из единицы называют комплексное число e , для которого e n =1 и при k = 1, 2, . . . , n − 1. 23.8. а) Докажите, чтоб) Докажите, что sin p 2n sin 2 p 2n . . . sin (n − в) Докажите, что cos p 2n cos 2 p 2n . . . cos (n − 1) p 2n = √ n 2 n −1 23.9. а) Докажите, чтоб) Докажите, что sin p 2n + 1 sin 2 p 2n + 1 . . . sin n p 2n + 1 = √ 2n + 1 2 n Глава 23. Комплексные числа. Докажите, что примитивные корни й степени из единицы — это числа cos 2m p n + i sin 2m p n , где число взаимно просто с n. 23.11. Пусть e — примитивный корень й степени из единицы. Докажите, что + e k + e 2k + . . . + e (n −1)k = ( 0 при 1 6 k 6 n − при k = n. 23.12. Пусть z 1 , . . . , z n — вершины правильного угольника на комплексной плоскости, z 0 — его центр. Докажите, что если P(z) — многочлен степени не выше n − 1, то+ . . . + P(z n ) = nP(z 0 ). 23.13. Пусть e — примитивный корень степени n из единицы. Докажите, что (1 − e )(1 − e 2 )(1 − e 3 ) . . . (1 − e n −1 ) = n. 23.14. Докажите, что произведение длин всех сторон и диагоналей, проведённых из одной вершины правильного n-угольника, вписанного в окружность радиуса 1, равно n. 23.15. а) Докажите, что многочлен P(x) = x 4n + x 3n + x 2n + + x n + 1 делится на многочлен Q(x) = x 4 + x 3 + x 2 + x + 1 тогда и только тогда, когда n не делится наб) Докажите, что если числа m и n взаимно простые, то+ . . . + x 2n + x n + 1 делится на x m −1 + . . . + x 2 + x + 1. 23.16. Докажите, что. . .+(−1) n −1 cos n (n −1) p n = n 2 n −1 23.17. Дано 2n+2 числа a −n , a −n+1 , . . ., a n+1 . Рассмотрим + 2 числа −n, −n + 1, . . . , n + где e = cos p n + i sin p n . Докажите, что Решения задач. Корни многочленов. Докажите, что если z 0 — корень многочлена с вещественными коэффициентами, то z 0 — тоже корень этого многочлена. Докажите, что для любых натуральных чисел a, b, c многочлен x 3a + x 3b+1 + делится на x 2 + x + 1. 23.20. Дан многочлен x n + a 1 x n −1 + . . . + a n . Найдите многочлен, корнями которого являются а) квадраты корней этого многочлена б) кубы корней этого многочлена. При каких натуральных n выражение a n (b − c) + + b n (c − a) + c n (a − b) делится на a 2 + b 2 + c 2 + ab + bc + ca? 23.22. а) Докажите, что многочлен делится на x 2 + x + 1 тогда и только тогда, когда n = 6k ± б) Докажите, что P n (x) делится на (x 2 + x + тогда и только тогда, когда n = 6k + в) Докажите, что P n (x) не делится на (x 2 + x + Решения. Ясно, что Re(ab) = Re(ab) = Re(ab). 23.2. Ясно, что |a ± b| 2 = (a ± b)(a ± b) = |a| 2 + |b| 2 ± (ab + Далее, число ab + ab = ab + ab вещественное, поэтому оно равно + ab) = 2 Re(ab). 23.3. Пусть z = a + ib и w = c + id, где a, b, c, d — вещественные числа. Тогда ± w| 2 = (a ± c) 2 + (b ± d) 2 = a 2 ± 2ac + c 2 + b 2 ± 2bd + Поэтому |z + w| 2 + |z − w| 2 = 2(a 2 + b 2 + c 2 + d 2 ) = 2|z| 2 + 2|w| 2 |