The Gossip Problem:
Suppose there are $n$ ladies in a group, each aware of a gossip no one else in the group knows about. These ladies communicate by telephone; when two ladies in the group talk, they share information about all gossip each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two gossips. The gossip problem asks for $G(n)$, the minimum number of telephone calls that are needed for all n ladies to learn about all the gossip. Prove that $G(n)\geq 2n−4$ when $n\geq4$.
I came up with a solution for the Gossip Problem and would like to know if it is correct ( I was awarded 0 in an exam), Here is the gist of it:
Claim 1: In a call the maximum Gossips that can be gained is n.
This only occurs when they among them have all gossips and there are no overlaps.
Claim 2: In the first (n-1) calls the maximum that can be gained is k+1 in the kth call {In the first call 2 and second call 3 etc.}
This is because after the kth call each lady can know a maximum of k+1 gossips.
From our 2 conjectures the Maximum possible number of gossips gained in C1,C2... is of the form 2,3,4,5...n,n,n,n. Let us call the maximum gossips gained as $f(n)$
Now we know the required number of gossips gained is $n^2-n$
Hence we can write, $f(n)>=n^2-n$
Let the number of meetings be 2n-k
After simplification we get,
$n(n+1)/2-1+(n-k+1)n>=n^2-n$
which is $n^2+n-2+2n^2-2nk+2n>=2n^2-2n$
Hence , $n^2+n(5-2k)-2>=0$
Now the interval of n is (4 , infinity). In both the possible graphs we get:
$f(4)>=0$
Hence , $16+20-8k-2>=0$
$k<=4.25$ and from here $k<=4$
We hence get the number of meetings is greater than or equal to 2n-4.
Further there are famous sequences of steps to prove the existence of 2n-4 as a solution to conclude that the minimum number of meetings required is atmost 2n-4.
Eg: Separate 4 ladies and make the n-4 ladies give their gossip to any of the 4 ladies then let the 4 ladies gain all gossips through a sequence of 4 calls and then let them give their gossip to the n-4 ladies . So , there is $n-4+n-4+4=2n-4$ for all n . Mind Your Decisions made a video on this as well .
So please let me know if this is correct. I'm surprised I came up with something this simple to a reputed hard problem :) .
There must be something going wrong in the "after simplification we get" step. From your two "conjectures" (it would be better to call them "claims"), adding up the number of possible gossips gained after the first $2n-k$ calls gives $f(2n-k)=3n^2/2+(1/2-k)n-1$ provided $k\leq n$, which is already more than the required number for $k\approx n/2$.