Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 159
Текст из файла (страница 159)
Теперь, Ао +~ ~/(Ао лА ) =1 ~=1 тогда и только тогда, когда существует т, так что Ас" = 1 и А, = 1. Но, по индуктивному предположению, это имеет место тогда и только тогда, когда существует Й-путь из з в ги и 1-путь из ти в зч Последнее утверждение истинно тогда и только тогда, когда существует )с+ 1-путь из з в зч 27. Путь из вершины и, в вершину о, существует тогда и только тогда, когда существует )с-путь из о, в о, для некоторого 1 < )с < т, т.е. тогда и только тогда, когда Ас'ь = 1 для некоторого 1 < и < ги, или тогда и только тогда, когда А„ = 1.
29. Если дерево ТЯ, Е) не является ориентированным, то транзитивным замыканием является )г х 1'. Если Т(Ъ', Е) — ориентированное дерево, то аВ6, если а — предок 6. в) 2; г) 4. 111 110 100 101 001 000 111 110 100 101 001 111111 111110 111100 110111 110110 110100 100111 100110 100100 101111 101110 101100 001111 001110 001100 111101 110101 100101 101101 001101 111001 111000 110001 110000 100001 100000 101001 101000 001001 001000 9. Поскольку ги = 2', первые т цифр вершин в каждом столбце образуют код Грея для т. Следовательно, первые т цифр первой вершины и последней вершины в столбце отличаются ровно одной цифрой. Последние и цифр вершин в каждом столбце совпадают.
Следовательно, первая и последняя вершины в столбце отличаются ровно одной цифрой, поэтому они являются смежными. Поскольку и = 2', последние и цифр вершин в каждой Раздел б.7. 1. а) 1; 3. 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 О 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 О 0 1 0 0 О 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 б) 2; 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 О 1 1 0 0 0 1 1 1 0 0 1 1 1 1 890 Ответы к упражнениям строке образуют код Грея для п. Таким образом, последние п цифр первой вершины и последней вершины в строке отличаются ровно одной цифрой. Первые т цифр вершин в каждой строке совпадают. Вполне очевидно, что первая и последняя вершины в строке отличаются ровно одной цифрой, поэтому они являются смежными.
Раздел 7.1. 1. 1, 2, 3, 4, 5, 6, 7, 8, 9, 1О, П, 12, !3, 14, 15, 16, !7, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, !01, 102, !03, 104, 105, 106, !07, 108, 109, 110, 111, 112, ПЗ, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, !27, 128, 129, 130, !31, 132, 1ЗЗ, 134, 135, 136, 137, 138, !39, 140, 141, 142, 143, 144, !45, 146, 147, 148, !49, 150, !51, 152, 153, 154, 155, 156, !57, 158, 159, 160, 161, 162, 163, 164, 165, !66, !67, 168, 169, 170, 171, 172, !73, 174, 175, 176, 177, 178, !79, 180, !81, !82, 183, 184, 185, 186, 187, 188, 189, 190, !91, 192, 193, 194, 195, 196, !97, 198, !99, 200.
3. 37 13. 5. 37 47. 7. 47 63. Раздел 7.2. 1. 32з = 45з — 1001, поэтому 1001 не является простым числом, 3. 70з — 7а = 4851, поэтому 4851 не является простым числом. 5. 90э — 7з = 8051, поэтому 8051 не является простым числом, 7. 90з — 13э = 7931, поэтому 7931 не является простым числом. Раздел 7.3. 1. а) 75=8х9Ч-3; б) 102=5х20+3; в) 81=9х9+О; г) 16=25хО+16.
3. а) 75; 6) 54; в) 11799; г) 271377; д) 179196. 5. Если ах+ Ьу = НОД(а,Ь), то д юх+ йод у = 1. Любой делитель чисел х и у должен также делить 1. Поэтому числа х и у — взаимно простые. 7. Процедура Алгоритм деления (а, Ь): Положить о = 0 и т = а; Условный цикл.' до тек пор, пока т > Ь, Положить а = а+ 1 и т = т — Ь; Конец условного цикла; Конец процедуры. 9. Допустим, что существуют такие т и з, что та = а и НОД(т,з) = Ь. Тогда т = иЬ и з = иЬ, поскольку НОД(т,з) делит как т, так и з.
Таким образом, а = иьиЬ = иибз и Ьз ] а. Обратно, если Ь ] а, то иЬ = а для некоторого целого и. Положим т = иЬ и з = Ь. Тогда та =а и НОД(т,з) =Ь. 11. НОД(а,Ь) = ах Ч- Ьу = а(х — Ь) + Ь(х + а). 13. (п НОД(а,Ь)) ] па и (п НОД(а,Ь)) ] пЬ. Таким образом, (и НОД(а,Ь)) ] НОД(па,пЬ). п НОД(а, Ь) = п(иа+ иЬ) при некоторых целых а и Ь. НОД(па, пЬ) ] пиа и НОД(па, пЬ) ] пиЬ. Таким образом, НОД(па,пЬ) ] п(иа+ иЬ), так что НОД(па,пЬ) ] п НОД(а,Ь) и НОД(па, пЬ) = п НОД(а, Ь).
Раздел 7.4. 1. а) ]3;2,1,3], ]3;2,1,2,1]; 6) ]О; 20, 1, 8, 1, 1, 2], ]О; 20, 1, 8, 1, 1, Ц; в) [ — 1;1,6,1,3,1,5,1,1,1,2], ]-1;1,6,1,3,1,5,1,1,1,1,1],' Ответы к упражнениям 891 г) ]О; 3, 2, 1, 3], ]О; 3, 2, 1, 2, 1]; 3.
а) ]2;4,4,4,4,4,2 Ч- ч'5]; в) ]3; 7, 15, 1,292, 1, 1.736...]; д) ] — 1; 1, 7, 1, 4], ] — 1; 1, 7, 1, 3, 11. 6) ]1; 2, 2, 2, 2, 2, 1 + ъГ2]; ) ]1:1,1,1,1,1, — ",~]. Раздел 7.5. в) г) 5. По теореме 7.П, Чь Чь-11ь + Чь-2 Чь-2 = ге+в Чь — 1 Ч вЂ” 1 Ч— 1 " + Чь-з ть-з Ч-— Чь-з 1 1 + гь з Ч- гь — 2 ' ' ' 7. р-з = О, ч-з — 1. Раздел 8.1. 1.
139, 233, 46. 3. а) 53 х 52 х 51 х 50 = 7027800; 6) 8 х 52 х 51 х 50 = 1060800; в) 45 х 52 х 51 х 50 = 5967000; г) 20 х 33 х 32 х 31+ ЗЗ х 32 х 31 х 30 5. 10 — 10х9х8х7=4960. 7. 2зо = 1073741824. 9. 2 х 26з + 2 х 26з = 36504. 11. а) 16; 6) 1; 13. 10э. 15. 3 17. 699 — 87 = 612. 19 26з + 26з 18252 21. 254. 23. 2 — 8 = 120. 25. 10 — 9 = 3439. 27. 26 х Збе.
= 1636800. в) 15. 1. Докзззтельство проведем индукцией. Поскольку Чо = 1, то Чо > О. Предположим, что Ч > 0 для всех т < к. Но Чь = Чь Пь+Чь з. По индуктивному предположению, Чь з и Чь з больше, чем О. По определению конечной цепной дроби, гь положительно. Поэтому Чь положительно. 3. а) 6) 892 Ответы е упражнениям Раздел В.2. 1.
120 + 110 — 80 = 150, 50, 3. 57 + 36 — 5 = 88. 5. 40 + 26 — 13 = 53. 7. 100 — 14 = 86. 9. 2 х 8! = 80640. 11. а) 11111; 6) 10000; 13. 400 Ч- 286 + 182 — 57 — 36 — 26 + 5 = 754. 15. 333 + 286 + 250 — 47 — 83 — 35 Ч- 11 = 715. 17. а) 60; 6) 120; в) 65; 19. 38212 в) 20000; г) 79,999. г) 200; д) 40. Раздел В.В. 1. а) 6720; 6) 6652800; 3. 210, 70, 120, 60. 5. 18 17 16 = 4896. 7. а) 10! = 3628800; 9.
а) 3360; 6) 8820; 11. 2880. 13. 387897600. в) 792; д) 91. г) 91; 6) 2' 5! = 3840. в) 30240; г) 36960; д) 50400. .. (",,) 17. 4. = 22394644272. Раздел В.4. 1. 21453. 3. 21534. 5. (а,с, е). 7. (2,3,4). 9. (2,3). 11. (1, 5, 6) . 13. (1,3,4,6). 15. здз, ззи,дзз,дзз, зли, зиз. 17.
(а,Ь,с,д),(а,Ь,с,е),(а,Ь,д,е),(а,с,д,е),(Ь,с,д,е). 19. 235237860. 21. 58656, включая асе "фулл хаус", или 54912, исключая асе "фулл хаус", 23. 252. 25. 210, 968. 27. 30045015. 29. 167960. 31. а Ч- 8а Ь и- 28а Ь + 56азЬ и- 70а Ь + 56а Ь + 28а Ь + 8аЬ + Ьз. 33. -8646663168. 35. -262440. Ответы к упражнениям 893 Раздел 8.8. а) 36' 6) зб В) 36' 36 ' г) 36 ) 129. ЗО1 ' Г) 36. 22 3. а) Я; 39ОЩ.
11. а) 2596966 А422; 2 98960' и 345 Вб1 ' Раздел 8.8. 81 1. —. 4!2!' 6! 3. — '. 31 26! 5. — ' 8!6!9!3! 35! 7!7!7!7! 24! 9. — ' . ' !4!)' 12' 11 . 263з 31933440 3!6!3! 13. †' 2 455 . 45З 4!5!6!3! !5 ' 42245з 2217600000 Раздел 8.7. 16! 1. — = 1820. 4! 12! 12! 3.
— ' = 220. 9!31 14! 5. — = 1001. 4! 10! 12! 7. — '=66. 2! 10! 54912 б) щббз 5148 2598960' 36 2598960 ' 9216 2598960' 19. абсде7дН1)Ытппордгя!иитсхуз, зухитиитягдроптп!!4215д7едсЬа. 21. 1абсде), 1иитхуз). 23. Цикл пот от 1 до С!п,т): Использовать процедуру Сочетание (33.Г) для образования 1-го т-сочетания из п элементов; Использовать процедуру Обобщенная перестановка, чтобы упорядочить все перестановки из г элементов, образованных процедурой Сочетание (95.Г); Конец цикла. 894 Ответы к упражнениям 9.
— ' — 40 = 415. 15! 33! !12! 16. 11. — = 560. ' 3П3! Раздел 8.3. 1. 21. 3. Если у одного человека 29 взаимных друзей, то каждый имеет 29 взаимных друзей. Если это не так, то количество взаимных друзей, которое люди могут иметь, изменяется от 0 до 28, поэтому существует 29 возможностей. Но в компании имеется 30 человек, поэтому, по крайней мере, 2 человека должны иметь одинаковое количество взаимных друзей. 5. 51.
7. 25. 9. Пусть аыаз,аз,...,а„— последовательность из и положительных целых чисел. Пусть з1 =ам за =а1+аз, аз =аг+аз+аз, ..., з„=аг+аз+аз+ . +а„. Каждое з, эквивалентно г; по модулю и, где 0 < г, < и — 1. Если какое-либо из г; равно О, то з; делится на и, и доказательство завершено. Если нет, то существует и — 1 значений для г; и п штук г,. Следовательно, два из г„например, г, и гь, должны иметь одно и то же значение. Предположим, что у < /с, тогда аз ю ч-а,ее+. + аь делится на и. 11.
26 + 1. 13. 11. 15. ~ 1-13. 17. Рассмотрим пары чисел (1,2), (3,4),(5,6),... (2п — 1,2п). Имеется п пар чисел, поэтому если у нас п+ 1 чисел, то два должны принадлежать одной и той же паре. Эти два числа отличаются на 1. 19. Поскольку О+ 1+ 2+ 3+ + и — 1 = п(п — 1)/2, существует только и — 1 различных целых чисел, сумма которых меньше, чем п(п — 1)/2. Поэтому т является суммой не более п — 1 различных целых чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
