WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 27 |

1.61. Сколько существует (невырожденных) треугольников периметра 100 с целыми длинами сторон Глава Комбинаторика 1. Сложить или умножить 2.1. а) В Стране Чудес есть три города A, B и C. Из города A в город B ведет 6 дорог, а из города B в город C — 4 дороги. Сколькими cпособами можно проехать от A до C б) В Стране Чудес построили еще один город D и несколько новых дорог — две из A в D и две из D в C. Сколькими способами можно теперь добраться из города A в город C Правило суммы. Если элемент a можно выбрать m способами, а элемент b (независимо от выбора элемента a) — n способами, то выбор «a или b» можно сделать m + n способами.

Правило произведения. Если элемент a можно выбрать m способами, а элемент b (независимо от выбора элемента a) — n способами, то выбор «a и b» можно сделать m · n способами.

2.2. Cколько существует различных семизначных телефонных номеров (cчитается, что номер начинаться с нуля не может) 2.3. Номер автомашины состоит из трех букв русского алфавита (30 букв) и трех цифр. Сколько существует различных номеров автомашин 2.4. В некоторой школе каждый школьник знаком с 32 школьницами, а каждая школьница — с 29 школьниками. Кого в школе больше:

школьников или школьниц и во сколько раз 2.5. В языке одного древнего племени было 6 гласных и 8 согласных, причем при составлении слов гласные и согласные непременно чередовались. Сколько слов из девяти букв могло быть в этом языке 2.6. Алфавит племени Мумбо-Юмбо состоит из трех букв. Словом является любая последовательность, состоящая не более чем из четырех букв. Сколько слов в языке племени Мумбо-Юмбо (См. также 12.9.) 2.7. Сколько существует шестизначных чисел, делящихся на 5 2.8. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра 14 2. Комбинаторика 2.9. Сколько существует десятизначных чисел, в записи которых имеется хотя бы две одинаковые цифры 2.10. Каких семизначных чисел больше: тех, в записи которых есть единица, или остальных 2.11. Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру, нужно правильно набрать пятизначный номер. Каково наименьшее количество номеров нужно перебрать, чтобы наверняка открыть камеру (Числа 23 и 37 можно увидеть и в числе 237.) 2.12. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево (например, таких как 54345, 17071) 2.13. Сколько существует девятизначных чисел, сумма цифр которых четна 2.14. Сколькими способами можно разложить 7 монет различного достоинства по трем карманам 2.15. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует четырехзначных «симпатичных» чисел 2.16*. На двух клетках шахматной доски стоят черная и белая фишки. За один ход можно передвинуть любую из них на соседнюю по вертикали или по горизонтали клетку. (две фишки не могут стоять на одной клетке). Могут ли в результате таких ходов встретится все возможные варианты расположения этих двух фишек, причем ровно по одному разу 2. Принцип Дирихле Принцип Дирихле (принцип ящиков). При любом распределении nk + 1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем k + 1 предмет.

2.17. Докажите, что среди москвичей есть два человека с равным числом волос, если известно, что у любого человека на голове менее одного миллиона волос.

2.18. В мешке 70 шаров, отличающихся только цветом: 20 красных, 20 синих, 20 желтых, остальные — черные и белые. Какое наименьшее число шаров надо вынуть из мешка, не видя их, чтобы среди них было не менее 10-ти шаров одного цвета 2. Принцип Дирихле 2.19. Некоторые точки из данного конечного множества соединены отрезками. Докажите, что найдутся две точки, из которых выходит поровну отрезков.

2.20. Имеется 2k + 1 карточек, занумерованных числами от 1 до 2k + 1. Какое наибольшее число карточек можно выбрать так, чтобы ни один из извлеченных номеров не был равен сумме двух других извлеченных номеров 2.21. Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга 2.22. Сто человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое из мужчин сидят друг напротив друга.

2.23. На складе имеется по 200 сапог 41, 42 и 43 размеров, причем среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви.

2.24. Несколько футбольных команд проводят турнир в один круг.

Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей.

2.25*. Дано 51 различных двузначных чисел (однозначные числа считаем двузначными с первой цифрой 0). Докажите, что из них можно выбрать 6 таких чисел, что никакие 2 из них не имеют одинаковых цифр ни в одном разряде.

2.26. Числа от 1 до 101 выписаны в произвольном порядке. Докажите, что из них можно вычеркнуть 90 чисел так, что оставшиеся 11 чисел будут следовать одно за другим в порядке возрастания или убывания.

2.27. Имеется 2000 точек. Какое максимальное число троек можно из них выбрать так, чтобы каждые две тройки имели ровно одну общую точку 2.28. Даны 1002 различных числа, не превосходящих 2000. Докажите, что из них можно выбрать три таких числа, что сумма двух из них равна третьему. Останется ли это утверждение справедливым, если число 1002 заменить на 1001 2.29*. Дана прямоугольная таблица, в каждой клетке которой написано вещественное число, причем в каждой строке таблицы числа расположены в порядке возрастания. Докажите, что если расположить числа в каждом столбце таблицы в порядке возрастания, то в строках полученной таблицы числа по-прежнему будут располагаться в порядке возрастания.

16 2. Комбинаторика 2.30. В волейбольном турнире команды играют друг с другом по одному матчу. За победу дается одно очко, за поражение — ноль. Известно, что в один из моментов турнира все команды имели разное количество очков. Сколько очков набрала в конце турнира предпоследняя команда и как она сыграла с победителем 2.31. Бесконечная клетчатая доска раскрашена в три цвета (каждая клеточка — в один из цветов). Докажите, что найдутся четыре клеточки одного цвета, расположенные в вершинах прямоугольника со сторонами, параллельными стороне одной клеточки.

2.32. Докажите, что из 11 различных бесконечных десятичных дробей можно выбрать две такие, которые совпадают в бесконечном числе разрядов.

2.33. На плоскости даны 6 точек так, что никакие три из них не лежат на одной прямой. Каждая пара точек соединена отрезком синего или красного цвета. Докажите, что среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет. (См. также 5.36.) 2.34. Докажите утверждение задачи 1.26 при помощи принципа Дирихле.

3. Размещения, перестановки и сочетания Определение. Пусть M = {a1,..., an} — множество из n элементов. Наборы вида (ai,..., ai ) будем называть k-размещениями. Два 1 k k-размещения считаются различными, если они отличаются друг от друга входящими в них элементами или порядком элементов.

Если в размещениях элементы ai,..., ai попарно различны, то 1 k это размещения без повторений. Если же среди элементов ai,..., ai, 1 k могут попадаться одинаковые, то такие наборы называются размещениями с повторениями.

Количества размещений без повторений и с повторениями обознача ются Ak и Ak соответственно.

n n 2.35. Докажите равенства:

а) Ak = n(n - 1)... (n - k + 1); б) Ak = nk.

n n 2.36. В пассажирском поезде 17 вагонов. Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник Определение. Перестановками называются n-размещения без повторений элементов множества M = {a1,..., an}.

3. Размещения, перестановки и сочетания Количество перестановок множества из n элементов обозначается Pn.

2.37. Докажите равенство Pn = n!.

2.38. Сколько существует способов расставить 8 ладей на шахматной доске так, чтобы они не били друг друга 2.39. Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг 2.40. Сколько существует ожерелий, составленных из 17 различных бусинок 2.41. Найдите сумму всех 7-значных чисел, которые можно получить всевозможными перестановками цифр 1,..., 7.

