By genius's implicit request, here is my solution, belatedly:
**********************************************************
THE DON'S PROBLEM
"Each of n elderly dons knows a piece of gossip not known to any of the others. They communicate by telephone, and in each call the two dons concerned reveal to each other all the information they know so far. What is the smallest number of calls that can be made in such a way that, at the end, all the dons know all the gossip?"
1. Let P(n) be the minimum number of conversations necessary to effect a complete dissemination of all gossip.
2. Let D(n) be a minimum-length sequence of conversations in which n dons disseminate all gossip. There will be P(n) conversations in D(n).
3. Let K(n) be the set of dons. It has n elements.
4. Represent each conversation in D(n) by a pair (m,n) of elements of K(n) (dons).
5. Each conversation (mj, nj) has two "immediate successors", namely (mj+1, n) and (mj, nj+1). Similarly, each has two immediate predecessors (mj-1, nj) and (mj, nj-1).
6. If (c, d) follows (a, b) at some point in D(n), then we say (a, b) -> (c, d)
7. To disseminate all gossip completely, it is necessary and sufficient that for each (a, b), (c, d): (a, b) -> (c, d) (i.e. everyone's information reaches everyone else.
8. Given any D(n), the reverse of this also satisfies the conditions of the don's problem.
9. Given a finite set A, I use val(A) to denote the number of elements in A.
THEOREM.
For all n > 3, P(n) = 2n - 4.
Proof.
Let K(4) = {a, b, c, d}. Then one possible D(4) is {(a, b), (c, d), (b, c), (a, d)}. Clearly this may be done in other ways, but in no way can four dons disseminate their gossip in three or fewer conversations. So P(4) = 2n - 4. Now all gossip may be exchanged among the dons in K(5) by adding (a, e) to either end of the above D(4), giving one possible D(5). This gives 6 conversations sufficient for five dons. By repeatedly applying this method, we see that in general P(n) = P(n-1) + 2 = 2n - 4. Thus 2n - 4 conversations are sufficient, but not necessarily necessary, for complete gossip among the dons.
QED
THEOREM.
For all n, P(n) = 2n - 4.
Proof.
We will proceed by induction on n. As a basis, note that for n=1,2, 2n - 4 < 0, so it must be true for those values. Beyond that, assume it holds for all integers up to n-1. The possibilities for the conversation configuration for a given n can be divided into six cases.
In the first case, each don has at least four conversations. Thus the total number of conversations is at least 2n > 2n - 4, so it holds in this case.
In the second case, there exists some m ( K(n) such that m is involved in only one conversation, say (m, y). Thus in addition to (m, y), n - 2 conversations are necessary to propagate m's gossip. However, to get all gossip to y before (m, y) requires at least n - 2 more, for a total of 2n - 3 conversations.
The third case is that in which, given some m,p ( K(n), there are at least two conversations between them. Then if we remove all conversations between m and p from D(n), and replace m by p wherever it appears. Then we have a set of conversations that suffices to spread all gossip from the other n - 1 dons, i.e. D(n-1). By the induction hypothesis, P(n-1) = 2n - 6, so P(n) = 2n - 4.
A very similar argument suffices for the fourth case, in which there exists some conversation (m, y) where y already knows all gossip.
At this point, we know that if (m, p) is m's first or last conversation, then it is p's as well.
In the fifth case, there exists some m such that m has precisely two conversations, and that the cases 2,3,4 do not apply. Then the two conversations are (m, p) before (m, k). Now (p, q) is the immediate successor of (m, p), and (k, l) the immediate predecessor of (m, k). Since (m, p) is the first conversation of m and p, m can only communicate to all dons but m, p, k, through (k, q), taking n-3 conversations. Similarly, to do it through (k, l) takes n-3. If the two sets of conversations traversed in doing this are disjoint, we have 2n - 6 conversations, plus (m, p) and (m, k), for a total of 2n - 4. If they are not disjoint, then the fourth case applies.
The final case that remains is that in which there exists some don m that is in three conversations, and all others are in at least three. Say the three conversations with m are, in order of occurrence, (m, b), (m, c), (m, d). Say each has the respective immediate: successor (b, H), successor (c, G), precursor (d, Y). Let J, K2 be the sets of conversations reached from (m, b) and (m, c) respectively. Let K1 and F be the sets of conversations leading to (m, c) and (m, d). Except for K1 and K2, none of these sets has an element in common. If we were to substitute (b, c) for (m, c), and eliminate (m, b) and (m, d), then the gossip of n-1 dons is disseminated, and by the induction hypothesis, P(n) = 2n - 4. Now note that val(J U K2) = n-2 and val(F U K1) = n - 2 Then, because of the one element shared by K1 and K2,
val(J U K1 U F U K2) = val(J U K2) + val(K1 U F) - 1 = 2n - 5.
Now look at what happens if (q, p) ( J U K2 and q learns m's gossip. Then if (r, q) is before (q, p), then (r, q) ( F U K1. Since q makes = 3 conversations, (r, q) is not a first conversation, so each end conversation in J U K2 has a corresponding, non-first conversation in F U K1. Therefore val(F U K1) = n. Therefore val(J U K1 U F U K2) = n - 2 + n -1 = 2n - 3. Thus P(n) = 2n - 4 for all n.
QED
Since for all n = 4, P(n) = 2n - 4 and P(n) = 2n - 4, we can conclude that P(n) = 2n - 4. Thus the dons may communicate all of their gossip in 2n - 4 conversations, provided that there are at least four dons present.
~Mark
*********************************************************