Практические задания по дисциплине «Дискретная математика» для НГТУ

1. Имеется 3 разных учебника алгебры, 4 разных учебника истории и 5 разных учебников геометрии. Сколькими способами можно выбрать по одному экземпляру каждого учебника? 2. Сколькими способами можно составить трехцветный полосатый флаг (полосы горизонтальные), если имеется материал 5 различных цветов? Та же задача, если одна из полос должна быть красной? 3. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского, на любой другой из этих языков? 4. Сколькими способами на шахматной доске можно выбрать 2 разных квадрата: а) произвольного цвета, б) белого цвета, в) одного цвета, г) разного цвета, д) разного цвета, не лежащие на одной и той же горизонтали и вертикали, е) одного цвета, не лежащие на одной и той же горизонтали и вертикали? 5. Десять студентов сдают экзамен. Сколькими способами могут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки? 6. На загородную прогулку поехали 92 человека. Бутерброды с колбасой взяли 47 человек, с сыром 38 человек, с ветчиной – 42 человека, и с сыром и с колбасой 28 человек, и с колбасой и с ветчиной – 31 человек, и с сыром и с ветчиной – 26 человек. Все три вида бутербродов взяли 24 человека, а несколько человек вместо бутербродов захватили с собой пирожки. Сколько человек взяли с собой: а) пирожки; б) только бутерброды с колбасой? 7. В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем: а) 8 открыток, б) 8 различных открыток? 8. У одного человека есть 7 различных книг по математике, а у другого – 9. Сколькими способами они могут обменять а) книгу одного на книгу другого, б) три книги одного 3 книги другого? 9. В кухне пять одинаковых лампочек. Каждая может гореть или не гореть. Сколькими способами а) может быть освещена кухня, б) можно зажечь 3 лампочки? 10. Сколькими способами можно выбрать из полной колоды карт (52 карты) а) по одной карте каждой масти; б) по одной карте каждой масти так, чтобы среди вынутых карт не было ни одной пары одинаковых, т.е. двух тузов, двух дам и т.д.; в) по одной карте каждой масти так, чтобы карты красных мастей и карты черных мастей образовывали пары (например, девятки пик и треф и валеты бубен и червей)? 11. Сколькими способами можно из 10 человек а) выбрать 5 для участия в спартакиаде, б) составить 2 спортивные команды по 5 человек в каждой? 12. Сколько нечетных (четных) чисел можно составить из цифр числа 36941, если каждую цифру можно использовать не более одного раза? 13. Сколько различных четырехзначных чисел, делящихся на 4 можно составить из цифр 1, 2, 3, 5, 7, 9 если каждая цифра может встречаться в записи числа несколько раз? 14. Сколько различных четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6 если каждая из них может повторяться несколько раз? 15. Сколькими способами можно составить расписание занятий на понедельник, если в этот день должно быть 5 занятий: по алгебре, геометрии, истории, географии и литературе, причем алгебра и геометрия не должны следовать непосредственно друг за другом? 16. Сколько прямоугольников, составленных из клеток доски с m вертикалями и n горизонталями, содержат клетку с координатами (i j , ) ? 17. Сколькими способами можно составить комиссию из 4 человек, выбирая ее членов из 7 супружеских пар, но так, чтобы члены одной семьи не входили в комиссию одновременно? 18. На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 пары для танца? 19. Сколькими способами из группы, состоящей из 7 мужчин и 4 женщин, можно выбрать 6 человек так, чтобы среди них было не менее 2 женщин? 20. Сколько целых чисел в диапазоне от -20 до 999, не делятся ни на 5, ни на 7? 21. Поезду, в котором находится m пассажиров, предстоит сделать n остановок. Сколькими способами могут выйти пассажиры на этих остановках? Решите ту же задачу, если учитывается лишь количество пассажиров, вышедших на каждой остановке. 22. Человек имеет 6 друзей и в течении k дней приглашает к себе 3-x из них так, что компания ни разу не повторяется. Сколькими способами может он это сделать, если k = 20, k =10 , k = 30? 23. Имеется n абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары? 24. В кошельке лежит по 20 монет достоинством в 1, 2, 5 и 10 рублей. Сколькими способами можно из этих 80 монет выбрать двадцать? 25. Сколькими способами можно поставить на шахматную доску 8 ладей, так чтобы они не били друг друга: а) ладьи не различимы; б) все ладьи различны. 26. Сколько способов разбить 12 человек на две группы по 7 и 5 человек так, чтобы два данных человека оказались: а) в разных группах; б) в одной группе? 27. Сколькими способами можно разбить класс из 30 школьников на три группы по 10 человек, если а) образовавшиеся группы будут играть друг с другом в КВН, б) одна группа на выходные поедет в лес, а две другие проведут день на теплоходе? 28. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза. 29. Сколько существует 10-значных чисел, сумма цифр которых равна: а) 2; б) 3; в) 4? 30. Общество из n членов выбирает из своего состава одного представителя. Сколькими способами может произойти голосование, если каждый голосует за одного человека (быть может, и за себя), а) голосование открытое; б) голосование — тайное, т.е. учитывается лишь число голосов, поданных за каждого кандидата, и не учитывается, кто за кого голосовал. 31. На конференции должны выступить докладчики A, B , C , D, E и F , причем B не может выступать раньше A. Сколькими способами можно установить очередность выступлений? 32. Сколькими способами можно разрезать ожерелье, состоящее из 30 различных бусин на 8 частей (резать можно только между бусинами)? 33. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом? 34. Сколькими способами натуральное число n можно представить в виде суммы: а) k неотрицательных целых слагаемых, б) k натуральных слагаемых, если считать различными представления, отличающиеся порядком? 35. Найти сумму четырехзначных чисел, получаемых при всевозможных перестановках цифр 1, 2, 3, 4. 36. На полку надо поставить k книг в черных переплетах и n книг в синих переплетах, причем все книги разные. Сколькими способами можно расставить книги так, чтобы книги в черных переплетах стояли рядом? 37. Сколькими способами можно разложить 12 монет в 5 различных кошельков, если: а) монеты одинаковые; б) монеты разные? 38. Сколькими способами 4 черных шара, 5 белых шаров и 6 синих шаров могут быть разложены в 7 различных пакетов (некоторые пакеты могут быть пустыми), если: а) шары одинаковые, б) шары разные? 39. Сколько различных перестановок можно образовать из букв следующих слов: а) зебра, б) баран, в) водород, г) абракадабра? 40. Сколькими способами можно разместить n одинаковых шаров по m различным урнам при следующих условиях: а) пустых урн нет; б) во второй урне k шаров; в) в первых s урнах соответственно 1 2 , ,… 41. Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти? 42. Сколько имеется шестизначных чисел, у которых ровно 3 цифры четные? 43. Сколькими способами можно выложить в ряд 5 красных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих шара не лежали рядом? 44. Среди всех чисел от 1 до 10n каких больше: тех, для записи которых используется цифра 9, или тех, которые записываются без нее? 45. Сколько существует целых чисел от 0 до 10n, в десятичной записи которых нет двух стоящих рядом одинаковых цифр? 46. Сколькими способами можно расположить в ряд 10 белых и 4 черных шара так, чтобы черные шары не лежали рядом, если а) шары одного цвета неотличимы друг от друга, б) все шары разные. 47. Сколькими способами можно расставить 20 одинаковых (разных) книг в книжном шкафу с 5 полками (каждая полка может вместить все 20 книг), если а) некоторые полки могут быть пустыми; б) на каждой полке должна быть хотя бы одна книга; в) на каждой полке должно быть не менее трех книг?