Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
f(n)= α·r 1 n + β·n·r 1 n . Доказательство. В случае равных корней характеристического уравнения выражение α·r 1 n + β·r 1 n нельзя считать общим решением, так как в формуле f(n)= α·r 1 n + β·r 1 n = r 1 n · ( α+β)= δ·r 1 n останется только одна постоянная и выбрать её так, чтобы удовлетворить двум начальным f(0)=a, f(1)=b условиям, невозможно. Найдем второе решение отличное от r 1 n Если квадратное уравнение С С имеет два совпадающих корня r 1 = r 2 , то по теореме Виета С r 1 , а С - r 1 2 . Поэтому уравнение записывается так r 2 = 2· r 1 ·r+–r 1 Тогда рекуррентное соотношение имеет вид f(n+2)= 2 r 1 f(n+1)+ - r 1 2 f(n). Докажем, что nr 1 n является решением данного рекуррентного соотношения. Подставим nr 1 n в полученное рекуррентное соотношение, получим верное равенство (n+2)r 1 n+2 =2r 1 (n+1)r 1 n+1 –r 1 2 nr 1 n =2nr 1 n+2 + 2r 1 n+2 –nr 1 n+2 =(n+2)r 1 n+2 , значит, nr 1 n является решением данного рекуррентного соотношения. Таким образом, имеем два решения рекуррентного соотношения r 1 n и nr 1 n . Общее решение будет иметь вид f(n)= αr 1 n + Задача. Для последовательности си, удовлетворяющей рекуррентному соотношению f(к+2)=4f(к+1)–4f(к), выписать формулу общего члена. Решение. Характеристическое уравнение имеет вид r 2 –4r+4=0, его корни r 1 =r 2 =2. Общее решение рекуррентного соотношения к к+ β·к·2 к . Найдем коэффициенты α и β, пользуясь тем, что f(1)=0 и f(2)=8. Решим систему уравнений 2· α+2·β=0 4· α+8·β=8 Получим α=–2 и β=2. Формула общего члена Линейные рекуррентные соотношения, порядок которых больше 2, решаются аналогично. Задача. Найдем общее решение рекуррентного соотношения f(n+4)=5f(n+3)–6f(n+2)–4f(n+1)+8f(n). Решение. Характеристическое уравнение имеет вид r 4 -5r 3 +6r 2 +4r-8=0 Решая его, получаем корни r 1 =2, r 2 =2, r 3 =2, r 4 =-1. Значит, общее решение имеет вид f(n)=2 n-1 ( α+β·n+γ·n 2 )+δ·(–1) n-1 Асимптотики Асимптотики – это искусство оценивания и сравнения скоростей роста функций. Нередко в задачах на нахождение общего решения рекуррентного соотношения не требуется точное значение го члена, чаще бывает достаточной оценка порядка, а иногда требуется только оценка скорости роста функции f(n). Для описания роста функции используется О- символика. (ввел Поль Бахман в 1894 г) Запись f(n)=O(g(n)) означает, что существуют положительные константы M и n 0 , такие, что ) ( ) ( n g M n f ⋅ ≤ , для всех целых Пример. Для рекуррентного соотношения f(n)=5f(n–1)–6f(n–2), с начальными членами f(1)=0 и f(2)=13 общее решение имеет вид f(n)=2 n +3 n . Можно сказать, что f(n)=O(3 n ). Докажем это. Здесь M=2, а n 0 =1. Неравенство 2 n +3 n ≤3 n +3 n верно для всех n≥1 3 n +3 n =2·3 n , значит, 2 n +3 n ≤2·3 n , следовательно, f(n)=O(3 n ) Пример. Для последовательности Фибоначчи, как было доказано выше, формула общего члена имеет вид ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + = n n n f 2 5 1 2 5 1 5 1 . Легко доказать, что f n =O(2 n ). Соотношение f(n)=O(g(n)) называют асимптотическим соотношением, оно означает, что функция f(n) растет не быстрее, чем функция g(n). Определены еще два асимптотических отношения. Определение 1. Функция f(x) асимптотически равна (эквивалентна) g(x) (обозначается f(x) ∼g(x)) при x→x0, если lim (f(x)/g(x))=1. Если функция f(x) эквивалентна g(x), то это означает, что f(x) растет с такой же скоростью, как и g(x). Определение 2. f(x)=o(g(x)) при x →x0, если lim (f(x)/g(x))=0. Если f(x)=o(g(x)), то это означает, что функция f(x) растет медленнее, чем g(x). Замечание. В соотношениях, использующих О-символику, левые и правые части несимметричны правая часть всегда содержит меньше информации, чем левая, и поэтому нельзя в любом контексте заменять левую часть выражения правой. Например, из двух корректных асимптотических равенств х=О(х 2 ) их Ох) не следует, что х=х 2 Примеры. 1. Полином асимптотически равен своему старшему члену при х. 2. Полином f(n)=2n 5 +6n 4 +6n 2 +18 есть О. 3. Функция f(n)=2 n есть O(2 n+1 ) и o(5 n+1 ). 4. Для линейного рекуррентного соотношения общее решение имеет вид С 1 n +C 2 r 2 n +…+C k r k n . Если нас интересует только асимптотическое поведение последовательности, то достаточно рассмотреть лишь члены Ci( r i ) n , у которых r i имеет максимальное абсолютное значение среди тех членов, у которых Ci≠0. Существуют оценки и асимптотики для комбинаторных чисел. Наиболее известна асимптотика для чисел n!, называемая формулой Стирлинга: n! ∼ n n e n n − π 2 О-символику используют также для оценки сложности алгоритма. Одной из важнейших характеристик алгоритма является его временная сложность в худшем случае. Пусть некоторая задача имеет размерность n (например, длина массива при сортировке. Обозначим через t(n) максимальное число действий, необходимое для решения задачи. Под действием понимают выполнение простой операции – любой арифметической операции, операции сравнения, присваивания и т. п. При этом сложность алгоритма зависит от конкретного вида команд. Поэтому при оценке интересует лишь асимптотическая сложность алгоритма, то есть порядок роста сложности при условии, что размер задачи неограниченно возрастает. Алгоритм считается достаточно хорошим, если сложность этого алгоритма есть О k ) при некотором k>0. В таком случае говорят, что задача может быть решена за полиномиальное время, асам алгоритм называется полиномиальным. ) ( 0 n i n i i x O x a = ∑ = Задачи по комбинаторике Общие правила комбинаторики 1. Имеется пять видов конвертов и четыре вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма 2. Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный 3. Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный, так чтобы они не лежали на одной горизонтали и вертикали 4. Из 12 слов мужского рода, 9 женского и 10 среднего надо выбрать по одному слову каждого рода. Сколькими способами это можно сделать 5. У одного человека есть 7 книг по математике, ау другого – 9 книг. Сколькими способами они могут обменять книгу одного на книгу другого 6. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для участия в состязании. Сколькими способами может быть сделан этот выбор 7. Имеется 6 пар перчаток разных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну – на правую так, чтобы эти перчатки были различных размеров 8. Из трех различных экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать 9. Сколькими способами можно выбрать гласную и согласную буквы из слова КАМЗОЛ 10. На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать 11. Составляются знаки, состоящие из геометрической фигуры (окружности, квадрата, треугольника или шестиугольника, буквы и цифры. Сколько таких знаков можно составить 12. При составлении экипажа космического корабля необходимо учитывать психологическую совместимость экипажа. Известно, что команда состоит из трех человек капитана, инженера и врача. Причем на должность капитана есть четыре кандидата k 1 , k 2 , k 3 , k 4 , на место инженера – 3 кандидата i 1 , i 2 , i 3 и на место врача - 3 кандидата v 1 , v 2 , vi 3 . Проведенные исследования показали, что командир психологически совместим с инженерами i 1 , i 3 и врачами v 2 , v 3 , командир k 2 – с инженерами i 1 , i 2 и со всеми врачами, командир k 3 – с инженерами i 1 , i 2 и врачами v 1 , v 3 , командир k 4 – со всеми инженерами и врачом v 2 . Кроме того, инженер психологически несовместим с врачом v 3 , инженер i 2 – с врачом v 1 , инженер i 3 – с врачом v 2 . Сколькими способами можно составить команду корабля 13. В Стране Чудес есть четыре города А, Б и В и Г. Из города А в город Б ведет 6 дорога из города Б в город В - 4 дороги, Из города А в город Г - две дороги, и из города Г в город В - тоже две дороги. Сколькими способами можно проехать от А до В 14. В магазине одежды продаются 5 видов костюмов троек (брюки, пиджак, жилет, 7 видов брюк, 3 вида пиджаков и 2 вида жилетов, кроме того, 3 вида костюмов двоек брюки, пиджак. Сколькими способами можно сделать покупку, содержащую брюки, пиджаки жилет 15. У двух начинающих коллекционеров помарок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен 16. В книжном магазине лежат 6 экземпляров романа И.С. Тургенева “Рудин”, 3 экземпляра его же романа Дворянское гнездо и 4 экземпляра романа Отцы и дети. Кроме того, есть 5 томов, содержащих романы “Рудин” и Дворянское гнездо, и 7 томов, содержащих романы Дворянское гнездо и Отцы и дети. Все книги различны. Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов 17. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу 18. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты, по одной каждой масти 19. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты разных мастей и достоинств 20. В корзине лежат 12 яблоки апельсинов. Ваня выбирает из неё яблоко или апельсин (что-то одно, после чего Надя берет и яблоко и апельсин. В каком случае Надя имеет большую свободу выбора если Ваня взял яблоко или если он взял апельсин 21. Сколькими способами можно поставить на доску две шашки - белую и черную, так, чтобы белая шашка могла бить черную Черная белую Обе шашки могут бить друг друга Ни одна не может бить другую Формула включения и исключения 22. Исследователь рынка сообщает следующие данные. Из 1000 опрошенных 811 нравится шоколад, 752 нравятся конфеты и 418 - леденцы, 570 нравится шоколад и конфеты, 356 - шоколад и леденцы, 348 - конфеты и леденцы, а 297 - все три вида сладостей. Показать, что в этой информации содержатся ошибки. 23. В классе учатся 45 школьников, в том числе 25 мальчиков. 30 школьников учатся на хорошо и отлично, в том числе 16 мальчиков. Спортом занимаются 28 учеников, в том числе 18 мальчиков и 17 учащихся на хорошо и отлично. 15 мальчиков учатся на хорошо и отлично ив тоже время занимаются спортом. Докажите, что в этой информации сдержатся ошибки. 24. В отделе научно-исследовательского института работают несколько человек, причем каждый из них знает хотя бы один иностранный язык. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек работают в отделе Сколько человек знают только английский язык Только французский 25. Сколько чисел впервой сотне не делится ни на одно из чисел 2, 3, 5? 26. Сколько существует натуральных чисел меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7? 27. В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 -одно ухо, 80 - одну руку и 85 - одну ногу. Страховая компания Веселый Роджер, в которой застрахованы пираты, задалась вопросом каково минимальное число потерявших одновременно глаз, ухо, руку или ногу (страховой случай Total Permanent Disablement, при котором выплаты компании максимальны Размещения с повторениями 28. Назовем натуральное число симпатичным, если в его записи встречаются только нечетные цифры. Сколько существует 4-значных симпатичных чисел 29. Четыре студента сдают экзамен. Сколько может быть вариантов распределения оценок, если известно, что все студенты экзамен сдали 30. На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния красный, желтый, зеленый 31. Сколькими способами можно отправить 6 писем стремя курьерами 47 32. В клубе велосипедистов считается плохим знаком иметь членский билет, в номере которого есть цифра 8. Поэтому председатель клуба решил выдавать билеты с номерами, в которые ни одна 8 не входит. Сколько было членов в группе, если известно, что использованы все трехзначные номера, не содержащие ни одной восьмерки 33. На флоте применяют семафор флажками. Каждой букве соответствует определенное положение флажков. Всего положений каждого флажка пять – вниз отвесно, вниз наклонно, горизонтально, вверх наклонно и вверх отвесно. Как правило, флажки находятся по разные стороны от тела сигнальщика. Но при передаче некоторых букв оба флажка расположены по одну и туже сторону. Почему пришлось сделать такое исключение 34. Вселении проживают 2000 жителей. Доказать, что, по крайней мере, двое из них имеют одинаковые инициалы. 35. Каждую клетку квадратной таблицы 2x2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы 36. Крокодил имеет 68 зубов. Доказать, что среди 16 17 крокодилов может не оказаться двух с одними тем же набором зубов. 37. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32) 38. При передаче сообщений по телеграфу используется код Морзе. В этом коде буквы, цифру и знаки препинания обозначаются точками и тире. При этом для одних букв используется только один знак (Е ·), а для некоторых приходится использовать пять знаков (Э · · - · ·). Почему нельзя обойтись меньшим числом знаков 39. Сколькими способами можно заполнить одну карточку в лотерее «Спортпрогноз»? (В этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча – победа одной из команд либо ничья счет роли не играет. 40. Трое юношей и две девушки выбирают место работы. В городе есть три завода, где требуются рабочие в литейный цех (туда берут лишь мужчин, две ткацкие фабрики туда приглашают лишь женщин) и две фабрики, где требуются и мужчины и женщины. Сколькими способами могут они распределиться между этими предприятиями 41. Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо? Размещения без повторений 42. Сколькими способами в группе студентов из 34 человек можно выбрать старосту и казначея Если известно, что один человек не может занимать две должности сразу. Если известно, что один человек может занимать две должности сразу. 43. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать 44. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице- президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост 45. Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов 46. Забор состоит из 100 дощечек. У Тома Сойера есть краски 150 различных цветов. Сколько существует различных раскрасок забора, если все дощечки покрашены в разный цвет Та же задача, но дощечки могут быть покрашены в одинаковый цвет. 47. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили два различных числа 48. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4 и 5? Тот же вопрос, но при условии, что ни одна цифра не повторяется 49. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают ровно три имени 50. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен 51. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов А если одна полоса обязательно должна быть красной 52. Сколькими способами можно составить расписание надень из 5 различных уроков, если изучается 14 предметов 53. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга. Сколькими способами они могут накрыть стол для чаепития (каждый получает одну чашку, одно блюдце и одну ложку 54. На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги 55. Докажите, что 1 1 1 − − − ⋅ + = n m n m n m A n A A 49 56. На группу из 34 человек выделено две путевки в Сочи и Евпаторию. Сколькими способами можно распределить путевки Известно что один человек не может получить две путевки сразу. Известно, что один человек может получить две путевки сразу. Перестановки 57. Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу 58. Сколькими способами можно выложить вряд красный, черный, синий и зеленый шарики 59. В ряду зрительного зала 15 кресел. Сколькими способами можно разместить на них 15 человек 60. На полке n различных книг. Скольким способами их можно переставить. 61. Сколькими способами можно рассадить за круглым столом 6 мужчин и 6 женщин таким образом, чтобы мужчины и женщины чередовались 62. Сколько существует перестановок из n различных элементов, в которых один данный элемент идет впереди другого данного элемента 63. Сколько можно сделать перестановок из n различных элементов, в которых данные два стоят рядом 64. Сколько можно сделать перестановок из n различных элементов, в которых данные два не стоят рядом 65. Лингвисты разгадывают записи некоторого племени. Известно, что каждый символ обозначает один звук. Всего в алфавите 26 символов. Сколькими способами можно сопоставить звуки знакам письма Во сколько раз уменьшится количество возможных вариантов, если ученым удалось найти 7 знаков, обозначающих гласные, и 19 согласные 66. Сколько существует различных последовательностей длины 5, составленных из трех 1 и двух 0? 67. Сколько существует различных пятизначных чисел, составленных из трех 1 и двух 0? 68. Бусы - это кольцо, на которое нанизаны бусины. Бусы можно поворачивать, ноне переворачивать. Сколько различных вариантов бус можно сделать из 13 разноцветных бусин 69. Предположим теперь, что бусы можно и переворачивать. Сколько тогда различных бус можно сделать из 13 разноцветных бусин 50 70. Сколькими способами на доске из n вертикалей и горизонталей можно расположить n ладей так, чтобы они не могли бить друг друга Ответьте на вопрос задачи, если все ладьи одинаковы и если все они различны. 71. Слово - любая конечная последовательность букв русского алфавита. Выясните, сколько различных слов можно составить из слова) ВЕКТОР б) ЛИНИЯ в) ПАРАБОЛА г) БИССЕКТРИСА д) МАТЕМАТИКА. Сочетания 72. Группе из пяти сотрудников выделено три путевки. Сколько существует способов распределения путевок, если · Все путевки различны, · Все путевки одинаковы 73. Сколько вариантов экзаменационной комиссии, состоящей из 5 человек, можно создать их 14 преподавателей 74. Сколькими способами можно выбрать из n человек упорядоченную группу из k человек Сколькими способами можно выбрать из n человек неупорядоченную группу из k человек 75. У одного школьника есть 6 книг по математике, ау другого - 8. Сколькими способами они могут обменять три книги одного натри книги другого 76. При встрече 12 человек обменялись рукопожатиями. Сколько сделано рукопожатий 77. Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников для участия в математической олимпиаде. Сколькими способами это можно сделать 78. Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников одного для участия в математической олимпиаде, другого для участия в олимпиаде по физике. Сколькими способами это можно сделать, при условии, что олимпиады проходят водно время 79. Есть 3 билета в различные театры. Сколькими способами они могут быть распределены среди 25 студентов группы, если каждый студент может получить только один билет. ) 80. На группу из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами они могут быть распределены (не более одного билета в руки 81. В шахматном кружке занимаются 2 девочки и 7 мальчиков. Для участия в соревновании необходимо составить команду из четырех человек, в которую обязательно должна входить хотя бы одна девочка. Сколькими способами это можно сделать 51 82. В классе, в котором учатся Петя и Ваня - 31 человек. Сколькими способами можно выбрать из класса футбольную команду (11 человек) так, чтобы Петя и Ваня не входили в команду одновременно 83. Во взводе 3 сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования 84. На школьном вечере присутствуют 15 юношей и 12 девушек. Сколькими способами можно выбрать из них четыре пары для танца 85. Сколькими способами можно вырезать прямоугольник из клеток доски размером m х n, при условии, что стороны прямоугольника состоят из целого количества клеток 86. Докажите формулу Р k )= |