Telefonate

[axpgn]

Supponiamo che ognuna delle $n$ persone componenti un certo gruppo di amici, conosca esattamente solo un pezzo di un'informazione, che tutti gli $n$ pezzi siano differenti e che tutti insieme forniscano l'informazione completa.

Ogni volta che una persona del gruppo telefona ad un'altra persona del gruppo, la persona chiamante comunica tutto quel che sa alla persona chiamata (sia il pezzo di informazione che conosceva inizialmente, sia i pezzi di cui è venuta a conoscenza tramite le telefonate di altre persone del gruppo) mentre la persona chiamata non dice nulla al chiamante.


Qual è il minimo numero di telefonate tra membri del gruppo necessarie affinché tutti conoscano tutto?


Cordialmente, Alex

[mgrau]

2(n-1)
Il primo chiama il secondo, che chiama il terzo, fino al penultimo che chiama l'ultimo, che ora ha tutta l'informazione, Che ciascuno faccia almeno una chiamata, ossia n-1 telefonate, mi pare necessario per poter comunicare il proprio pezzo.
Poi l'ultimo chiama tutti gli altri (altre n-1 chiamate) così tutti sanno tutto.
Ma immagino che questa sia la risposta banale

[axpgn]

Bene, hai dimostrato che quello è il numero di telefonate sufficiente a raggiungere lo scopo.
Ma è anche il minimo?

[mgrau]

Dopo le prime n-1 chiamate, mi pare che uno solo abbia tutta l'informazione. (anche questo andrebbe dimostrato...)
Quindi a tutti gli altri n-1 manca qualche pezzo, e tutti quindi devono ricevere almeno una telefonata per completare.

[axpgn]

Più o meno è come la vedo anch'io però ho il dubbio che occorra una soluzione più formale, o no?



Cordialmente, Alex

[mgrau]

Anch'io non sono troppo convinto. Però una soluzione diversa mi stupirebbe...
Ma quindi, tu non hai la risposta?

[axpgn]

Sì, sì, la risposta è quella, anch'io mi sono dato una "dimostrazione" simile ma sto cercando qualcosa di più "formale" ...

[axpgn]

Ne ho trovata una ...

Sappiamo che esiste una successione finita di telefonate che permette a tutti di essere perfettamente informati (per esempio quella che hai detto tu).
All'interno di questa sequenza esiste una telefonata al termine della quale la persona chiamata, diciamo $p$, è la prima ad essere a conoscenza dell'informazione completa.
Prima di questa chiamata (e compresa questa) ci devono essere state almeno $n-1$ chiamate, altrimenti come potrebbe $p$ sapere tutto?
D'altra parte dopo questa telefonata "cruciale", ci sono $n-1$ persone da informare pienamente quindi come minimo ci saranno da fare altre $n-1$ telefonate.
In totale e al minimo $2(n-1)$.
Va bene?

Cordialmente, Alex

[mgrau]

"axpgn":... esiste una telefonata al termine della quale la persona chiamata, diciamo $p$, è la prima ad essere a conoscenza dell'informazione completa.
Prima di questa chiamata (e compresa questa) ci devono essere state almeno $n-1$ chiamate,

Sì, questa sarebbe la dimostrazione della prima affermazione, che io non ho dato.
Però, devo dire che mi aspettavo qualcosa di più mirabolante...

[axpgn]

Vabbè, dai ...

[ghira1]

$2n-4$ per $n>=4$. 0,1 e 3 per $n=1, 2, 3$.

L'ho visto in un corso di teoria dei grafi. Riferimenti: https://mathworld.wolfram.com/Gossiping.html

[axpgn]

No, ghira, non è lo stesso problema (se ho capito bene) : nel tuo link dice "they pass on to each other as many scandals as they know" che non è il nostro caso ... IMHO


Cordialmente, Alex

[ghira1]

"axpgn":No, ghira, non è lo stesso problema (se ho capito bene) : nel tuo link dice "they pass on to each other as many scandals as they know" che non è il nostro caso ... IMHO

Hai assolutamente ragione. Ho letto male la domanda. Ma la risposta alla tua domanda è in fondo alla stessa pagina, no?

[axpgn]

Sì, non l'avevo letto tutto, mi ero fermato quando avevo capito che era un problema diverso e non ho proseguito nella lettura