Using your Head is Permitted

December 2013 solution

This month, the solutions sent to me (both correct and incorrect) were quite varied. A popular upper bound proved was 2/3. I will mention in particular a solution by Radu-Alexandru Todor. The 2/3 bound was proved there very elegantly by showing an injective mapping from the set of ID allotments in which some employee, E, receives exactly one present to the set of ID allotments in which that employee receives none. From this, one can conclude that the expected portion of employees who receive no presents is at least as high as the expected portion of those who receive exactly one, and from here the 2/3 bound can be derived directly. The solution did not use the graph's undirectedness property, but merely the fact that each vertex has at least 2 out-going edges. Radu's solution stands out in that he proved this 2/3 bound to be tight, by constructing a (directed) graph that reaches it exactly. This is the directed cycle with self-loops. For undirected graphs, I am not familiar with a solution that is quite as elegant as this, or that reaches numerical results that are as clean, but the upper bound is, nevertheless, tighter than 2/3. To show it, let us first off change a little the rules of the game. Instead of allotting the numbers 1 through N out of a hat, let each employee pick, independently and uniformly, a real number in the range [0,1]. I claim that keeping all other rules of the game as they are leads to the same distribution of presents.

To see this, consider a relaxation of the original problem where we omit the requirement for the graph to be connected. Now, add M isolated vertices. By taking M to infinity (and dividing each number in the hat by N+M), the original rules of the game become the new ones. Clearly, the addition of the isolated vertices does not affect the question of which of the original N players received a present, so we can safely ignore them.

With these new rules, let us now begin by proving the 0.75 bound.

Consider how many presents are sent to employees whose ID is in the range [0,0.5]. For such a present to be sent, both the sending employee and all of her LinkedIn connections (of which there is at least one) must have IDs in this same range. The expected number of such presents is therefore never more than N/4. This being the number of such presents, clearly the number of employees whose number is in this range who receive presents cannot be larger. Even if all other employees receive presents, there is only an expected N/2 of them, leading to the desired 3/4 N upper bound in total.

(I will remark at this point that all the correct solutions I've seen make, at some point, this leap between "expected number of presents" and "expected number of employees". The majority of incorrect solutions this month try to prove exactly the same claim but going directly for the number of gift-receiving employees, and, in order to do so, invariably rely on incorrect steps in the probabilistic rationale. In this particular case both camps tended to reach the same conclusion, but it is not difficult to construct a question where this particular type of derivation error leads to incorrect results.)

To get to a bound tighter than 3/4, consider that the 3/4 N bound required every employee to have only one LinkedIn connection. For any employee with d LinkedIn connections, the probability that this employee will be sending out a present to someone whose ID is in [0,0.5] drops from 1/4 to 2-(d+1). On the other hand, for any employee with d LinkedIn connections, the probability that this particular employee will receive a present is never more than d/(d+1), because there is a 1/(d+1) chance that this employee will have a lower ID than any of its connections, a case in which the employee will surely not receive any present. In a situation where (almost) all employees have exactly one connection, the upper bound is therefore really 1/2.

One can therefore take p1 to be the percentage of employees who have exactly one connection, and calculate the two bounds above given p1. The real bound would be the minimum of the two bounds, and the best bound is the maximum value of this minimum over the entire range of possible p1 values. This happens to be when the two bounds are equal to each other.

This leads to the equation

0.625+0.125 p1 = 1-0.5 p1,
where the left side is the result of the original bound given p1 and the right side is the new bound. This leads to p1 = 0.6 and an improved bound of 0.7.

The 0.7 bound can be improved further, by noting that the original threshold value picked (0.5) is not necessarily optimal. Whereas 0.5 was optimal for the original choice p1=1, for a general p1 value we can do better. Optimally, one counts the number of presents sent to people with ID x for those x values that receive less than one present, in expectation, and one counts the people (whether or not they receive presents), otherwise. This makes the bound tighter.

A final improvement can be done by parameterizing also by the percentage of employees with other d values. This adds infinitely many parameters pd that need to be optimized, but using Lagrange multipliers it is possible to show that at most 2 of them can be nonzero at the optimum. Add to this the fact that they need to sum to 1, and we have only two parameters to play with: p1 and d.

Putting all this together, the best upper bound I know of is approximately 0.63319213231789395, which is about midway from the original 3/4 bound to the highest-value graph that I've been able to construct, and is a marginal improvement over the 2/3 bound. (The best graph will be given in the Ponder This solution.)

Back to riddle

Back to main page