2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Комбинаторика. Много.
Сообщение21.06.2013, 19:27 
Аватара пользователя
Здравствуйте, уважаемые участники форума. Прошу проверить на корректность ответы и размышления.

1)В книжный магазин поступили 5 видов книг по одинаковой цене (каждой из книг достаточно много,$>17$). Имеется денежная сумма, равная $17$ ценам одной книги. Сколько способов совершить покупку?

Поскольку каждую покупку мы можем совершить покупкой только одного вида книг, то имеем дело с сочетаниями с повторениями. Поэтому ответ $C_{17+5-1}^{5-1}$

2)Сколькими способами можно расставить на шахматной доске $8$ ладей так, чтобы они никакие $2$ не били друг друга?

Скорее всего имелось в виду, что ладьи одного цвета могут бить друг друга, иначе смысл теряется. В таком случае первую ладью ставим $64=8\cdot 8$ вариантами. Вторую можно поставить везде, где не бьёт первая (то есть, можно ставить на любой клетке, столбец и строка которой не совпадают с предыдущими), то есть, $7\cdot 7$ вариантов и т.д . Ответ $64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4$

3)Сколько всего вариантов того, что, перемешивая буквы разрезной азбуки "М" "А" "Т" "Е" "М" "А" "Т" "И" "К" "А", получится слово "математика"?

В слове 'математика' можно перемешивать все буквы, которые повторяются. Ответ $2!\cdot 3! \cdot 2!$

4)Cколько всего различных слов можно получить, перемешивая буквы разрезной азбуки "М" "А" "Т" "Е" "М" "А" "Т" "И" "К" "А"?

Каждое перемешивание соответствует слову, в котором $2-M$, $3 -A$, $2-T$ и так далее. То есть, имеем дело с сочетаниями с повторениями. Ответ $\frac{10!}{2!3!2!}$

5)
Сколькими способами $8$ человек можно рассадить за круглым столом, чтобы 2 фиксированных лица сидели напротив?

Фиксируем одного человека по кругу. Затем садим второго напротив. Остальных можно переставлять произвольно, поэтому ответ $6!$.

6)
Сколькими способами можно рассадить класс из $10$ дев. и $10$ мал. по $10$ партам, чтобы за каждой партой сидели мал. и дев., а за каждым мал. сидела дев. и за каждой дев. сидел мал.?

В таком случае рассадка проводится в шахматном порядке. Но таких рассадки $2$. В каждой из них выделяются $10$ мест на мал. и $10$ мест на дев. Поэтому ответ $\left(10!\right)^{2}\cdot 2$
7)Сколькими способами можно рассадить $20$ людей по $5$ вагонам, чтобы первые $3$ вагона заняли соответственно $2,5,3$ человека? (Людей считать разными)

Сначала нужно выбрать $2$ человека в $1$ вагон, $3$ человека в $3$ вагон, $5$ человек во $2$ вагон. Это можно сделать $C_{20}^{2}\cdot C_{18}^{5}\cdot C_{13}^{3}$ способами. Оставшиеся $10$ людей садятся в один из последних вагонов, поэтому вариантов $2^{10}$. Ответ $C_{20}^{2}\cdot C_{18}^{5}\cdot C_{13}^{3}\cdot 2^{10}$

А если людей считать одинаковыми? Тогда рассаживание в первые $3$ вагона однозначно, в последние $2$ можно рассадить $C_{10+2-1}^{2-1}$ способами. Это и будет ответ.

8)Сколькими способами можно рассадить $10$ коз и $15$ волков по $3$ вагонам, чтобы ни одна коза не попала в один вагон с волком?

Можно либо рассадить всех волков в $1$ вагон ($3$ способа), а оставшихся коз по $2$ вагонам и наоборот. Поэтому общее число будет равно $3\cdot C_{10+2-1}^{2-1}+3\cdot C_{15+2-1}^{2-1}$

Но это решение нерационально, так как можно увеличить число коз, волков и вагонов так, что ручной подсчёт займёт много времени. Как эту задачу можно решить рациональнее?

 
 
 
 Re: Комбинаторика. Много.
Сообщение21.06.2013, 19:58 
1) Да
2) А если сначала поставить последнюю ладью, а в конце первую, то расстановка будет та же?
3) Да
4) Да
5) А что, первый человек может сесть без вариантов?
6) Да
7) Да
8) Да
Что бы рациональнее было, надо раскрыть $C^{2-1}_{*}$. Это и к другим ответам относится.

 
 
 
 Re: Комбинаторика. Много.
Сообщение21.06.2013, 20:25 
Аватара пользователя
2)Ладьи у нас можно считать одинаковыми (ведь цвет не влияет на то, бьет или нет). Поэтому я считаю, что не имеет значения, какую ладью считать первой или последней, они все равно одинаковы.
5) Формально там еще есть 0 действие - отметить начало отсчета, но оно определяется однозначно с точностью до поворота. А уже затем на это место мы садим 1 человека.

Я оставлял именно в таком виде, чтобы было видно, что я пользовался именно формулой сочетаний с повторениями.
Но вопрос к последней задаче все-таки остается открытым.

-- 21.06.2013, 19:53 --

Я понял, что имелось в виду по поводу ладей. Что будут ли одинаковыми расстановками одна и другая, если расставить ладьи по тем же местам, но в другом порядке. Конечно же, это одинаковые расстановки. Но вот учитывалось ли это при подсчете..похоже, что нет.
Нужно еще разделить на количество таких возможных перестановок, то есть ответ будет $8!$

 
 
 
 Re: Комбинаторика. Много.
