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
2 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

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,,10}\{1, 2, 3, \dots, 10\}: π(1)=9,π(2)=10,π(3)=8,π(4)=6,π(5)=4,π(6)=1,π(7)=7,π(8)=3,π(9)=5,π(10)=2. \begin{aligned} \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{aligned} (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).(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}\{1, 2, 3, 4, 5\}: Cycle TypeNumber of Permutations1,1,1,1,111,1,1,2101,1,3201,2,2151,4302,320524 \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 11+102+203+152+304+203+245120=13740.\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 nn 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 - 2 years, 10 months ago

Log in to reply

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 - 2 years, 10 months ago

Log in to reply

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

Manuel Kahayon - 2 years, 10 months ago

Log in to reply

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

Manuel Kahayon - 2 years, 10 months ago

Log in to reply

I got that by considering the cycle which person 1 is in. AMAZING! It's 1+12+13++1x1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{x} :D

Manuel Kahayon - 2 years, 10 months ago

Log in to reply

Well done!

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

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

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

Finally, summing over 1kn1 \le k \le n, we find that the expected number of cycles is 1+12+13++1n.1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}.

Jon Haussmann - 2 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...