WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 28 | 29 || 31 | 32 |   ...   | 65 |

21.27. а) Пусть dk нечётное число с наибольшим номером k. Тогда одно из чисел ak, bk, ck равно 1, например ak = 1. Начинающий берёт из первой кучки камни так, чтобы числа ak+1, ak+2,... не изменились, а каждое из чисел dk, dk-1, dk-2,..., d0 стало чётным. В частности, число ak изменяется:

оно становится равно 0; это означает, что первый игрок действительно берёт по крайней мере один камень.

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

Игра закончится за конечное число ходов. При этом после хода второго игрока в какой-то кучке обязательно остаётся хотя бы один камень. Поэтому второй игрок выиграть не может.

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

21.28. Пусть n = a0 + 2a1 + 22a2 +... + 2kak двоичная запись числа n.

Тогда n = a1 + 2a2 + 22a3 +... + 2k-1ak n = a2 + 2a3 +... + 2k-2ak n = a3 +... + 2k-3ak......

n = ak 2k Поэтому n n n + +... + = 2 22 2k = (2 - 1)a1 + (22 - 1)a2 + (23 - 1)a3 +... + (2k - 1)ak = = n - (a0 + a1 +... + ak).

21.29. В d-ичной системе счисления, где d = 10100, мы получаем последовательность натуральных чисел, которые не содержат цифры c = 11.. 1.

.

Глава 21. Системы счисления Как и в задаче 21.8, получаем an dk для некоторого n (d - 1)k. В таком k случае an/n 1 +.

d - n 21.30. Легко видеть, что = 0 при k > m и pk n = am, pm n = amp + am-1, pm-......

n = ampm-1 + am-1pm-2 +... + a1.

p Поэтому n n n + +... + = p p2 pm = am(1 + p +... + pm-1) + am-1(1 + p +... + pm-2) +... + a1 = pm - 1 pm-1 - 1 p - = am + am-1 +... + a1 = p - 1 p - 1 p - ampm + am-1pm-1 +... + a1p + a0 - (am + am-1 +... + a0) =.

p - 21.31. Наибольшая степень простого числа p, на которую делится n!, рав n n n на + + +... Поэтому согласно задаче 21.30 наибольшая степень p p2 p n + m (m + n)! числа p, на которую делится =, равна m m!n! m + n - s(m + n) m - s(m) n - s(n) s(m) + s(n) - s(m + n) - - =, p - 1 p - 1 p - 1 p - где s(m) сумма цифр числа m в p-ичной системе счисления.

Остаётся доказать, что s(m+n) = s(m)+s(n)-(p-1)k, где k количество переносов при сложении чисел m и n. При каждом переносе сумма цифр уменьшается на p - 1: вместо p + a получается 1 + a.

21.32. Согласно задаче 14.30 (1 + x)p 1 + xp (mod p). Индукцией по k k k получаем (1 + x)p 1 + xp (mod p). Значит, m (1 + x)b = (1 + x)b0+b1p+...+bmp = m = (1 + x)b0(1 + x)b1p... (1 + x)bmp m (1 + x)b0(1 + xp)b1... (1 + xp )bm bi m bi i xkp (mod p).

k i=0 k=242 Глава 21. Системы счисления m Поэтому коэффициент при xa = xa0+a1p+...+amp в выражении для (1 + x)b b0 b1 bm b по модулю p равен.... С другой стороны, он равен.

a0 a1 am a 21.33. О т в е т: система с основанием 3. С помощью m = dn цифр мы можем записать dm/d чисел. Поэтому нужно доказать, что 3m/3 dm/d, т.е.

3d d3 для любого натурального d. Это неравенство доказано в решении задачи 13.11.

21.34. Согласно задаче 13.5 имеет место неравенство 1·1!+2·2!+3·3!+...+ + k · k! < (k + 1)!, поэтому для данного n число k определяется однозначно.

А именно, должны выполняться неравенства k! n < (k + 1)!. Затем выбираем ak так, чтобы выполнялись неравенства akk! n < (ak + 1)k!. Тогда akk! n < (k+1)!, поэтому ak k. Кроме того, n-akk! < (ak+1)k!-akk! = k!.

Поэтому для числа n - akk! можно повторить те же самые рассуждения.

21.35. Предположим, что требуемое равенство имеет место. Домножив n!p обе части равенства на n!, получим равенство вида = nX + xn, где X q n!p целое число. Таким образом, целое число и xn остаток от делеq n!p ния этого числа на n. Отметим, что если число целое и m > n, то число q m!p делится на m, поэтому xm = 0. Ясно также, что если число n достаq точно велико, то n! делится на q. Таким образом, числа n и xn определены однозначно. Аналогично получаем, что xn-1 это остаток от деления числа 1 n!p - xn на n - 1 и т.д. В конце остаётся целое число x1.

n q Глава 22.

Графы Графом называют набор точек (называемых вершинами графа), некоторые из которых соединены рёбрами. При этом нас интересует только то, какие именно пары точек соединены рёбрами. Многие задачи естественно формулируются на языке графов.

