Kat&Pop - Рефераты - Программа ВМШ - семестр 2, занятие 4.

Занятие четвертое. (8.10.2000г.)

Комбинаторика

(правило произведения) Пусть имеется два множества предметов, в одном из них А предметов, а в другом В предметов. Образуем пары предметов: один из них берем из первого множества, а второй - из второго. Тогда число таких пар равно А´ В.

  1. Из города Лисса в город Гель-Гью можно проехать только через Зурбаган. Из Лисса в Зурбаган ведет 5 дорог, из Зурбагана в Гель-Гью 3 дороги. Сколько путей ведет из Лисса в Гель-Гью?
  2. Вася собрал 15 васильков и 10 маргариток и решил подарить их двум девочкам - Марго и Рите. Сколькими способами он может разделить свои цветы на два букета, если хочет, чтобы у каждой девочки было хотя бы по одному васильку и не менее двух маргариток?
  3. Осел, Козел, Мартышка и Косолапый Мишка затеяли играть квартет. Дело не пошло, и звери решили усесться на тех же четырех местах по-другому. Сколькими способами можно это сделать? А если каждый из зверей не хочет сидеть на том месте, на котором уже сидел? Сколькими способами можно расположить на 5 пеньках 5 зверей? А на шести пеньках 6? А на семи пеньках 6 зверей?
  4. Семь девушек водят хоровод. Сколькими способами они могут встать вкруг? если способы, отличающиеся поворотом на одну, две, три… девушек не различаются? если важно только то, какие у девушки соседки?
  5. В классе 25 учеников. Учитель решил назначить двух дежурных. Сколькими способами он может это сделать? А трех дежурных?
  6. Сколькими способами можно рассадить 5 животных на 7 местах? животных на (n+2) местах? 7 животных на 11 местах?
  7. Имеется 5 одинаковых с виду замков и 5 похожих ключей. Сколько попыток надо сделать, чтобы установить, какой замок открывается каким ключом.
  8. Та же задача, но замков 7, а ключей 10. Та же задача, но среди замков два абсолютно одинаковые (и ключи к ним одинаковые).
  9. В городе Лиссе автобусные номера записывают четырьмя цифрами: от 0000 до 9999. Автобус называется счастливым, если сумма первых двух цифр его номера равна сумме последних двух цифр его номера. Сколько в городе Лиссе счастливых автобусов с суммой первых двух цифр 7? Сколько всего в Лиссе счастливых автобусов?
  10. Сколькими способами можно прочитать слово АВРАКАДАБРА по таблице:
  11. Сколькими способами можно разбить 10 человек на пары? А 2n человек?

Домашняя работа по теме Комбинаторика (все задачи по 12 баллов):

  1. Штирлиц хочет послать телеграмму из n слов. Всего в секретном языке m слов. Сколько вариантов телеграмм он может составить?
  2. В оркестре "Незадачливых зверей" n участников. Вначале они сидели на m пеньках (некоторые пеньки были пустые), теперь они хотят пересесть по-другому, потому что считают, что так станут лучше играть. Сколькими способами они могут пересесть?
  3. В классе n человек. Надо выбрать для дежурства m человек. Сколькими способами это можно сделать?
  4. (20 баллов) В большой коробке лежат шарики цветов (шарики ничем не отличаются). Для игры Коля хочет взять n шариков и положить их в m коробок. Сколькими способами он может это сделать?
  5. В классе n учеников. Надо отправить делегацию покупать подарок учителю. Сколькими способами это можно сделать?

Дополнительные задачи по комбинаторике.

  1. Сколькими способами можно посадить 7 мужчин и 7 женщин за круглый стол так, чтобы никакие две женщины не сидели рядом?
  2. Сколько существует перестановок чисел 1, 2, 3,…n, в которых 1 и 2 не стоят на своих местах?
  3. Сколькими способами можно составить трехцветный флаг, если имеется материал 5 различных цветов? Тот же вопрос, но одна из полос должна быть красная.
  4. На школьном вечере присутствуют 12 юношей и 15 девушек. Сколькими способами можно выбрать из них 4 пары для танца?
  5. Сколько существует счастливых билетов? (Счастливый билет - это такой билет с шестизначным номером, у которого сумма первых трех цифр равна сумме последних трех цифр.)