# The dons problem

Acolyte
Posers and Puzzles 25 Oct '02 22:29
1. Acolyte
25 Oct '02 22:29
This isn't my problem, it was given to me by my one of my lecturers. Rumour has it that
you can count the number of undergraduates in the whole of Cambridge who've cracked this
one on one hand. Here goes...

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?
2. 25 Oct '02 22:44
from the stomach: 2n-3 ?
Gil.
3. Acolyte
25 Oct '02 23:19
Sorry if I didn't make this clear... I don't know the answer and don't really want to find it out
unless I work it out myself (very, very unlikely). So I probably shouldn't have posted it here.
It's just a problem I thought people might find interesting, that's all. By the way genius,
here's a chance to earn your nickname ;-).
4. royalchicken
CHAOS GHOST!!!
03 Dec '02 22:593 edits
if &quot;genius&quot; wishes to earn his nickname, he may attempt the following. if we
pick a positive integer, c(1) (the n is a subscript), and let:

'''''''''''''''' / c(n)/2 if c(n) = 0 (mod 2)
c(n+1)= |
''''''''''''''''' \ 3c(n)+1 if c(n) = 1 (mod 2)

the problem is to show that for any c(1), there will always be some positive
integer k such that c(k) = 1. try the first few integers, and see how this
conjecture is motivated. i have made some serious progress on this, which is of
a detailed nature and i will describe it if anyone is interested. however, it
is very difficult. if &quot;genius&quot; can prove this, he will have earned his
nickname. i'll have the answer to the &quot;dons problem&quot; shortly.

~mark (royalchicken)
5. genius
Wayward Soul
04 Dec '02 19:29
Originally posted by royalchicken
if "genius" wishes to earn his nickname, he may attempt the
following. if we
pick a positive integer, c(1) (the n is a subscript), and let:

'''''''''''''''' / c(n)/2 if c(n) = 0 (mod 2)
c(n+1)= |
''''''''''''''''' \ 3c(n)+1 if c(n) = 1 (mod 2)

the problem is to show that for any c(1), there will alwa ...[text shortened]... his
nickname. i'll have the answer to the "dons problem" shortly.

~mark (royalchicken)
going by this post, i'm not sure if i can do it on my limited maths base
(i'm only in 5th year, and were just doing calculus, and i'm trying to
read up on the theory behind it plus do the actual homework...which is
simple, by anyway). i'll try the problem, but give me time-i've got too
much on...

G
6. royalchicken
CHAOS GHOST!!!
04 Dec '02 21:40
sintubin has a remarkably astute stomach. the gossiping don's can always do it
in 2N-3 moves (i think this is optimum). if the dons are numbered 1-N, and Don
1 (not an epic by Byron) speaks to all of the others, then Dons 1 and N will
know all of the gossip, and N-1 conversations will have taken place. Now each
of the other Dons is missing some of the gossip. so Don 1 or Don N has a
conversation with each, filling in all of the gaps. this will take N-2
conversations, for a total of 2N-3. would that i were endowed with such an
intelligent duodenum...

