WisFaq!

Boom met knopen van graad 1 of 2009

Beste Wisfaq,

Ik zit met de volgende vraag: gegeven is een boom met n knopen. Elk van deze knopen heeft graaf 1 of graad 2009. Bepaal de mogelijke warden van n.

Ik beschouw nu verschillende mogelijkheden:

1. Er zijn slechts twee knopen, elk met graad 1 (n=2) in dit geval
2. Beschouw een knoop (noem deze x1) met graad 2009, oftewel een knoop verbonden met 2009 andere knopen. Elk van deze 2009 andere knopen (noem deze y1 … y2009) is (afgezien van x1) verbnden met 0 andere knopen, of met 2008 anderen. In het geval dat een zeker y verbonden is met 0 andere knopen (afgezien van x1) is dit het einde van een tak. In het geval date en zekere y verbonden is met 2008 andere knopen → herhaal bovenstaande redenering.

Ik zit vast in stap 2, omdat ik geen formula kan vinden voor dit patroon en ik hoop dat jullie me daarmee kunnen helpen.

Vriendelijke groet,

Herman.

herman de vries
13-1-2009

Antwoord

Probeer het eens door vooraf het aantal (k) punten van graad 2009 vast te leggen en dan de mogelijkheden voor n uit te pluizen; misschien komt er dan een formule los.
k=0 heb je al: n=2
k=1 heb je ook al: n=2010
k=2: die twee moeten verbonden zijn (want ...), dus krijg je n=2009+2009=4018.
k=3: ...

kphart
27-1-2009