Сообщение21.06.2013, 21:14 
2) Теперь правильно
5) Хм, по моему, в условии не сказано "с точностью до поворотов".

 
 
 
 Re: Комбинаторика. Много.
Сообщение21.06.2013, 21:19 
Аватара пользователя
5) Дело в том, что на то круг и является кругом, чтобы циклические перестановки совпадали. Но все же я не уверен, правильно решил или нет.

 
 
 
 Re: Комбинаторика. Много.
Сообщение21.06.2013, 21:29 
Аватара пользователя
venco в сообщении #739257 писал(а):
5) Хм, по моему, в условии не сказано "с точностью до поворотов".
Обычно в этих задачках когда пишут "круглый стол", имеют в виду именно неразличимость конфигураций, полученных друг из друга поворотом.

 
 
 
 Re: Комбинаторика. Много.
Сообщение22.06.2013, 08:47 
cool.phenon в сообщении #739219 писал(а):
2)Сколькими способами можно расставить на шахматной доске $8$ ладей так, чтобы они никакие $2$ не били друг друга?

Скорее всего имелось в виду, что ладьи одного цвета могут бить друг друга, иначе смысл теряется. В таком случае первую ладью ставим $64=8\cdot 8$ вариантами. Вторую можно поставить везде, где не бьёт первая (то есть, можно ставить на любой клетке, столбец и строка которой не совпадают с предыдущими), то есть, $7\cdot 7$ вариантов и т.д . Ответ $64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4$
Только если считать ладьи неразличимыми, а одинаковые позиции, полученные разными путями - различимыми. Второе для меня совсем не очевидно. Я решал бы как "сколько существуют разных позиций..."

 
 
 
 Re: Комбинаторика. Много.
Сообщение22.06.2013, 11:59 
Аватара пользователя
Ну, что касается этого вопроса, то тут все ясно: в условии не сказано, считать ли ладей одинаковыми или нет, но если считать разными, то задача существенно усложняется, а так как в таком случае считаем ладьи одинаковыми, то естественно считать именно те позиции в которых ладьи стоят одинаково, но расстановки получены иначе, различными.

 
 
 
 Re: Комбинаторика. Много.
Сообщение22.06.2013, 15:03 
Аватара пользователя
Shadow в сообщении #739369 писал(а):
Только если считать ладьи неразличимыми, а одинаковые позиции, полученные разными путями - различимыми. Второе для меня совсем не очевидно. Я решал бы как "сколько существуют разных позиций..."

Как раз в этом решении ладьи и различимы. Демонстрирую. Есть $64$ варианта для первой ладьи. Например, она может стать на клетку $A1$, и тогда вторая, например, из своих $49$ вариантов может выбрать клетку $B2$. А может встать на клетку $B2$, и тогда вторая из своих $49$ вариантов может выбрать, например, клетку $A1$. Варианты $A1, B2, \ldots$ и $B2, A1, \ldots$ посчитаны как разные. Это и называется "ладьи различимы". Что совершенно то же самое, что "одинаковые позиции, полученные разными путями - различимыми". Почему Вы различили эти две вещи - загадка.

А вот ситуация, когда ладьи неразличимы, более естественна. На $8!$ перестановок следует поделить в этом случае.

 
 
 
 Re: Комбинаторика. Много.
Сообщение22.06.2013, 16:11 
--mS-- в сообщении #739417 писал(а):
Варианты $A1, B2, \ldots$ и $B2, A1, \ldots$ посчитаны как разные. Это и называется "ладьи различимы
У меня была интерпретация ладьи неразличимы, а вот ходы различимы (что то же самое, что ладьи различимы - Вы правы) $A1,B2 \text { и } B1,A1$ разлчны.
--mS-- в сообщении #739417 писал(а):
А вот ситуация, когда ладьи неразличимы, более естественна

Именно это я имел ввиду. Сколько вариантов для ладьи на вертикали $A$...

 
 
 
 Re: Комбинаторика. Много.
Сообщение24.06.2013, 13:29 
Аватара пользователя
Задачи еще буду добавлять, проверьте, пожалуйста, их на правильность.

9) Очередь в столовую состоит из $30$ человек. В столовой в наличии только $28$ пирожков. Сколько способов расставить очередь так, чтобы $2$ определённым людям не досталось пирожков?

2 определённых людей ставим в самый конец, это можно сделать $2$ способами. Остальные $28$ людей можно как угодно переставлять. Поэтому ответ $2\cdot 28!$

 
 
 
 Re: Комбинаторика. Много.
Сообщение25.06.2013, 12:25 
Аватара пользователя
$\uparrow $

 
 
 
 Re: Комбинаторика. Много.
Сообщение25.06.2013, 14:05 

(Оффтоп)

Ну вот почему все пришли за пирожками, причем именно за одним?

 
 
 
 Re: Комбинаторика. Много.
Сообщение25.06.2013, 14:32 
Аватара пользователя

(Оффтоп)

Это как буфет моего университета, там больше ничего нет :-)

 
 
 
 Re: Комбинаторика. Много.
Сообщение25.06.2013, 14:37 

(Оффтоп)

И все студенты берут ровно один пирожок? :-)
А к решению вопросов нет...

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group