The dons problem

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?

from the stomach: 2n-3 ?
Gil.

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 ;-).

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 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 "genius" can prove this, he will have earned his
nickname. i'll have the answer to the "dons problem" shortly.

~mark (royalchicken)

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

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.

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 >= 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 >= 4 (in fact it probably isn't.)

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
understand some of it. I've read about this problem before; I think it said somewhere that
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!

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?

if you (Acolyte) would give me your email address, i could send you the work i
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 "genius's" 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.)

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?

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 >= 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 -> N is required.

Originally posted by royalchicken
if you (Acolyte) would give me your email address, i could send you the work i
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.

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
out a few things about this problem, namely:

1.it is called the Collatz conjecture;
2.the late mathematician Paul Erdos stated that "mathematics is not ready for
the Collatz conjecture" (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 "shagen@gwi.net".

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>=c. note
that n < P(n) <= 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.