Комбинаторная задача

8 Февраль 2012, 0:04

Интересная задачка по комбинаторике, которая заставляет задуматься (см. задачник по алгебре и анализу М.И. Башмакова, Б.М. Беккера, В.М. Гольхового и Ю.И. Ионина).

Задача. Имеется десять различных ящиков, шесть неразличимых белых шаров и шесть неразличимых черных шаров. Сколькими способами можно разложить все шары по ящикам так, чтобы в каждом ящике оказался хотя бы один шар?

Вся сложность комбинаторики состоит в том, чтобы понять. Здесь трудно что-то выучить наизусть. Как только заканчиваются простейшие задачи, приходит конец и “лобовому’’ применению формул для числа сочетаний, размещений и перестановок (ага, а если еще взять соединения с повторениями, то начинается полная путаница!). В любой более-менее неочевидной комбинаторной задаче нужно четко понимать, как подсчитать варианты так, чтобы ничего не пересчитать несколько раз и чтобы никакой вариант не остался неучтенным. И вот когда становится ясным алгоритм такого пересчета, задача решается сразу же. Самое главное, что комбинаторика нужна, и комбинаторные задачи встречаются много где: в химии, генетике, физике, информатике, во многих областях математики (скажем, классическая теория вероятностей — сплошная комбинаторика!). Поэтому знать ее нужно. Но более того, комбинаторика весьма интересна, а еще она заставляет думать, и это еще один ее огромный плюс. В общем, читайте книгу Н.Я. Виленкина “Комбинаторика’’, учитесь на задачах, решайте их (я, кажется, повторяюсь ).

Показать решение

Шаров всего двенадцать, а ящиков десять. Положим в каждый ящик по одному шару, останется два шара. Таким образом, либо в одном ящике будут лежать 3 шара, а во всех остальных по одному шару, либо в двух ящиках будет по два шара, а во всех остальных по одному шару. Рассмотрим все возможные случаи.

Пусть в одном ящике лежат три черных шара. Тогда во всех остальных лежат $3$ черных и $6$ белых шаров. Выберем ящик, в который положим черные шары, это можно сделать $10$ способами. Теперь из оставшихся $9$ ящиков выберем $3$ , в которые положим черные шары (в остальные $6$ ящиков положим по одному белому шару) — ${\sf C}_{9}^{3}$ вариантов. Итак, общее количество способов так разложить шары равно:

$10\cdot C_{9}^{3}=840 .$

Ровно столько же, а именно $840$ вариантов разложить шары по ящикам так, чтобы в одном ящике лежали три белых шара, а в остальных — по одному шару.

Разложим шары так, чтобы в одном ящике лежали $2$ черных и $1$ белый шар. Выберем этот ящик $10$ способами, а затем из оставшихся $9$ ящиков выберем $4$ , в которые положим черные шары:

$10\cdot C_{9}^{4}=1260$ способов раскладки.

И столькими же способами можно разложить шары так, чтобы в одном ящике лежало $2$ белых и $1$ черный шар.

Теперь пусть в двух ящиках лежат по два шара. Пусть в обоих ящиках эти шары белые. Выбираем эти два ящика ${\sf C}_{10}^2$ способами, а из оставшихся $8$ ящиков теперь выберем $2$ , в которые положим оставшиеся белые шары. Итого

$C_{10}^2\cdot C_8^2=1260$ способов.

И столько же способов разложить шары по ящикам так, чтобы в двух ящиках лежало по $2$ черных шара.
Пусть в одном ящике лежат два черных шара, а в другом — черный и белый шары. Выбираем ящик, в который положим два черных шара $10$ способами, после этого $9$ способами выберем ящик, в который положим черный и белый шары. Осталось выбрать из $8$ ящиков $3$ , в которые положим оставшиеся черные шары:

$10\cdot9\cdot {\sf C}_8^3=5040$ способов.

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

В одном ящике может лежать два белых, а в другом — два черных шара. Выбираем ящик, в который положим два белых шара — $10$ вариантов. Из оставшихся $9$ ящиков выберем тот, в который положим два черных шара — $9$ способов. Из $8$ пустых ящиков выберем $4$ , в которые положим белые шары — ${\sf C}_8^4$ способа выбора (в остальные ящики положим черные шары). Всего

$10\cdot9\cdot {\sf C}_8^4=6300$ способов.

И последний случай. В двух ящиках могут лежать по черному и белому шару. Выберем эти два ящика ${\sf C}_{10}^2$ способами. А теперь из оставшихся $8$ ящиков выберем 4, в которые положим черные шары:

${\sf C}_{10}^2\cdot C_8^4=3150$ вариантов.

Теперь складываем все полученное и находим

$2\cdot840+2\cdot1260+2\cdot1260+2\cdot5040+6300+3150=26250$ способов.

Это и есть ответ на вопрос задачи.

Теги: задача, комбинаторика, средняя и старшая школа
Рубрика: Разные задачи | Отзывы (RSS) | Трекбек

Математика, которая мне нравится

Комбинаторная задача

Оставьте свой отзыв

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер