De winnaar van de breinbreker van oktober 2021 is Robbe Schildermans. Hoera! We belonen dit met een abonnement op het wiskundetijdschrift Pythagoras. We ontvingen ook correcte inzendingen van Jasper Devreker en Steven Van Overberghe. Bedankt!
Oplossing:
Merk vooreerst op dat een gangster die geen geldt bij zich heeft niet neergeschoten kan worden.
Elke gangster wil als eerste prioriteit blijven leven dus ze zullen altijd een bedrag nemen waarmee ze zeker zijn dat ze levend de kelder kunnen verlaten. Dit bedrag bestaat altijd door de vorige opmerking.
We tonen nu met inductie twee eigenschappen aan:
Inductie hypothese Als er n gangsters zijn en 20n briefjes verlaten ze de kelder allemaal levend 20 briefjes.
Inductie basis, n = 1: Dan neemt de enige gangster gewoon het geldt en gaat naar buiten.
Inductie stap, n > 1:
Als de eerste gangster 20 briefjes neemt weten de andere gangsters door (*) dat ze ook 20 briefjes gaan krijgen. Dus zullen ze die niet neerschieten.
Stel uit het ongerijmde dat de eerste gangster (die we A noemen) strikt meer dan 20 briefjes neemt. Dan blijven er strikt minder dan 20n briefjes over, dus is er een volgende gangster (B) die met strikt minder dan 20 briefjes de kelder levend zal verlaten. Maar dan had B beter A neergeschoten, wat niet kan want alle gangsters verlaten de kelder levend.