Drugs op school
Opgave - PUMA 2009 vraag 2
Op een school zitten 2009 studenten, elke twee studenten zijn ofwel bevriend met elkaar, ofwel niet bevriend met elkaar. Een drugshandelaar wil nu enkele studenten omkopen om op die school te dealen. Hij wil dit zodanig doen dat twee dealers nooit bevriend zijn met elkaar, maar wel iedere niet-dealende student bevriend is met minstens één dealer. Toon aan dat als hij zijn dealers goed kiest (en iedereen omkoopbaar is), dit altijd mogelijk is, ongeacht wie er juist met wie bevriend is.
- login om te reageren
Oplossing
Als iemand bevriend is met een dealer noemen we die een klant. We construeren een geschikte verzameling dealers.
Herhaal volgend proces, tot iedere student ofwel dealer of ofwel klant is:
Dit proces moet stoppen (want in elke stap stijgt het aantal dealers, maar er kunnen nooit meer dan 2009 dealers zijn, want er zijn maar zoveel studenten in totaal). Wanneer het stopt zijn nooit twee dealers bevriend (gezien we dit steeds zo gekozen hebben bij het aanduiden van dealers) en is iedereen die geen dealer noodzakelijk een klant (anders was het proces nog niet gestopt) en dus per definitie bevriend met een dealer.