Граф называют связным, если для любых его вершин v и v найдётся последовательность вершин v1 = v, v2, v3,..., vn = v, в которой любые две соседние вершины vi и vi+1 соединены ребром.

Циклом называют последовательность рёбер v1v2, v2v3,..., vn-1vn, vnv1 (n 3).

22.1. Докажите, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. (Иными словами, в любом графе с шестью вершинами есть либо три вершины, попарно соединённые рёбрами, либо три вершины, попарно не соединённые рёбрами.) 22.2. Докажите, что в любом графе число вершин, из которых выходит нечётное число рёбер, чётно.

22.3. Дан отрезок OA. Из конца отрезка A выходит 5 отрезков AB1, AB2, AB3, AB4, AB5. Из каждой точки Bi могут выходить ещё пять новых отрезков, или ни одного нового отрезка и т.д. Может ли число свободных концов построенных отрезков равняться 1001 22.4. а) Докажите, что граф, в котором из каждой вершины выходит чётное число рёбер, можно представить в виде объединения непересекающихся циклов.

б) Докажите, что граф, в котором количество вершин, из которых выходит нечётное число рёбер, равно 2n, можно представить в виде объ244 Глава 22. Графы единения непересекающихся циклов и n несамопересекающихся путей, идущих по рёбрам.

22.1. Обходы графов Назовём обходом графа путь, идущий по рёбрам графа и проходящий по каждому ребру ровно один раз.

22.5. Докажите, что если обход графа существует, то количество вершин, из которых выходит нечётное число рёбер, не превосходит двух.

(Эйлер) 22.6. Докажите, что если граф связен и количество вершин, из которых выходит нечётное число рёбер, не превосходит двух, то существует обход этого графа. (Эйлер) 22.2. Ориентированные графы Граф называют ориентированным, если на каждом его ребре указано направление движения, т.е. ребро выходит из одной вершины и входит в другую.

22.7. Докажите, что любой связный граф с чётным числом рёбер можно ориентировать так, что из каждой вершины будет выходить чётное число рёбер.

22.3. Паросочетания Паросочетанием называют набор рёбер графа, не имеющих общих вершин. Паросочетание называют максимальным, если в него входит наибольшее возможное число рёбер (т.е. любое паросочетание для данного графа содержит не больше рёбер, чем максимальное паросочетание).

22.8. Докажите, что паросочетание максимально тогда и только тогда, когда в графе нет пути, который идёт по рёбрам графа и обладает следующими свойствами: 1) из любых двух соседних рёбер пути одно принадлежит паросочетанию, а другое не принадлежит; 2) из начальной и конечной точек пути не выходят рёбра паросочетания; 3) начало и конец разные вершины. (Берж) Глава 22. Графы 22.9. Пусть вершины графа разбиты на два непересекающихся множества X и Y, причём все рёбра соединяют вершины из разных множеств. Докажите, что паросочетание, включающее все вершины множества X, существует тогда и только тогда, когда для любого набора выделенных вершин из множества X количество вершин, соединённых с выделенными вершинами, не меньше количества выделенных вершин.

(Холл) 22.10. На танцы пришло несколько юношей и несколько девушек, причём каждая девушка знакома ровно с k юношами и каждый юноша знаком ровно с k девушками, причём k 1. Докажите, что они могут разбиться на пары так, что в каждой паре будут юноша и девушка, знакомые друг с другом.

Решения 22.1. Пусть v произвольная вершина графа с шестью вершинами. Среди оставшихся пяти вершин есть либо три вершины, соединённые рёбрами с v, либо три вершины, не соединённые рёбрами с v. Пусть v1, v2, v3 вершины, соединённые рёбрами с v. Если вершины v1, v2, v3 попарно не соединены рёбрами друг с другом, то они образуют искомую тройку вершин. Если какието две из вершин v1, v2, v3 соединены ребром, то вместе с вершиной v они образуют искомую тройку. Для вершин v1, v2, v3, не соединённых рёбрами с вершиной v, рассуждения аналогичны.

22.2. Вычислим двумя способами количество пар, состоящих из ребра и одного из его концов. С одной стороны, это количество равно удвоенному числу рёбер; в частности, оно чётно. С другой стороны, оно равно сумме чисел рёбер, выходящих из всех вершин. Эта сумма чётна, поэтому в неё входит чётное число нечётных слагаемых. А нечётные слагаемые соответствуют как раз тем вершинам, из которых выходит нечётное число рёбер.

22.3. О т в е т: да, может. При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно 4k + 1. При k = получаем нужное число свободных концов.

22.4. а) Применим индукцию по числу рёбер графа. Для графа с двумя рёбрами утверждение очевидно. Возьмём теперь произвольный граф и будем идти по его рёбрам, выйдя из некоторой вершины и не проходя дважды по одному и тому же ребру. Из каждой вершины выходит чётное число рёбер, поэтому мы можем продолжать обход до тех пор, пока не попадём в вершину, в которой уже побывали (эта вершина не обязательно та, из которой мы 246 Глава 22. Графы вышли). В результате получится некоторый цикл. Выбросив все рёбра, входящие в этот цикл, мы получим граф с меньшим числом рёбер, в котором снова из каждой вершины выходит чётное число рёбер. По предположению индукции этот граф можно разбить на непересекающиеся циклы.

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

