Matematik, fråga om Induktion
Hejhej!
Har en fråga jag kört fast med, hoppas någon kan hjälpa :(
Var och en av n>=4 personer känner till en hemlig upplysning som inte är identisk med någon annans. Visa att det räcker med 2n-4 telefonsamtal mellan dessa personer för att alla ska känna till alla hemligheter. Vi förutsätter att alla har tillgång till en telefon och att under varje samtal utbyts alla hemligheter som båda talande känner till.
Har ingen aning om vart jag ens ska börja.. Något med induktion iaf.
Tack i förhand!
Vet du hur ett induktionsbevis fungerar? Det består av tre steg:
Basen: Visa att påståendet är sant för det första talet (n=4)
Induktionsantagandet: Anta att påståendet är sant för ett fixt n
Induktionssteget: Visa att givet antagandet ovan är påståendet sant för n+1.
(Ska man vara petig ska man efter det tredje steget också hänvisa till induktionsaxiomet, som säger att om stegen ovan är uppfyllda så är påståendet sant för varje tal)
Så det du behöver göra först är att visa att det är sant för n=4 (hur många telefonsamtal behövs då?). Därefter behöver du komma på ett sätt att sprida informationen mellan n+1 personer på 2(n+1)-4 samtal, givet att det går att sprida den mellan n personer på 2n-4 samtal. Hur många extra samtal har du på dig jämfört med när det var en färre deltagare? Vad ska du använda de samtalen till?
Problemet är ett känt problem kallat on a telephone problem som första gången löstes av Rob Tjideman år 1971. Idag är problemet mer känt som the gossip problem. Det är ett ganska omfattande att bevisa detta problem som kräver fördjupade kunskaper inom diskret matematik. Ett exempel på detta finner du här.
Det är, som du säger, svårt att visa att 2n-4 är undre gräns. Det är däremot (relativt) lätt att visa att det är tillräckligt, vilket den här uppgiften gick ut på.
