Gift Exchange

There were 5 family members who each brought their own gift, and then the 5 gifts were exchanged within the family.

How many ways could they have exchanged the gifts such that none of them got their own?


The answer is 44.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

There are 2 2 scenarios that would suit the conditions:

  1. The gifts were exchanged in a group of 3 3 people and another a group of 2 2 people.
  2. The gifts were exchanged in a ring of 5 5 people.

Let's consider the former case first: there are ( 5 3 ) = 5 ! 3 ! 2 ! = 10 \binom{5}{3} = \dfrac{5!}{3!2!} = 10 ways to separate 5 5 into groups of 3 3 and 2 2 people. Then within the pair of people, there is only one way they can exchange gifts.

Now for group of 3 3 people, there are ( 3 1 ) ! = 2 ! = 2 (3-1)! = 2! = 2 ways to exchange gifts in the ring of 3 3 people. Alternatively, we can rethink the scenario as joining the vertices of a triangle without repeating the line twice, and there are only 2 2 possible ways to draw a triangle as shown below:

As a result, for the first scenario, there are 10 × 2 = 20 10\times 2 = 20 ways to exchange the gifts.

Now within the ring of 5 5 people, it is as if everyone was getting in a circle and passed the gift to the person to their right. Again, we can rethink of the scenario as joining the vertices of a pentagon:

So first, the first person (A) has a choice of 4 4 gifts to choose from, and when one is chosen, the owner of that chosen gift will make the next choice. However, he or she can't choose A's gift as it will form a ring of 2 2 people as previously done, so that person will have 3 3 choices left to choose. Continuing on like this, we can calculate the combinations as ( 5 1 ) ! = 4 ! = 24 (5-1)! = 4! = 24 ways.

Finally, there are 20 + 24 = 44 20+24 = \boxed{44} ways they can exchange gifts among the 5 5 people.

Geoff Pilling
Dec 27, 2016

This can be solved by the derangement formula:

! n n ! ( 1 1 1 ! + 1 2 ! 1 3 ! + + ( 1 ) n 1 n ! ) = n ! k = 0 n ( 1 ) k k ! !n \equiv n! \left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+ \cdots +(-1)^n\frac{1}{n!}\right) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}

! 5 = 44 !5 = \boxed{44}

Using the derangement formula = 5 ! ( 1 1 1 1 + 1 2 1 6 + 1 24 1 ) = 120 ( 11 30 ) = 44 5!(\frac{1}{1} - \frac{1}{1} +\frac{1}{2} - \frac{1}{6} + \frac{1}{24} -\frac{1}{}) = 120(\frac{11}{30}) = 44

Sir you made a mistype here : 120 ( 11 30 ) = 265 120 \left( \dfrac{11}{30} \right) = 265 .

Tapas Mazumdar - 4 years, 1 month ago

Log in to reply

Thanks. I edited my solution.

A Former Brilliant Member - 4 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...