Whose Shoe Is It, Anyway?

Consider the number of ways in which the 5 people can pick up their left shoes. Either 0, 2, 3, or 5 people pick up their own shoes since we can't have exactly 1 person picking up his/her own shoe or exactly 1 person not picking up his/her own shoe. Note that the number of ways in the 0 and 2 cases is equal to the number of ways in the 3 and 5 cases by symmetry. So we now look at two cases:

Case 1: Exactly 3 people pick up their own left shoes. There are $\binom{5}{3}=10$ to choose these people. There is $1$ way for the other 2 people to pick up wrong left shoes and $2$ ways for these 3 people to pick up wrong right shoes. Thus, there are $10 \times 1 \times 2 = 20$ ways for the 5 people to leave with exactly 1 right shoe each in this case. $\square$

Case 2: All 5 people pick up their own left shoe. We want to count the number of ways in which none of them pick up their own right shoe.

Let $!n$ denote the number of ways in which $n$ people all pick up the wrong shoe. We have $!1=0$ and $!2=1.$ Note consider $!n$ for some random positive integer $n.$ Label the people $p_1, p_2, ..., p_n$ and their corresponding shoes $s_1, s_2, ..., s_n.$ Suppose $p_1$ takes $s_i$ with $i \neq 1.$ If $p_i$ takes $s_1$ then we have reduced the problem so that the total number of arrangements is just $!(n-2).$ If we forbid $p_i$ from taking $s_1$ then we have reduced the problem to $n-1$ people since each person is forbidden from taking exactly 1 shoe. Since there are $n-1$ choices for $i,$ we obtain the recursion $!n=(n-1)(!(n-1)+!(n-2)).$ Therefore, $!3=2, !4=9, !5=44.$ It follows that there are $44$ arrangements for this case. $\square$

We have a total of $64$ arrangements in these two cases. Hence, there are $128$ total cases by the symmetry noted above. There are $5!^2=14400$ total ways the 5 people could each grab 1 left shoe and 1 right shoe, so our probability is $\frac{128}{14400}=\frac{2}{225}$ yielding an answer of $227.$ $\blacksquare$

For a preliminary visualisation, we call the 5 people $A,B,C,D,E$ , and let the corresponding 10 shoes be $a_l, a_r, b_l, b_r, c_l, c_r, d_l, d_r, e_l, e_r$ , where the subscript refers to left or right . Since $A$ leaves with exactly one of his own shoe, it can be assumed WLOG that $A$ takes $a_l$ , and one right shoe, say for instance $b_r$ . In this case, since $B$ has to leave with exactly one of his own shoe, and his right shoe has been taken by $A$ , $B$ has to take $b_l$ to fulfill the condition. Now, we have 2 cases for the right shoe that $B$ can take:-

(1) $B$ takes $a_r$ . (2) $B$ takes some other right shoe, such as $c_r$ .

It is clear that in case (1), $(A,B)$ forms a set of 2 people such that they both keep 1 of their own shoes (in this case left ) and shuffle their other shoes (in this case right ) such that none of them have their own shoe at the end of the shuffling - in this case for a set of 2 people only, this shuffling refers to simply swapping.

Once this set is formed, we can see that $(C,D,E)$ have to form a set of 3 people, otherwise if $(C,D)$ form a set of 2 people, then $E$ will have to leave with both his shoes, which is not allowed.

In case (2), we can repeat the process for $C$ to show that either $(A,B,C)$ forms a set of 3 people, or $C$ takes $D$ 's shoe (WLOG), and causes all 5 people to form a set (since $E$ cannot form a set on his own, i.e. otherwise he will have to leave with both his shoes, which is not allowed).

From this preliminary observation, it is easy to see that in order for the condition in the question to hold, these 5 people have to form sets of 2 or more people, where a set is defined earlier, in other words, there is no other way to fulfill the condition other than to form sets . And in this respect, there are only 2 possible types of sets to form: (3 people, 2 people) or (5 people).

Now we note that there are a total of $5!$ ways to shuffle the left shoes among the 5 people, and similarly for the right shoes (ignoring any conditions). As such, there are a total of $(5!)^2$ possibly leavings of the 5 people.

Next, we need to count the total number of leavings that fulfill the condition of "each person leaves with exactly one of their own shoes".

To form sets of (3 people, 2 people):-

$\rightarrow$ (1) First we need to choose how to separate the 5 people into the sets : $5 \choose 2$ ways.

$\rightarrow$ (2) Next, for the set of 2 people, we need to decide which shoe ( left or right ) that both people get to keep, then the other shoes' swapping will be fixed automatically: 2 ways.

$\rightarrow$ (3) For the set of 3 people, similarly we need to decide which shoe side to shuffle: 2 ways.

$\rightarrow$ (4) After deciding which side to shuffle, we note that there are $2!$ ways to shuffle it, since the first person has 2 (other peoples') shoes to choose from, and the owner of that second shoe will have only 1 choice left in order to prevent a simple swapping: 2 ways.

To form a set of (5 people):-

$\rightarrow$ (1) Choosing which side to shuffle: 2 ways.

$\rightarrow$ (2) Choosing how to shuffle the shoes, similar to the logic above: $4!$ ways.

Hence, the total number of leavings that fulfill the condition is ${5 \choose 2} (2)(2)(2) + (2)(4!) = 128$ .

Hence probability is $\frac{128}{(5!)^2} = \frac{2}{225}$ and the required answer is $227$ .

Let A be the event that each person leaves with exactly one of their own shoes.

$P(A) = \displaystyle\sum_{n=0}^5 \binom{5}{n} \cdot \frac{!(5-n)}{n!} \cdot \frac{!n}{n!}$

where:

$n$ refers to the number of left shoes that are chosen by their rightful owner; thus, the number of right shoes chosen by their rightful owner is $5-n$ ;

$\binom{5}{n}$ refers to the number of ways that we can choose those $n$ left shoes;

$\frac{!(5-n)}{n!}$ refers to the probability that the remaining $5-n$ left shoes were given to the wrong owner;

$\frac{!n}{n!}$ refers to the probability that the remaining $n$ right shoes were given to the wrong owner; and

$!x$ refers to derangement.

We get the sum of these product for all possible values of $n$ (0 to 5) to get the correct probability.

$P(A)=\frac{2}{225}$ . Thus, $a+b=227$ .

The so-called "dearrangment number" is useful here. Define the $n$ -th dearrangement number, $D_n$ , to be the number of ways to permute $n$ objects such that none of the object is sitting at the original position. We have:

$D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}$

and

$D_n = n D_{n-1}+(-1)^n, D_0=1$

(For more information, check dearrangement on wikipedia. The first relation above can be found using either inclusion-exclusion principle or recursive relations, and the second can be easily deduced from the first.)

Using the recursive relation above, it is easy to find that $D_1=1-1=0, D_2=1, D_3=2, D_4=9, D_5=44$ . Now we go back to the problem.

Among the $5$ people, and for any $k=0,1,\cdots,5$ , if $k$ of them is fixed and exactly they are bound to wear their own left-shoe at the end of the night, then their are $5-k$ people who are bound to wear the wrong left-shoe. This is exactly a dearrangement of $5-k$ objects. Also, the exactly those $k$ people who wear their own left-shoe are bound to wear wrong right-shoes. This is a dearrangement of $k$ objects. Since there are $\binom{5}{k}$ way to fix $k$ people among $5$ , and how the $k$ people wear wrong right-shoes does not affect how the $n-k$ other people wear left left-shoes, we know that the answer is the sum of $\binom{5}{k} D_k D_{5-k}$ , which is equal to:

$1\cdot 1 \cdot 44+ 5\cdot 0 \cdot 9+ 10\cdot 1 \cdot 2 +10\cdot 2 \cdot 1 + 5\cdot 9 \cdot 0 + 1 \cdot 44 \cdot 1$ $= 128.$

Therefore the desired probability is equal to $128/(5!)^2 = 2/225$ , and the answer is thus $227$ .

We name person k's ( $P_k$ ) left shoe to be $L_k$ and right shoe to be $R_k$ , where k = 1,2,..5.

When each person leaves with exactly one of their own shoes, it could mean the following:

1) 0 people get the correct left shoe, and 5 people get the correct right shoe.

2) 1 person get the correct left shoe, and 4 people get the correct right shoe.

3) 2 people get the correct left shoe, and 3 people get the correct right shoe.

4) 3 people get the correct left shoe, and 2 people get the correct right shoe.

5) 4 people get the correct left shoe, and 1 person get the correct right shoe.

6) 5 people get the correct left shoe, and 0 people get the correct right shoe.

Note that cases 2 and 5 are impossible since it is not possible for exactly 4 people to get the correct right/left shoe and the other 1 to get the wrong shoe.