22.5. Из каждой вершины графа, отличной от начала или конца обхода, выходит чётное число рёбер.

22.6. Согласно задаче 22.4 данный граф можно представить в виде объединения непересекающихся циклов и, возможно, одного несамопересекающегося пути. Если граф состоит только из несамопересекающегося пути или только из цикла, то всё ясно. Если есть несамопересекающийся путь, то возьмём его, а если несамопересекающегося пути нет, то возьмём произвольный цикл. Предположим, что помимо выбранного пути (цикла) есть ещё какие-то дополнительные циклы. Из связности графа следует, что есть дополнительный цикл, одна из вершин которого лежит на несамопересекающемся пути (выбранном цикле). Если выбросить этот дополнительный цикл, то получится граф, для которого обход существует по предположению индукции. Поэтому можно поступить следующим образом. Будем обходить полученный граф до тех пор, пока не дойдём до вершины, принадлежащей дополнительному циклу. После этого совершим обход дополнительного цикла, а затем продолжим обход полученного графа. В результате получим обход исходного графа.

22.7. Сначала ориентируем граф произвольно. Рассмотрим все вершины, из которых выходит нечётное число рёбер. Их число чётно. Действительно, сумма чисел рёбер, выходящих из всех вершин, равна числу рёбер, поэтому она чётна. Таким образом, если есть хотя бы одна вершина v1, из которой выходит нечётное число рёбер, то есть ещё хотя бы одна такая же вершина v2.

Пользуясь связностью, соединим их набором рёбер. Среди всех таких наборов возьмём тот, в котором число рёбер наименьшее (тогда в нём не будет циклов). Изменим ориентации всех рёбер этого набора на противоположные, а ориентации всех остальных рёбер оставим без изменений. После такой операции из вершин v1 и v2 будет выходить чётное число рёбер, а из всех остальных вершин будет выходить столько же рёбер, сколько и раньше. Несколькими такими операциями мы уничтожим все вершины, из которых выходит нечётное число рёбер.

22.8. Предположим сначала, что в графе есть путь, обладающий указанными свойствами. Из начальной и конечной точек этого пути выходят рёбра, не принадлежащие паросочетанию, поэтому путь состоит из нечётного числа рёбер v1v2, v2v3,..., v2n-1v2n. Построим новое паросочетание, выбросив рёбра Глава 22. Графы v2v3, v4v5,... и добавив рёбра v1v2, v3v4,... (Это можно сделать, потому что из вершин v1 и v2n по условию не выходят рёбра паросочетания.) Новое паросочетание содержит на одно ребро больше, чем старое, что противоречит максимальности.

Предположим теперь, что есть два паросочетания M и M, причём M содержит больше рёбер, чем M. Построим для паросочетания M путь, обладающий требуемыми свойствами. Рассмотрим только те рёбра, которые входят ровно в одно из паросочетаний M и M. Любой путь, идущий по таким рёбрам, обладает свойством 1), поскольку если из какой-то вершины выходят два из рассматриваемых рёбер, то одно из них принадлежит M, а другое принадлежит M и не принадлежит M. Рассмотрим все пути, которые максимальны в том смысле, что их нельзя увеличить. Среди них обязательно найдётся путь, у которого рёбер паросочетания M больше, чем рёбер паросочетания M; это следует из того, что паросочетание M содержит больше рёбер, чем M. Этот путь, очевидно, обладает свойством 3). Легко убедиться, что он обладает и свойством 2). Действительно, пусть v конец или начало этого пути. Из v выходит ребро паросочетания M. Из максимальности пути следует, что из v не выходит ребра, которое принадлежит M и не принадлежит M. Но ребро, которое одновременно принадлежит M и M, тоже не может выходить из v, потому что из v не могут выходить два ребра паросочетания M.

22.9. В одну сторону утверждение очевидно: если паросочетание существует, то количество вершин из множества Y, соединённых с выделенными вершинами даже только рёбрами паросочетания, уже равно количеству выделенных вершин.

Предположим теперь, что указанное условие выполняется, но нужного паросочетания не существует. Чтобы прийти к противоречию, возьмём максимальное паросочетание M. По предположению в X есть вершина x, из которой не выходит рёбер паросочетания M. Рассмотрим все пути, идущие из вершины x, рёбра которых поочерёдно то лежат в M, то не лежат. Пусть X и Y множества концов этих путей, лежащих в X и Y. Согласно зада че 22.8 из максимальности M следует, что из каждой вершины множества Y выходит ребро паросочетания M; очевидно также, что из каждой вершины множества X, кроме вершины x, выходит ребро паросочетания M. Пусть X это множество X без вершины x.

Pages:     | 1 |   ...   | 28 | 29 || 31 | 32 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.