Nissen alver [julenøtt]

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
skf95
Descartes
Descartes
Innlegg: 421
Registrert: 17/12-2010 14:35

Julenissen har akkurat mottatt ønskelisten til Vaktmester fra matematikk.net. Han innser han har dårlig tid, og trenger derfor hjelp av så mange alver som mulig. Faktisk anslår han at minst 150 alver totalt må til for å bli ferdig i tide. Han ber sin sekretæralv om å sende ønskelisten til tre nye alver, med oppfordring om at disse gjør det samme (altså at hver av dem sender ønskelisten videre til ytterligere 3 alver). Noen alver er pliktoppfyllende og gjør som de blir bedt om, mens andre lar være. Dagen etter, når spredningen av ønskelisten har stoppet opp, har 101 alver mottatt ønskelisten, men ikke sendt den videre.

Rekker julenissen og hans alver å bli ferdig i tide? Anta ingen alver mottar ønskelisten flere ganger, og at alle som mottar den hjelper til med å lage gaver.
Vaktmester
World works; done by its invalids
World works; done by its invalids
Innlegg: 827
Registrert: 26/04-2012 09:35

Jeg får litt assosiasjoner til robotjulenissen i Futurama av dette :-) "I'll be back. Back when you least expect it: Next christmas!!"

Vi har her et ternært tre hvor alle nodene enten har 0 eller 3 barn. Vi vet at treet har 101 bladnoder, og ønsker at det totalt skal inneholde minst 150 noder.

Antall bladnoder i et tre med n noder er $(2n+1) / 3$

Her burde jeg sikkert utledet formelen, men..

Løser $(2n+1) / 3 = 101$ for n og får $n=151$

Altså får Vaktmester julegaven sin. Yey!
Svar