Waste less time on Facebook — follow Brilliant.
×

An exchange gift breakdown

I don't know how to answer the following, so here goes.

10 people decide to exchange gifts, in the following manner:

All 10 people write down their names on pieces of paper, and along with their names go their gift preferences.

They put the names in a box and then each person randomly picks out a name from the box.

They then give their gifts to the person whose name they drew from the box. If a person draws his own name, then he gives his gift to himself.

Now, if Anne gives his gift to Bob, and Bob gives his gift to Charles, and Charles gives his gift to Anne, then Anne, Bob and Charles are said to be in a chain, with 3 members.

Now for the million-dollar question:

What is the expected length of the longest chain in the group?

Note by Manuel Kahayon
7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

I don't know how much you know about permutations, so I'll start from the basics. Consider the following permutation \(\pi\) on the set \(\{1, 2, 3, \dots, 10\}\): \[ \begin{align*} \pi(1) &= 9, \\ \pi(2) &= 10, \\ \pi(3) &= 8, \\ \pi(4) &= 6, \\ \pi(5) &= 4, \\ \pi(6) &= 1, \\ \pi(7) &= 7, \\ \pi(8) &= 3, \\ \pi(9) &= 5, \\ \pi(10) &= 2. \end{align*} \] (This is just like assigning names to people, except we're using numbers. In other words, imagine we assign a number from 1 to 10 to everyone.) One way to work with a permutation is to write down its cycles. So for the permutations above, \(\pi\) takes 1 to 9, 9 to 5, 5 to 4, 4 to 6, then 6 back to 1. Similarly, it takes 2 to 10 and 10 to 2, 3 to 8 and 8 to 3, and 7 to itself. So we can write down the cycles of the permutation \(\pi\) this way: \[(1, 9, 5, 4, 6) (2, 10) (3, 8) (7).\] This representation is known as the cycle decomposition of a permutation. Your question is to determine the expected length of the longest cycle in a random permutation.

To do so, we can list all the cycle types, and how many permutations there are of each type. The cycle type refers to the length of the cycles in the permutation. For the example above, the cycle type is 1, 2, 2, 5, because there is one cycle of length 1, two cycles of length 2, and one cycle of length 5.

This is what the table would look like for permutations on the set \(\{1, 2, 3, 4, 5\}\): \[ \begin{array}{cc} \text{Cycle Type} & \text{Number of Permutations} \\ \hline 1, 1, 1, 1, 1 & 1 \\ 1, 1, 1, 2 & 10 \\ 1, 1, 3 & 20 \\ 1, 2, 2 & 15 \\ 1, 4 & 30 \\ 2, 3 & 20 \\ 5 & 24 \end{array} \]

So for 5 people, the expected length of the longest cycle is \[\frac{1 \cdot 1 + 10 \cdot 2 + 20 \cdot 3 + 15 \cdot 2 + 30 \cdot 4 + 20 \cdot 3 + 24 \cdot 5}{120} = \frac{137}{40}.\] Everything would be done similarly for 10 people; once you determine the numbers in the table, the rest is a routine calculation.

Having said all this, I doubt there is any nice, general formula for your problem, i.e. one that would generalize to \(n\) people. You could consider the expected number of cycles in a random permutation; it turns out that this question has a relatively nice answer. Jon Haussmann · 7 months ago

Log in to reply

@Jon Haussmann I got that by considering the cycle which person 1 is in. AMAZING! It's \(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{x}\) :D Manuel Kahayon · 7 months ago

Log in to reply

@Manuel Kahayon Well done!

Here is a simple counting proof. Let \(n\) be the number of people, and let \(1 \le k \le n\). We count the number of \(k\)-cycles (cycles of length \(k\)) among all \(n!\) permutations.

First, we determine the number of different possible \(k\)-cycles. There are \(\binom{n}{k}\) ways to choose the \(k\) numbers to go into the \(k\)-cycle, then \((k - 1)!\) ways to arrange them to form a \(k\)-cycle. This gives \[\binom{n}{k} (k - 1)!\] possible \(k\)-cycles.

Now, each particular \(k\)-cycle appears in \((n - k)!\) different permutations (because there are \(n - k\) elements remaining), so the expected number of \(k\)-cycles is \[\frac{\binom{n}{k} (k - 1)! (n - k)!}{n!} = \frac{1}{k}.\]

Finally, summing over \(1 \le k \le n\), we find that the expected number of cycles is \[1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}.\] Jon Haussmann · 7 months ago

Log in to reply

@Jon Haussmann \(\large E(x) = \frac{\displaystyle \sum_{i=1}^{x-1} E(i) + x}{x}\) ? Manuel Kahayon · 7 months ago

Log in to reply

@Jon Haussmann Oh, thanks, I understood everything you said :D

But what about the expected number of cycles? Can you please give a hint? O.o Manuel Kahayon · 7 months ago

Log in to reply

@Manuel Kahayon Oh, wait, I'm getting a nice formula... Manuel Kahayon · 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...