Originally posted by royalchickenIn any graph, the sum of the degrees of the vertices is twice the number of edges. It follows
"I think we're going round in circles here. This system is SUFFICIENT to get the
dons to
communicate the gossip in 2c - 4 conversations. I don't think you've shown that this
particular system is NECESSARY for all c >= 4. "
i am aware. this is what i am having difficulty showing.
i expressed myself poorly about vertices of odd degree. i ...[text shortened]... ory existed
until four days ago, when this problem prompted me to read a book on the subject.)
that any graph will have an even number of odd vertices. But I don't see how this
demonstrates 2n-5 is impossible.
I'm sorry if I've come across a bit negative in recent posts. I suspect the result you are
trying to prove to be false, however I don't have any firm evidence to support this, nor do I
have an alternative proposition. I got no further on this problem than you have.
Arguably the best mathmo in my year at college said, when I asked him about the dons
problem, 'Oh, I sweated blood for a year over that, so I'm not going to try again now.'
There's nothing wrong with trying (in fact you can learn much by trying hard and failing), but
if you don't get anywhere with this problem, don't be too disappointed; I've been assured by
several people that it's MUCH harder than it looks. At least with this problem, unlike the
Collatz conjecture, some people have definitely managed to solve it before (though if you
sent in a correct solution to the University, they'd be pretty impressed!😀)
"In any graph, the sum of the degrees of the vertices is twice the number of
edges. It follows
that any graph will have an even number of odd vertices. But I don't see how this
demonstrates 2n-5 is impossible."
it doesn't, yet. i was unaware that the sum of the degrees of all vertices of
some graph will be twice the number of edges. now that i think about it, it is
pretty obvious (one of those things that you don't think of until it seems
important or someone else tells you).
i have a solution (emailed it to Acolyte). gave up on the graph approach,
looked at the conversation chains themselves. 2n - 4 IS optimum. Acolyte
rightly considers it difficult because the proof of this is rather hairy. (my
proof is rather inelegant and brutish, but works). i can attest to the
difficulty of this problem, because over the past few days i have actually been
approached by acquaintences extolling the virtues of sleep, and recommending it.
i admire the fact that you must have slogged through the whole thread to find that tidbit. H.E. Dudeney (1847-1930, according to the copy of one of his books i have) wrote a large number of puzzles of the sort discussed in this forum. they are collected in several books, my favorite being "the canterbury puzzles" (like chaucer, only i would maintain more interesting...).
Originally posted by royalchickenCongratulations! 😀😀😀
Acolyte-I just recieved an email from prof. Gowers. He didn't want to spoill his own fun (he wants to solve it sometime), so he gave it to one Imre Leader, who has solved it, who deemed my solution correct. Thanks for presenting such an interesting problem and discussing it.
Prof. Gowers has a Fields medal, for heaven's sake! And if you want to know who Imre Leader is, try going here:
www.geocities.com/imre_leader_appreciation_society/
I'm going to have to tell Tim Austin (scary first-year mathmo at my college) about this. When he hears how long your proof was, he will hang his head in shame! Seriously though, if/when you read maths at university, apply to Trinity College, Cambridge - THE place to be for mathematics. 😉
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
*********************************************************