On optimal fast solutions to the problem of gossiping by letters

Abstract

We determine a fast solution to the problem of gossiping by letters, for a number n of persons, 2^s < n ≤ 3·2^s-1 (s positive integer), which requires only 3n - 4 letters, instead of n[log ₂ n] as in the classical solution by Entringer and Slater [1]. We conjecture that our solution is optimal.