Cursus voor deelnemers Beverwedstrijd
Klaar voor de volgende uitdaging na de Beverwedstrijd? Wil je moeilijkere puzzels oplossen, andere puzzel-fans ontmoeten en kans maken op meer prijzen? Zet de volgende stap naar de Nederlandse Informatica Olympiade! Combineer programmeren met uitdagende Beverwedstrijd-achtige problemen, en maak kans om Nederland te vertegenwoordigen bij de International Olympiad in Informatics. Wil je je inschrijven voor de cursus? Of wil je wanneer het zover is op de hoogte blijven?
Antwoorden puzzel
Laten we elke bevercoin een nummer van 1 t/m 9 geven om ze uit elkaar te houden.
Als eerste wegen we een stapel met bevercoins 1, 2 en 3 tegen een stapel met bevercoins 4, 5 en 6.
Er zijn nu drie opties:
- De stapel met 1, 2 en 3 is lichter: De nepmunt is 1, 2 of 3
- De stapel met 4, 5 en 6 is lichter: De nepmunt is 4, 5 of 6
- De twee stapels zijn even zwaar: De nepmunt is 7, 8 of 9
- Één van de twee bevercoins is lichter: Dit is de nepmunt
- Ze zijn even zwaar: De overige munt is de nepmunt
Dit kan minimaal in 3 keer wegen.
Als we meer dan 9 bevercoins hebben, is onze strategie van opdracht A niet meer mogelijk. Het is duidelijk dat we dus meer dan 2 keer wegen nodig zullen hebben.
Laten we in plaats van 25 bevercoins, werken met 27 bevercoins. We kunnen 2 groepen van 9 bevercoins tegen elkaar wegen. Als een van deze twee groepen lichter is dan de ander, zit de nepmunt in die groep. Anders zit de nepmunt in de overige groep bevercoins. Nu hebben we 9 bevercoins, dus kunnen we de strategie van vraag A toepassen om in 2 keer de nepmunt te vinden.
Gezien we met 27 bevercoins de nepmunt in 3 keer wegen kunnen vinden, kan dit ook met 25 bevercoins. En gezien we al hebben laten zien dat het niet in 2 keer kan, is dit antwoord optimaal.
Als we meer dan 9 bevercoins hebben, is onze strategie van opdracht A niet meer mogelijk. Het is duidelijk dat we dus meer dan 2 keer wegen nodig zullen hebben.
Laten we in plaats van 25 bevercoins, werken met 27 bevercoins. We kunnen 2 groepen van 9 bevercoins tegen elkaar wegen. Als een van deze twee groepen lichter is dan de ander, zit de nepmunt in die groep. Anders zit de nepmunt in de overige groep bevercoins. Nu hebben we 9 bevercoins, dus kunnen we de strategie van vraag A toepassen om in 2 keer de nepmunt te vinden.
Gezien we met 27 bevercoins de nepmunt in 3 keer wegen kunnen vinden, kan dit ook met 25 bevercoins. En gezien we al hebben laten zien dat het niet in 2 keer kan, is dit antwoord optimaal.
In de vorige vraag hebben we een patroon kunnen herkennen:
We kunnen de overige bevercoins altijd in drie groepen verdelen
en dan met 1 keer wegen bepalen in welk van de drie groepen de nepmunt zit.
Hierdoor kunnen we met elke keer wegen de groep drie keer zo klein maken.
Als we voor een getal willen bepalen hoe vaak we moeten wegen, moeten we kijken hoe vaak we het getal drie keer zo klein kunnen maken voordat we minder dan 1 munt over hebben.
Voor 25 is dit bijvoorbeeld 3 keer:
25 → 8.333 → 2.778 → minder dan 1
Voor 50 is dit 4 keer:
50 → 26.667 → 5.556 → 1.852 → minder dan 1
Als we voor een getal willen bepalen hoe vaak we moeten wegen, moeten we kijken hoe vaak we het getal drie keer zo klein kunnen maken voordat we minder dan 1 munt over hebben.
Voor 25 is dit bijvoorbeeld 3 keer:
25 → 8.333 → 2.778 → minder dan 1
Voor 50 is dit 4 keer:
50 → 26.667 → 5.556 → 1.852 → minder dan 1
De oplossing voor dit probleem lijkt op een veel voorkomende techniek in Competitief Programmeren, zoals Binary Search en Divide and Conquer.
Bij deze technieken gaat het erom dat je een probleem op een grote hoeveelheid waardes herhaaldelijk opsplitst in kleinere problemen.
Zo kun je met Binary Search snel een waarde vinden in een gesorteerde lijst getallen. Je kan dit doen door te kijken of het middelste getal van je gesorteerde lijst groter of kleiner is dan de waarde waar je naar zoekt. Als hij groter is, weet je dat de waarde waar je naar zoekt links van het midden ligt. Zo heb je dus het aantal getallen wat je doorzoekt, 2 keer zo klein gemaakt. Als je dit herhaaldelijk blijft doen, kun je snel je waarde vinden.
Op zoek naar meer van dit soort puzzels? Schrijf je nu in voor de maillijst!
Zo kun je met Binary Search snel een waarde vinden in een gesorteerde lijst getallen. Je kan dit doen door te kijken of het middelste getal van je gesorteerde lijst groter of kleiner is dan de waarde waar je naar zoekt. Als hij groter is, weet je dat de waarde waar je naar zoekt links van het midden ligt. Zo heb je dus het aantal getallen wat je doorzoekt, 2 keer zo klein gemaakt. Als je dit herhaaldelijk blijft doen, kun je snel je waarde vinden.
Op zoek naar meer van dit soort puzzels? Schrijf je nu in voor de maillijst!
