matematikk.net

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.

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!