No label defined (Q3972008)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 15364
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 15364 |
Statements
25 June 1992
0 references
generalized Fibonacci numbers
0 references
gossip
0 references
telephone problem
0 references
\(k\)-conference calls problem
0 references
\(k\)-telegraph problem
0 references
0.8889893293380737
0 references
0.8858869075775146
0 references
0.8391392827033997
0 references
[For the entire collection see Zbl 0698.00017.] In the gossip problem there are \(n\) persons, each knowing a piece of information ( gossip) unknown to others. At each discrete unit of time information is exchanged between pairs of persons when all the information known to one is passed on to the other. If information exchange takes place in both ways (modelled by an undirected graph) we have the telephone problem. If exchange can take place only in one way in unit time (modelled by a directed graph) we have a telegraph problem. If, in unit time, a person can communicate with \(k\) others we have a \(k\)- conference calls problem or a \(k\)-telegraph problem, respectively. One of the objectives is to find the minimum number \(T_ k(n)\) of rounds (time) necessary for a complete exchange of information. The authors settle a conjecture of Entringer and Slater for the \(k\)-telegraph problem: \[ T_ k(n)=\alpha_ k\log_{k+1}(n)+O(1)\text{ with } \alpha_ k\to 1\text{ as } k\to\infty. \] They actually prove that, for \(k\geq 2\), \(T_ k(n)\in\{\lceil\log_{\tau_ k}n\rceil,\lceil\log_{\tau_ k}n\rceil+1\}\) where \(\tau_ k={1\over 2}[k+(k^ 2+4)^{1/2}]\) is the positive root of \(x^ 2-kx-1=0\). The proof technique involves the generation of a message sequence involving the recurrent sequence \(\{F_ k(t)\}\) defined by \(F_ k(0)=0\), \(F_ k(1)=1\) and \(F_ k(t+1)=kF_ k(t)+F_ k(t+1)\) for \(t\geq 1\). This is an obvious generalization of the Fibonacci sequence. At least two sets of people seem to be working on these problems in non- communicating compartments. For example the list of references in the paper under review and the one by \textit{Akos Seress} [Combinatorial mathematics, Proc. 3rd Int. Conf., New York/NY (USA) 1985, Ann. N.Y. Acad. Sci. 555, 375-382 (1989; Zbl 0722.05059)] have empty intersection.
0 references