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

[ins-]

В шкаф се намират [tex]n[/tex] различни чифта обувки. По случаен начин са извадени [tex]2r[/tex] обувки [tex](2r<n)[/tex]. В колко от случаите измежду извадените обувки има поне един чифт?

[pal702004]

Доста неясна формулировка. Какво се приема за отделен "случай" Наредбата има ли значение, лява-дясна има ли значение? Например

$A_L,B_R$
$A_L,B_L$
$B_L,A_R$
и т.н един "случй ли е, или са различни?

За да няма всякакви тълкувания, предлагам да се намери вероятността сред извадените да има поне един чифт. Или нито един чифт, което е допълнението. Да пресметнем вероятността да няма нито един чифт. Първата извадена може да е всякаква, втората обаче можем да изберем между $n-2$ (без извадената и нейния "чифт") следващата по $n-4$ и т.н

$P=\dfrac n n \cdot \frac{n-2}{n-1}\cdot \dfrac{n-4}{n-2}\cdots$ Тъй като $n$ е четно, $n=2k$

$P=\dfrac{2^rV_k^r}{V_{2k}^{2r}}$

[ins-]

Задачата е от общински кръг на олимпиада по математика (1996 г.). Условието е 1:1 с това, дадено на участниците.

Предполагам, че под "случай" се разбира един възможен избор. Краен отговор: [tex]C_{2n}^{2r}-2^{2r}.C_{n}^{2r}[/tex]. При нужда мога да пратя линк към решението. Комбинаториката не ми е силна страна. Не успях да разбера решението и затова пуснах задачата.

Разсъждавам така:

Разглеждам чифтовете обувки като множество с [tex]n[/tex] елемента (всеки чифт е отделен елемент).

