Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation Acolyte
    Now With Added BA
    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. Donation Acolyte
    Now With Added BA
    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. Standard member royalchicken
    CHAOS GHOST!!!
    03 Dec '02 22:59 / 3 edits
    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)
  5. Standard member 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. Standard member 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. Donation Acolyte
    Now With Added BA
    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 >= 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.)
  8. Donation Acolyte
    Now With Added BA
    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
    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!
  9. Standard member 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. Standard member royalchicken
    CHAOS GHOST!!!
    05 Dec '02 19:41 / 2 edits
    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.)
  11. Standard member 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. Donation Acolyte
    Now With Added BA
    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 >= 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.
  13. Donation Acolyte
    Now With Added BA
    06 Dec '02 16:15
    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.
  14. Standard member 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
    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".
  15. Standard member royalchicken
    CHAOS GHOST!!!
    06 Dec '02 21:28 / 1 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>=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.