2.42. а) Сколькими способами 28 учеников могут выстроиться в очередь в столовую б) Как изменится это число, если Петю Иванова и Колю Васина нельзя ставить друг за другом 2.43. Сколькими способами можно выбрать четырех человек на четыре различные должности, если имеется девять кандидатов на эти должности 2.44. Из класса, в котором учатся 28 человек, назначаются на дежурство в столовую 4 человека. Сколькими способами это можно сделать Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин Определение. Пусть M = {a1,..., an} — множество из n элементов. k-сочетаниями называются наборы (ai,..., ai ), в которых по1 k рядок считается несущественным. То есть два k-сочетания считаются различными, если они отличаются друг от друга входящими в них элементами, но не порядком элементов.

Аналогично размещениям сочетания бывают без повторений и с повторениями.

Количества сочетаний без повторений и с повторениями обозначаются Ck и Ck соответственно.

n n 2.45. Из двух математиков и десяти экономистов надо составить комиссию из восьми человек. Сколькими способами можно составить комиссию, если в нее должен входить хотя бы один математик 2.46. На плоскости дано n точек. Сколько имеется отрезков с концами в этих точках 2.47. На плоскости проведено n прямых «общего положения». Найдите количество точек пересечения этих прямых. Сколько треугольников образуют эти прямые 18 2. Комбинаторика 2.48. На двух параллельных прямых a и b выбраны точки A1, A2,..., Am и B1, B2,..., Bn соответственно. Сколько будет точек пересечения, если провести все отрезки вида AiBj (1 i m, 1 j n), при условии, что никакие три из этих отрезков в одной точке не пересекаются 2.49*. Ключи от сейфа. Международная комиссия состоит из человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии Рассмотрите задачу также в том случае, когда комиссия состоит из n человек, а сейф можно открыть при наличии m членов комиссии (m n).

2.50. У Нины 7 разных шоколадных конфет, у Коли 9 разных карамелек. Сколькими способами они могут обменяться друг с другом пятью конфетами 2.51. Докажите равенства n! (n + k - 1)! а) Ck = ; б) Ck = Ck =.

n n n+k-(n - k)! k! (n - 1)! k! 2.52. Докажите, что биномиальный коэффициент Ck можно опреn делить как количество способов выбрать k-элементное подмножество в множестве из n элементов.

2.53. Бином Ньютона. Докажите справедливость формулы (x + y)n = C0 xn + C1 xn-1y + C2 xn-2y2 +... + Cnyn.

n n n n Числа Ck называются биномиальными коэффициентами, поскольку они n возникают при возведении в степень бинома x + y.

2.54. Сколько рациональных слагаемых содержится в разложении 4 а) ( 2 + 3)100; б) ( 2 + 3)300 2.55*. Докажите, что для любого натурального a найдется такое n натуральное n, что все числа n + 1, nn + 1, nn + 1,... делятся на a.

2.56. Сколько диагоналей имеет выпуклый:

а) 10-угольник; б) k-угольник (k > 3) 2.57. В выпуклом n-угольнике проведены все диагонали. Они разбивают его на выпуклые многоугольники. Возьмем среди них многоугольник с самым большим числом сторон. Сколько сторон он может иметь 3. Размещения, перестановки и сочетания 2.58. Анаграммы. Анаграммой называется произвольное слово, полученное из данного слова перестановкой букв. Сколько анаграмм можно составить из слов: а) точка; б) прямая; в) перешеек; г) биссектриса; д) абракадабра; е) комбинаторика Некоторые комбинаторные задачи решаются, если условие удается переформулировать в терминах слов и анаграмм. Примером может служить следующая задача.

2.59. Шахматный город. Рассмотрим прямоугольную сетку квадратов размерами m n — шахматный город, состоящий из «кварталов», разделенных n - 1 горизонтальными и m - 1 вертикальными «улицами». Каково число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла (точка (0; 0)) в правый верхний угол (точку (m; n)) (См. также 2.77.) 2.60. Имеется куб размером 10 10 10, состоящий из маленьких единичных кубиков. В центре O одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент, причем так, чтобы расстояние до точки O увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному 2.61. Параллелограмм пересекается двумя рядами прямых, параллельных его сторонам; каждый ряд состоит из m прямых. Сколько параллелограммов можно выделить в образовавшейся сетке 2.62. Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу:

