The dons problem

Originally posted by royalchicken
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 s ...[text shortened]... ns.
this is obvious, but having a tight bound on P(n) is knowledge worth having in
the open.

That's not quite what I meant. What I was trying to say was that k(n) = 2n - c -&gt; k(t) =&lt;
2t - c for all c,n and t &gt;= n. This does indeed give you an upper bound to the solution, but
it's still ~2n for sufficiently large n. What it does show is that none of the terms in the
solution grow or shrink faster than n - ie no n^m, where m&gt;1, and certainly no postive
exponentials. However there could still be terms lurking in there that grow like log n, for
example.
I suspect that the solution will not tend towards a linear equation of the form 2n - c, but
that's just because I know the answer is far from easy to obtain.

this much is clear. i intended that more as a check of any solution that is
obtained.

Originally posted by royalchicken
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 ...[text shortened]... to you...)

expect (or don't be surprised upon recieving) an email from "shagen@gwi.net".

You can do something with it:

Let c(1) = m be the minimal counterexample. Suppose m = k.2^n + 1 , where k is odd
(possibly k = 1) and n &gt;= 2. Then c(4) = 3k.2^(n-2) + 1 , which is less than c(1). So m is
not minimal (contradiction). Obviously m is not even, so it must be of the form 2k + 1,
where k is odd.

OK, maybe that's not very helpful, as it only deals with 3/4 of the numbers.

I've had a quick look at the document you've sent me, and I don't think the characters are
displaying properly on my computer. Still the bits I could make out had me a bit confused.
What is the significance of s(1)s(2)....s(n) ? Surely this is 0 for any n &gt; 1. Or does s(n)
mean something other than the parity function you seemed to define at the start? (as I say,
it's not displaying properly.)

the first method you suggest is identical to something i tried with little
success. as you noticed, s1s2...sn IS always zero, i have not changed the
definition of s. i was afraid of that happening with the characters. all i can
suggest is that you download a freeware program called &quot;equation magic lite&quot;
(about 1.4 MB, i think). it will allow you to read things in LATeX format , and
as you are in math(s), you may find it useful in future. sorry.

as regards the don's problem, i have reason to believe that 2n-4 IS the optimum
method. i am working on a proof.

Originally posted by royalchicken
all i can
suggest is that you download a freeware program called "equation magic lite"
(about 1.4 MB, i think). it will allow you to read things in LATeX format , and
as you are in math(s), you may find it useful in future. sorry.

Yes, I've been meaning to get hold of one of those. Unfotunately equation magic doesn't
seem to be available for the Mac.

1. i will give it to you in PDF format. sorry about this.

2. i have a proof that P(n) = 2n-4 for all n &gt;= 4. (it is 10 degrees F here,
nothing to do...).

You have already shown that P(n) = 2n-4 is suffiecient to disseminate all gossip
among all of the dons. thus it will suffice to show that there exists no c in N
such that P(c) &lt;= 2c-5. to start, assume that there does exist such a c, and
further suppose that it is the minimum c for which P(c) &lt;= 2c-5. this implies
that P(c-1) = 2(c-1)-4 = 2c-6. therefore, if our initial assumption is correct,
then for that c, P(c) = P(c-1) + 1. Now Let D(c-1) be the graph (V(c-1),
E(c-1)), where V(c-1) is the set of c-1 vertices (dons) and E(c-1) is the set of
edges (conversations) necessary to disseminate all gossip in the optimum manner.
by the initial assumption, E(c-1) has P(c-1) = 2c-6 elements. now further,
D(c-1) must have all vertices be of minimum degree 2 in order for all gossip to
be disseminated. this holds for any graph representing a sequence of
conversations satisfying the don's problem. now D(c) must have c vertices
(dons), and, by our assumption, 2c-5 edges. so we have added one vertex and one
edge. thus in D(c) there exists some vetex of degree 1, and therefore it
requires the addition of an edge to satisfy the don's problem. thus there
exists no c where P(c) = 2c-5. therefore 2c-4 is optimum. QED

(i email-ically ran this by someone i know who is doing her graduate work in
graph theory, she doesn't seem to think anything is wrong with it, hence the
audacity of the QED).

the scheme neede to do it in 2n-4 is complicated enough so that not all of the
dons would think of it. therefore, at least one telephone call would be
necessary beforehand to disseminate the method, for a total of 2n-3, which we
said originally! 🙂

this problem is apparently a special case of something called tidjeman's theorem,
which says that 2n-4 is optimum. his proof is simpler, though.

Originally posted by royalchicken
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)...
...[text shortened]... ng a tight bound on P(n) is knowledge worth
having in
the open.

Huh? (I need desperately to relearn my math. HELP!) By the way, did
you know that LaTeX is also used for chess games?

Rein, who aced AP Calc. and went seriously downhill from there.

Originally posted by royalchicken
1. i will give it to you in PDF format. sorry about this.

2. i have a proof that P(n) = 2n-4 for all n >= 4. (it is 10 degrees F here,
nothing to do...).

You have already shown that P(n) = 2n-4 is suffiecient to disseminate all gossip
among all of the dons. thus it will suffice to show that there exists no c in N
such that P(c) <= 2c-5. to ...[text shortened]... ory, she doesn't seem to think anything is wrong with it, hence the
audacity of the QED).

