Версия для печати темы

Автор: Demon0ide 17.3.2007, 19:29

Доброго времени суток, если вас не затруднит, не могли бы помочь решить задачку, желательно объяснить решение.

Формулировка:
Сколько существует способов избрания президента, вице президента, секретаря и казначея среди членов клуба, включающего 8 студентов последнего курса, 10 студентов предпоследнего курса, 15 второкурсников и 20 первокурсников, если:
1) президентом должен быть студент последнего курса?
2) первокурсники могут быть избраны только на должность секретаря?

Помогите пожалуйста, заранее благодарю.

Автор: venja 18.3.2007, 9:25

До конца не уверен, но возможно так.

Будем выбирать в таком порядке (так удобнее):
президента, вице-президента, казначея, секретаря .

Используем ПРАВИЛО ПРОИЗВЕДЕНИЯ из комбинаторики.
Тогда общее число вариантов будет:

8*((8-1)+10+15)*(8+10+15-2)*((8+10+15-3)+20)=...

Автор: A_nn 18.3.2007, 10:21

Думаю, что 1 и 2 - две разные задачи.
И еще думаю, что можно быть сразу всем (президент - он же казначей, разве не хорошо? ).


Но это только предположения.

Автор: Demon0ide 18.3.2007, 17:03

A_nn прав - это 2 разных решения. Есть ещё варианты?

Автор: Руководитель проекта 18.3.2007, 17:48

1. A_nn - это она
2. А у вас есть свои соображения по поводу этой задачи?

Автор: A_nn 18.3.2007, 17:53

Алгоритм остается тот же. Выбираем президента - 8 способов, вице-президента - 53 способа (если можно сидеть на двух стульях), казначея - 53, секретаря, и все это перемножаем.
Если все-таки один человек - одна должность, то 6*52*51*50

Вторая - аналогично.

Автор: Demon0ide 18.3.2007, 18:14

вроде как понял... только 6 почему в выражении?

т.е. всего способов: 53

8(способов выбора президента)*(53-1)*(53-2)*(53-3)

Так что ли?

А для второго случая получается:

20*(53-20-1)*(53-20-2)*(53-20-3)

Так?

Автор: A_nn 18.3.2007, 18:30

6 - это я нечаянно, 8 конечно.
2) не так, секретарь не обязательно с 1 курса.
И порядок выборов лучше тот, который предлагал venja.
А первая - верно, если нельзя занимать две должности, о чем в задаче не говориться, так что, повторяю, возможно, что и по-другому надо (как я вначале писала).

Автор: Demon0ide 18.3.2007, 20:14

>не так, секретарь не обязательно с 1 курса.
Погодь, там написано 'первокурсники могут быть избраны только на должность секретаря?', следовательно, как я понял нам надо выбрать секретаря с 1 курса, секретарь один, а остальные специальности - все кроме первокурсников. Разве не так?

Автор: A_nn 18.3.2007, 20:17

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

Автор: Demon0ide 19.3.2007, 17:33

Это окончательное решение правильное, подтвердите:
выбор Президент- Вице-Президент-казначей-секретарь
8(способов выбора президента)*(53-1)*(53-2)*(53-3)
(53-20-1)*(53-20-2)*(53-20-3)*53

Автор: A_nn 19.3.2007, 17:41

Так не получится. (53-20)*(53-20-1)*(53-20-2)*50.
Почувствуйте разницу

Автор: Demon0ide 19.3.2007, 18:03

да-да, точно... спасибо... описался )) огромное тебе спасибо!

Автор: Demon0ide 25.3.2007, 12:49

Задача оказалась полу-верной... ну это в принципе уже не важно. Подкинули еще кучу задач, вот незнаю решить вот эти две:

1. Сколькими способами можно переставить буквы в слове ПАРАЛЛЕЛИЗМ так, чтобы не менялся порядок гласных букв.

2. В 10 урнах распределены 6 белых и 6 черных одинаковых по размеру шаров, причем в каждой урне есть хотя бы один шар. Сколько существует вариантов распределения шаров

-------------------------------------------------------------------------------------------

Мои мысли по поводу 1 задачи:

Фиксируем гласные, выделяем 7 мест под согласные, т.е.

_А_А__Е_И__
1 2 34 5 67 - места

