Uitwerkingen Sum of Us 1
Instant Insanity
Opgave 1A: Opgave 1B: Voor elk van de vier kubussen kun je een graaf maken die correspondeert met de desbetreffende kubus. Elk van deze grafen bevat drie lijnen. Er is een lijn tussen twee punten, wanneer de kubus de twee kleuren op twee overstaande vlakken heeft staan. Alles samenvoegen in ´e´en graaf geeft de volgende graaf:
Opgave 1C: Een oplossing bestaat uit een duo deelgrafen, deze zijn hieronder naast elkaar weergeven. E´en van de volgende drie oplossingen is goed:
Opgave 1D: Geef ´e´en van de tabellen van 1E. Afhankelijk van welke deelgrafen je in vraag 1C hebt genomen. Om van deelgrafen een oplossing te maken ga je als volgt te werk. We gaan er voor het gemak even vanuit dat de linkergraaf correspondeert met de voor en achterkant van de dobbelstenen en de rechter met de twee zijkanten (andersom zou je op hetzelfde antwoord uitkomen). We starten met de voor/achterkant, dus met de linkergraaf. Kubus 1 heeft G en B op de voor of achterkant. We kiezen bijvoorbeeld dat groen op de voorkant zit en blauw op de achterkant. Kubus 2 heeft ook een blauw vlak, kies daarom bij kubus 2 een blauwe voorkant (de kleuren aan de voor en achterkant van de toren moeten immers verschillend zijn). Daardoor weten we dat de achterkant van kubus 2 rood moet zijn. Bepaal zo de voor en achterkanten van de toren en vul dit in, in de tabel. De verdeling van links en rechts is nu nog willekeurig. Omdat we de dobbelsteen nog kunnen draaien zonder dat de voor en achterkant veranderen. Bepaal nu op dezelfde wijze als net de invulling voor de zijvlakken. Vul deze invulling in, in de tabel.
1
Opgave 1E: Een van de onderstaande tabellen is al gegeven bij vraag 1D. De andere twee krijg je door vanuit een ander duo deelgrafen op dezelfde wijze de oplossing te bepalen. Let op! Wanneer voor/achterkant of linker/rechterkant zijn verwisseld zien we dit als dezelfde oplossing! In de onderstaande tabellen zijn de kolommen voorkant/achterkant en links/rechts verwisseld. In elke tabel staan acht weergaven van dezelfde oplossing.
1e k1 k2 k3 k4
voor W B R G
achter R G B W
links G R W B
rechts B R G W
voor G R W B
achter B R G W
links W B R G
rechts R G B W
W B R G
R G B W
B R G W
G R W B
B R G W
G R W B
W B R G
R G B W
k1 k2 k3 k4
R G B W
W B R G
B R G W
G R W B
B R G W
G R W B
R G B W
W B R G
k1 k2 k3 k4
R G B W
W B R G
G R W B
B R G W
G R G W
B R W B
R G B W
W B R G
2e k1 k2 k3 k4
voor G B W R
achter B R G W
links R G B W
rechts W B R G
voor R G B W
achter W B R G
links G B W R
rechts B R G W
k1 k2 k3 k4
B R G W
G B W R
W B R G
R G B W
W B R G
R G B B
B R G W
G B W R
k1 k2 k3 k4
B R G W
G B W R
R G B W
W B R G
R G B W
W B R G
B R G W
G B W R
k1 k2 k3 k4
G B W R
B R G W
W G R G
R B B W
W B R G
R G B W
G B W R
B R G W
k k k k
1 2 3 4
2
3e k1 k2 k3 k4
voor W B R G
achter R G B W
links G R W B
rechts R B G W
voor G R W B
achter R B G W
links W B R G
rechts R G B W
k1 k2 k3 k4
W B R G
R G B W
R B G W
G R W B
R B G W
G R W G
W B R G
R G B W
k1 k2 k3 k4
R G B W
W B R G
R B G W
G R W B
R B G W
G R W B
R G B W
W B R G
k1 k2 k3 k4
R G B W
W B R G
G R W B
R B G W
G R W B
R B G W
R G B W
W B R G
3
2
Ticket to Ride
Opgave 2A:
De afbeelding hierboven geeft gevraagde de ge¨ınduceerde graaf aan. De graaf bevat enkel de 12 gevraagde knopen ´en alle lijnen tussen die knopen.
4
Opgave 2B:
Totale lengte = 22 Bovenstaande afbeelding is een van de mogelijke oplossingen. De graaf moet een boom zijn, want stel dat de graaf een cykel bevat, dan zorgt het weglaten van een lijn uit de cykel ervoor dat de kosten lager worden en aan de eisen is nog steeds voldaan. Verder moet de graaf samenhangend zijn, want elke knoop moet via een pad dat verbonden zijn met elke andere knoop. Opgave 2C: I = 9 (B = ∅) In dit algoritme ’bouw’ je de boom stap voor stap, dus je begint met de lege verzameling. Hieraan voeg je, verderop in het algoritme, elke keer een lijn aan toe tot je klaar bent. II = 15 (f (l) ≤ f (l0 ) voor alle l0 ∈ L) Dit betekent dat je een van de goedkoopste lijnen kiest. III = 6 (|B| = 6 n − 1) Een boom bevat maximaal n − 1 lijnen. Een opspannende boom moet alle punten van de graaf met elkaar verbinden. Hiervoor zijn minimaal n − 1 lijnen nodig. Een minimaal opspannende boom bevat dus precies n − 1 lijnen. IV = 11 (Voeg l toe aan B) De goedkoopste lijn uit de snede moet toegevoegd worden aan B. Door de lijnen steeds op deze manier te kiezen, kunnen er geen cykels ontstaan en heb je na het toevoegen van n − 1 lijnen, dus precies een opspannende boom gevonden. Omdat je steeds de goedkoopste lijn kiest, zijn de kosten van de opspannende boom minimaal.
5
Opgave 2D: Er zijn meerdere antwoorden mogelijk, maar hieronder staat een voorbeeld van een minimaal opspannende boom.
Totale minimale lengte = 34
6
3
Sudoku
Opgave 3A: {A1, A3, C1, C3} {A2, A4, C2, C4} {B2, B4, D2, D4} {B1, B3, D1, D3} {A1, A4, B1, B4} {A2, A3, B2, B3} {C2, C3, D2, D3} {C1, C4, D1, D4} {A1, A2, B1, B2, C1, C2, D1, D2} {A3, A4, B3, B4, C3, C4, D3, D4} Alle andere onvermijdelijke verzamelingen in de puzzel zijn verenigingen van bovenstaande onvermijdelijke verzamelingen. Opgave 3B: Dit is een minimale verzameling hints zodat de puzzel een unieke oplossing heeft. Deze hints hebben een niet-lege doorsnede met elke onvermijdelijke verzameling. De getallen in de onvermijdelijke verzamelingen liggen dan vast door de hints. Dus de puzzel heeft een unieke oplossing. Verder is het zo dat het verwijderen van een van de elementen uit de verzameling (een van de hints) ervoor zorgt dat er een onvermijdelijke verzameling is die een lege doorsnede heeft met de verzameling hints. De verzameling hints is dus minimaal. De getallen van die onvermijdelijke verzamelingen kun je dan op verschillende manieren invullen en dus heeft de puzzel geen unieke oplossing meer. Opgave 3C: Alle mogelijke oplossingen: {C6, X} met X ∈ {A3, A5, A6, B5, B6, D5, D6, E3, E5, E6, F 5, F 6} 2 1 3 2 5 6 1 3 1 2 4 6 1 3 2 5 4 1 3 6 1 3 6 5 1 6 1 4 1 3 4 1 5 3 6 3 2 3 6 5 2 Dit laatste betekent dat de rode hint gecombineerd moet worden met ´e´en van de blauwe hints. {D6, E3}
7
4
Memory
Opgave 4A: Het zijn 8 paren van 2 afbeeldingen. We gebruiken kennis van de combinatoriek om te zien dat het aantal het volgende is: 16! 16! = 8 2!2!2!2!2!2!2!2! 2! Opgave 4B: We zien dat om aan de voorwaarden te kunnen voldoen, we het bord als volgt moeten opbouwen. Op de ene helft van het bord, als we het bord horizontaal doormidden delen, moeten de acht verschillende afbeeldingen liggen. de andere 8 tegels moeten zo geordend worden op de andere helft van het bord zodat als je het bord twee keer draait, het hetzelfde bord wordt. Deze helft ligt dus geheel vast ten opzichte van de eerste helft.
Dit betekent dat we moeten uitrekenen op hoeveel manieren we de 8 verschillende tegels kunnen ordenen, hiermee hebben we het aantal borden uitgerekend. Dit is: 8! Opgave 4C: Tactiek 2 Om het maximum te krijgen zul je zo veel mogelijk tegels tweemaal moeten omdraaien. Meer dan twee keer kan niet per tegel, omdat wanneer je weet waar een paar ligt, je deze direct omdraait. Om de eerste veertien tegels allemaal twee keer om te draaien, zal het spel als volgt gaan: De eerste twee tegels zijn verschillend. Vervolgens draai je elke beurt bij je eerste tegel een afbeelding om die je nog niet tegen bent gekomen, daarom zul je nog een tegel moeten omdraaien die je nog niet kent. De tweede tegel is een afbeelding waarvan je al wel weet waar de andere helft van het paar ligt (die heb je dus al eens omgedraaid in een eerdere beurt). Deze draai je in de beurt erna direct om, deze beide tegels heb je dan dus twee keer omgedraaid. Zo ga je het bord af, tot de laatste twee tegels, deze zijn in dit geval verschillend. De laatste 2 tegels draai je echter maar 1 keer om. Om dit in te zien bekijken we de verschillende opties: – Als deze verschillend zijn, draai je de eerste tegel om en weet je al waar de andere helft van het paar ligt, omdat dit de laatste tegels zijn. De beurt daarna draai het laatste paar, dit zijn de laatste twee tegels. – Als ze hetzelfde zijn, is dit het laatste paar en hoef je ze dus enkel om te draaien. Tactiek 3 Voor het eerste paar moeten we 18 tegels omdraaien. Want in het maximale geval zijn de eerste en laatste tegel een paar. Je zult dan dus eerst alle 16 tegels moeten omdraaien en daarna nog eens het paar. Vervolgens begin je opnieuw met de overige 14 tegels. Op dezelfde manier zien we dat je dan maximaal 16 tegels moet omdraaien voor het tweede paar. Dit gaat zo door. We bekijken het moment dat er nog 4 tegels over zijn. Ook in dit geval is het nog mogelijk dat je eerst alle tegels moet omdraaien voor je het paar hebt. We moeten hierbij onthouden dat je enkel de eerste tegel die je omdraait onthoudt en alleen kijkt of de volgende tegel 8
de andere helft van het paar is of niet. Dus dit betekent dat je eerst weer 4 tegels moet omdraaien en dan draai je het paar. Voor de laatste 2 tegels hoef je natuurlijk alleen die 2 tegels om te draaien, omdat dit een paar is. Tactiek Tactiek 2 Tactiek 3
Aantal tegels maximaal 16+14=30 18+16+14+12+10+8+6+2=86
Opgave 4D: Om dit probleem te generaliseren gaan we er nu vanuit dat we in plaats van 16 tegels, 2n tegels hebben en dus n paren. We gebruiken wat we hebben gezien bij opgave 3a om dit uit te rekenen. Als je het nog niet helemaal ziet, probeer dan eens voor een ander aantal (bijvoorbeeld 10) om te vergelijken met de uitkomsten bij 16 tegels. Tactiek Tactiek 1 Tactiek 2 Tactiek 3
Aantal tegels maximaal 2 × 2n 2 × (2n − 2) + 2 Pn−2 2 + i=0 (2n + 2 − 2i)
Natuurlijk zijn formules die er anders uitzien maar hetzelfde zijn (door plaatsing van haakjes) ook correct.
9
5
Cluedo
Opgave 5A: Eerst moeten we de verwachte aantal kaarten bepalen voor 10 potjes.
Verwacht Bastiaan Willem Jasper
Kamers 26 32 26 32 26 32
Wapens 16 23 16 23 16 23
Verdachten 16 32 16 32 16 32
Nu moeten we de grenswaarde bepalen. We weten dat het significantieniveau, namelijk 10%. Nu moeten we de vrijheidsgraden bepalen. Voor de rijen zien we dat als we weten hoeveel kaarten van de kamers en wapens Bastiaan bijvoorbeeld heeft gekregen, dan weten we hoeveel verdachten ze heeft gekregen. Dit omdat je weet hoeveel kaarten ieder krijgt (namelijk 6). Dit betekent dus dat er 2 vrijheidsgraden zijn in de rijen. Ook weet je van elke kaart (kamers, wapens en verdachten) hoeveel er in het spel zitten, dus als je weet hoeveel kamers bijvoorbeeld Bastiaan en Willem hebben, weet je hoeveel Jasper er heeft. Dit is dus ook 2 vrijheidsgraden in de kolommen. In totaal is dit dus 4 vrijheidsgraden. De grenswaarde is dan 7.78. Daarna tellen we de waarnemingen op om te kijken wat er daadwerkelijk is waargenomen over die 10 potjes.
Verwacht Bastiaan Willem Jasper
Kamers 25 20 35
Wapens 20 20 10
Verdachten 15 20 15
Om de χ2 -waarde te berekenen moeten we de formule invullen. Voor het gemak berekenen (o −e )2 we eerst de componenten ij eij ij . Daarna zullen we die optellen. Verwacht Bastiaan Willem Jasper
Kamers 0.1042 1.6667 2.6042
Wapens 0.6667 0.6667 2.6667
Verdachten 0.1667 0.6667 0.1667
Nu berekenen we de χ2 -waarde: χ2 = 0.1042 + 0.667 + 0.1667 + 1.6667 + 0.6667 + 2.6042 + 2.6667 + 0.1667 = 9.375 Dus de χ2 -waarde is dus 9.375. Jasper speelt wel vals
Opgave 5B: Om een verwachtingswaarde uit te rekenen moeten we de verschillende mogelijke situaties bedenken. We bekijken het geval dat Willem om een kamer vraagt, en de wapen en verdachte zelf op handen heeft. De andere twee gevallen gaan op een gelijke wijze. Er zijn 2 situaties mogelijk. Namelijk dat er geen kaart wordt getoond, (niemand heeft de gevraagde kamer in handen) of dat er wel een kaart wordt getoond. (iemand heeft de gevraagde kamer wel in handen.) Voor deze situaties bepalen we de RGI en de kans. 10
niet Voor de RGI vulen we de gegeven formule in. V´o´or het uitspreken van het vermoeden wist Willem nog niets over 6 kamers (er zijn 9 kamers totaal en hij heeft er 3 in handen, die zijn het dus niet). In de teller komt nu ook 6. We zien dus: RGI = 1. De kans dat deze situatie zich voordoet is 16 , dit is de kans dat precies de kamer die Willem vermoedt, in de envelop zit. De 3 die hij in handen heeft zitten er immers sowieso niet in. wel Ook nu rekenen we de RGI uit met de formule. In de noemer staat een 6 (zoals hierboven) en in de teller staat een 1. Dus: RGI = 61 . De kans dat deze situatie zich voordoet is de kans dat een andere kamer dan de gevraagde kamer in de geheime envelop zit. Dit is dus 5 6. Voor het wapen en het verdachte gaat dit hetzelfde. Alleen staat steeds in de noemer steeds respectievelijk 4 (6 − 2) en 5 (6 − 1). Gekozen kaart Kamer Wapen Verdachte
Verwachtinswaarde van de RGI 1 5 1 11 6 × 1 + 6 × 6 = 36 ≈ 0.31 1 3 1 7 4 × 1 + 4 × 4 = 16 ≈ 0.44 1 4 1 9 5 × 1 + 5 × 5 = 25 ≈ 0.36
Conclusie: Willem kan het beste om een Wapen te vragen. Opgave 5C: We bekijken eerst het geval dat hij een kamer en verdachte vraagt. (kamer en wapen is equivalent) Er zijn 4 situaties mogelijk. Namelijk a. dat er niet een kaart wordt laten zien, (niemand heeft de gevraagde kamer ´en verdachte in handen) b. dat iemand de gevraagde kamer in handen heeft en de gevraagde verdachte in de envelop zit c. dat iemand de gevraagde verdachte in handen heeft en de gevraagde kamer in de envelop zit d. kamer en verdachte zitten beide NIET in de envelop (beide kaarten zitten in handen van de andere spelers) Voor deze situaties bepalen we de RGI en de kans. 1 ad a. De kans dat deze situatie zich voordoet is 28 . Voor de RGI vulen we de gegeven formule in. V´o´or het uitspreken van het vermoeden wist Willem nog niets over 7 kamers en 4 verdachten. Voor beide weet hij nu dat ze in de envelop zitten. Dus RGI = 1 + 1 = 2. 6 ad b. De kans dat deze situatie dit voordoet is 28 . Als je een kamer te zien krijgt kun je niet weten of de verdachte in de envelop zit, of dat deze nog bij een speler in handen zit. Je wint dus enkel informatie ten opzichte van de kamer. Dus RGI = 71 . 3 ad c. De kans dat deze situatie dit voordoet is 28 . Als je een verdachte te zien krijgt kun je niet weten of de kamer in de envelop zit, of dat deze nog bij een speler in handen zit. Je wint dus enkel informatie ten opzichte van de verdachte. Dus RGI = 14
11
ad d. De kans dat deze situatie dit voordoet is 18 28 . Voor de RGI moeten we even goed nadenken. We moeten hier apart een soort verwachting berekenen. Je krijgt namelijk maar 1 kaart te zien, er zijn dus 2 verschillende situaties mogelijk. De kans dat je verdachte te zien krijgt is 12 , een kamer is dan 21 . Deze kansen moeten dan gecombineerd worden met de RGI per mogelijkheid ( 41 of 17 ). RGI =
1 1 1 1 11 × + × = 4 2 7 2 56
Voor de kamer en het wapen en verdachtre en het wapen gaat dit hetzelfde. Dat geeft de volgende tabel: Gekozen kaarten Kamer en wapen Kamer en verdachte Verdachte en wapen
Verwachtinswaarde van de RGI 1 6 1 3 1 18 11 28 × 2 + 28 × 7 + 28 × 4 + 28 × 56 ≈ 0.26 1 6 1 3 1 18 11 28 × 2 + 28 × 7 + 28 × 4 + 28 × 56 ≈ 0.26 1 3 1 3 1 9 2 16 × 2 + 16 × 4 + 16 × 4 + 16 × 8 ≈ 0.36
Conclusie: Willem kan het beste om een wapen en verdachte te vragen.
12