1. Thanks, I can read it now. The function used in the conjecture can only take discrete
values; does this affect the subsequent convergence calculations? (I don't know as I haven't
really done any analysis yet)

2. I can't see anything wrong with your argument until this point:

'so we have added one vertex and one edge'

Obviously we've adjoined a vertex and increased the number of edges by one. But I remain
to be convinced that D(c) is necessarily a direct extension of D(c-1). In fact, D(3) is not a
subgraph of D(4) (try drawing them!), so why must D(c-1) be a subgraph of D(c) ?

i did rethink this, and was at first chagrined by the fact that D(3) is not a
subgraph of D(4).
however, D(3), D(4) are not considered by our argument, because i am trying to
prove that P(c) = 2n-5 is impossible only in cases where P(c-1) = 2(c-1) - 4.
it is not a subgraph because the method needed to get P(c) = 2c-4 requires at
least four dons. however, this does not explain away your objection. i have to
think about this.

the system that allows it to be done in 2c - 4 demands that D(c-1) be a subgraph
of D(c). in the system, one has a &quot;core group&quot; of 4 dons, and everyone else
talks to one in the core group, who each then talk amongst themselves. for
example, if we have five dons, A,B,C,D,E, and (X,Y) is a conversation, then:

(A,E); (A,B); (C,D); (A,C); (B,D); (A,E)

now for six, all we need to do is tack (A,F) onto each end, and we have it in 8.
but you knew this. however, if we wanted to do it in 7, we could then try any
of the different pairs (A or B or C or D or E,F), and find that none suffice.
to do it in 2c - 5 means that we need an at least 1- connected graph with c
vertices, 2c - 5 edges, and no vertex of odd degree (think about the problem and
see why this follows). this is clearly impossible.

Originally posted by royalchicken
the system that allows it to be done in 2c - 4 demands that D(c-1) be a subgraph
of D(c). in the system, one has a "core group" of 4 dons, and everyone else
talks to one in the core group, who each then talk amongst themselves. f ...[text shortened]... oblem and
see why this follows). this is clearly impossible.

&quot;in the system, one has a &quot;core group&quot; of 4 dons, and everyone else
talks to one in the core group, who each then talk amongst themselves.&quot;

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 &gt;= 4.

&quot;however, if we wanted to do it in 7, we could then try any
of the different pairs (A or B or C or D or E,F), and find that none suffice.&quot;

Obviously. But this assumes that D(6) is an extension of D(5), so depends on the first point.

&quot;to do it in 2c - 5 means that we need an at least 1- connected graph with c
vertices, 2c - 5 edges, and no vertex of odd degree (think about the problem and
see why this follows).&quot;

I don't see why 'no vertex of odd degree' follows, since it isn't necessary for 2c - 4: the
sequence of conversations (A,E),(A,D),(B,C),(C,D),(A,B),(B,E) is sufficient for 5 dons to
communicate in 2*5 - 4 conversations, but it creates two odd vertices, namely A and B.

PS The above example shows that you can't even say that any two optimal graphs for a given
c are isomorphic (is that the right word?) since my example of D(5) is not isomorphic to
yours.

&quot;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 &gt;= 4. &quot;

i am aware. this is what i am having difficulty showing.

i expressed myself poorly about vertices of odd degree. i don't believe it can
be done in such a way that an ODD NUMBER OF VERTICES are of odd degree. (which
immediately implies that 2n-5 is impossible). however, i don't know exactly how
to show this (in fairness, however, i was unaware that graph theory existed
until four days ago, when this problem prompted me to read a book on the subject.)