Итого получаем, что у нас 7 гласных надо расположить в этих 7 ячейках. Если мы заполним 7 ячеек 4ми согласными, кроме 3х согласных 'Л', то получим любые перестановки этих семи согласных, так как на остальные 3 места встанут эти буквы 'Л'. Тогда получаем

Ответ: A (4 из 7)=7*6*5*4

Верно?

PS: Со второй задачах весь в раздумьях...

Автор: Black Ghost 25.3.2007, 14:28

Если так, то верно...
Но... если можно переставлять и гласные?
т.е. например
ПРЛЛЛЗМААЕИ - порядок следования гласных не меняется
этот момент не мешало бы уточнить

Автор: Black Ghost 25.3.2007, 14:59

Насчет второй задачи...
для начала нужно расположить в 10 урнах по одному шару:
а) сначала все 6 черных шаров кладем в урны C(из 10 по 6) способами, остальные 4 урны заполняем четырьмя белыми шарами (не забываем, что кладем по одному шару)
далее оставшиеся 2 белых шара можно разложить в урны:
-10-ю способами так, что 2 этих шара окажутся в одной урне
-C(из 10 по 2) способами так, что эти 2 шара будут в разных урнах
б) сначала 6 белых шаров кладем в урны C(из 10 по 6) способами, остальные 4 урны заполняем четырьмя черными шарами
далее оставшиеся 2 черных шара можно разложить в урны:
-10-ю способами так, что 2 этих шара окажутся в одной урне
-C(из 10 по 2) способами так, что эти 2 шара будут в разных урнах
в) сначала 5 черных шаров кладем в урны C(из 10 по 5) способами, остальные 5 урн заполняем пятью белыми шарами
далее оставшиеся 1 черный и 1 белый шар можно разложить в урны:
-10-ю способами так, что 2 этих шара окажутся в одной урне
-2C(из 10 по 2) способами так, что эти 2 шара будут в разных урнах

дальше, думаю, будет понятно, где чё складывать, а где умножать
для варианта а) будет так C(из 10 по 6) * (10+C(из 10 по 2))

это всё, конечно, если различаются сами урны, т.е. они могут быть с самого начала пронумерованы №1, ..., №10

Автор: Demon0ide 25.3.2007, 15:50

Млин... действительно. Понимаешь, сейчас объясню ситуацию, - препод дал задания, мы начали у него 'уточнять', а тот: "Ничего не знаю, делайте сами", вот что тут подумать. Вот как бы ты Black Ghost делал?

По поводу второй.
>сначала все 6 черных шаров кладем в урны C(из 10 по 6)
Вот это не догнал, C(из 10 по 60) это откуда? Мы разве выбираем 6 шариков из мест, в которые мы хотим их положить? можешь пояснить?...

Автор: Black Ghost 25.3.2007, 16:20

нет, ты путаешь - мы выбираем не шарики, а УРНЫ (если их предварительно пронумеровать) и в них кладём шарики (которые по условию отличаются только цветом)

C(из 10 по 6) - это сколькими способами можно выбрать 6 урн из 10 урн, чтобы заполнить их черными шарами (по одному в каждой урне), причем без учета порядка

C(из n по m)=n!/(m!(n-m)!)

Автор: Demon0ide 25.3.2007, 16:45

Тогда получается выражение
2 * C[6 из 10] * (10+С[2 из 10])
+
С [5 из 10] * (10 + С[2 из 10])

Так?

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

Также, можно ли как-то связать с шарами, а не с урнами, к примеру 3 способа выбора шаров по однму в каждую урну * количество перемещений оставшихся 2х.

