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
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