genius-i was not entirely fair to you (although, as you are one year my senior,
i feel no need to be particularly gentle). the problem i gave is the Collatz
conjecture-one of the outstanding unsolved problems of mathematics. i have only
made progress with a fairly good knowledge of analysis (calculus et al) and
number theory. i have yet to prove it, though. give it a go-it is infectiously
interesting.
7. Acolyte
04 Dec '02 23:59
sintubin has a remarkably astute stomach. the gossiping don's can always do it
in 2N-3 moves (i think this is optimum).
2N-3 isn't optimum: for N = 4 the dons can talk in pairs and then swap around a bit, so they
all know the gossip after 4 calls. This approach can be extended for N &gt;= 4 so N dons can
get all the gossip after 2N-4 calls. But I haven't found any better solutions, nor can I show
that this is optimal for all N &gt;= 4 (in fact it probably isn't.)
8. Acolyte
05 Dec '02 00:30
Originally posted by royalchicken
genius-i was not entirely fair to you (although, as you are one year my senior,
i feel no need to be particularly gentle). the problem i gave is the Collatz
conjecture-one of the outstanding unsolved problems of mathematics. i have only
made progress with a fairly good knowledge of analysis (calculus et al) and
number theory. i have yet to prove it, though. give it a go-it is infectiously
interesting.
If you do maths at Cambridge, you're going to be one of the people who goes to 4th year
lectures in the first term, aren't you! ðŸ˜‰ Or are you already here...

I don't know much analysis yet, but if you explained what progress you had made, I might
the result had been proven for 'sufficiently large' c(1) (ie that the set of all counterexamples
is bounded above), but no-one knows how big the least sufficiently large number is.

The dons problem has been solved, but apparently there are only 2 undergraduates in the
whole of Cambridge who have solved and proven it!
9. royalchicken
CHAOS GHOST!!!
05 Dec '02 19:32
i am certainly no Cambridge student. i am a 15-year old high school student
from a town in what amounts to the middle of nowhere. i have a sick fascination
with this kind of thing, and i quite like this forum. are you familiar with the
puzzles of Dudeney?
10. royalchicken
CHAOS GHOST!!!
05 Dec '02 19:412 edits
have done on said conjecture. (it would be typographically ungainly in straight
text.) however, i have proved that every starting value will produce a sequence
that TENDS towards one as the number of terms generated increases without bound
(but i have not proven that there is always a term EQUAL to one, as the
conjecture requests.) i have also gone in a different direction, by proving
that in a sufficiently long sequence, there will be precisely twice as many
halvings as there are mulitplications by three and additions of one. this
indicates an obvious downward tendency. as i said before, a very interesting
problem, and one useful in keeping &quot;genius's&quot; head to a manageable volume :&gtðŸ˜‰
(the paucity of postings by genius in the past few days indicating that he is
holed up in a hovel with gallons of coffee, beating his head against a wall
trying to solve it.)
11. royalchicken
CHAOS GHOST!!!
06 Dec '02 00:03
i am correct in saying that a method for the dons to converse is optimum if
there exists some number n of dons for which there is no more efficient method?
also-just to check that it can always be done in 2n-4, i did prove that this
can be done. i then tried n=4 to 12, but i was curiously unable to work out how
it is done with 13 dons. it must be possible though. can someone tell me how?
12. Acolyte
06 Dec '02 15:52
Originally posted by royalchicken
i am correct in saying that a method for the dons to converse is optimum if
there exists some number n of dons for which there is no more efficient method?
also-just to check that it can always be done in 2n-4, i did prove that this
can be done. i then tried n=4 to 12, but i was curiously unable to work out how
it is done with 13 dons. it must be possible though. can someone tell me how?
Suppose n dons can communicate all the gossip in k calls. Then if you add another don, all
he has to do is talk to one of the other dons right at the start, then talk to one of the other
dons right at the end; so (n + 1) dons can certainly communicate all the gossip in (k + 2)
calls. Therefore any solution of the form 2n + constant will work for n &gt;= c if it works for n
= c, but that doesn't prove the solution is optimum.

I think what is meant by an optimum solution is that if I give you any number of dons,
you will be able to tell me the minimum number of calls required for that number of
dons
. Essentially, a function f:N -&gt; N is required.
13. Acolyte
06 Dec '02 16:15
Originally posted by royalchicken
have done on said conjecture. (it would be typographically ungainly in straight
text.) however, i have proved that every starting value will produce a sequence
that TENDS towards one as the number of terms generated increases without bound
(but i have not proven that th ...[text shortened]... oled up in a hovel with gallons of coffee, beating his head against a wall
trying to solve it.)
My email address is: cdr29ycam.ac.uk (Replace the y with an @, you never know where the
spambots are lurking!)

I've reached the end of term, so I should have time to have a look at this problem.
Somehow I doubt I'll get very far though... have you tried the 'minimal counterexample'
approach? If you can prove 'there is no minimal counterexample' then you've proved the
conjecture, because any non-empty subset of N has a least element.
14. royalchicken
CHAOS GHOST!!!
06 Dec '02 21:26
i tried something like this, with no good progress. however, the stratagies
which i will email to you provide some semblance of a proof. i have also found

1.it is called the Collatz conjecture;
2.the late mathematician Paul Erdos stated that &quot;mathematics is not ready for
the Collatz conjecture&quot; (a rather discouraging assessment...)
3.various organizations have offered rewards totaling about \$10 000 US, (that's
6 250 pounds to you...)

expect (or don't be surprised upon recieving) an email from &quot;shagen@gwi.net&quot;.
15. royalchicken
CHAOS GHOST!!!
06 Dec '02 21:281 edit
given that insight of yours into the don's problem i may be able to solve it
with a generating function. let k(n) be successive coefficients in the
maclaurin series expansion of some continuous differentiable function f(x)...

also, say, as Acolyte did, that for some c, k(n) = 2n - c for all n&gt;=c. note
that n &lt; P(n) &lt;= 2n-c, where P(n) is the smallest number of conversations.
this is obvious, but having a tight bound on P(n) is knowledge worth having in
the open.