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

Posers and Puzzles

  1. 05 Mar '15 02:34
    There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.

    How many calls is the least they have to make between themselves?
  2. Subscriber coquette
    Already mated
    05 Mar '15 07:21
    Originally posted by WanderingKing
    There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.

    How many calls is the least they have to make between themselves?
    6

    a calls b with item 1
    b calls c with items 1 & 2
    c calls d with itmes 1, 2 & 3
    d calls e with items 1, 2, 3 & 4
    e calls f with itmes 1, 2, 3, 4 & 5
    a still needs a call to get the information
  3. Standard member wolfgang59
    Infidel
    05 Mar '15 07:49
    Originally posted by WanderingKing
    There are n men in a village. Each of them has a piece of juicy information about the private life of someone they all know. They want to share the information so that every one of them has all of it. And they want to do all of this by phone because they're all sick with different contagious diseases. And it's 1951 so there are no conference calls.

    How many calls is the least they have to make between themselves?
    (n-1)^2 ... or less.
  4. 05 Mar '15 08:54
    Originally posted by coquette
    6

    a calls b with item 1
    b calls c with items 1 & 2
    c calls d with itmes 1, 2 & 3
    d calls e with items 1, 2, 3 & 4
    e calls f with itmes 1, 2, 3, 4 & 5
    a still needs a call to get the information
    Does b know item 3 after all of this?
  5. 05 Mar '15 08:59
    Originally posted by wolfgang59
    (n-1)^2 ... or less.
    How did you arrive at this number? An obvious bound is n^2, a slightly less obvious one is (n-1)*n/2.
  6. Standard member wolfgang59
    Infidel
    06 Mar '15 03:11
    Originally posted by WanderingKing
    How did you arrive at this number? An obvious bound is n^2, a slightly less obvious one is (n-1)*n/2.
    (n-1)^2

    It looked pleasant after a few drinks.


    But isn't 2n-2 a possibility?
    One person takes a call from all the others. (That is (n-1) calls).
    He now knows everything.
    He then informs the rest of the village. (Another (n-1) calls)

    So it can be done in (2n-2) calls. Not sure how to prove that is minimum or even if it is minimum.
  7. 06 Mar '15 13:42 / 2 edits
    That's a great observation! Maybe taking a look at some small values of n would be a good idea now so we can test this bound.
  8. 06 Mar '15 21:28 / 4 edits
    8 people, a,b,c,d,e,f,g,h

    first calls: ab, cd, ef, gh
    second calls : ac, eg
    third calls : cg
    now c and g know everything
    a calls e, now a and e know everything too
    finish off by someone who knows everything calling b,d,f and h

    So 12 calls are needed for 8 people.

    Another way:
    round 1: ab, cd, ef, gh
    round 2: ac, bd, eg, fh
    round 3: ae, cg, bf, gh

    now they know everything, 12 calls again
    So I think it is n * log2(n) if n is a power of 2

    This must surely be a minimum, in the second way shown it is clear that everyone's amount of information is doubling in each round.
  9. 07 Mar '15 00:01 / 1 edit
    That's the correct number for 8 men.

    About the log conjecture: for 2 men 1 call is enough! So even if it's true in some sense it must be honed.

    Edit: Oh, and this contradicts wolfgang's conjecture, since 2*8-2 is 14. But wolfgang's 2*n-2 is certainly correct as an upper bound so let's compare 2n-2 to n*log2(n).

    We have n*log2(n)-(2n-2)=n(log2(n)-2)+2=n(log2(n/4))+2.

    This is clearly positive for n>=4 because then log2(n/4)>=0. Actually, it's still positive for n=3. So, for n>=3, n*log2(2) is greater than the upper bound given by wolfgang, so it cannot be correct. That's another thing that needs to be taken care of if this idea is to be taken further.
  10. 07 Mar '15 01:21
    Oh, I didn't notice one thing. 8*log2(8)=24. Did you mean n*log2(n)/2?
  11. 07 Mar '15 21:16 / 3 edits
    Ah yes sorry! n*log(2)/2

    16 people should be 32 calls...

    ab, cd, ef, gh, ij, kL, mn, op
    ac, bd, eg, fh, ik, jL, mo, np
    ae, cg, bf, dh, im, ko, jn, Lp
    ai, em, ck, go, bj, fn, dL, Hp.

    The idea is that with n/2 calls each round we can double the size of groups, where everyone in the group knows what everyone else in the group knows. It starts off with n groups of size 1, then n/2 group of size 2, then n/4 groups of size 4... etc.
  12. 07 Mar '15 22:12 / 3 edits
    Originally posted by iamatiger
    Ah yes sorry! n*log(2)/2

    16 people should be 32 calls...

    ab, cd, ef, gh, ij, kL, mn, op
    ac, bd, eg, fh, ik, jL, mo, np
    ae, cg, bf, dh, im, ko, jn, Lp
    ai, em, ck, go, bj, fn, dL, Hp.

    The idea is that with n/2 calls each round we can double the size of groups, where everyone in the group knows what everyone else in the group knows. It starts off with n groups of size 1, then n/2 group of size 2, then n/4 groups of size 4... etc.
    There's a general problem with this function, the same that I mentioned in the previous post. x*log(x) grows faster than any linear function and wolfgang's bound (which is correct) is linear. Any idea around x*log(x) will have to take it into account and might be doomed because of the bound.

    Here's a plot of the function showing that x*log2(x)/2 is a convex function: http://postimg.org/image/5vp85c7sz/

    Wolgang's observation gives us that for 16 men the number of necessary calls is not greater than 2*16-2=30. So 32 can't be the right number.
  13. 07 Mar '15 22:28
    I think the two kinds of approach in your (wolfgang and tiger's) posts can complement each other. It's a good idea to give a general algorithm for any n as wolfgang did and try to show that it gives the optimal number of calls (which wolfgang refused to do ). Trying to get a "feel" for how the function grows as tiger did is also not a bad idea.

    In any case I think it is clear by now that a proof that a certain solution, however obtained, is optimal will be the hard part.
  14. 07 Mar '15 23:05 / 3 edits
    Hmm, actually Wolfgang's method is (n-1) + (n-2) = 2n-3 calls I think, because if person 'a' calls everyone else, then on the call where he finds everything out he can tell the person he is currently calling everything without incurring another call

    that means my method beats Wolfgang's at n = 8, but at n-16 Wolfgang's method takes 29 calls and mine takes 32, so wolfgang is clearly best

    But, how about we do this:

    ab cd ef gh ij kl mn op
    ac eg ik mo
    ae im
    ai
    now a and i know everything, 15 calls so far (equal progress with wolfgang's method)
    em
    now a,i,e and m know everything 16 calls so far
    in 12 more calls we can distribute the knowledge to the remainder

    So we took 28 calls, one better than wolfgang's method

    Theorem: Wolfgang's method is a worst case that can always be bettered when n is a power of 2
  15. 08 Mar '15 00:38 / 4 edits
    Very nice!

    So to summarize: when n=2^k, we can do this in 2n-4 calls.

    This is proven using your method: we need

    (2^(k-1)+2^(k-2)+...+2^1+2^0)+1=(2^k-1)+1=2^k=n

    calls to fully inform 4 people, and then n-4 calls are enough to inform the rest. Care needs to be taken of the initial values of course since we might not even have a group of 4.

    For four people this method works. For two people the method is a bit meaningless and the formula doesn't work: it would imply that 0 calls are needed while 1 call is necessary. For one person we need 0 calls and the formula gives a negative number. But this is a formality. I'll list the values:

    1 man - 0 calls,
    2 men - 1 call,
    3 men - 3 calls,
    4 men - 4 calls.

    These are easily verified to be optimal.

    For n=2^k, k>1, we have a procedure to do it in 2n-4 calls.

    There are two paths to take now. We could try to continue working on the powers of two (either show that 2n-4 is optimal for them or find a better algorithm), or we could try to take a look at other numbers, for which, so far, we know a procedure to do it in 2n-3 calls.