Here is a very hard problem that doesn't require any advanced mathematical techniques to solve, just a huuuuge brain!
There are N>3 gossiping women and each of them knows some item of gossip not known to the others. They talk to each other via the telephone and in each conversation they tell each other all they know at that point in time. What is the minimum number of phone calls required before each woman knows all the gossip.
Hmm, interesting question.
I've got something that shows you can do it in 2N - 4 for an even number of women. I imagine you could extend this to do it for an odd number too, but it doesn't really show that this is the minimum number of conversations required.
I'd be interested in knowing the proper proof as I'm sure it's a lot more elegant than what I have below!
Ignoring women gossiping and thinking about it in terms of connected nodes.
Basically, it is:
Let there be C nodes and let N(i) represent the ith node.
Step 1
Join the nodes into C/2 disconnected pairs (i.e. 1-2, 3-4, etc.)
Thus each node has knowledge of one other node.
This step takes C/2 connections, one connection for each pair.
Step 2
Now join N(2) to N(j) where j is even and <= C/2
i.e. N(2) -> N(4), N(2) -> (N6) etc.
if C/2 is even this needs (C/4)-1 connections.
if C/2 is odd it needs ((C-2)/4)-1 connections.
Now, we do the same for N(k) to N(C) where k is even and > C/2
if C/2 is even this needs (C/4)-1 connections.
if C/2 is odd it needs ((C+2)/4)-1 connections.
And we see that to complete to this step requires (C/2)-2 connections whether C/2 is even or odd.
Step 3
We now have two nodes, N(a) & N(b) where a,b <= C/2 that know about all other nodes from N(1) to N(l) where l is the largest even integer that is <= C/2
Similarly we have two nodes N(c) & N(d) where c,d > C/2 that know about all nodes from N(l+1) to N(C)
Now, join N(a) with N(c) and N(b) with N(d) to give four nodes that know about all nodes from N(1) to N(C)
Step 3 takes two connections.
It has taken C/2 + (C/2) - 2 + 2 = C connections to get this far.
As there are four nodes that know about all C nodes there are C-4 nodes that don't, so we join from one of the nodes in the know to the other nodes, which takes C-4 connections.
Total is C + C - 4 = 2C - 4 connections.
