WisFaq!

Duivenhokprincipe

Hallo, we moeten deze week een huistaak maken in verband met het duivenhokprincipe (ladenprincipe).
Ik heb reeds met voorbeeldjes gemerkt dat de opgave juist is maar ik weet niet hoe ik dit moet bewijzen, is het mogelijk om hier wat info over te geven?

De opgaven zijn:
1. Bewijs dat er in een verzameling van 5 natuurlijke getallen er steeds minstens 3 te vinden zijn waarvan de som een drievoud is.
2.Bewijs dat er in een verzameling van 6 natuurlijke getallen er steeds minstens 4 te vinden zijn waarvan de som een drievoud is.
3.Tracht dit probleem uit te breiden en te bewijzen voor een verzameling van n natuurlijke getallen (n=5).

Bedankt.

Yen
30-1-2006

Antwoord

Hulpstellinkje "duivenhok":
Uit elk drietal natuurlijke getallen kan ik minstens een drievoud halen (waardoor er uiteindelijk altijd minder dan drie getallen overblijven die geen drievoud kunnen vormen)

Bewijsje "duivenhok":
Neem drie willekeurige natuurlijke getallen. Bekijk het modulo 3. Elk getal is 0,1 of 2 (modulo 3). Als er bij de drie getallen een 0 zit dan klaar. Als de 3 getallen (modulo 3) hetzelfde zijn (1,1,1) of (2,2,2) dan ook klaar.
In het andere geval heb je dus (1,1,2) of (1,2,2) en daar kan je ook een drievoud uithalen (1+2), waarmee de hulpstelling "duivenhok" voor alle varianten van drietallen bewezen is.

Het leuke hiervan is dat je nu in een klap ook 1. en 2. en 3. bewezen hebt.... ga zelf maar na Even nog wat losse eindjes aan elkaar knopen en klaar !!!

Met vriendelijke groet
JaDeX

jadex
31-1-2006