а) из 12; б) из 24 спортсменов 2.63. Имеется множество C, состоящее из n элементов. Сколькими способами можно выбрать в C два подмножества A и B так, чтобы а) множества A и B не пересекались;

б) множество A содержалось бы в множестве B 2.64. Полиномиальная теорема. Докажите, что в равенстве 1 m (x1 +... + xm)n = C(k1,..., km)xk... xk 1 m k1+...+km=n коэффициенты C(k1,..., km) могут быть найдены по формуле n! C(k1,..., km) =.

k1! ·... · km! Числа C(k1,..., km) называются полиномиальными коэффициентами.

20 2. Комбинаторика 2.65. При игре в преферанс каждому из трех игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку.) (См. также 2.95.) 2.66. Сколько существует 6-значных чисел, у которых каждая последующая цифра меньше предыдущей 2.67. Имеется m белых и n черных шаров, причем m > n. Сколькими способами можно все шары разложить в ряд так, чтобы никакие два черных шара не лежали рядом (См. также 3.129, 11.84.) 2.68. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров так, чтобы ни один ящик не оказался пустым Сколькими способами можно разложить n одинаковых шаров по m (n > m) пронумерованным ящикам так, чтобы ни один ящик не оказался пустым 2.69. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров (на этот раз некоторые ящики могут оказаться пустыми) 2.70. Сколько решений имеет уравнение x1 + x2 + x3 = а) в натуральных; б) в целых неотрицательных числах (См. также 11.67.) 2.71. Сколькими способами можно составить букет из 17 цветков, если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки Определение. Биномиальные коэффициенты удобно располагать в виде таблицы, которая называется треугольником Паскаля C0 C0 C1 1 1 C0 C1 C2 1 2 2 2 C0 C1 C2 C3 1 3 3 3 3 3..........................................

Он обладает самыми разнообразными свойствами (см. задачи 2.76, 2.77).

3. Размещения, перестановки и сочетания 2.72. Почему равенства 112 = 121 и 113 = 1331 похожи на строчки треугольника Паскаля Чему равно 114 2.73. Сколькими способами двигаясь по следующей таблице от буквы к букве к в в а а а д д д д р р р р р а а а а а а т т т т т т т можно прочитать слово «квадрат» 2.74. Придумайте какой-нибудь способ достроить треугольник Паскаля вверх.

2.75. При каких значениях n все коэффициенты в разложении бинома Ньютона (a + b)n нечетны 2.76. Вычислите суммы:

а) C0 + 2C1 + 22C2 +... + 25C5;

5 5 5 б) C0 - C1 +... + (-1)nCn;

n n n в) C0 + C1 +... + Cn.

n n n 2.77. Докажите тождества:

а) CmCk = CkCm-k;

r m r r-k б) Cm+1 = Cm + Cm+1;

n+1 n n в) Cn = (C0 )2 + (C1 )2 +... + (Cn)2;

2n n n n г) Ck = C0 Ck + C1 Ck-1 +... + Ck C0 ;

n+m n m n m n m д) Ck = Ck-1 + Ck-1 +... + Ck-1.

n n-1 n-2 k-Попробуйте доказать эти тождества тремя разными способами:

пользуясь тем, что Ck — это количество k-элементных подмножеств в n множестве из n элементов; исходя из того, что Ck — это коэффициент n при xk у многочлена (1 + x)n; пользуясь «шахматным городом» из задачи 2.59.

2.78. Свойство шестиугольника. Докажите равенство Ck-1 · Ck+1 · Ck = Ck · Ck+1 · Ck-1.

Pages:     | 1 || 3 | 4 |   ...   | 27 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.