BlAUwE lIjNEN

Begin juli vond in Zuid-Afrika de Internationale Wiskunde Olympiade (IMO) plaats. Nederland behaalde de dertiende plek in het landenklassement en presteerde hiermee beter
dan ooit tevoren. Van de zes teamleden had Jeroen Winkel de hoogste score: 32 van de
42 punten. Hij bespreekt in dit artikel de allermoeilijkste opgave van deze IMO.
■ door Jeroen Winkel
Blauwe lijnen
26
Opgave 6 van deze IMO ging over n lijnen in ‘algemene ligging’. Dit wil zeggen dat er geen twee lijnen
evenwijdig zijn aan elkaar, en dat er geen drie lijnen
door één punt gaan. Deze lijnen verdelen het vlak
in een aantal gebieden, waarvan sommige een eindige oppervlakte hebben. Deze noemen we de eindige gebieden. De bedoeling is om √n of meer van
de lijnen blauw te kleuren, zó dat geen enkel eindig
gebied een volledig blauwe rand krijgt.
In figuur 1 zie je een voorbeeld met 5 lijnen. Er
zijn 6 eindige gebieden: 4 driehoeken, een vierhoek
en een vijfhoek. In het plaatje zijn 3 lijnen blauw
gekleurd terwijl geen van de eindige gebieden een
volledig blauwe rand heeft. Het werkt dus in dit
voorbeeld, want 3 ≥ √5. Merk op dat als een van de
andere twee lijnen ook nog blauw zou worden gekleurd, dan ofwel gebied 1 danwel gebied 2 (en in
dat geval ook de gebieden 3 en 4) een volledig blauwe rand zou krijgen.
Aantal punten Om wat meer gevoel voor de
opgave te krijgen, bekijken we eerst maar eens wat
een algemene ligging precies inhoudt. Elke twee lij-
nen zijn niet evenwijdig, dus snijden elkaar. Ook
zijn er geen drie lijnen die door één punt gaan,
dus voor elk paar lijnen is er precies één snijpunt.
Het aantal snijpunten is dus gelijk aan het aantal
tweetallen lijnen. Het aantal tweetallen lijnen is
n(n – 1)/2: er zijn n mogelijkheden voor de ene lijn,
n – 1 mogelijkheden voor de andere lijn, en de deling door 2 is nodig omdat anders elk tweetal dubbel wordt geteld. Het aantal snijpunten van n lijnen
in algemene ligging is dus n(n – 1)/2.
Maximale kleuringen In figuur 2 zie je
een figuur waarbij 7 lijnen zijn getekend. Het lukt
eenvoudig om er 4 blauw te kleuren, zodat aan de
voorwaarden wordt voldaan: de 15 eindige gebieden hebben allemaal niet een volledig blauwe rand.
Omdat 4 ≥ √7, is dit voldoende. We zien echter ook
dat het niet mogelijk is om nóg een lijn blauw te
kleuren; dan zou er een eindig gebied ontstaan met
een volledig blauwe rand. We noemen deze kleuring daarom maximaal. Ook de kleuring in figuur 1
was maximaal.
Wat weten we van deze maximale kleuringen?
1
5
6
Figuur 1
2
4
3
Figuur 2
P YTHAGORAS NOVEMBER 2014
27
Het Nederlandse team: v.l.n.r. Bob Zwetsloot (16 jaar, Noordwijkerhout, 5 vwo, Teylingen College Leeuwenhorst; reisde mee als winnaar van de aanmoedigingsprijs), Michelle Sweering (goud, 17 jaar, Krimpen aan
den IJssel, 6 vwo, Erasmiaans Gymnasium Rotterdam), Matthew Maat (zilver, 14 jaar, Enschede, 4 vwo, Bonhoeffer College Enschede), Peter Gerlagh (goud, 18 jaar, Tilburg, 6 vwo, Theresia Lyceum Tilburg), Bas Verseveldt (zilver, 17 jaar, Tilburg, 6 vwo, Theresia Lyceum Tilburg), Jeroen Winkel (goud, 17 jaar, Nijmegen, 6
vwo, Stedelijk Gymnasium Nijmegen), Tysger Boelens (brons, 18 jaar, Ter Apel, 6 vwo, RSG Ter Apel).
P YTHAGORAS NOVEMBER 2014
28
Ten eerste is het duidelijk dat er altijd eentje moet
bestaan: we kunnen gewoon één voor één lijnen
blauw kleuren, totdat het niet meer kan. En als we
een maximale kleuring hebben, weten we ook dat
als we een willekeurige niet-blauwe lijn blauw kleuren, er dan een eindig gebied ontstaat dat wel een
volledig blauwe rand heeft (anders hadden we die
lijn toch nog blauw kunnen maken bij het maken
van de maximale kleuring). Elke niet-blauwe lijn zit
dus aan de rand van ten minste één eindig gebied
waarvan de rand verder helemaal blauw is. Noem
nu een snijpunt van twee blauwe lijnen een blauw
punt. We gaan koppelingen maken tussen niet-blauwe lijnen en blauwe punten. We weten dat elke nietblauwe lijn aan ten minste één eindig gebied grenst
waarvan de rand voor de rest alleen blauw is. Dit
gebied heeft minstens twee blauwe zijden (namelijk als het in feite een driehoek is) en van zijn hoekpunten is er dus minstens één een blauw punt. Nu
wordt de niet-blauwe lijn aan één van deze blauwe
punten gekoppeld. In figuur 3 zie je een voorbeeld:
de niet-blauwe lijn zit hier aan een vierhoek en twee
driehoeken die elk verder alleen maar blauwe lijnen
bevatten. Als er meerdere van zulke eindige gebieden zijn met verder alleen maar blauwe lijnen, kiezen we er gewoon eentje. Kies bijvoorbeeld de vierhoek. Dit gebied bevat twee blauwe punten: A en B.
De niet-blauwe lijn kan dus gekoppeld worden aan
A of B: dit maakt niet uit, ook hier kiezen we er
weer willekeurig eentje.
Noteer met k het aantal blauwe lijnen in een
maximale kleuring. We weten van deze lijnen ook
dat ze allemaal niet evenwijdig zijn aan elkaar en
dat er geen drie lijnen door één punt gaan, dus ook
deze k lijnen zijn in algemene ligging. Dus er zijn
k(k – 1)/2 blauwe punten.
Rondom elk blauw punt liggen precies 4 gebieden (zie figuur 3: de vier gebieden rondom punt B
zijn aangegeven). Dus naast elk blauw punt kunnen
hoogstens 4 eindige gebieden liggen waarvan maar
één stukje van de rand niet blauw is, dus er kunnen
hoogstens 4 lijnen aan dit punt gekoppeld zijn. Dus
elke niet-blauwe lijn is gekoppeld aan een blauw
punt, en elk blauw punt is gekoppeld aan ten hoogste 4 niet-blauwe lijnen: er zijn dus hoogstens 4 keer
zoveel niet-blauwe lijnen als er blauwe punten zijn.
Er zijn n – k niet-blauwe lijnen en k(k – 1)/2 blauwe
punten, dus n – k ≤ 4 · k(k – 1)/2 = 2k(k – 1), dus
n ≤ 2k2 – 2k + k < 2k2, dus k ≥ n / 2 . We hebben
nu dus al een kleuring met minstens n / 2 blauwe lijnen! Dit was op de IMO 3 punten waard, van
de 7.
Met de klok mee Om te bewijzen dat we √n
lijnen blauw kunnen kleuren, moeten we onze methode enigszins aanpassen. We hadden eerst voor
elke niet-blauwe lijn een gebied gevonden dat die
lijn aan de rand heeft, en verder alleen blauwe lijnen, en de niet-blauwe lijn vervolgens gekoppeld
aan een willekeurig blauw punt in het gebied. Nu
nemen we niet een willekeurig blauw punt in het
gebied, maar het eerste blauwe punt dat we krijgen
als we vanaf de niet-blauwe lijn met de klok mee de
punten langsgaan. In figuur 3 zou (als we weer de
vierhoek zouden kiezen) de niet-blauwe lijn dus gekoppeld worden aan punt B, en niet punt A.
Nog steeds is elke niet-blauwe lijn nu gekoppeld
aan een blauw punt. We kunnen nu echter bewijzen dat bij elk blauw punt hoogstens 2 niet-blauwe
lijnen horen. We doen dit door aan te nemen dat
er een blauw punt is dat bij minstens 3 niet-blauwe
2
1
B
3
4
A
Figuur 3
P YTHAGORAS NOVEMBER 2014
C
m
B
x
l
A
y
Figuur 4
lijnen hoort, en dan een tegenspraak af te leiden.
Stel dus dat er een blauw punt A is dat bij minstens
3 niet-blauwe lijnen hoort. Dan zijn er dus 3 gebieden rondom A, waarvan de rand bijna helemaal
blauw is. Daarvan moeten er dan 2 naast elkaar liggen. Noem de niet-blauwe lijn in de rand van het
ene gebied l en die in de rand van het andere gebied
m, waarbij het gebied van m in de richting van de
klok na het gebied van l komt (zie figuur 4, maar let
nog even niet op de ligging van de punten B of C;
we voeren deze punten straks pas in en gaan ook
dan pas afleiden welke dichter bij A ligt). In deze figuur zijn niet alle lijnen getekend; er kunnen nog
andere blauwe en/of niet-blauwe lijnen tussendoor
lopen. Noteer met x de lijn door A die grenst aan
beide gebieden, en met y de andere lijn door A. We
weten dat m het enige niet-blauwe stukje is van het
gebied boven A, en l het enige niet-blauwe stukje
van het gebied links van A. Noteer met B het snijpunt van l en x, en met C het snijpunt van m en x.
We weten dat B en C niet hetzelfde punt zijn, omdat er geen drie lijnen door een punt gaan. Ook weten we dat A het eerste blauwe punt is als we vanuit lijnstuk l kloksgewijs langs de punten lopen. Er
zit dus precies één lijnstuk tussen l en A. Er lopen
maar twee lijnen door A, en aangezien het met de
klok mee gaat, moet dit lijnstuk AB zijn. Dit betekent dus dat B in het gebied van l zit. Kennelijk zitten A en B in hetzelfde gebied, dus er kan geen enkele lijn meer door het lijnstuk AB lopen, want die
zou B dan van het gebied afsnijden. Dit betekent
dus ook dat C niet op het lijnstuk AB ligt, want de
lijn m loopt door C. Dus B ligt tussen A en C. Nu
bekijken we het gebied dat hoort bij de lijn m. Dit
is dan een gebied met één niet-blauw stukje, name-
lijk van de lijn m, en A zit in het gebied. Maar als A
in het gebied zit, dan zit B ook in het gebied, want
er loopt geen lijn door het lijnstuk AB. Maar dan zit
er ook een stukje van l in de rand, en l is niet blauw.
We hebben nu dus nog een niet-blauw stukje in de
rand van het gebied. Dit leidt tot de tegenspraak.
Dus elke niet-blauwe lijn is nu gekoppeld aan
een blauw punt, en elk blauw punt is gekoppeld aan
hoogstens 2 niet-blauwe lijnen. Dus het aantal nietblauwe lijnen is hoogstens 2 keer zo groot als het
aantal blauwe punten. Het aantal niet-blauwe lijnen
is n – k en het aantal blauwe punten is k(k – 1)/2,
dus n – k ≤ 2 · k(k – 1)/2 = k(k – 1) = k2 – k, dus
n ≤ k2, dus k ≥ √n. We hebben dus √n of meer blauwe lijnen!
Nog meer blauwe lijnen? Wat we nu
hebben bewezen is niet alleen dat we √n of meer lijnen blauw kunnen kleuren; het is dat elke maximale kleuring al minstens √n blauwe lijnen heeft. Het
maakt dus niet uit hoe we het doen, als we steeds
maar nieuwe lijnen blauw maken totdat het niet
meer kan, komen we al op minstens √n blauwe lijnen. Het is daarom niet verbazingwekkend dat we
op een groter aantal blauwe lijnen uit kunnen komen door een slimmere methode te gebruiken:
de teamleider van het Amerikaanse IMO-team
Po-Shen Loh heeft bewezen dat het ook met
c logn · √n blauwe lijnen kan, voor een zekere
constante c > 0. Dit bewijs gebruikt moeilijkere
technieken en combinatorische stellingen. Voor n
groot genoeg geldt natuurlijk c logn > 1. Er geldt
zelfs c logn > M voor elke M die je maar wilt, mits
je n maar groot genoeg maakt. Dit is dus een grote
verbetering. ■
P YTHAGORAS NOVEMBER 2014
29

Download Report