Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 75
Текст из файла (страница 75)
Каждый набор (гы г, ..., гя), при котором система имеет решения, однозначно определяет некоторый вектор !У Е В". Отсюда (п -Н 1) ) 2". Верхняя оценка для числа векторов в базисной системе может быть получена из того, что система р(Й„В) = г„является системой линейных уравнений с п неизвестными. б) Нижняя оценка вытекает из задачи 1) и оценки числа возрастающих цепей длины п — 1, верхняя из задачи 4). 72" ' з — 1т 3.8.
! „1 !. Указание. См. гл., задачу 1.11. 3.10. 1) Рассмотреть В„" (Н). 2) Например, А = !Н; Н Е В", ОНО четное). 3.11. Инду кция по п. При п = 1 последовательность (0), (1) образует требуемый цикл в В . Пусть Нв, Ны ..., Нз 1 является циклом в В". Если а "- набор в В", то обозначим через ои набор из В"г', полученный приписыванием символа и Е 10, 1) справа к набору а.
Тогда последовательность авО, НгО, ..., Н зО., Н з1, ..., Нз1, ае1 является циклом в В" +1. 3.12. 1), а), в), д), ж), з) Векторы а являются п-универсальными, в остальных случаях нет. 3.13. 1) Ц2) = 4, ЦЗ) = 6, 1(4) = 8. 3.14. 1) Нижняя оценка. Пусть а = (101.. 0), Д = (О!... Ц, М = = (7 Е В„": Осг Ю 70 = 1), Аз = (Н) О М, Аз = (7)) 1З М. Ясно, что р(п) > > )А~ (и)( = (Аз(и)! = и. 2) Нижняя оценка. Пусть А = 1(ом ..., оы) Е В": сзз = 1). Ясно, что р''1и) > ~А~ = 2" Верхняя оценка.
Если ОВГЗ Я ) 1 для любых Н, ~9 Е А С В", то А не содержит противоположных наборов. Положив А = 16: Н Е А), имеем А О А С В', А О А = О. Отсюда ~А~ (2" 3.16. !П.Л. К!ейшап.) Пусть 1(п, гп, й) чисао троек Я, 71, у) таких, что НЕВв",ОА, ДЕВ~', 7ЕВ,'„'+я и НО!7=7, НГ1)з=О. Тогда "-("."") ='<™') - '(© -"И"-') '((.
"") — -") ('"'.") Отсюда вытекает требуемое неравенство. 3.17. 1) Шары радиуса ! с центрами в кодовых словах не пересекаются тогда и только тогда, когда расстояние между двумя кодовыми словами не меньше 21-Е 1. 3.18. Ц 3. 2) 4. 3) 3. 4) 4. 5) 4. 3.19. Указание. Использовать задачу 3.17. 3.20. 1) Обнаруживает одну ошибку и исправляет ноль ошибок. 2)п — 1и [ ~. 3) — — 1 и 4) Обнаруживает одну ошибку при четных п и ноль ошибок при нечетных и,.
исправляет ноль ошибок. 3.21. 1) 100110. 2) 110011. 3) 0011001. 4) 1010101. 5) 111001011011. б) 0010110001111. 7) 1110000110011. 8) 000011110111011. зоо Гл. 711. Элементы теории кодирования 3.22. 1) 1. 2) 110. 3) 110. 4) 0011. 5) 0101. 6) 1101. 7) 0011. 8) 0111110. 9) 110110100. 10) П110111101. 3.24. 1) д(х ) = хг(хзхзхех - Ч хзхзхлхз). 2) д(х ) = хз(хлхо(хьх3з о хзхз) о х1хзхлхз). 3.25.
1) Вообще говоря, нет. 2) Ла. 3) Вообгце говоря, нет. 3.26. Пусть С = ((оз...о„) Е С: о1 ОЗ...о„= о). Тогда Со и Се являются кодами, обнаруживающими одну ошибку, и шах(~Со~, ~С1() > ~С~/2. 3.34. Пусть С С В" — - код с расстоянием д+ 1 и о Е В". Положим Сн = (7 Е В": 7 = В Ю В, В Е С). Тогда, если С является (и, д)-кодом и р(Й, В) ~ (д, то С- П Сд = О. Отсюда вытекает требуемое неравенство. 3.35. Утверждение вытехает из задачи 3.34 и из того, что р(В, )7) < д для любых вершин В, В из (д — Ц-мерной грани куба В".
3.36. Неравенство следует из задачи 3.35 при С = В". 3.38. 2" 3.39. Не существует. Имеем (Я(л~(Й)! = 148 при всех Й Е Выз. Но 148 не является степенью двойки, что противоречит задаче 3.27. 3.41. Пусть в некотором зквидистантном (и, 24 -Е 1)-коде С содержатся три вершины Н, Д, 7. Без ограничения общности можно считать, что В = О. Тогда (Щ = )Я = 24-~-1, а значит, р(В, 7) четное число, что противоречит условию. 3.42. Разобьем ц координат на блоки величины ф2. Каждому блоку сопоставим набор, в котором единицы стоят в координатах, содержащихся в данном блоке.
Полученное множество наборов образует зквидистантный (и, д)-код мощности (2н)Й). 3.44. Указание. Использовать задачу 3.33, 5). 3.45. 1) Пусть С --. максимальный (и, й, 24)-код. 'Гогда подмножество С10 = СПВ,"л является (н — 1, й — 1, 24)-кодом. Число пар (з, В), где 1 < 1 < ц, )1 Е Сбц не превосходит н. т(и — 1, й — 1, 24).
С другой стороны, для каждого набора В Е С существует ровно й таких пар. Отсюда й т(п, й, 24) < н т(п — 1, й — 1, 24). С учетом того, что т(н, й, 24)— целое число, получаем требуемое неравенство. 2) Вытекает (применить индукцию) из задачи 1) с учетом того., что т(п. — й 1- д — 1, д — 1, 24) = 1. 4.2. 1) а), в), г) Нет. 6), д), е) Лз..
2) а) (000, 111) О А. 6) Вз*'. в), г) Вз. д) А О (0000, 0010, 1101, 1111), е) А О (0000, 0001, 1010, 1110). 3) а) (10Ц. 6) (100). в), г) О. д) (1001). е) (1010). 4.7. 1) а) в) 2. г) 1, д) ж) 4. (ооп) . (10100) „(10001) 2) а) Н=(11). 6) Н" (ШО1' в) Н* ~01000]' г) Н* (ШОО~' 0101010 1001100 шоооо~ 0001111 4.11. 4(С(М)) = 7. 24 Г. П. Гаврилов, А. А. Сапоженко 370 Ответы, указания, решеннв Глава У111 1.1.
Ц (20)з. Билеты неравноценны. Первый билет можно распределить 20-ю способами, второй 19-ю, третий — 18-ю. 2) 20'. 3) С(20,. 3). 1.2. Ц 9!. 2) С(9, 3) С(6, 3). Первую шеренгу можно выбрать С(9, 3) способами, после чего вторую С(6, 3) способами.
Пользуясь правилом произведения, получаем результат. 1.3. Ц Каждый из членов перестановки с повторениями можно выбрать независимо от других и способами. С использованием правила произведения получаем, что Р(и, т) = и". 2) Из каждого (и, т)-сочетания без повторений путем перестановок можно получить т) различных (и, т)-перестановок, причем каждая (и, т)- перестановка может быть получена таким способом. Отсюда т! С(и, т) = = Р(и, т).
Поскольку (см. пример 3) Р(и, т) = (п)„то С(и, т) = (и),)т! = = (".) 3) Каждому (из т)-сочетанию А с повторениями, составленному из элементов множества С = (ам..., а„), поставим в соотвотствие вектор а(А) длины и + т — 1 из т единиц и и — 1 нулей такой, что число нулей, находюцихся между (1 — Ц-й и 1-й единицами, равно числу элементов а„входяздих в сочетание А (1 = 2, ..., и), а число нулей, стоящих перед первой единицей (после (и — Ц-й единицы), равно числу элементов ае (соответственно элементов а„),входяппзх в сочетание А. Это соответствие между сочетаниями и векторами взаимно однозначно. С другой стороны, число векторов с и — 1 единицами и т нулями равно С(и + т — 1,и.
— Ц, поскольку каждому такому вектору можно взаимно однозначно сопоставить сочетание из и+ т — 1 элементов по и — 1. Отсюда с учетом результата предыдущей задачи получаем, что С(и, т) = ) витт — 11 и — 1 14 Цй" 2)йл.йз... й» 3) ( ). 1.6. Ц 2 ". 2) (2'")„. 1.6. ( т ) (, ) . Применяется правило произведения. 1 7 Ц (Л) ( Л )(и — а — )У),-.л-л. 1.8. Ц 4(и — 4). Масть карт можно выбрать четырьмя способами, после чего наименьший номер карты можно выбрать и — 4 способами. 2) 4и(и — Ц. Выбрать номер четырех карт можно и способами, после чего оствшуюся карту можно выбрать 4(тл — Ц способами. 3) 24и(и — Ц.
4) 4(б). в) 4з(и — 4). 6) 4и( 2 ). 7) 12и(2) -т 4из( ). 1.9. 2) 147. 2) 26. Число случаев выпацения одинаковых граней равно 6, число е'61 способов выпадения попарно различных граней равно (3) = 20. 3) 300 -т 300з -'г 300з. Гл. )г111. Элементы комбинаторики 371 1.10. Ц (,—,) 2) (", '). 3) -'(и2 ) + 2(Г 2 )) (и — (гп — Ц 4 1) 2) (п 4 9) 3) (и-»-й) 1.12. Ц (1+ гг!)(1+ аз)... (1+ г! ). Каждому делителю ро'...р!» (О < 1», < а„! = 1, ..., г) можно взаимно однозначно сопоставить вектор (»»! ., »9,). Лалео см. задачу 1.4, 2) 2) 2".
Каждому делителю р! ! ...р"„'" числа п., не делящемуся на квадрат, можно сопоставить двоичный вектор (»»г, ..., »»,). 3) П(".' '- и -Ц ' ь=! Указание. Заметить, что после раскрытия скобок в выражении (1 + р! 4-... т р, ' )... (1 -»- р, -и... 4- р„" ) каждый делитель присутствует в качестве слагаемого суммы ровно один раз.
Пругое доказательст во. Число („) равно числу спогибов выбора й-элементного подмножества из 5» = (ог, ..., е„). Но каждому )г-элементному подмножеству взаимно однозначно соответствует его дополнение в с», являющееся (и — й)-элементным множеством. 1.15. Ц Решение. Положим гг„! = ~ 1. Пусть уже определены ~(п — Ц!3 коэффициенты а„г, а„з, ..., гг„,.
Тогда т — а„г(п — Ц! — а„з(п — 2)! —... — гг,(п — !)»~ — » г!»вЂ” (и — ! — Ц! Единственность представления докажем от противного. Пусть некоторому т соответствуют два вектора: а(гп) = (аг, ..., аи !) и»э(т) = = (»3», ..., »! — !). Пусть 1 наибольший из номеров разрядов, в которых векторы различаются. Без ограничения общности можно считать, что а! <»3». Имеем — ! — ! ! †! ! †! 0 = ~г»3,г! — ~ гг,г! > (»1! — а )12 — ~ ~а,гг > »2! — ~ ~! ° »2! > О. =! =! =! =! Пришли к противоречию. 2) Н(4) = (О, 2), а(15) = (1, 1, 2), а(37) = (1, О, 2, Ц. 3)р(0,2,0,4)=100, р(0,2,Ц=10, р(1,2.,3,2)=71.
4) о(2!3,1,4) =8, и(3,5,2, 1,4) =68, о(1!3,3,5,2) =9. 5) Пусть задано число т. Представим его в виде гп = а! 1! + а!. 2! +... ... -»- а »(п — Ц), где а, < 1, 1 < г. '< п. Построение искомой подстановки я равносильно гюстроению вектора (»г(Ц, »г(2), ..., к(п)), Координаты к(1) зададим по индукции. Положим »г(Ц = а„! -~- 1. Если координаты к(Ц, ..., к(1' — Ц определены, то положим к(1) = а„. + 1+ з(1), где е(1') число тех к(Й), 1 < Й < 1', для которых к(Й) < к(1).
б)яг=(2,1,4,3), »г»з=(4,1,2,3), гг»з=(2,1,5,3,4). 1.16. Ц Координаты вектора»3(т) = (»1», ..., Щ,) определяютгя следующим образом: »3! —. наибольшее целое такое, что т > ( 5 ). Если / »3! '! 24* 372 Ответы, указания, решеннв Д, ..., с3, уже определены, то Д; 1 --. наибольшее целое такое, что т — ( „1) — ( Я ) —... — („1 ) > ( *э(). Единственность доказывается так же, как и в задаче 1.15, Ц. 2) а) )3(19) = (6, 4, 1, 0), так как ( ) + ( ) + ( ) + ( ). б) су(25) = (6, 3, 2). в) Д(32) = (6, 5,.
4, Ц . 3) а) т = 18, так как т = ( ) + ( ) + ( ) = 23. б) т=13, в) т=10. 4) Сопоставим вектору Н = (аы ..., ав) из Во сначала вектор С) = = (Сум ..., Д.), в котором )3 + 1 является номером координаты (й — 1 + Ц-й слева единицы в наборе о, 1 (1 ( й. После этого полагаем и(Н) = д(/3) + 1. Например, если Н = (1, О, О, 1, 0), то /8 = (3, 0), ц(Н) = д(/э) + 1 = ( ) + (о) 1.17. При и = 1 равенство (Ц проверяется непосредственно. Пусть равенство доказано для некоторого п ) 1. Имеем Е("~')" = Е (©'(."- ))'ь =Е(".)'"'Е(."- )'" = = ~ ©сь ~- ~- ('й)ся" = (1 -~ с)" -~ с(1 ~ с). = (1 ~ с)-". ь — — о ь=о 1.18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
