1. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    10 Dec '02 00:13
    Originally posted by royalchicken
    "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.)
    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.

    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!😀)
  2. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    10 Dec '02 20:56
    "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).
  3. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    10 Dec '02 21:04
    i'll shut up about it until i make some progress 🙂
  4. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    14 Dec '02 02:04
    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.
  5. Joined
    30 Nov '01
    Moves
    4207
    20 Dec '02 20:07
    What is the Dudney puzzle ?
  6. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    21 Dec '02 19:34
    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...).
  7. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    22 Dec '02 21:41
    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.
  8. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    23 Dec '02 01:16
    Originally posted by royalchicken
    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.
    Congratulations! 😀😀😀

    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. 😉
  9. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    23 Dec '02 17:21
    thank you for your encouraging post. that website is quite funny. what is a Fields medal (it sounds impressive)?
  10. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    23 Dec '02 17:30
    i read the "mathmo test" at that website. it is ammusingly accurate. as to cambridge, i certainly will.
  11. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    23 Dec '02 23:15
    The Fields medal is the most prestigious prize in mathematics (stupid Nobel 😠). It's awarded once every four years, to exactly 4 mathematicians. To be eligible, you must also be under 40, so it's no 'lifetime achievement award'. Prof. Gowers won one in 1998.
  12. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    24 Dec '02 01:262 edits
    tell him 'grats. There is no Nobel in math(s) because Mittag-Leffler had an affair with Nobel's wife, correct?
  13. Donationtom
    Missing in action
    Joined
    26 Feb '01
    Moves
    1565
    17 Jan '03 14:45
    I hate to disparage such luminaries, but you're all wrong.

    The answer is simply 1. Have none of you ever heard of conference calls?
  14. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    17 Jan '03 17:37
    I'm a luminary? Kewl 😉. Seriously, though, what is the minimum number of conversations required if the conversations are one-way (like email, for example)?
  15. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    23 May '03 19:55
    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

    *********************************************************
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree