Mastermindcode kraken
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Mastermindcode kraken
Waarschijnlijk kent iedereen hier mastermind wel, je hebt een code die kan bestaan uit een bepaald aantal kleuren vervolgens mag de ander gaan raden. De ander gokt een bepaalde combinatie en vervolgens wordt met zwarte en witte pinnetjes aangegeven hoeveel kleuren er goed staan (zwart) en hoeveel kleuren er wel in zitten maar niet op de juiste plek staan (wit), er wordt niet aangegeven welke kleuren goed staan.
Nu vroeg ik me af hoeveel zetten je maximaal nodig hebt om de code van de ander te kraken, bijvoorbeeld in de situatie waarbij je 6 kleuren mag verdelen over 5 plaatsen (kleurherhaling uiteraard toegestaan) of in de situatie waarin je n kleuren mag verdelen over k plaatsen (kleurherhaling uiteraard weer toegestaan).
Nu vroeg ik me af hoeveel zetten je maximaal nodig hebt om de code van de ander te kraken, bijvoorbeeld in de situatie waarbij je 6 kleuren mag verdelen over 5 plaatsen (kleurherhaling uiteraard toegestaan) of in de situatie waarin je n kleuren mag verdelen over k plaatsen (kleurherhaling uiteraard weer toegestaan).
- Berichten: 5.679
Re: Mastermindcode kraken
Even een ruwe schatting. Als we het aantal plaatsen P noemen en het aantal kleuren K, dan zijn er KP mogelijkheden, en per beurt krijgt je W witte en Z zwarte pinnetjes met W en Z [grotergelijk]0 en W+Z[kleinergelijk]P.
Voor de pinnetjes zijn er per beurt W=0..P(P+1-W) mogelijkheden (want W kan 0 t/m P zijn, en bij iedere W zijn er P+1-W mogelijkheden voor Z) = n=1..P+1n = (P+1)(P+2)/2.
Per beurt kun je dus maximaal (P+1)(P+2)/2 gevallen onderscheiden, waardoor het aantal beurten dat je nodig hebt in ieder geval (P+1)(P+2)/2Log(K)[.]P is.
In het geval dat K=6 en P=5 is dat dus minstens 4 beurten. Maar dan hou je nog geen rekening met het gegeven dat je niet in elke beurt (P+1)(P+2)/2 zinnige gevallen kunt afsplitsen, of dat sommige van die pinnetjes-combinaties veel meer overgebleven mogelijkheden open laten dan andere. Als je dat ook meeneemt zal het benodigde aantal beurten wel hoger worden.
Voor de pinnetjes zijn er per beurt W=0..P(P+1-W) mogelijkheden (want W kan 0 t/m P zijn, en bij iedere W zijn er P+1-W mogelijkheden voor Z) = n=1..P+1n = (P+1)(P+2)/2.
Per beurt kun je dus maximaal (P+1)(P+2)/2 gevallen onderscheiden, waardoor het aantal beurten dat je nodig hebt in ieder geval (P+1)(P+2)/2Log(K)[.]P is.
In het geval dat K=6 en P=5 is dat dus minstens 4 beurten. Maar dan hou je nog geen rekening met het gegeven dat je niet in elke beurt (P+1)(P+2)/2 zinnige gevallen kunt afsplitsen, of dat sommige van die pinnetjes-combinaties veel meer overgebleven mogelijkheden open laten dan andere. Als je dat ook meeneemt zal het benodigde aantal beurten wel hoger worden.
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 385
Re: Mastermindcode kraken
minimum 1 en maximum oneindig als je een zeer groot kalf bent.
Re: Mastermindcode kraken
Ik ga er natuurlijk wel vanuit dat je altijd de 'beste' zet doet, dat wil zeggen de zet waarmee je de meeste codes uitsluit.minimum 1 en maximum oneindig als je een zeer groot kalf bent.
- Berichten: 5.679
Re: Mastermindcode kraken
Aanvulling op hierboven: P-1 zwarte pinnetjes en één witte kan natuurlijk niet, dus die (P+1)(P+2)/2 wordt één minder: P(P+3)/2.
Je kunt met een bepaalde zet niet zonder meer combinaties uitsluiten, want dat hangt af van de pinnetjes die je krijgt. Je wilt juist onderscheiden: je moet de zet nemen waarvoor zoveel mogelijk van de overgebleven mogelijke codes met verschillende pinnetjes worden beantwoord, liefst een beetje gelijkmatig verdeeld qua aantallen.Ik ga er natuurlijk wel vanuit dat je altijd de 'beste' zet doet, dat wil zeggen de zet waarmee je de meeste codes uitsluit.
In theory, there's no difference between theory and practice. In practice, there is.
Re: Mastermindcode kraken
hmm, ik ging daarnet alle mogelijkheden voor 5 plaatsen opschrijven en ik kwam hierop:
GGGGG
GGGGW
GGGGZ
GGGWW
GGGWZ
GGGZZ
GGWWW
GGWWZ
GGWZZ
GGZZZ
GWWWW
GWWWZ
GWWZZ
GWZZZ
GZZZZ
WWWWW
WWWWZ
WWWZZ
WWZZZ
WZZZZ
ZZZZZ
Dat zijn dus 21 mogelijkheden.
GGGGG
GGGGW
GGGGZ
GGGWW
GGGWZ
GGGZZ
GGWWW
GGWWZ
GGWZZ
GGZZZ
GWWWW
GWWWZ
GWWZZ
GWZZZ
GZZZZ
WWWWW
WWWWZ
WWWZZ
WWZZZ
WZZZZ
ZZZZZ
Dat zijn dus 21 mogelijkheden.
- Berichten: 5.679
Re: Mastermindcode kraken
Dat was die (P+1)(P+2)/2 die ik eerst had, maar deze combinatie kan niet: WZZZZKlaaskaas schreef:hmm, ik ging daarnet alle mogelijkheden voor 5 plaatsen opschrijven en ik kwam hierop:
(...)
Dat zijn dus 21 mogelijkheden.
Je kunt er niet 4 goed hebben en één op een foute plek
Daarom P(P+3)/2, als P=5 dan is dat 20.
In theory, there's no difference between theory and practice. In practice, there is.
Re: Mastermindcode kraken
ohjaRogier schreef:Dat was die (P+1)(P+2)/2 die ik eerst had, maar deze combinatie kan niet: WZZZZKlaaskaas schreef:hmm, ik ging daarnet alle mogelijkheden voor 5 plaatsen opschrijven en ik kwam hierop:
(...)
Dat zijn dus 21 mogelijkheden.
Je kunt er niet 4 goed hebben en één op een foute plek
Daarom P(P+3)/2, als P=5 dan is dat 20.
- Berichten: 4.810
Re: Mastermindcode kraken
dan kan GWWWW en GZZZZ ook niet dus dat maakt 18
maar heb je er dan ook aan gedacht dat gzwzg kan ? en ook gzgzw ? Er zijn dus duidelijk wel meer combinaties [/i]
maar heb je er dan ook aan gedacht dat gzwzg kan ? en ook gzgzw ? Er zijn dus duidelijk wel meer combinaties [/i]
-
- Berichten: 104
Re: Mastermindcode kraken
Stel dat x aantal combinaties gelijkwaardig zijn voor de volgende zet. Dan moet je hiervan in de veronderstelling dat je het antwoord weet, de slechtste combinatie van nemen.Rogier schreef:Aanvulling op hierboven: P-1 zwarte pinnetjes en één witte kan natuurlijk niet, dus die (P+1)(P+2)/2 wordt één minder: P(P+3)/2.
Je kunt met een bepaalde zet niet zonder meer combinaties uitsluiten, want dat hangt af van de pinnetjes die je krijgt. Je wilt juist onderscheiden: je moet de zet nemen waarvoor zoveel mogelijk van de overgebleven mogelijke codes met verschillende pinnetjes worden beantwoord, liefst een beetje gelijkmatig verdeeld qua aantallen.Ik ga er natuurlijk wel vanuit dat je altijd de 'beste' zet doet, dat wil zeggen de zet waarmee je de meeste codes uitsluit.
- Berichten: 5.679
Re: Mastermindcode kraken
Die kunnen allemaal wel hoorCycloon schreef:dan kan GWWWW en GZZZZ ook niet dus dat maakt 18
maar heb je er dan ook aan gedacht dat gzwzg kan ? en ook gzgzw ? Er zijn dus duidelijk wel meer combinaties [/i]
Als de code rood-groen-blauw-geel-paars is, en jij doet rood-groen-blauw-geel-oranje, dan krijg je GZZZZ...
En als je oranje-rood-groen-blauw-geel kiest, krijg je GWWWW
In theory, there's no difference between theory and practice. In practice, there is.
-
- Berichten: 104
Re: Mastermindcode kraken
Als K=2 en P=2, dan is het maximum aantal zetten M=3.
Voor K=6 en P=5 zou M wel eens zeer hoog kunnen liggen.
Voor K=6 en P=5 zou M wel eens zeer hoog kunnen liggen.