Комбинаторика. Задачи 151-200

Задачи по комбинаторике

Задачи 151-200 с ответами

содержание задачника

  1. Из Лондона в Кембридж ведут 3 шоссе, пересекаемые 4 проселочными дорогами. Сколькими способами можно совершить путешествие, если ни по одному участку шоссе не едут в направлении Лондона и ни один участок не проезжают дважды?  
  2. Имеется неограниченное количество монет достоинством в 10, 15 и 20 коп. Сколькими способами можно выбрать 20 монет?
  3. Надо отгадать, какие пять монет держит в руке партнер. Монеты бывают достоинством в 1, 2, 3, 5, 10, 15, 20, 50 коп. и 1 руб. Сколько может быть дано неверных ответов?
  4. Сколько существует пятизначных чисел? Во скольких из них все цифры четны? Во скольких все цифры нечетны? Во сколько не входят цифры, меньше чем 6? Во скольких нет цифр, больших чем 3? Сколько из них содержат все цифры 1, 2, 3, 4, 5? Сколько содержат все цифры 0, 2, 4, 6, 8?
  5. Стороны каждой из двух игральных костей помечены числами 0, 1, 3, 7, 15, 31. Сколько различных сумм может получиться при метании этих костей?
  6. Стороны каждой из трех игральных костей помечены числами 1, 4, 13, 40, 121, 364. Сколько различных сумм может получиться при их метании?
  7. Кидают шесть игральных костей, помеченных числами 1, 2, 3, 4, 5, 6. Во скольких случаях они дадут один вид очков? Два вида? Три вида? Четыре вида? Пять видов? Шесть видов? Все кости считаются различимыми друг от друга.
  8. Бросают n игральных костей. Сколько может получиться различных результатов (результаты, отличающиеся лишь порядком очков, считаются одинаковыми; на каждой кости нанесены 1, 2, 3, 4, 5, 6 очков)?
  9. Сколькими различными способами можно представить число 1 000 000 в виде произведения трех сомножителей? Представления, отличающиеся порядком сомножителей, считаются различными.
  10. Сколькими различными способами можно представить число 1 000 000 в виде произведения трех сомножителей? Представления, отличающиеся порядком сомножителей, считаются одинаковыми.
  11. Сколькими способами можно разложить в два кармана девять монет различного достоинства?
  12. Сколькими способами можно распределить 3n различных предметов между тремя людьми так, чтобы каждый получил n предметов?
  13. Даны 2n элементов. Рассматриваются всевозможные разбиения их на пары, причем разбиения, отличающиеся друг от друга только порядком элементов внутри пар и порядком расположения пар, считаются совпадающими. Сколько существует различных таких разбиений?
  14. Даны nk элементов. Рассматриваются всевозможные разбиения их на n групп по k элементов в каждой группе, причем разбиения, отличающиеся друг от друга только порядком элементов внутри групп и порядком расположения групп, считаются совпадающими. Сколько существует различных таких разбиений?
  15. Сколькими способами можно разбить 30 рабочих на 3 бригады по 10 человек в каждой бригаде? На 10 групп по 3 человека в каждой группе?
  16. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза?
  17. Сколькими способами можно разложить 10 книг на 5 бандеролей по 2 книги в каждой (порядок бандеролей не принимается во внимание)?
  18. Сколькими способами можно разложить 9 книг на 4 бандероли по 2 книги и 1 бандероль в 1 книгу?
  19. Сколькими способами можно разложить 9 книг на 3 бандероли по 3 книги в каждой?
  20. Сколькими способами 3 человека могут разделить между собой 6 одинаковых яблок, 1 апельсин, 1 сливу, 1 лимон, 1 грушу, 1 айву и 1 финик?
  21. Сколькими способами 3 человека могут разделить между собой 6 одинаковых яблок, 1 апельсин, 1 сливу, 1 лимон, 1 грушу, 1 айву и 1 финик так, чтобы каждый получил по 4 плода?
  22. Лица А, В и С имеют по 3 яблока каждый и, кроме того, А имеет 1 грушу, 1 сливу и 1 айву, В имеет 1 апельсин, 1 лимон и 1 финик, а С имеет 1 мандарин, 1 персик и 1 абрикос. Сколькими способами могут они распределить между собой эти фрукты так, чтобы каждый получил по 6 штук?
  23. Сколькими способами можно раздать колоду в 52 карты 13 игрокам по 4 карты каждому игроку? Та же задача с условием, что каждый имеет по одной карте каждой масти. Та же задача при условии, что одни имеет карты всех четырех мастей, а все остальные— карты одной и той же масти.
  24. Сколькими способами можно вынуть 4 карты из полной колоды в 52 карты так, чтобы были 3 масти? Так, чтобы были 2 масти?
  25. Сколькими способами можно раздать 52 карты четырем игрокам так, чтобы каждый получил по три карты трех мастей и четыре карты четвертой масти?
  26. Сколькими способами можно раздать 18 различных предметов 5 участникам так, чтобы четверо из них получили по 4 предмета, а пятый — 2 предмета? Та же задача, но трое получают по 4 предмета, а двое — по 3 предмета.
  27. Имеется 14 пар различных предметов. Найти полное число выборок из этих предметов? Две выборки отличаются друг от друга своим составом, но не порядком предметов.
  28. Сколькими способами 4 черных шара, 4 белых шара и 4 синих шара могут быть разложены в 6 различных пакетов (некоторые пакеты могут быть пустыми)?
  29. Сколькими способами можно разложить 3 руб. и 10 полтинников в 4 различных пакета?
  30. Доказать, что количество разбиений числа n на несколько слагаемых равно количеству разбиений числа 2n на n слагаемых (порядок слагаемых не принимается во внимание).
  31. n предметов расположены в ряд. Сколькими способами можно выбрать из них три предмета так, чтобы не брать никаких двух соседних элементов?
  32. Ребенок ставит на первые две линии шахматной доски белые и черные фигуры (по два коня, два слона, две ладьи, ферзя и короля каждого цвета). Сколькими способами он может это сделать?
  33. Ребенок ставит на шахматную доску белые и черные фигуры (по два коня, два слона, две ладьи, ферзя и короля каждого цвета). Сколькими способами он может это сделать?
  34. Ребенок ставит на шахматную доску белые и черные фигуры (по два коня, два слона, две ладьи, восемь пешек, ферзя и короля каждого цвета). Сколькими способами он может это сделать?
  35. Сколькими способами можно поставить 15 белых и 15 черных шашек на 24 поля так, чтобы на каждом поле были или только белые, или только черные шашки?
  36. Сколькими способами можно расставить 20 белых шашек на шахматной доске так, чтобы это расположение переходило само в себя при вращениях доски на 90°?
  37. Сколькими способами можно расставить 20 белых шашек на шахматной доске так, чтобы это расположение было симметрично относительно линии, делящей доску пополам?
  38. Сколькими способами можно расставить 20 белых шашек на шахматной доске так, чтобы это расположение было симметрично относительно линии, делящей доску пополам, при условии, что шашки ставятся на черные поля?
  39. Сколькими способами можно расставить 12 белых и 12 черных шашек на черные поля доски так, чтобы это положение было симметрично относительно центра доски?
  40. Сколькими способами можно расставить 12 белых и 12 черных шашек на черные поля доски так, чтобы при симметрии относительно центра доски цвета шашек меняются?
  41. Сколькими способами можно поставить 20 белых шашек на крайние линии шахматной доски так, чтобы это расположение не менялось при повороте доски на 90°?
  42. Сколькими способами можно расположить 20 белых шашек на крайних линиях шахматной доски так, чтобы на противоположных сторонах доски шашки стояли симметрично относительно линий, делящих пополам доску?
  43. Сколькими способами можно расположить в 9 лузах 7 белых шаров и 2 черных шара? Часть луз может быть пустой, и лузы считаются различными.
  44. Сколькими способами можно расположить в 9 лузах 7 белых шаров, 1 черный шар и 1 красный шар?
  45. Сколькими способами можно раздать 27 книг лицам А, В и С так, чтобы А и В вместе получили вдвое больше книг, чем С?
  46. В лифт сели 8 человек. Сколькими способами они могут выйти на четырех этажах так, чтобы на каждом этаже вышел по крайней мере один человек?
  47. Сколькими способами можно выбрать из чисел от 1 до 100 три числа так, чтобы их сумма делилась на 3?
  48. Сколькими способами можно выбрать из 3n последовательных целых чисел три числа так, чтобы их сумма делилась на 3?
  49. Имеется n белых, и один черный шар. Сколькими способами можно положить некоторые из этих шаров в n+1 луз, если в каждую лузу помещается не более одного шара?
  50. Сколькими способами можно расставить m белых и n черных шаров так, чтобы между белыми и черными шарами было 2r-1 контактов? 2r контактов?

