informatie

deel 1: het is mogelijk met $2n-2$ keer te bellen

Beschouw de personen $A_1,A_2 \dots A_n$ met elk één stukje informatie.
Stap $1$: $A_1$ belt naar $A_n$, dit is sowieso de eerste stap omdat iedereen toch maar één stukje informatie heeft.
Stap $2$:$A_2$ belt naar $A_n$
...
Stap $n-1$: $A_{n-1}$ belt naar $A_n$

"Dit is de snelste manier om één iemand alle informatie te geven, omdat $n-1$ mensen hun informatie aan $1$ iemand moeten geven. "
Alternatief : $A_i$ belt $A_{i+1}$ telkens, op die manier zal na $n-1$ keer $1$ persoon alles weten, maar ook de anderen weten al informatie.
Vervolgens weten we dat al de andere $n-1$ mensen altijd een tekort aan informatie hebben, en ze moeten dus nog minstens één keer opgebeld worden. Dus als $A_n$ nog $n-1$ keer belt, heeft iedereen alle informatie. Het totaal aantal telefoontjes is dus gelijk aan $2n-2$, we hebben dus al bewezen dat het mogelijk is met $2n-2$ keer te bellen.

deel 2
We bewijzen nu dat het niet mogelijk is met minder dan $2n-2$ keer te bellen.

Bewijs: Met ieder telefoontje kan max. $1$ persoon alle info vanaf dan weten.
Stel $t= max_{i=1}^{i=n} ($stukken info geweten door A_i$)$
Stel $s= $ aantal personen die alle stukken info hebben.

Merk op dat in iedere telefoontje $t$ en $s$ met max. $1$ kunnen worden verhoogd.
$t$ en $s$ kunnen beide verhoogd worden met $1$ aesa de persoon die gebeld werd, alles weet na het telefoontje, maar hiervoor niemand alle info wist.

Bij het einde is $t+s= n+n=2n.$
Bij de start is $t+s= 1+0=1$
We moeten dus minimaal $2n-1$ keer $t+s$ kunnen ophogen met $1$ (waarbij $1$ keer dubbel werd gerekend)
Dat geeft dat er minimaal $(2n-1)-1$ keer gebeld moest worden.

QED