Quick gossiping without duplicate transmissions (Q1080864): Difference between revisions

There are n people, each knowing a gossip. They communicate by phone calls, and whenever two persons talk they tell all information they know at that time. Denote by f(n) the minimal number of necessary calls when everybody hears each gossip exactly once. We prove that \[ f(n)=2.25n-6\;if\;n=4k,\quad k\geq 2\quad and \] \[ 2.25n-4.5\leq f(n)\leq 2.25n-3.5\;if\;n=4k+2,\quad k\geq 5. \] (If n is odd, or \(n=4k+2\), \(0<k<5\) then there are no appropriate sequences of calls at all.)