Tien getallen rond een tafel
Op de Wisfaq stond laatst weer een aardige vraag:
Natuurlijke getallen van 1 tot en met 10 zijn geordend in een willekeurige volgorde rond een cirkel. Je kan steeds (dus in een cirkel is er minstens 1 geval) 3 opeenvolgende getallen vinden waarvoor de som groter is dan 17.
Hoe zou je zoiets aanpakken? Meestal kun je wel iets over die sommen zeggen waardoor blijkt dat er één (of meer) over een bepaalde grens moet gaan, bijvoorbeeld als de som van al die sommen groot moet zijn.
In dit geval kunnen de tien sommen bij elkaar optellen; dan tellen we elk getal 1, 2, …, 9, 10 driemaal mee dus we krijgen als totaal 3×(1+2+…+9+10)=3×55=165.
Dat betekent dat niet alle sommen kleiner dan 17 kunnen zijn, want dan zou hun totaal niet groter zijn dan 10×16=160. Het eerste succes is binnen: we zien vrij goedkoop dat tenminste één drietal een som van 17 of meer moet hebben.
Vervolgens heb ik een paar vellen kladpapier gebruikt om de getallen zo rond de tafel te plaatsen dat alle sommen niet groter waren dan 17. Waarom? Voor mij is het zo dat als ik zoiets vaak genoeg mis zie lopen ik een idee krijg hoe te bewijzen dat het gevraagde waar is: de reden van het mislopen is soms een sleutel tot een bewijs.
In dit geval bleek het lastig het gemiddelde van de sommen in de buurt van 16,5 te houden, dus ging ik kijken hoe dat gemiddelde gelijk kon zijn aan 16,5 terwijl alle sommen niet groter dan 17 mochten zijn.
Na wat proberen bleek dat ten minste vijf van de sommen gelijk aan 17 moeten zijn; immers, bij vier (of minder) sommen gelijk aan 17 zijn de andere zes (of meer) sommen niet groter dan 16 en dus zou het totaal niet groter zijn dan 4×17+6×16=164, en dat is net te klein.
Daarnaast bleek dat er ook maar ten hoogste vijf sommen gelijk aan 17 konden zijn. Dat was zo duidelijk dat ik het eerst over het hoofd zag: neem vier getallen op een rij: x1, x2, x3, x4.
Omdat x1≠x4 volgt dat x1+x2+x3≠x2+x3+x4. Van elk tweetal naast elkaar liggende sommen is er dus hooguit één gelijk aan 17.
Als we de tafel rondlopen zien we dus nooit twee sommen gelijk aan 17 naast elkaar; dat betekent dat we niet meer dan vijf maal een 17 zullen zien.
Nu weten we dat er precies vijf sommen gelijk zijn aan 17, maar dan moeten de andere vijf sommen gelijk zijn aan 16 (om het totaal op 165 te houden) en de sommen 17 en 16 komen dus om en om voor.
Loop nu de tafel rond en noem de getallen die je ziet x1, x2, … en begin op een plek waar x1+x2+x3=17. Dan moet vervolgens gelden
- x2+x3+x4=16, en
- x3+x4+x5=17, en
- x4+x5+x6=16, en
- x5+x6+x7=17.
Trek de tweede vergelijking van de eerste af, je ziet x1-x4=1.
Trek de vierde vergelijking van de vijfde af, je ziet x7-x4=1.
Maar nu volgt x1=x7 en dat kan niet want we hadden tien verschillende getallen rond de tafel gezet.
Conclusie: elke poging alle tien de sommen kleiner dan of gelijk aan 17 te houden zal falen. Hoe je de getallen ook neerzet, er is een som die groter is dan 17.
In de Wiskunde heet zoiets een (niet-constructief) existentiebewijs: we laten zien dat iets moet voorkomen maar er is geen recept dat het gewenste verschijnsel aanwijst. Het bewijs geeft (slechts) aan hoe een poging zal stranden: je moet vijf keer 17 als som hebben, en vijf keer 16, en die moeten om en om voorkomen en dan loopt het echt mis: twee verschillende getallen moeten gelijk zijn.
Opdracht.
Om te puzzelen: is er een verdeling met alle sommen niet groter dan 18? Ik heb het nog niet geprobeerd.
Recent Comments