Skip to main content

Het paleis van de sultan is heel bijzonder, zoals de tekening laat zien. Vanuit zijn kamer (S) loopt een netwerk van gangen, die alle óf noord-zuid óf west-oost georiënteerd zijn.

Bij P is de kamer van de prinses. Elke nacht wil de sultan de prinses bezoeken om haar een sprookje te vertellen. Maar op de tocht naar de prinses mag hij alleen maar een zuidelijke of oostelijke richting inslaan (in de tekening dus slechts naar beneden of naar rechts). Hij stelt zichzelf ook nog de eis, dat hij daarbij elke mogelijke route van S naar P precies één keer zal afleggen.

Hoeveel nachten is de sultan hiermee dan bezig?

Antwoord

Niet te geloven: 1001 nacht!

De verklaring gaat als volgt. De sultan moet 10 keer naar het oosten en 4 naar het zuiden bewegen. Twee van de vele mogelijkheden zijn dus: ZOOOZOOOOOZZOO en OOZOOOOOZZOOOZ.

De vraag is dus op hoeveel manieren je 10 O’s en 4 Z’s kunt rangschikken, zonder twee keer dezelfde reeks te vormen.

We stellen ons voor dat we 14 lege vakjes hebben. In 4 ervan moet een Z komen (de overige 10 zijn dus O’s). Voor de eerste te plaatsen Z heb je 14 mogelijke posities (want alles is nog leeg). Voor de tweede zijn er 13, voor de derde 12 en voor de vierde 11 mogelijkheden. Dat wil zeggen dat er 14 × 13 × 12 × 11 = 24024 mogelijke rangschikkingen zijn. Maar dat zijn er wel teveel. Immers bij het plaatsen van de vier Z’s hoeven we geen rekening te houden met de volgorde (of je nu de eerste Z, de tweede Z, de derde Z of de vierde Z op de eerste plek van de reeks zet, dat maakt geen verschil: in alle gevallen ga je een gang naar beneden). Nu kun je vier Z’s (of welke vier andere objecten je maar neemt) op 4 × 3 × 2 × 1 = 24 manieren rangschikken. In de genoemde 24024 mogelijkheden komt dus elke variant 24 keer voor. Daarom is het aantal werkelijk verschillende routes 24024 : 24 = 1001.

 

Alternatieve oplossing

In de tekening is aangegeven op hoeveel manieren elk ‘kruispunt’ in het paleis (vanuit punt S) is te bereiken.

Bijvoorbeeld de plaats waar het getal 55 staat is vanuit het noorden op 10 manieren te bereiken en vanuit het westen op 45 manieren. Zo kan het hele diagram worden ingevuld. Bij P verschijnt dan het getal 1001.

Overigens is de uitkomst ook te vinden met de bekende driehoek van Pascal (die je trouwens in de figuur hierboven ook kunt vinden, als je ‘diagonaal’ kijkt). De waarde is gelijk aan het aantal manieren waarop je vier elementen uit een totaal van 14 kunt kiezen.

Wiskundig is dat 14!/4!(14-4)! = 1001.