И... что по поводу первой... как бы исправить (((((

Автор: Black Ghost 25.3.2007, 17:05

Ну да, вроде бы так получается

Не понял вопрос: в смысле - почему мы сначала размещаем 6 черных шаров, а на остальные 4 белых не смотрим? или как?

По поводу первой задачи:
если бы ты свой вариант не предложил, я бы о нем и не задумался, так как в задаче не сказано, что гласные должны находиться на тех же позициях, что и в начальном слове... поэтому я бы решал по предложенному мной варианту, когда все буквы можно переставлять (понятно, что если мы меняем 2 одинаковые буквы местами ничего нового не получается):
11! - всевозможных перестановок букв в слове (всего 11 букв в слове)
11!/ (3! * 4!) - столькими способами можно переставить буквы, чтобы порядок гласных не изменился
делим на 3!, потому что у нас 3 буквы Л одинаковые
делим на 4!, потому что у нас 4 буквы гласные (которые не должны менять порядок)

а вообще, можно и 2 варианта преподу предложить...

P.S. Насколько мне известно - это задачи из комбинаторики, странно, что их дают в дискретной математике, у нас например, они давались в теории вероятностей (где собственно и должны давать)

Хотя.... щас я еще поразмыслю над первой задачей, а то у меня сомнения есть

Автор: Demon0ide 25.3.2007, 17:08

>Не понял вопрос: в смысле - почему мы сначала размещаем 6 черных шаров, а на остальные 4 белых не смотрим? или как?

Да! Именно.

Автор: Black Ghost 25.3.2007, 17:21

Ну да, вроде всё правильно, можно проверить для несложной аналогичной задачи (как я всегда и делаю) - у нас есть слово aabc

aabc
aacb
abac
acab
abca
acba
baca
caba
bcaa
cbaa
baac
caab
Это различные перестановки букв
4!/2!=12, как и должно быть

Вот еще: дано слово aabcd - порядок следования букв c и d не должен меняться
aabcd
aacbd
aacdb

abacd
acabd
acadb

abcad
acbad
acdab

abcda
acbda
acdba

baacd
caabd
caadb

bacad
cabad
cadab

bacda
cabda
cadba

bcaad
cbaad
cdaab

bcada
cbada
cdaba

bcdaa
cbdaa
cdbaa

5!/(2!*2!)=30, как и должно быть

Автор: Black Ghost 25.3.2007, 17:41

На остальные 4 белых шара мы не смотрим, потому что они не различаются ничем... Если бы они различались, например, размерами или весом пришлось бы и на них смотреть

Автор: Demon0ide 31.3.2007, 11:25

Эхх... разобрался в принципе, спасибо.

Если несложно, можете помочь сделать ещё парочку Приведены задания и как я думаю их решить.

1. Сколькими различными способами можно выбрать несколько букв из фразы "Око за око зуб за зуб". Порядок букв не учитывается.
PS: Мин. - 1 буква, максимально -, как сказал препод, считайте сами, просто выборка.

Решение:
Во фразе (4*О,2*К,4*З,2*А,2*У,2*Б) = 16 букв.
Я думаю, что надо использовать C выборку.
т.е.: C(1из16)+С(2из16)+......+С(16 из 16). - выборки без учёта порядка.

2. Сколькими способами можно переставить буквы в слове "тиктак", так чтобы одинаковые буквы не шли друг за другом.

Решение:
Для начала все перестановки - 6!, теперь надо убрать:
1) Все повторяющиеся - 2! и 2!
2) Варианты, когда будут повторяться символы - ??? (непонятно)
Т.е. 6! / (2!*2!*что-то ещё)

----------------------------------------------------------
Пожалуйста проверьте 1ую и помогите со второй.

Автор: Black Ghost 31.3.2007, 14:16

Первая задача вроде правильно, только надо формулу сократить по биному Ньютона

Вторую задачу не знаю, как сделать при помощи формул... может, просто тупо методом перебора:
Сначала рассмотрим более простую задачу: у нас 2 буквы т, а остальные 4 разные, тогда всевозможные перестановки так, что
буквы т не идут подряд можно записать примерно так:
т.т... 4! перестановок
т..т.. 4! перестановок
т...т. 4! перестановок
т....т 4! перестановок
.т.т.. 4! перестановок
.т..т. 4! перестановок
.т...т 4! перестановок
..т.т. 4! перестановок
..т..т 4! перестановок
...т.т 4! перестановок
понятно, что вместо точек мы как угодно можем ставить остальные буквы, и для каждого случая у нас будет 4! перестановок


теперь мы вспоминаем, что у нас есть еще 2 одинаковые буквы к, оставшиеся 2 буквы различные...
тогда во всех строчках (выше) уже у нас будет не 4! перестановок, а 4!/2! - в этих перестановках 2 одинаковые буквы к, но пока еще мы не накладываем на них условие задачи (чтобы буквы к не следовали подряд)

теперь наложим условие задачи и на буквы к
Каких ситуаций НЕ ДОЛЖНО БЫТЬ:

1) рассматриваем первый случай т.т...

т.ткк.
т.т.кк
2 комбинации
Это для первого случая

4) рассматриваем 4-й случай т....т
ткк..т
т.кк.т
т..ккт
3 комбинации

Для остальных случаев всё аналогично
И теперь учитываем, что в каждом из этих случаев 1), 4) и т.д. у нас еще и 2 разные буквы меняются местами 2! способами