For every possible combination in case 1, if we let $P_k$ to take $L_j$ and $R_i$ instead of $L_i$ and $R_j$ , we get all the combinations in case 6. By doing that to case 6, we get all the combinations in case 1, and thus we call cases 1 and 6 "inverses" of each other. By the same logic, cases 3 and 4 are "inverses" of each other as well. Therefore, there is the same number of cases 1 and 6, and the same number of cases 3 and 4.

We consider cases 1 and 3.

Case 3:

3 people get the correct right shoe, and thus the 2 people that got the wrong shoe must have taken each other's. There are ${5 \choose 3}$ combinations where 3 people get the correct shoe, bringing us to a total of 10 possibilities.

The 3 people that got the correct right shoe have got the wrong left shoe. We call a pair of people that have taken exactly each other's shoes (i.e. A took B's shoes and B took A shoes) as a "switched pair". There is no "switched pair" here as this would mean the third person has the correct shoe. Therefore, out of the three people, the first person A has 2 possible choices (say he picked person B's shoe), and person B would only have a single choice (not A's or B's shoes). The last person obviously only have a choice, which brings us to 2 possible choices in total.

Therefore, there is a total of $10 \times 2 = 20$ possibilities for case 3.

Case 1:

5 people got the correct right shoe, so there is only a single case for this.

When 5 people got the wrong left shoe, there can only be either 0 or 1 "switched pairs". 2 "switched pairs" is not possible as this would mean the fifth guy gets the correct shoe. When there is 1 "switched pair", there is 2 possibilities for the remaining three people to get the wrong shoe (see earlier - case 3). There is also ${5 \choose 2} = 10$ possibilities of getting a "switched pair", so there are $10 \times 2 = 20$ cases where there is a "switched pair". When there are no "switched pairs", there are no three people who have their shoes mixed up internally among them as well (if not, the other two will be a "switched pair"). So, the first person A has 4 possible choices (say he picked B's shoes), B has 3 possible choices (not A or B's shoes - say he picked C's shoes). C has 2 possible choices (not A, B or C's shoes), while the last two people only have a choice each. This brings us $4 \times 3 \times 2 = 24$ possibilities.

Therefore, there is a total of $1 \times (20 + 24) = 44$ possibilities for case 1.

Hence, there is a total of $2 \times (20 + 44) = 128$ cases where each person leaves with exactly one of their own shoes. There is a total of $5! \times 5! = 14400$ possible combinations, so the probability is $\frac{128}{14400} = \frac{2}{225}$ .

First, notice that we can have:

Case 1: 5 people with the correct left shoe and the wrong right shoe

Case 2: 3 people with correct left shoe and the remaining 2 with the correct right shoe and two other symmetric cases with the left and right switched.

Note: no 4 people case since if 4 people gets it right, the last one also gets it right.

Case 1 is counting the number of derangement of 5 objects for the right shoe, which could be done by the inclusion/exclusion principle. It has 44 ways.

For case 2, first choose the 3 people to have their own left shoe, $5\choose 3$ . That implies that the other two people have their own right shoe, which means that these 3 people must have their left shoe swap with one another, which means if the 3 people are A, B and C, they have either B, C, A right shoe or C, A, B right shoe respectively. And the other two people have no choice. So case 2 has ${5\choose 3 }* 2$ ways.

Considering the symmetric cases as well, we get:

$2*(44+{{5}\choose {3}} * 2) = 128$ ways out of a total of $5!^2$

which reduces to $\frac{2}{225}$ .

let the five persons are A,B,C,D,E and they bring a pair of shoes at the first time. we assume that A bring $A_{1}$ for the left shoe and $A_{2}$ for the right shoe and the same assumtion as B,C,D,and E.

first we find the number of ways where 3 people (A,B,C) come to a party that each person leaves with exactly one of their own shoes.

without loss of generality A grabs the correct left shoe (there are 2 ways because in another case A grabs the corect right shoe), so A has 2 ways to grab wrong right shoe. let A grabs B's right shoe, because of that, so B grabs the correct left shoe and C's right shoe. Then C brings the correct left shoe and A's right shoe. So there are 2 $\times$ 2=4 ways

Now we find the number of ways for 5 people. without loss of generality A grabs the correct left shoe (there are 2 ways because in another case A grabs the corect right shoe), so A has 4 ways to grab wrong right shoe. Let A grabs B's right shoe.

Case I

B grabs A's right shoe. C,D,E can swarp their shoes and there are 4 ways . So there are $1 \times 4 = 4$ ways

Case II

B grabs the right left shoe and the other one(3 ways for C,D,E) assume C's right shoe then C grabs right left shoe and A's right shoe. D,E can swarp their shoes and there are 2 ways. So there are $3 \times 2 = 6$ ways for this case

Case III

B grabs the right left shoe and the other one(3 ways for C,D,E) assume C's right shoe then C grabs right left shoe and the other one (2 ways for D,E) assume D's right shoe. then D grabs the correct left shoe and E's right shoe, and the last E bring his left shoe and A's right shoe. So there are $3 \times 2=6$ ways

total ways $2 \times 4 \times (4 + 6 + 6) = 128$ ways

the probality is $\frac{128}{5! \times 5!} = \frac{2}{225} = \frac{a}{b}$ so a+b = $2+225=227$

For details on derangement check here: Derangement
First of all total number of different pairs of shoes possible with 5 left and 5 right shoe $=$ (possible arrangements of left shoe $\times$ possible arrangements of right shoe ) $= 5!\times 5!$ .
Therefore, total possible shoe arrangements = $14400$ .
Now we need to calculate the probability that each person leaves with exactly one of their own shoes. This can done is following ways:
Case 1: All 5 persons leave with their own left shoes but no one wears their own right shoe, so use derangement on their left shoes.
For this, Total possible such cases = $\binom{5}{0} \times !5 = 44$
(!n denotes derangement of n elements)
Case 2: All 5 persons leave with their own left shoes but no one wears their own right shoe, so use derangement on their left shoes.
For this, Total possible such cases = $\binom{5}{5} \times !5 = 44$
Case 3: 3 persons leave with their own left shoe and 2 with their own right shoe. So we derange 3 left shoe and 2 right shoe
For this, Total possible such cases = $\binom{5}{2} \times !3 \times !2 = 20$
Case 4: 2 persons leave with their own left shoe and 3 with their own right shoe. So we derange 2 left shoe and 3 right shoe
For this, Total possible such cases = $\binom{5}{3} \times !2 \times !3 = 20$

Hence the required probability is $\frac {44+44+20+20}{14400} = \frac {2}{225}$ .
Therefore the value of $a+b = 227$

Note that the number of arrangements such that each person picks a right shoe and a left shoe without any other restriction is given by (5^2)(4^2)(3^2)(2^2)(1^2)=14400.

Now, we calculate the number of arrangements auch that each person leaves with their exactly one of their own shoe (referred from now on as the correct shoe). We partition into six cases.

Case A: Each person picks the left shoe as their correct shoe. The number of arrangement is given by the derangement formula 5!(1-1/1!+1/2!-1/3!+1/4!-1/5!)=44.

Case B: Exactly one person leaves with the right shoe as his correct shoe. The derangement formula yields (1!)(1-1/1!)(4!)(1-1/1!+1/2!-1/3!+1/4!)=0 There are five way we can permute the right shoe recipient but it doesn't matter in this case as (0)(5) still yields the answer 0.

Case C: Exactly two persons leave with the right shoes as their correct shoe. Again the derangement formula yields (2!)(1-1/1!+1/2!)(3!)(1-1/1!+1/2!-1/3!)=2. We now calculate the number of ways we can permute the right shoe recipient. Note that there are 5C2=10 such ways. Hence, number of arrangements = (2)(10)= 20.

Case D: Exactly 3 person leaves with right shoe as their correct shoe. Note that by symmetry, the number of arrangement is same as case C =20.

Case E: Exactly four persons leave with the right shoe as their correct shoe. Note that by symmetry the number of arrangement is same as that of case B=0.

Case F: All people pick the right shoe as their correct shoe. Note that the number of arrangement is same as that of case A=44.

By adding all the number of arrangements up, we get. 44+20+20+44=128. Dividing 128 by 14400 yields the probability 2/225. Hence, a+b=2+225=227. Q.E.D.

The Following 4 cases would be the favorable cases in this question:

i) All 5 persons leave with their own left shoes make sure that no one wears their own right shoe, so use derangement ii) 3 persons leave with their own left shoe and 2 with their own right shoe make sure to derange 3 left shoe and 2 right shoe iii) 2 persons leave with their own left shoe and 3 with their own right shoe make sure to derange 2 left shoe and 3 right shoe iv) All 5 persons leave with their own right shoes make sure that no one wears their own left shoe, so use derangement

