- 25 Oct '02 22:29This 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? - 25 Oct '02 23:19Sorry 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 ;-). - 03 Dec '02 22:59 / 3 editsif "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) - 04 Dec '02 19:29

going by this post, i'm not sure if i can do it on my limited maths base*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)

(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 - 04 Dec '02 21:40sintubin 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. - 04 Dec '02 23:59

2N-3 isn't optimum: for N = 4 the dons can talk in pairs and then swap around a bit, so they**sintubin has a remarkably astute stomach. the gossiping don's can always do it**

in 2N-3 moves (i think this is optimum).

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.) - 05 Dec '02 00:30

If you do maths at Cambridge, you're going to be one of the people who goes to 4th year*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.

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! - 05 Dec '02 19:41 / 2 editsif 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 :>

(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.) - 06 Dec '02 00:03i 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? - 06 Dec '02 15:52

Suppose n dons can communicate all the gossip in k calls. Then if you add another don, all*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?

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*. Essentially, a function f:N -> N is required.

dons - 06 Dec '02 16:15

My email address is: cdr29ycam.ac.uk (Replace the y with an @, you never know where the*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.)

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. - 06 Dec '02 21:26i 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". - 06 Dec '02 21:28 / 1 editgiven 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.