За избраните елементи имаме следните възможности - между тях да има точно един чифт (случай [tex]1[/tex]) обувки, (случай [tex]2[/tex]) да има точно два чифта обувки, ..., (случай [tex]r[/tex]) - да има [tex]r[/tex] чифта обувки (максималният брой чифтове е [tex]r[/tex], защото от [tex]2r[/tex] обувки могат да се образуват най-много r чифта.

Общият брой възможностите, в които измежду избраните [tex]2r[/tex] обувки има поне един (различен) чифт е сборът от възможностите във всеки от изброените [tex]r[/tex] случая, а именно: [tex]C_{n}^{1} + C_{n}^{2} + ... + C_n^{r}[/tex].

Греша ли някъде? Ако не - възможно ли е намереният от мен израз да бъде опростен?

[pal702004]

Между другото малко съм се объркал. Решавал съм го като "има $n$ обувки. А всъщност има $n$ чифта - тоест, $2n$ обувки, от които се вадят $2r$. Така че формулите ми трябва да се поправят.
Относно решението на ins. Ами не е правилно. Какво означава $C_n^1$. Примерно, извадили сме бял чифт. А това, че от останалире $r-2# обувки всички трябва да са по 1 от различен цвят къде е отбелязано.
Вадим 4 обувки. бял чифт, по 1 черна и кафява обувка. И бял чифт, по една жълта и синя обувка - това са различни варианти за "само един чифт - бял". и т.н
Да не говорим, че "черна лява и кафява дясна" и "черна лява и кафява лява" могат според интерпретацията да се броят различни случаи.

Така че във формулата $C_n^1$ трябва да се замени с $C_n^1\cdot C_{n-1}^{2r-2}$ ако не греша.
Накакъв чифт и кои от останалите $n-1$ цвята ще участват с 1 обувка.
Тоест, не е толкова просто

[ins-]

Относно решението на ins. Ами не е правилно. Какво означава $C_n^1$. Примерно, извадили сме бял чифт. А това, че от останалире $r-2# обувки всички трябва да са по 1 от различен цвят къде е отбелязано.

[tex]C_{n}^{1}[/tex] означава, че в случай, че е избран точно един чифт - той може да е бял, жълт, лилав и т.н., но сред останалите [tex]2r-2[/tex] обувки не трябва да има нито един чифт.

[pal702004]

[tex]C_{n}^{1}[/tex] означава, че в случай, че е избран точно един чифт - той може да е бял, жълт, лилав и т.н., но сред останалите [tex]2r-2[/tex] обувки не трябва да има нито един чифт.

Това е една от хилядите интерпретации, за кото говорих в началото. Ами още една интерпретация. Отговор - r начина:. 1 чифт, 2 чифта ....$r$ чифта. Затова - каква е вяроятността и добра форма.

[ins-]

По моя начин вероятността би трябвало да е: [tex](C_{n}^1+C_{n}^2+...+C_{n}^{r})/C_{2n}^{2r}[/tex]. Правилно ли разсъждавам?

Мисля, че не, защото във всеки от случаите не отчитам фактът, че останалите обувки са различни и могат да бъдат избрани по много начини, както pal702004 е отбелязал.

[drago]

@inc: Не е правилно по следната причина. Когато броиш добрите случаи(има поне 1 чифт) ти разглеждаш следните възможни случаи: има 1 чифт, има 2 чифта,... т.н. Ако има точно $k$ чифта, възможностите да се изберат тези чифтове са $\binom{n}{k}$, но след това трябва да умножиш по нещо което дава останалите възможности. Но и така не е правилно, защото ще броиш една конфигурация, да кажем с $k$ чифта, няколко пъти - ще я броиш във фамилията с $1,2,\dots,k$ чифтове.

Най-лесно става като се опиташ да преброиш не възможностите на "добрите" комбинации, а на лошите, тези които не стават. И така, ако извадиш $2r$ обувки и всичките са от различни чифтове, значи ти си барнал $2r$ чифта от възможни $n$. Възможностите са $\binom{n}{2r}$. От всеки от тези барнати чифтове можем да изберем или едната или другата обувка, така че възможностите стават $2^{2r}\binom{n}{2r}$. Всичките възможности са $\binom{2n}{2r}$. Така че възможностите, в които имаме изваден поне един чифт са
$$\binom{2n}{2r} - 2^{2r}\binom{n}{2r}$$

Забележка. Условието пита не за вероятността да извадиш нещо, а за броя на случаите, които удовлетворяват нещо!

[Гост]

drago, точно така е както казваш. Мислих още известно време над тази задача. През 90-те не съм виждал често комбинаторика на общински кръг. Затова ми стана интересна. Както казах - комбинаториката не ми от силните страни, но се опитах да помисля. Не бях успял да разбера решението и се опитах да измисля алтернативно. Ако беше се получило - идеята ми беше да стигна до комбинаторно тъждество. Лошото е, че както е казал pal702004 трябва се умножава по едни комбинации, но те вероятно са некоректни. Ако бяха правилни - при заместване с конкренти числови стойности на $r$ и $n$ по двата възможни начини за решение щеше да се стига до едни и същи стойности, но не се получава така. Опитах се да измисля други комбинации, но ако не съм се объркал - стигам до задачи, които са еквивалентни с дадената, но за по-малки стойности. Заради това ситуацията се усложнява прекалено много и зациклям. Ако трябва да се реши по разумен начин задачата, то е както е показано от drago и в официалното решение.

[peyo]

В шкаф се намират [tex]n[/tex] различни чифта обувки. По случаен начин са извадени [tex]2r[/tex] обувки [tex](2r<n)[/tex]. В колко от случаите измежду извадените обувки има поне един чифт?

Зачетох се в решенията на тази задача и ми стана интересно. Тук по-горе на няколко пъти стана дума, че ние не търсим вероятност, а броя случаи за нещо. Аз сега си мисля, че ние по-лесно можем да намерим този брой случаи като първо намерим вероятността, за въпросните случаи и я умножим по всички случаи по следния начин:

Каква е вероятността да не извадим нито един чифт? (с други думи да извадим само обувки от различни чифтове)

Имаме общо 2n обувки. Вадим от тях 2r обувки, една по една:
За първата обувка вероятността е:
1
За 2-рата обувка вероятността е:
$1.\frac{2n-2}{2n-1}$ (защото вече сме извадили една обувка и втората обувка от този чифт не може да я вадим също)
За 3-тата обувка вероятността е:
$1.\frac{2n-2}{2n-1}.\frac{2n-4}{2n-2}$
...
За 2r-тата обувка вероятността е:
$1.\frac{2n-2}{2n-1}.\frac{2n-4}{2n-2}...\frac{2n-2.2r}{2n-2r}$

И така вероятността за поне един чифт:
$P = 1- \frac{2n-2}{2n-1}.\frac{2n-4}{2n-2}...\frac{2n-2.2r}{2n-2r}$

2r обувки от 2n където подредбата не е от значение можем да извадим по:

$\frac{(2n-1)(2n-2)...(2n-2r)}{2r!}$

И така търсения от задачата брой е:

$B = \frac{(2n-1)(2n-2)...(2n-2r)}{2r!} ( 1- \frac{2n-2}{2n-1}.\frac{2n-4}{2n-2}...\frac{2n-2.2r}{2n-2r} )$

[drago]

В общи линии е така. Трябва само да коригираш 2 неща:
"а 2r-тата обувка вероятността е:..." - с един член по-къс е правилния израз.
"2r обувки от 2n където подредбата не е от значение можем да извадим по:..." - малко трябва да се измести изразът в числителя.
Ориентирай се по моя пост. Трябва да докараш същото число.

[peyo]

В общи линии е така. Трябва само да коригираш 2 неща:
"а 2r-тата обувка вероятността е:..." - с един член по-къс е правилния израз.
"2r обувки от 2n където подредбата не е от значение можем да извадим по:..." - малко трябва да се измести изразът в числителя.
Ориентирай се по моя пост. Трябва да докараш същото число.

Ами да! Моя грешка. За първата обувка вероятността е: 1, но трябваше да го напиша като $\frac{2n}{2n}$ и тогава нямаше да го загубя. С тези промени изглежда ще получа твоя отговор.