with total no of cases being $5!\times5!$

Hence the expression becomes { $C(5, 0)\times44$ + $C(5, 2)\times1\times2$ + $C(5, 3)\times1\times2$ + $C(5, 5)\times44$ }/{ $5!\times5!$ } = 2/225

a + b = 227

according to the given situation.......... there can be four cases that we can think of firstly if all of them take their shoes with them(RIGHT,NO LEFT) Then,all five of them can TAKE their LEFT ONES (NO RIGHT) Then two people take their left and three right then last we can take three people left shoes and 2 people right

now go on and add all the cases we made using your knowledge of binomial theorem........

[5C0 44+5C2 2+5C3 2+5C5 44]/(5FACTORIAL)^2

SOLVING THIS WE GET 2/225

hence a+b=227

5 people attend a party and now the question talks about different conditions so we make different cases for this kind of problems 1. all of the people leave with their right shoes 2.same but with left ones now 3.3 left and 2 right 4.3 right and 2 left

now, accordingly by the use of binomial theorem [5 C 0 44+5 C 2 1 2+5 C 3 2+5 C 5 44]/5! 5! WE GET 2/225

therefore a+b=227 hence this is the solution

Here we will do casework on the number of people leaving with the correct left shoe.

Case 1: Everybody leaves with the correct left shoe. Then we must make sure that nobody leaves with the correct right shoe. Each way this happens corresponds to a derangement--a derangement is a permutation of a set of numbers so that no number is permuted to itself. You can read more about derangements by searching it on Google; for now we will use the recursive formula $!n=(n-1)(!(n-1)+!(n-2))$ where $!0=1$ and $!1=0$ , which isn't hard to show. Since nobody leaves with the correct right shoe, the number of ways that this case could happen is simply $!5$ , which can be calculated to be 44.

