Wikipedia:Reference desk/Archives/Mathematics/2022 March 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 19

Dissemination problem

Consider $n$ people, each of whom knows a particular fact. How many two-person meetings are required for everybody to know everything, where at each meeting everything known to date is shared? I can't get below $2n-3$, achieved in this way, for example: person $1$ meets everyone else up to person $n$ (taking $n-1$ meetings), then re-meets everyone from $2$ to $n-1$ (taking $n-2$ meetings). Is it possible to do the job in fewer, or indeed to prove that $2n-3$ is the lowest number? →2A00:23C6:AA07:4C00:4C7E:441:A97:15A2 (talk) 13:30, 19 March 2022 (UTC)

It is certainly possible to do better in general: with $n=4$, for example, the meetings AB, CD, AC, BD work. But in fact you only get that one bit of improvement: see https://oeis.org/A058992 . -- JBL (talk) 15:47, 19 March 2022 (UTC)