wpthemepostegraund

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

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

 

1.

В киоске продают 5 видов конвертов и 4 вида марок. Сколькими способами можно купить конверт и марку?

Ответ. 5 · 4 = 20.

2.

В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

Ответ. 110.

Решение. Капитаном может стать любой из 11 футболистов. После выбора капитана на роль его заместителя могут претендовать 10 оставшихся человек. Таким образом, есть 11 · 10 = 110 разных вариантов выбора.

Эта задача отличается от предыдущей тем, что выбор капитана ограничивает круг претендентов на роль заместителя: капитан не может быть своим заместителем. Таким образом, выборы капитана и его заместителя не являются независимыми — такими, как выборы конверта и марки.

3.

Сколькими способами можно выбрать гласную и согласную буквы из слова КОНВЕРТ?

Ответ. 2 · 5 = 10.

Решение. Гласную можно выбрать двумя способами (О или Е), а согласную — пятью способами (К, Н, В, Р или Т).

4.

Сколькими способами можно поставить на шахматную доску белую и чёрную ладьи так, чтобы они не били друг друга?

Решение. Белую ладью можно поставить на любую из 64 клеток. Независимо от своего расположения она бьёт 15 полей (включая поле, на котором она стоит). Поэтому остаётся 49 полей, на которые можно поставить чёрную ладью. Таким образом, всего есть 64 · 49 = 3136 разных способов.

 

5.

Сколькими способами можно поставить на шахматную доску белого и чёрного короля, чтобы получилась допустимая правилами игры позиция?

Ответ. 3612.

Решение. Белого короля можно поставить на любое из 64 полей. Однако количество полей, которые он при этом будет бить, зависит от его расположения. Поэтому разберём три случая:

  • если белый король стоит в углу (углов всего 4), то он бьёт 4 поля (включая то, на котором стоит) и остаётся 60 полей, на которые можно поставить чёрного короля;
  • если белый король стоит на краю доски, но не в углу (таких полей 24), то он бьёт 6 полей, и для чёрного короля остаётся 58 возможных полей;
  • если же белый король стоит не на краю доски (таких полей 36), то он бьёт 9 полей, и для чёрного короля остаётся 55 возможных полей.

Таким образом, всего есть

4 · 60 + 24 · 58 + 36 · 55 = 3612

способов расстановки королей.

6.

Ранним утром на рыбалку улыбающийся Игорь мчался босиком. Сколько осмысленных предложений можно составить, вычёркивая некоторые слова этого предложения? (Во все предложения обязательно должны входить подлежащее Игорь и сказуемое мчался.)

Ответ. 24 предложения.

 

Решение. Для каждого из слов улыбающийся, босиком и словосочетания на рыбалку есть две возможности: входить или не входить в предложение. Поэтому если не учитывать слова ранним утром, то можно составить

2 · 2 · 2 = 8

предложений. Из каждого их них можно получить три предложения: одно — со словами ранним утром, второе — только со словом утром, третье — без этих слов.

 

7.

Начальник транспортного цеха пригласил несколько человек на совещание. Каждый участник совещания, входя в кабинет, пожимал руки всем присутствующим. Сколько человек участвовали в совещании, если было всего 78 рукопожатий?

Ответ. 13.

8.

Крыса бежит по лабиринту, который устроен так, что сначала она должна выбрать одну из двух дверей, затем одну из трёх дверей, а за каждой из них её ожидают четыре двери. Пройдя дверь, крыса не может вернуться через неё обратно. Сколькими различными путями крыса может пройти лабиринт от начала до конца?
281.

В поход ходили 80% учеников класса, а на экскурсии было 60% класса, причём каждый был в походе или на экскурсии. Сколько процентов класса были и там, и там?

Ответ. 20%.

Указание. 80 + 60 – 100 = 20.

9.

В классе 35 учеников. 20 из них занимаются в математическом кружке, 11 — в биологическом, а 10 ничем не занимаются. Сколько ребят занимаются и математикой, и биологией?

Ответ. 6.

Указание. Хотя бы в каком-то кружке занимаются 35 – 10 = 25 учеников. Далее, 20 + 11 – 25 = 6.

 

10.

На дискотеке 80% времени был выключен свет, 90% времени играла музыка и 50% времени шёл дождь. Какую наименьшую долю времени всё это обязано было происходить одновременно?

Ответ. 20%.

Решение. Перейдём к дополнительным событиям: свет был включен 20% времени, музыка молчала 10%, а дождь не шёл 50% времени, так что дополнительные события не могли занять более

20 + 10 + 50 = 80%

времени. Следовательно, музыка под дождём в темноте звучала не меньше

100 – 80 = 20%

времени.

11.

Из 100 человек 85 знают английский язык, 80 — испанский, 75 — немецкий. Сколько человек заведомо знают все три языка?

Наводящий вопрос. Сколько человек не знают английский язык? испанский? немецкий?

12.

Каких натуральных чисел от 1 до 1993 больше: тех, которые кратны 8, но не кратны 9, или тех, которые кратны 9, но не кратны 8?

Ответ. Тех, которые кратны 8, но не кратны 9.

Решение. Добавим к тем и другим числа, кратные и 8, и 9. Остаётся сравнить количество чисел, кратных 8 ([1993/8] = 249), с количеством чисел, кратных 9 ([1993/9] = 221).

 

13.

