×

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
1 year, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

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.

- 1 year, 3 months ago

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

- 1 year, 3 months ago

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}.$

- 1 year, 3 months ago

$$\large E(x) = \frac{\displaystyle \sum_{i=1}^{x-1} E(i) + x}{x}$$ ?

- 1 year, 3 months ago

Oh, thanks, I understood everything you said :D

But what about the expected number of cycles? Can you please give a hint? O.o

- 1 year, 3 months ago

Oh, wait, I'm getting a nice formula...

- 1 year, 3 months ago