Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 82
Текст из файла (страница 82)
П. Гаврилов, А. А. Сапоженко 402 Ответы, указания, решения 6 21 1) Р(ггг ) = (З) (т)з/((2)) 6.22. ( ).2 628. ( )((з)и " )((,'„)) Глава 1Х 1.2. 1) Если множество (гг,..., гь) зафиксировано, то число граней В","; " равно числу двоичных наборов (егг... тг), т.е. равно 2 . 2) Если Н б В",'"„' „' " Ез В„",*"„",„* 'г, то аг = гг, ..., гтя = тя, а следовательно, грани совпадагот. Приходим к противоречию.
3) Вытекает из задач 1) и 2) с учетом того, что В",""'„'"' = 2' /и1 4) Число способов выбора направления (гг, ..., гь) равно (й). Теперь утверждение следует из задачи 1). б) Следует из задачи 4). 6) Если Н б В","';,*", то вектор (ггг...ггг) однозначно определяется вектором Н и множеством (гг, ..., гя), Последнее можно выбрать ( ) способами. 7) Код грани О размерности и, содержащей заданную грань Н размерности 1,получается из кода грани Н расстановкой Й вЂ” 1 прочерков среди и — 1 координат, имеющих значение 0 или 1.
8) Лля символов ег и гЗ из множества (О, 1, —.) введем операцию полагая: и 11 = ог если ег = 17; ег В = гг (сг гиз = )г), если о б (О, 1); (соответственно если г8 б (О, 1), о = —.-), значение ег )1 неопределенно, если о ~ )г и щ Д б (О, 1). Естественным образом операция распространяется на векторы из О".
Нетрудно убедиться в том, что если Н и В -- коды граней Е и Н, то вектор Н,9 определен тогда и только тогда, когда Е С Н ф Я. В последнем случае Н 3 является кодом грани, совпадающей с Р С Н. 9) Вытекает из задачи 7). 1.4. Положим 1, = и — и,. Тогда числа 1, удовлетворяют неравенству Макмиллана <з 2 ' < 1. Поэтому существует префиксныи двоичныи 1« . код с длинами кодовых слов 1г, ..., 1,. Пополним каждое кодовое слово ю, длины 1, прочерками в количестве и — 1,. Тогда каждое из так полученных слон ю, можно рассматривать как код грани размерности и — 1, = и,. То, что грани попарно не пересекаются, следует из префиксности кода. 1.5. 1) Рассмотрим множество всех интервалов Ли, В) таких, что Н б Вги~зр )г б В„" Ог7зр ЛлЯ каждой из () ) )) веРшин ег б В~"„7з~ сУществУет ( ~„7 ) ) веРшин В б В„г„гз~ таких, что о < В.
Таким обРазом, / и — )гг/3) 'г число пар (Л, ег) указанного вида, а значит, и число интервалов Ца, г8) рав- Ря. 1Х. Минимизация бувевь х функций п 1 'п — Ги,»31» но () ) )) ( ~ ) ) ). Нетрудно видеть, что все они попарно несравнимы. 2) Аналогично задаче 5.19.1 из гл. П. 1.6. Ц 2. 2) 3. 3) 2. 4) 3. 5) 2. 6) 3. 1.7. Ц 2. 2) 4. 3) 3. 4) 3.
5) 2. 6) 3. 1.8. Ц 2. 2) 1. 3) 1. 4) 2. 5) 5. 6) 4. 1.9. Ц 2. 2) 1. 3) 3. 4) 5. 5) 5. 6) 4. 1.10. 2) Рассмотреть матрицу вила»Р»-»1 — »вЦ, где Р»» . матрица размерности Гп — к+ Ц х Гк — Ц, состоящая сплошь из единиц, а 1„»э» единичная матрица размерности»п — Ге + Ц х»п — й + Ц. 1.11. Пусть А множество векторов»базисных) линейного»п, 1)-кода. Тогда ~А~ = й и А покрытие.
Последнее вытекает из следующих соображений. Пусть утй столбец имеет единицу в»-й координате. Поскольку »-я строка является линейной комбинацией базисных строк, то существует базисный вектор, имеющий единицу в блм разряде. 1.12*. Ц Пусть Л» — семейство всех Ге-элементных подмножеств строк матрицы М. Лля Р 6 Н» обозначим через н»Р) множество столбцов, не покрытых строками из Р, и пусть й» = (в) ~ иГР) среднее число ген» непокрытых вершин по подмножествам Р из й».. Пусть»' — множество столбцов матрицы М, а рГи) число тех Р из Л», которые не покрывают столбец и, а пГ»») число строк, .покрывающих столбец и. Тогда й»=( ) ~р»и)=(„) ~(™ )< <и( )ГГ( ) <п(1 — — ) <пе Лля всякого натурального Й имеем 6(М) ( Й+ р». Поэтому, полагая Й = 1»п вп Г т еви = ] — 1п — ~, получаем СГМ) < 1 ~- — 1п —.
в в и» 2) Пусть 6» доля тех столбцов матрицы М, которые остались непокрытыми после 1-го шага градиентной процедуры. Ясно, что 6о = 1. Покажем, что Г»»6». — 6»в») ) в»6»в)Г»». Неравенство равносильно утверждению о том, что на»л -Н Ц-м шаге можно выбрать строку, покрывающую не менее вг»6»)т столбцов. В самом деле, в каждом из п6» непокрытых столбцов содержится не менее в единиц, а число строк не превышает т. Таким образом, 6»» < 6»»1 — в/и»).
Отсюда по индукции следует, что 6» (»1 — в,»т) ( е ' д". Лля всякого натурального й имеем Ь»ЛМ) ( к+ п6». ( к+ пе ' '. Полагая к = ) — 1и ( — в) [, получавЂ.»» 1 т /ив 1 ем требуемое неравенство. 1.13*. Аналогично тому., ках в задаче 1.12, 2) доказывается, что 6» < — *» Г »» <ет»1 — е)(1 — — ) <е-';е ''. Лалее, полагая Ге=~ — 1п( — )( в 1 т /овец ГП в вп неравенстве ЛгГМ) < к+ п6»м получаем требуемое утверждение.
1.14. На первом шаге градиентной процедуры в покрытие войдет строка, покрывающая не менее п»»р столбцов, и не более п(1 — 1/р) останутся непокрытыми. Если А» множество непокрытых после к-го шага столбцов и ~А» ~ < пГ1 — 1»р)», то на Г)е -~- Ц-м шаге по крайней море одна из строк 404 Ответы, указания, решения покрывает не менее (Ая(/р столбцов. Отсюда )Агег! < (Аь((1 — 1/р) < < п(1 — 1/р)ььг. Таким образом, )Ая) < гг(1 — 1/р)". Посколыгу Ьг(Р) < < й.
+ ~Ая ~ при любом натуральном к, то, полагая ] (1п Р)/З1п(1 ') [ получаем утверждение. 1.15. — = — (1обя ( — + 1)). 1.16. Ц Множество 1г' = (Н б В': ОНО, и четное) является (и, Ц-протыкающим и )Х) = 2" . Остается показать, что б(п, Ц > 2" . В силу задачи 1.2 куб В" разбивается на 2" ' 1-мерных граней одного направления. В каждой из них должна присутствовать вершина (и, Ц-протыкающего множества. 2) Нижняя оценка очевидна. С другой стороны, гу = (О, Ц является (и, п — Ц-протыкающим. 3) (В.В.
Глаголов.) Указание. Рассмотреть гУ = (Н б В": ОЩ = : — О (шог1 3) ) ипи № = (а б Вп: н(Й) = 3 (шог1 4)). 4) (О.Б. Лупанов.) Нижняя оценка. Заметим, что, для того чтобы веригина Н = (пг, ..., гг„) содержалась в (и — 2)-мерной грани с колом у = = ('Уг, ..., '7 ), в котоРом У,, Тз б (О, Ц, нУжно, чтобы щ = У„о = У . Пусть 1г' С В" —. (и, и — 2)-протыкающее множество и ~гу~ = ти. Рассмотрим матрицу М, строками которой являются векторы из № Из предыдущего следует, что для каждой пары чисел (г, 1), 1 < г < ) < и, и любой пары (а., г), гг, т б (О, Ц, должна найтись строка й = (ог, ..., ег ) такая, что а, = и, о = т. Отсюда вытекает, что любые два столбца матрицы М попарно несравнимы.
Число попарно несравнимых двоичных наборов т г гп длины ги не превосходит...). Отсюда вытекает, что (,, )) > и. , (гп/2/) ' (иг/2 В е р х н я я о ц е н к а. Пусть т наименьшее целое такое, что (= / )) > и. Построим двоичную матрицу М с т строками и п попарно несравнимыми столбцами. Добавим к матрице две строки: 0 и 1. Тогда множество строк полученной матрицы будет (гг, и + 2)-протыкающим. ! гН б) Вытекает из того, что множество 7У = () Вггзгн является (и, й)- =в протыкающим. 6) Если гу является (и, 1)-протыкающим и С вЂ” г-мерная грань куба В", то ггг О С является (г, 1)-протыкакндим. Отсюда и из задачи 1.2, Ц вытекает требуемое неравенство.
7) Неравенство вытекает из задачи 1.12, если положить ги = 2", в = 2, п ()2 — Я 1.17. Ц 1+ 1. 2) Положим ~(Мтюг) = р„,г...г. Утверждение вытекает из того., что 1 и — 1-~-1 Г йд„ьг. г > пд„г г г г г, р„г. г целое и д„гпг ь г г г = ] 3) Ясно, что 4(М„,„цг) > 1, поскольку при любом выборе 1 векторов Нг, ..., Нг из В,", г можно подобрать вектор /3 б В,", не покрываемый ни одним из выбранных 1 векторов. Это можно сделать, выбрав по одной нулевой координате в каждом из векторов йг,..., Н„и положив их равными 1 в векторе /3. Если жс выбраны 1+ 1 векторов из В'„' г, так, что 405 Гл. 1Х. Минимизация булевых функций множества нулевых координат попарно не пересекаются, то все векторы из Вт" оказываются покрытыми. 4) Нижняя оценка вытекает из мощностных соображений: число покрыт'и1 Гттз ваемых столбцов равно (! ), а каждая строка покрывает (1) столбцов.
Верхняя оценка вытекает из задачи 1.12. 5) Верхняя оценка. Пусть и =4!! — 1)+г, 0 < г < ! — 2. Разобьем и, кттординат на ! — 1 блоков так, что два любых блока различаются по мощности не большо, чем на 1. Всего имеется г блоков мощности й+ 1, ! — 1 — г блоков мощности т!. Лля каждой пары координат произвольного из этих блоков возьмем вектор из Вл г, имеющий нули в этих координатах. Множество Р получаемых таким образом векторов имеет мощность 4+11 т( ) +1! — 1 — г)( ).
Покажем, что для каждого В из В,", т существует т3 из Р такой, что В < т3. В самом деле, поскольку число нулей в В равно 1, а число блоков равно ! — 1, то некоторый блок содержит некоторые дво нулевые координаты. В Р содержится вектор тз, имеющий нули в этих координатах. Ясно, что а < Д. 1.19. 1) 2.
2) 2. 3) 4. 4) 3. 5) 3. 6) 3. 1.20. 1) и. 2) п — 1. 3) л — 1. 4) и. 1.21. Указание. Два столбца матрицы М различаются в бнй строке тогда и только тогда, когда ф-я строка матрицы Мт ! покрывает сумму по модулю 2 этих столбцов. 1.22. Ц, 4), 5), 7) Ла. 2), 3), 6), 8), 9) Вообще говоря, нет. 1.23. Если матрица составлена менее чем из !об. л строк, то число попарно различных столбцов меньше и. 1.24. Пусть А и В тупиковые тесты матрицы М с тл строками. Тогда ни одно из включений А с В, В с А не имеет места. Отсюда вытекает, что число тестов не превосходит числа попарно несравнимых наборов в В'", а т значит,не превосходит , , )). ,~ ит!'2 1.25.
Число матриц размерности /т х и с попарно различными столбцами равно 2ь12 + 1)...12я — и+ 1). Число матриц размерности тл х п, у которых фиксированные й строк заданы, равно 2"т 1.26. 1) 11, 2), 11, 4), 12, 3), !3, 4). 2) 11, 2, 3), 11, 2, 4), 11, 3, 4). 1.27. !Э.Ш. Коспанов.) Если в матрице М с попарно различными столбцами расстояние между любыми двумя столбцами не меньше т), то в матриде Мтгт каждый столбед содержит не менее т! единиц. Теперь утверждение вытекает из задач 1.21 и 1.12. 2.1. Ц хт,хгхз. 2)хтхг. 3)хгхз, хтхгхт. 4)хт. 2.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