Сколько существует натуральных чисел, меньших 1000, которые не кратны ни 2, ни 5? А не кратных ни 2, ни 3, ни 5?

14.

Сколько существует шестизначных чисел, в записи которых есть хотя бы одна чётная цифра?

Ответ. 884375.

Указание. Вместо того, чтобы подсчитывать количество требуемых шестизначных чисел, определите количество шестизначных чисел, у которых все цифры нечётны.

Решение. Количество шестизначных чисел, в записи которых встречаются только нечётные цифры, равно 56 = 15 625. Всего шестизначных чисел 900 000. Поэтому количество шестизначных чисел, в записи которых есть хотя бы одна чётная цифра, равно

900 000 – 15625 = 884 375.

15.

Каких чисел больше среди первого миллиона: тех, в записи которых есть цифра 7, или тех, в записи которых её нет?289.

Сколько семизначных чисел не содержат цифры 2?

Ответ. 8 · 9 · 9 · 9 · 9 · 9 · 9 = 4 251 528.

16.

Сколькими способами 8 человек могут встать в очередь к театральной кассе?

Ответ. 8! = 40 320.

Указание. Первого человека можно выбрать 8 способами, второго (после того, как выбран первый) можно выбрать 7 способами, третьего — 6 способами, и так далее.

 

17.

Сколько существует 9-значных чисел, цифры которых расположены в порядке убывания (то есть каждая следующая меньше предыдущей)?

Ответ. 10.

 

Решение. Выпишем все цифры в порядке убывания: 9876543210. Чтобы получить девятизначное число, нужно убрать одну цифру. Это можно сделать 10 способами.

 

Сколько разных чисел можно получить, переставляя цифры чисел: а) 133; б) 9854; в) 3213; г) 98561; д) 32123?

18.

Сколько различных (не обязательно осмысленных) слов можно получить, переставляя буквы слов: а) крот; б) математика; в) наполеононенавистничество?
19.

Сколько существует трёхзначных чисел, в запись которых входит ровно одна цифра 5?

Ответ. 225.

 

Решение. Для перечисления всех удовлетворяющих условию задачи чисел рассмотрим три случая.

  • Число начинается на цифру 5. Вторую цифру (то есть разряд десятков) можно выбрать девятью способами, после чего третью цифру (разряд единиц) можно выбрать также девятью способами. Следовательно, в этом случае мы получаем 9 · 9 = 81 число.
  • Цифра 5 — в разряде десятков. Первую цифру можем выбрать восемью способами, а третью – девятью способами, и поэтому таких чисел 8 · 9 = 72.
  • Цифра 5 — в разряде единиц. Таких чисел 72.

Общее количество интересующих нас чисел равно 81 + 72 + 72 = 225.

20. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
21. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
22. Сколько есть шестизначных чисел, делящихся на 5?
23. Сколькими способами можно разложить 7 разных монет в три кармана?
24. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
25. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
26. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
27. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
28. Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
29. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, 8, если каждую цифру можно использовать только один раз?
30. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
31. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа 4:

4; 3+1; 1+3; 2+2; 2+1+1; 1+2+1; 1+1+2; 1+1+1+1.

Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.

Сколько существует различных разбиений числа 11 на 4 слагаемых?
32. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
33. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
34. Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
35. N девочек и N мальчиков рассаживаются произвольным образом в ряду из 2 N мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
36. N девочек и N мальчиков рассаживаются произвольным образом в ряду из 2 N мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

 

***

  1. Hапечатать все последовательности длины N из чисел 1,2..M
  2. Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово
  3. Hапечатать все перестановки чисел 1..N
  4. Сгенерировать все подмножества данного n-элементного множества {0,.., n-1}
  5. Дана строка S и набор A слов А[1],.. , A[k]. Разбить строку S на слова набора всеми возможными способами
  6. Перечислить все разбиения N на целые положительные слагаемые
  7. Перечислить все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел
  8. У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец
  9. Перечислить все расстановки 8-ми ферзей на шахматной доске, при которых они не бьют друг друга
  10. A Story about the N-Queens Problem: From Exponential to (Almost) Constant Time
  11. Перечислить все расстановки n ферзей на шахматной доске размера NxN, при которых никакие два не бьют друг друга. Намного более продвинутые методы, нежели в статье выше.
  12. Обход доски шахматным конем
  13. Нужно конем обойти всю шахматную доску NxN, побывав в каждой клетке всего лишь раз.
  14. Hапечатать все последовательности длины N из чисел 1,2..M
  15. Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово
  16. Hапечатать все перестановки чисел 1..N
  17. Сгенерировать все подмножества данного n-элементного множества {0,.., n-1}
  18. Дана строка S и набор A слов А[1],.. , A[k]. Разбить строку S на слова набора всеми возможными способами
  19. Перечислить все разбиения N на целые положительные слагаемые
  20. Перечислить все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел
  21. У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец
  22. Перечислить все расстановки 8-ми ферзей на шахматной доске, при которых они не бьют друг друга
  23. Перечислить все расстановки n ферзей на шахматной доске размера NxN, при которых никакие два не бьют друг друга. Намного более продвинутые методы, нежели в статье выше.
  24. Обход доски шахматным конем
  25. Нужно конем обойти всю шахматную доску NxN, побывав в каждой клетке всего лишь раз.

Thanks: Ruliz