Moeilijk bewijs(?)
Een paar weken geleden stond de volgende vraag op wisfaq.nl onder de titel Moeilijk bewijs.
Op een lijn zijn elf verschillende punten gegeven: P1,P2, …, P11. Voor elk tweetal punten geldt: de afstand tussen Pp en Pq is ten hoogste 1. Bewijs dat de som van alle (55) afstanden |PpPq| kleiner is dan 30.
Dat klinkt inderdaad moeilijk (55 afstanden niet groter dan 1 bij elkaar optellen en de som onder de 30 houden); tot je een plaatje tekent van alle elf punten van links naar rechts op die lijn. Voor die lijn kun je net zo goed de getallenlijn nemen en dan heb je elf getallen, P1,P2, …, P11 gerangschikt van klein naar groot (teken de situiatie maar even); De afstand tussen Pi en Pj is dan gewoon Pj-Pi als i<j. De situatie blijkt dan wat gunstiger: de grootste onderlinge afstand is P11-P1, de andere zijn kleiner (soms een stuk kleiner).
In groepen verdelen
Zo kun je bijvoorbeeld alle afstanden Pi+1-Pi voor i=1,2,…10 bij elkaar optellen en dat geeft P11-P1; toch mooi tien termen die samen niet meer dan 1 opleveren.
Vervolgens kunnen we alle afstanden Pi+2-Pi optellen, voor i=1,2,…,9. Dat doen we in twee groepen: voor de oneven i en voor de even i. We krijgen respectievelijk (P3-P1) + (P5-P3) + (P7-P5) + (P9-P7) + (P11-P9) = P11-P1 en (P4-P2) + (P6-P4) + (P8-P6) + (P10-P8) = P10-P2. De totale som is dus kleiner dan 2 (kleiner omdat P10-P2<1).
Als je de verschillen Pi+3-Pi gaat optellen, voor i=1,2,…,8, dan ontdek je dat je drie groepjes moet maken, elk met een som kleiner dan 1.
Bij de verschillen Pi+4-Pi krijg je vier groepen met een totale som kleiner dan 4.
Bij de verschillen Pi+5-Pi krijg je vijf groepen met een totale som kleiner dan 5.
Bij de verschillen Pi+6-Pi krijg je ook vijf groepen met een totale som kleiner dan 5: je krijg alleen P7-P1 tot en met P11-P5 omdat 6+6=12.
Dit loopt zo af, je krijg achtereenvolgens sommen die kleiner zijn dan 4, 3, en 2; aan het eind staat nog een keer P11-P1 en die is nioet groter dan 1.
Alles bij elkaar geteld is de totale som dus kleiner dan 1+2+3+4+5+5+4+3+2+1=30.
Kan het beter?
De 30 kan niet verbeterd: door P1 tot en met P6 heel dicht bij 0 te nemen en de rest van de punten heel dicht bij 1 kun je de totale som zo dicht bij 30 krijgen als je maar wilt.
Verder onderzoek
Probeer een formule op te stellen voor de kleinste bovengrens van de som van de ondelinge afstanden bij n punten.
Wat kunnen we zeggen als de punten in het vlak liggen? Alle ondelinge afstanden kleiner dan 1; hoe groot kan de som van die afstanden zijn?
Recent Comments