Pythagoras april 1999

door André de Boer

Er bestaat een wiskundig principe dat ladenprincipe heet. In het Engels: `pigeon-hole principle'. Het principe zegt dat als je 10 duiven over 9 hokken verdeelt, er minstens één hok is dat twee duiven bevat.

Dat dit klopt ligt voor de hand. Toch kun je met behulp van dit principe allerlei verrassende uitspraken bewijzen. Zie de volgende vijf beweringen, die je kunt bewijzen met behulp van het ladenprincipe.

1. In een groep van duizend mensen zijn er altijd twee op dezelfde dag jarig.

2. Er zijn in Nederland altijd twee mensen met hetzelfde aantal haren op hun hoofd.

3. Op een feestje met zes mensen bestaat er ofwel een drietal dat elkaar vantevoren al kende, ofwel een drietal dat elkaar van te voren helemaal niet kende.

4. Er bestaan twee machten van drie waarvan het verschil deelbaar is door 1999.

5. Er bestaat een macht van drie die eindigt op 001.

Tien gasten, negen kamers

De oplossing van dit raadsel kun je, evenals de bewijzen van de vijf uitspraken, vinden op de homepage van Pythagoras. Heb je geen Internet, stuur dan een briefje naar de redactie, dan krijg je de oplossing thuisgestuurd.

Voor het ladenprincipe zie ook: www.cut-the-knot.com/do_you_know/pigeon.html.

Tien vermoeide reizigers
Zochten onderkomen voor nacht en regen
Maar bij de herberg aanbeland
had de waard niet meer kamers dan negen

De waard was echter akelig slim
Hij gaf elk een eigen stee:
De eerste twee bracht hij naar kamer I
De derde leidde hij naar II

De vierde kreeg kamer III
Naar kamer IV ging nummer vijf
In V werd nummer zes gestopt
Zeven kreeg VI als nachtverblijf

De achtste sliep in VII, de negende in VIII
En terug naar I ging onze waard
Waar hij zoals gezegd
Twee reizigers had bewaard

Daarvan nam hij één, nummer tien en laatst
en bracht hem onder in kamer IX
Negen eenpersoonskamers werden zo
Is het geen wonder, opgemaakt voor tien!

De oplossing van de drogredenering

Als je het verhaaltje goed leest, dan doet de waard het volgende:

De bewijzen van de vijf uitspraken

1. In een groep van duizend mensen zijn er altijd twee op dezelfde dag jarig.

Bewijs. We gaan 1000 mensen verdelen over 365 dagen. Het ladenprincipe zegt dan dat er minstens twee mensen op dezelfde dag terechtkomen.

2. Er zijn in Nederland altijd twee mensen met hetzelfde aantal haren op hun hoofd.

Bewijs. Een mens heeft ongeveer 100.000 haren op zijn hoofd. Als we van alle 16 miljoen Nederlanders van ieder het aantal hoofdharen tellen, dan krijgen we 16 miljoen getallen tussen de nul en (zeg) 200.000. Het ladenprincipe zegt dat minstens twee ervan gelijk zijn.

3. Op een feestje met zes mensen bestaat er ofwel een drietal dat elkaar van tevoren al kende, ofwel een drietal dat elkaar van tevoren helemaal niet kende.

Bewijs. Noteer de 6 mensen met A, B, C, D, E en F.

Stap 1. Merk op dat onder de vijf mensen B, C, D, E, F er op zijn minst drie zijn die óf A al kende óf A niet kende.

Dit volgt uit het ladenprincipe, immers: óf slechts één persoon kent A en dan zijn er meer dan drie die A niet kennen, óf twee personen kennen A en dan zijn er precies drie die A niet kennen, óf drie of meer personen kennen A.

Stap 2. Neem eerst aan dat B, C, en D ooit kennis hebben gemaakt met A. Dan zijn er twee mogelijkheden: (I) B, C, en D zijn vreemdelingen voor elkaar, en dan zijn we klaar, (II) er is een tweetal, zeg B en C, dat elkaar al kende. Dan zijn we ook klaar, immers: A kent B, A kent C en B kent C. In beide gevallen zijn we klaar.

Stap 3. Wanneer B, C en D alle drie geen bekenden van A zijn, dan gaat het bewijs op dezelfde manier als in stap 2, alleen met `bekend' en `onbekend' verwisseld.

4. Er bestaan twee machten van drie waarvan het verschil deelbaar is door 1999.

Bewijs: Er zijn 1999 verschillende resten mogelijk wanneer we een willekeurig getal delen door 1999. Bijvoorbeeld, de rest van 2345 gedeeld door 1999 is gelijk aan 346 (want ).

Beschouw de volgende rij van machten van 3: . Deze bevat 2000 getallen. Volgens het ladenprincipe zijn er minstens 2 machten in die rij, laten we zeggen 3ⁿ en 3^m, die dezelfde rest hebben bij deling 1999. Het verschil van deze machten heeft rest 0 bij deling door 1999. Met andere woorden, het verschil is deelbaar door 1999. Dan is 3ⁿ-3^m deelbaar is door 1999 en zijn we klaar met het bewijs.

5. Er bestaat een macht van drie die eindigt op 001.

Bewijs: Net als in het bewijs van 4 kunnen we twee getallen n en m (n>m) vinden, waarvoor geldt dat 3ⁿ en 3^m dezelfde rest hebben bij delen door 1000. Dus is deelbaar door 1000. Daar 1000 en 3^m geen gemeenschappelijke factoren hebben moet de tweede factor 3^n-m-1 deelbaar zijn door 1000. Dat kan alleen als dit getal eindigt op 000. Maar dat houdt weer in dat 3^n-m eindigt op 001.
Notice: Undefined variable: footer_php_included in /websites/users/pyth/public_html/pythwww/common/footer.php on line 2

Deprecated: setlocale() [function.setlocale]: Passing locale category name as string is deprecated. Use the LC_* -constants instead in /websites/users/pyth/public_html/pythwww/common/footer.php on line 5