2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Pairs of shoes (combinatorics)
Сообщение09.10.2020, 23:21 
Аватара пользователя


13/10/07
755
Роман/София, България
In a closet are put $n$ different pairs of shoes. In a random way are taken $2r$ shoes $(2r<n)$. Find the number of cases we have taken at least one pair of shoes (from the same kind).

 Профиль  
                  
 
 Re: Pairs of shoes (combinatorics)
Сообщение10.10.2020, 09:15 
Аватара пользователя


01/11/14
1647
Principality of Galilee
I think we must start by calculating the number of cases when the selected shoes do not contain paired ones at all.

The pairs shown in our selection can be selected in $C_n^{2r}$ ways.

But from each selected pair we can choose both the right shoe and the left shoe. Or the whole pair. This we can do in $2^{2r}$ ways.

So we avoid a pair in our sample in $2^{2r}\cdot C_n^{2r}$ ways.

In total to choose $2r$ shoes among $n$ pairs we can in $C_{2n}^{2r}$ ways.

To sum up the required number of cases is $C_{2n}^{2r}-2^{2r}\cdot C_n^{2r}$

I suppose so.

 Профиль  
                  
 
 Re: Pairs of shoes (combinatorics)
Сообщение10.10.2020, 11:29 
Аватара пользователя


01/11/14
1647
Principality of Galilee
I looked at this problem a second time, then a third ...
It seems to me that it is too simple for the olympiad. Standard combinatorial problem.
No?

 Профиль  
                  
 
 Re: Pairs of shoes (combinatorics)
Сообщение10.10.2020, 11:59 
Аватара пользователя


13/10/07
755
Роман/София, България
I posted it as an olympiad problem, because it was given on a math olympiad (former second round, now first in the Bulgarian math olympiad). They have the same answer as your but I didn't undertstand the solution and tried to solve the problem in a different way.

What I did was - each different pair of shoes is an element of a set with $n$ elements. From the taken shoes is it is possible to have exactly $1$ pair of shoes (case $1$), exactly $2$ pairs of shoes (case $2$), ..., exactly $r$ pairs of shoes (case $r$). Summing the different cases gives $C_{n}^{1}+C_{n}^{2}+...+C_{n}^{r}$ as a final result.

Did I make a mistake? If no - is it possible the expression I found to be simplified further?

 Профиль  
                  
 
 Re: Pairs of shoes (combinatorics)
Сообщение10.10.2020, 12:32 
Заслуженный участник


20/12/10
8858
ins- в сообщении #1486544 писал(а):
is it possible the expression I found to be simplified further?
Yes, it is very easily. You may just use any computer algebra system (if you want to obtain the answer only and not anything else). The sums of binomial coefficients that you proposed can be evaluated by a standard algorithm.

 Профиль  
                  
 
 Re: Pairs of shoes (combinatorics)
Сообщение10.10.2020, 13:32 
Аватара пользователя


13/10/07
755
Роман/София, България
I'm not sure if my answer is correct. I think in each of the cases I miss the fact that the remaining shoes are different and can be chosen in many different ways and a "corresponding sequences of different shoes" can be found. Because of this it is possible each of my combinations to be multiplied by another one. For example in the first case it is $C_n^1\cdot C_{n-1}^{2r-2}$. Is that correct?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group