The Spaghetti
This is a level 2 question which should take approx. 4 minute in the interview
A bored young man has before him a plate containing 100 spaghetti. He decides to knot them to form loops. To do this, he starts by taking two spaghetti ends that protrude, at random, and knots them together. He repeats this operation until all the spaghetti have been knotted.
At the end of this process, how many loops has he made on average?
Try to solve this problem yourself before moving on to the solution below. Use hint if needed
.
.
.
Hint
One can consider the moment when the player’s success rate goes over 75%.
.
.
.
.
Solution
Let us denote bn as the average number of loops that the young man creates with a plate of n spaghetti. Thus, b1 = 1, and we seek b100. Let us consider a plate of spaghetti with n 2. For his first knot, the young man either ties a spaghetti to itself or the two spaghetti to each other. In the first case, the spaghetti is eliminated: there will be on average bn−1 + 1 loops. In the second case, everything happens as if the plate only had n-1 spaghetti on it: there will be on average bn−1 loops. The probability that the first spaghetti tied formed a loop is 1/(2n−1): indeed the young man chose
the first end at random and then has 2n - 1 choices for the second. The average number of loops is thus
which means that for large n,
ln(n)/2 is a good approximation of bn. We say that bn is on the order of ln(n)/2 . The growth of bn is logarithmic, and thus much slower than one might have thought.
.
.
😃 Your turn: Managed to crack this one?
👉 If you enjoyed this post, please consider leaving a like ❤️. Your support boosts visibility on Substack, helping more readers find this newsletter. Just hit the button at the bottom of this email.
👉 If you're loving this newsletter, why not share it with your friends? They might enjoy it too!