Mathy MSCHF [solution]
Solution for the week of 7/13
In July 13th’s puzzle, we got a taste of the math problems art collectors face…
In an alternate universe, MSCHF takes a slightly different route with their King Solomon’s Baby project. They now are offering up pieces from 10 identical giant styrofoam babies. Each styrofoam baby is identically cut up into 15 pieces. 10 lucky buyers are going to each be given 15 random pieces from the combined collection of 150 pieces (10 babies * 15 pieces per baby). You decide that you’re going to get your friends involved so that after you all receive your pieces, you will collectively have a complete set. The question is, how many of the 10 recipients need to be your friends in order for there to be >50% chance of having a complete baby set between the group of friends?
The remainder of the recipients are jealous of your scheme and decide they will try and trade the other recipients to get a complete set of their own. Recipients have no idea what other’s have so they pick their potential trading partners completely at random. Trades aren’t limited to one piece. In fact, trading partners will always maximize their trades. So for example, if person 1 has 2 belly buttons and 2 right butt cheeks and doesn’t have any left eyes or mouths while person 2 has no belly buttons or right butt cheeks but has 2 left eyes and 2 mouths, they will end up trading a belly button and right butt cheek for a left eye and mouth. On average how many items will two random participants trade with each other assuming neither has traded at all yet?
Thanks to Peter Ji for his correct submission. You can check it out here.
The first key observation to make about this problem is that employing k of your friends is identical to the situation where you, yourself are allowed to draw k*15 pieces. So the total number of ways of drawing your collective pieces is
We’ll write our equation with n and m for generality where n represents the number of styrofoam babies being divided and sold (10 in this case) and m is the number of pieces each is divided into (15 in this case).
So how many of these possible drawings result in at least one complete set? As is so often the case, the trick to this problem is defining the right variable. Let’s first reframe the problem a little bit
Of course, there are many ways a set can be incomplete. We could be missing a single piece or we could be missing many. For now, let’s image we are missing one piece; even in this case, it still isn’t obvious (at least to me) how many ways there are to draw while missing any one piece of the complete set. So let’s consider an even more constrained situation—the number of ways of drawing where we know one specific piece is missing. This is much easier. This situation is analogous to drawing from a subset of the complete pool that is missing every instance of that specific piece. Thus, the number of ways of this happening is
We can generalize this further. If we image missing a specific set of i pieces, we can employ the same logic to count the number of ways of that happening
Some of you may recognize that we now have everything we need to employ the inclusion-exclusion principal. For the uninitiated, we may be tempted to jump the a final expression
But this would be a mistake. If we consider the first term, there are m ways to choose 1 specific piece to be missing and the probability of that piece missing (the fraction above) is written correctly. The problem emerges when we multiply these together. As we stated above, the multiplication is a way of summing over all possible choices of 1 object from m. but summing probabilities is only valid when the events are mutually exclusive. So are these event mutually exclusive? Does missing one particular piece mean you necessarily have all other pieces? Of course not! You may be simultaneously missing multiple pieces, so these event are not mutually exclusive and we end up overcounting the number of ways that we can be missing pieces. And this only the first term. the same issue exists with each subsequent term as well.
Thankfully the Principal of Inclusion-Exclusion (PIE) comes to our rescue. More generally, PIE describes how we can count the number of elements in the union of multiple sets. Without getting too bogged down in the details—which we’ve covered in the past—PIE provides us with the factor we need to correct our count. Applying it here, we get
Now we just find the first value of k where the probability exceeds 50% which happens to be 3.
This second part was overly ambitious and neither I nor any solvers found a way to do it analytically. Simulation reveals that the answer is ~2.26 items traded (or ~1.13 trades).
Determining the probability of exactly one swap isn’t too hard but figuring out the probability of more than one swap get’s very complicated very quickly and most analytic approximations didn’t get as close I would like. A little tinkering with approximations using hypergeometric covariance helped get a close analytic-ish approximation but it’s inelegant and beyond the scope of this puzzle.
I hope you all enjoyed! Till next time!