Start with the situation of n gossipers that each have a different item of information. On each telephone call all information known to both parties is exchanged. The table below lists the total number of possible knowledge distributions (depending on the chosen sequence of calls) and the number of such distributions that can be reached with a given number of calls (but not with fewer calls).
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| # | 1 | 1 | 2 | 11 | 189 | 9152 | 1092473 | 293656554 | 166244338221 | 188620758836916 |
| d0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d1 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | ||
| d2 | 6 | 27 | 75 | 165 | 315 | 546 | 882 | |||
| d3 | 1 | 76 | 430 | 1475 | 3920 | 8876 | 17976 | |||
| d4 | 79 | 1725 | 10605 | 41405 | 125475 | 322119 | ||||
| d5 | 4180 | 59145 | 369180 | 1556660 | 5168520 | |||||
| d6 | 2731 | 229816 | 2686411 | 16771566 | 74298756 | |||||
| d7 | 477990 | 14916566 | 152871488 | 946796256 | ||||||
| d8 | 295321 | 56809557 | 1133866839 | 10505720001 | ||||||
| d9 | 16520 | 115163279 | 6418872796 | 98819769832 | ||||||
| d10 | 1420 | 86889419 | 24974052664 | 758218193454 | ||||||
| d11 | 15789900 | 55125490756 | 4483999465212 | |||||||
| d12 | 981540 | 55648019764 | 18656374653114 | |||||||
| d13 | 5040 | 20243146392 | 47738387914410 | |||||||
| d14 | 2455893090 | 64985976999745 | ||||||||
| d15 | 73604160 | 40481993669796 | ||||||||
| d16 | 57120 | 10391782344006 | ||||||||
| d17 | 986710556160 | |||||||||
| d18 | 26910450000 | |||||||||
| d19 | 52496640 |
Gossip distance distribution with n gossipers, up to equivalence.
As above, but consider knowledge distributions equivalent when they only differ by a relabeling of the gossipers.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| # | 1 | 1 | 2 | 4 | 16 | 111 | 1940 | 68300 | 4651805 | 573472861 |
| d0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| d2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | |||
| d3 | 1 | 5 | 6 | 7 | 7 | 7 | 7 | |||
| d4 | 7 | 19 | 24 | 25 | 26 | 26 | ||||
| d5 | 46 | 103 | 119 | 124 | 125 | |||||
| d6 | 36 | 395 | 656 | 734 | 751 | |||||
| d7 | 850 | 3437 | 4865 | 5220 | ||||||
| d8 | 518 | 13155 | 32225 | 40288 | ||||||
| d9 | 34 | 26959 | 179804 | 319699 | ||||||
| d10 | 5 | 19958 | 702813 | 2331047 | ||||||
| d11 | 3716 | 1550358 | 13709859 | |||||||
| d12 | 263 | 1546271 | 57152917 | |||||||
| d13 | 1 | 561917 | 145899848 | |||||||
| d14 | 70430 | 197131807 | ||||||||
| d15 | 2223 | 122169250 | ||||||||
| d16 | 4 | 31565063 | ||||||||
| d17 | 3059452 | |||||||||
| d18 | 87285 | |||||||||
| d19 | 213 |
For n ≥ 4 the most efficient way to exchange all information requires 2n−4 steps. For n=0,1,2,3 the number of steps needed is 0,0,1,3, respectively. (This was proved by Tijdeman (1971), Baker & Shostak (1972), Hajnal, Milner & Szemerédi (1972), and Bumby & Spencer.)
A series of telephone calls where in each step one of the two participants learns something new can last at most (n choose 2) steps. (Jan Draisma has a beautiful proof.)
For example, for n=5, a worst case conversation is: A-B A-C A-B A-D A-B A-C A-E A-B A-C A-D.
Up to equivalence, the unique knowledge distribution for n=7 that requires 13 steps is for the seven gossipers A,B,C,D,E,F,G to know ABCEF, ABCDEF, ACDEFG, ABCDEG, ABCDEFG, ABCDEFG, ABCDEFG.
Reach this after a conversation of length 13: A-C A-B C-E C-D B-D C-G D-G E-F A-E B-E C-F E-F E-G.
After a conversation of length 14: A-C A-E A-B C-E C-D B-D C-G D-G E-F A-E B-E C-F E-F E-G.
The part with n < 9 of the above tables was computed in Berndsen (2012).