Надеюсь понятно, как получается, последняя "табличка"
т.т... 4!/2!-2*2! благоприятных условию перестановок
т..т.. 4!/2!-2*2! благоприятных условию перестановок
т...т. 4!/2!-2*2! благоприятных условию перестановок
т....т 4!/2!-3*2! благоприятных условию перестановок
.т.т.. 4!/2!-2! благоприятных условию перестановок
.т..т. 4!/2!-2! благоприятных условию перестановок
.т...т 4!/2!-2*2! благоприятных условию перестановок
..т.т. 4!/2!-2! благоприятных условию перестановок
..т..т 4!/2!-2! благоприятных условию перестановок
...т.т 4!/2!-2*2! благоприятных условию перестановок

Осталось всё это сложить и получится нужный результат...

Я тут много лишнего написал. Конечно, решение можно записать коротко

Автор: Demon0ide 1.4.2007, 17:03

По поводу второй задачи (подкинул мысль своим, как ты его назвал, длинным ходом).

ТИКТАК - 6 символов

Смотри: Все перестановки: 6!. Убираем перестановки 2х К и 2х Т - делим на 2!*2!

А теперь... самое интересное, собсно что и затрудняет эту задачу - убрать такие варианты, в которых одинаковые буквы стоят друг за другом. Я подумал, а что если эти варианты пересмотреть и вычесть из результата.

итак, 6 мест:

1) для 2х 'K'

KK....
.KK...
..KK..
...KK.
....KK

т.е. лишние 5 вариантов

2) Для 'T' тоже 5 (аналогично)

-----------------------------------------

Я думаю, что надо сделать так: 6! / (2!*2!) - 5 - 5

Как думаешь, Black Ghost

Автор: Black Ghost 1.4.2007, 21:39

Во-первых, Demon0ide, почему ты вычитаешь 2 раза по 5? Там в каждом варианте аж по 4!/2! перестановок, т.е. нужно вычесть 2 * 5*4!/2!

Во-вторых, я тоже об этом думал - тогда ты 2 раза вычтешь вот такие варианты (что-то типа пересечения 1) и 2)):
.KKТТ. - пересечение .КК... и ...ТТ.
..ККТТ - пересечение ..КК.. и ....ТТ
KKТТ.. - пересечение КК.... и ..ТТ..
КК..ТТ - пересечение КК.... и ....ТТ
ну и т.д. сам можешь понапридумывать
Только я затрудняюсь пересчитать все эти пересечения и при этом не ничего не забыть.

А в первой задаче получилось с биномом Ньютона?

Автор: Demon0ide 2.4.2007, 6:06

С биномом пока нет, со второй... хм.. думаю..

Автор: Demon0ide 21.4.2007, 11:01

Вот задачу задали (предыдущие уже решил), интересьненькая:

Чёрт предложил карточному шулеру:
"Каждый раз, как ты перейдёшь мост и вернёшься обратно, твои деньги в кармане удвоятся, но за это ты мне заплатишь:
1 раз: 50p
2 paз: 100р
3 раз: 150р"

Шулер прошёл по мосту 17 раз. Сначала он значительно обогащался, но в конце остался должен чёрту 360 р, 72 копейки.

Вопрос:
1) Сколько денег было у шулера изначально.
2) Сколько минимально ему надо было иметь, чтобы не 'прогореть'.

Желательно ответить хотя бы на 1ый.

Автор: venja 21.4.2007, 11:25

Арифметическое решение:
идите в обратную сторону от 17-го раза к 1-му (если не лень)

Автор: Demon0ide 21.4.2007, 14:06

Забавно, это так называемое 'в лоб', а есть ли ещё варианты?