Case 2: Four people leave with the correct left shoe. In this case, exactly one person must leave with the wrong left shoe. This is impossible, for after four people choose their own left shoe, the last person has no choice but to choose his own left shoe.

Case 3: Three people leave with the correct left shoe. The two people that leave with the wrong left shoe must leave with their correct right shoes. Thus the three people with the correct left shoe must have a derangement of right shoes, and similarly the other two people must have a derangement of left shoes. This gives $!3\cdot !2=2\cdot 1=2$ ways. However, there are 10 ways to choose 3 people to leave with correct left shoes, so there are a total of $20$ ways that this case could occur.

Case 4: Two people leave with the correct left shoe. Then similarly three people must leave with the correct right shoe. This is analogous to Case 3, so this case has $20$ possibilities.

Case 5: One person leaves with the correct left shoe. Then four people must leave with the correct right shoe, which is analogous to Case 2, which has no possibilities.

Case 6: Nobody leaves with the correct left shoe. This is analogous to Case 1, which had $44$ possibilities.

Thus there are a total of $44+20+20+44=128$ ways that these 5 people could leave with exactly one of their shoes. Since we are looking for the probability, we must divide this number by the number of ways for them to grab the shoes-- $(5!)^2$ . Hence the probability is $\dfrac{128}{14400}=\dfrac{2}{225}$ , and $a+b=227$ .

Consider cases. The number of people that get their own left shoes can be either $0,2,3,5$ , since if 4 people get the correct shoe of one type, the fifth person must also.

If $0$ get their left shoe, all must get their right shoe. Probability of that is $\frac{1}{5!}$ . Probability that none get left shoe: either a 5 cycle, or a 2-cycle and a 3-cycle. $4!$ possible 5-cycles. $\binom{5}{2}$ possible 2-cycles and 2 possibilities for the corresponding 3-cycle. So the probability here is $\frac{4! + 2\binom{5}{2}}{(5!)^2} = \frac{44}{14400}$ .

If $2$ get their left shoe, the other $3$ must get right shoe. $\binom{5}{2}$ ways to choose who gets their left shoe. $2$ ways to give the other left shoes out. Only one way to give out the right shoes ( $3$ get their own and other two swap). So $20$ ways total give probability $\frac{20}{(5!)^2} = \frac{20}{14400}$ . We have the same situations for $3$ as we did for $2$ , and the same for $5$ as we did for $0$ , so the total probability is $\frac{128}{14400} = \frac{2}{225}$ . Hence, $a+b = 227$ .