Ответы

  1. 243
  2. 231
  3. 1286
  4. 90000; 2500; 3125; 1024; 768; 96
  5. 21
  6. 56
  7. 10800
  8. \(C_{n+5}^5\)
  9. 784
  10. 139
  11. \(2^9\)
  12. \(C_{3n}^{n}C_{2n}^{n}\)
  13. \(\displaystyle\frac{(2n)!}{2^nn!}\)
  14. \(\displaystyle\frac{(nk)!}{(k!)^nn!}\)
  15. \(\displaystyle\frac{30!}{(10!)^33!};\frac{30!}{(3!)^{10}10!}\)
  16. \(\displaystyle\frac{3\cdot 32!}{(16!)^2}\)
  17. 945
  18. 945
  19. 280
  20. 20412
  21. 690
  22. 19068
  23. \(\displaystyle\frac{(13!)^5}{(4!)^{12}(3!)^4}\)
  24. 81120
  25. \(\displaystyle\frac{(13!)^4}{(4!)^3(3!)^{12}}\)
  26. \(\displaystyle\frac{18!\cdot C_5^2}{(4!)^3(3!)^2}\)
  27. 4782969
  28. 2000376
  29. 5720
  30. \(C_{n-2}^3\)
  31. \(\displaystyle\frac{16!}{2^6}\)
  32. \(\displaystyle\frac{64!}{2^6\cdot 48!}\)
  33. P(32,8,8,2,2,2,2,2,2,1,1,1,1)
  34. \(\sum_{p,q}P(p,q,24-p-1)C_{14}^{p-1}C_{14}^{q-1}\)
  35. 4368
  36. \(C_{32}^{10}\)
  37. \(C_{16}^{10}\)
  38. \(\displaystyle\frac{16!}{6!6!4!}\)
  39. 7454720
  40. 21
  41. 561
  42. 289575
  43. 521235
  44. \(2^{18}\cdot C_{27}^9\)
  45. 40824
  46. 53922
  47. \(\displaystyle\frac{n}{2}(3n^2-3n+2)\)
  48. \((q+2)2^{q-1}-1\)
  49. \(2C_{m-1}^{r-1}C_{n-1}^{r-1}; C_{m-1}^{r}C_{n-1}^{r-1}+C_{m-1}^{r-1}C_{n-1}^{r}\)