Gossiping Logicians

[Griffin]

In puzzlania, there are n logicians who love nothing better than to take a break from logickizing and share a bit of gossip.

Initially, every logician knows one juicy bit of gossip. In order for one logician to call another, he must know at least one bit of gossip that the other does not. Furthermore, once on the phone, the two logicians inevitably share all the gossip that they know.

What is the most number of phone calls that can be made before everyone knows everything?

[mith]

(n^2-n)/2?

A calls B.
C calls A. C calls B.
D calls A. D calls C. D calls B.
etc.
Every pair talks once.

[Griffin]

Yep . Now, proof?

[Zag]

Proof:
f(2) = 1, by obviousness.
f(N) = f(N-1) + N -1, since you can isolate one person and no one calls him, and arrive f(N-1) with the remaining group. Then the one isolated person calls each of the others, none of whom have heard his gossip yet.

With some algebra, this works out to mith's formula (I'm pretty darn sure).

[Quailman]

Homework alert! I think you're being asked to help this kid with his homework.

[Zag]

[Quailman]

Can't you tell when I'm being sarcastic?

[mith]

Zag, that proof unfortunately only gives us a minimum. It doesn't prove that we can't do better.

(The basic idea of the proof seems pretty straightforward, I'm just too lazy to work out the details right now. And Griffin probably has something super elegant in mind. )

[Zag]

Fair enough. However, that represents every person talking to every other person, so it is clearly the maximum, too. (Well, clear to me, anyway. Perhaps it isn't clear to a mathematical certainty.)

Q. I'm ignoring you.

[mith]

It's clear to me too. But we can clearly have a given pair talk more than once (A talks to B, A talks to C, A talks to B again now that he has a new piece of gossip from C). We can see from the three person example that A talking to B again rules out B talking to C, so we've got the same total. But showing that that is always the case may be a little tricky.

[Griffin]

[ralphmerridew]

It's possible for logicians to call each other many times; if things are chosen properly, it's possible for one pair to have n-1 calls between themselves.

Algorithm:
- Sort the logicians into some order. Call the lowest numbered logician Alice
- Repeat:
- - Alice will call the highest numbered logician X such that Alice can tell X something new, but X can not tell Alice anything new, if there is one.
- - Otherwise, then Alice will call the lowest numbered logician X such that X can tell Alice something new, if there is one.
- - Otherwise, stop the algorithm.

So the pattern goes AB, AC, AB, AD, AC, AB, AE, AD, AC, AB, ...

[Lepton]

That's cute, and it gives exactly mith's formula, I think. (10 for n=5)

I think I'm not alone in thinking that there must be an elegant proof, but my efforts have been futile.

[L'lanmal]

This may be one of those occasions where it is easier to prove a more general formula, then specialize to the starting conditions (of each logician only knowing 1 piece of information).

[L'lanmal]

I think I'm on to something here, but I'm not all the way there.

Suppose we limit the logicians to speaking to their neighbors on either side.

Label the action of logician i speaking to logician i+1 as "s _i "

The braid relations are satisfied.
(That is, For |j-k| > 1, s _j s _k =s _k s _j . Which is another way of saying if two groups of logicians go a while without talking to each other, it doesn't matter which group talks amongst themselves first.
For |j-k| = 1, s _j s _k s _j =s _k s _j s _k : If three logicians talk amongst themselves three times, all three of them know the same things.)

The requirement that two cannot talk unless they have something to share ensures that conversations do not attempt to go up in the Bruhat order.

Therefore, the number of times the logicians will talk is (at most) equal to the number of inversions of the permutation (n, n-1, n-2, n-3 ... , 2, 1), which is n*(n-1)/2.

It remains to show that if "distant" logicians speak to each other, it can only accelerate the information sharing.