Opgave 2 (Versie voor klas 5 en klas 4 en lager), Finale Nederlandse Wiskunde Olympiade 2018.

De getallen 1 tot en met 25 worden elk blauw of rood gekleurd. Bepaal alle mogelijke kleuringen die voldoen aan de volgende regels:

• Regel 1: Het getal $5$ is rood.
• Regel 2: Als de getallen $x$ en $y$ verschillende kleuren hebben en $x + y \le 25,$ dan is $x + y$ blauw.
• Regel 3: Als de getallen $x$ en $y$ verschillende kleuren hebben en $x \cdot y \le  25,$ dan is $x \cdot y$ rood.

Hoe zou je zo'n opgave kunnen aanpakken? Stel nu eens voor dat je alle mogelijke kleuringen zou willen tekenen op een blaadje en dan wil controleren of ze aan de drie regels voldoen. In dit geval heb je dan $25$ getallen die elk twee kleuren kunnen hebben, blauw of rood. Het aantal mogelijke combinaties is dan $2^{25}$ (meer dan 33 miljoen), want voor het getal $1$ heb je twee kleuren, voor het getal $2$ heb je twee kleuren, net als voor het getal $3$ en ga zo maar door... Als je nu slim bent en bedenkt dat volgens regel 1 het getal $5$ rood is, heb je nog steeds $2^{24}$ (meer dan 16 miljoen) mogelijkheden waarvoor je regel 2 en 3 moet controleren. Dit is dus niet zo een handige strategie.

Een eerste kleuring

Wat is nu wel slim? Een goed idee is om eerst eens te kijken naar het getal 1. Stel dat het getal 1 rood is, wat weet je dan? Het getal $1$ en het getal $5$ hebben dezelfde kleur, dus je kunt regel 2 en 3 helaas (nog) niet toepassen. Dit wil je wel gaan doen, dus neem je aan dat een getal, bijvoorbeeld $2,$ blauw is. Dan weet je met regel 3 dat het getal $1 \cdot 2 = 2$ rood is. Maar je had net aangenomen dat $2$ blauw is, dus dit kan niet. Het maakt voor deze redenatie niet uit welk getal je kiest. Dus stel dat een willekeurig getal $x$ (kleiner of gelijk aan $25)$ blauw is. Dan weet je met regel 3 dat het getal $1 \cdot x = x$ rood moet zijn, dus $x$ is rood. Je had echter aangenomen dat $x$ blauw was, dus dat kan niet. Dus als getal $1$ rood is, bestaat er geen enkel getal dat blauw gekleurd is. Hieruit volgt dat als getal $1$ rood is, alle getallen van $1$ tot en met $25$ rood gekleurd moeten zijn.

Vervolgens moet je kijken of deze kleuring echt aan alle regels voldoet. Het getal $5$ is rood, dus de kleuring voldoet aan regel 1 en aangezien er geen twee getallen met verschillende kleuren zijn, voldoet deze kleuring ook aan regel 2 en 3. Je hebt nu al de eerste oplossing gevonden!

Nu met blauwe getallen

Nu moet je nog wel alle gevallen afgaan waarin het getal $1$ blauw is. Als $1$ blauw is, kun je dan met behulp van de regels ook de kleur van een ander getal bepalen? Ja, want je weet dat volgens regel 1 het getal $5$ rood is, dus je hebt twee getallen met een verschillende kleur! Als je vervolgens regel 2 toepast, vind je dat het getal $1 + 5 = 6$ blauw moet zijn. Op dezelfde manier krijg je dat ook $6 + 5 = 11$ blauw moet zijn, want $5$ is rood en $6$ is blauw. Als je dit nog twee keer doet, vind je dat de getallen $11 + 5 = 16$ en $16 + 5 = 21$ ook blauw zijn. De kleuren van de andere getallen weet je nu nog niet.

Regel 2 ‘omgekeerd’ gebruiken

Om deze te achterhalen moet je net iets slimmer zijn. Je kunt namelijk regel 2 ook ‘omgekeerd’ gebruiken. Als je weet dat twee getallen een verschillende kleur hebben dan moet hun som wegens regel 2 blauw zijn. Je weet dat geldt $1 + 4 = 5,$ en je weet ook dat $1$ blauw is en $5$ rood. Dus als $4$ rood is, dan volgt uit regel 2 dat $5$ blauw is. Dit kan (wegens regel 1) natuurlijk niet, dus het getal $4$ moet wel blauw zijn. Door regel 2 toe te passen, vind je met $5 + 4 = 9$ dat $9$ blauw is, net als de getallen $14, 19$ en $24.$

Hoe kan je nu de kleur van het getal $2$ bepalen? Hiervoor moet je regel 2 op een nog iets slimmere manier gebruiken. Als $2$ rood is, dan vind je met regel 2 dat het getal $1 + 2 = 3$ blauw moet zijn. Omdat $2$ en $3$ verschillende kleuren hebben, volgt door regel 2 dat hun som blauw is. Dit is echter niet waar, want $2 + 3 = 5$ en je wist al dat $5$ rood is. Hieruit volgt dat het getal $2$ blauw moet zijn. Door regel 2 meerdere keren toe te passen vind je dat ook de getallen $7 (5 + 2), 12, 17$ en $22$ blauw zijn.

Op dezelfde manier kun je ook de kleur van het getal $3$ achterhalen. Je weet immers dat $2$ en $3$ dezelfde kleur hebben, want $2 + 3 = 5$ en het getal $5$ is rood. Omdat je weet dat $2$ blauw is, is ook het getal $3$ blauw. Door regel 2 herhaaldelijk te gebruiken, krijg je dat de getallen $8, 13, 18$ en $23$ blauw zijn.

De kleur van de vijfvouden

Je hebt nu van bijna alle getallen de kleur gevonden, je weet alleen de kleuren van de 5-vouden $(10, 15, 20$ en $25)$ nog niet. Deze kan je (bijna allemaal) vinden met regel 3. Want daarin staat dat als 2 getallen een verschillende kleur hebben, hun product rood is. Je weet bijvoorbeeld dat $5$ rood is en $2$ blauw, dus met regel 3 vind je dat $2 \cdot 5 = 10$ rood is. Omdat je weet dat $3$ en $4$ blauw zijn, zijn met dezelfde redenatie ook $15$ en $20$ rood.

Zou je zo ook de kleur van het getal 25 kunnen bepalen? Helaas niet, want $5 \cdot 5 = 25$ en $5$ heeft dezelfde kleur als zichzelf. Ook met regel 2 kun je de kleur niet bepalen, want $25$ is ofwel de som van twee 5-vouden (die beide rood zijn) of van twee niet-5-vouden (die beide blauw zijn). Voor het getal $25$ zijn er daarom twee opties: $25$ is rood of $25$ is blauw.

Je hebt dus de volgende twee kleuringen als het getal $1$ blauw is:

• De getallen $5, 10, 15, 20$ en $25$ zijn rood en de rest van de getallen is blauw
• De getallen $5, 10, 15$ en $20$ zijn rood en de rest van de getallen is blauw

Controleren!

Het is belangrijk om te weten of ook deze kleuringen inderdaad aan de 3 regels voldoen, daarom ga je ze controleren. Aan regel 1 voldoen ze allebei, want het getal $5$ is rood. Hoe kun je controleren of ze aan regel 2 voldoen? Je begint eerst met de bovenste kleuring. Van twee getallen met verschillende kleuren weet je dat de één een vijfvoud is en de ander niet. Als je een niet-vijfvoud en een vijfvoud optelt, krijg je een niet-vijfvoud. Aangezien alle niet-vijfvouden blauw zijn, voldoet deze kleuring aan regel 2.

Vervolgens bekijk je of de onderste kleuring aan regel 2 voldoet. Dit gaat relatief snel, want de onderste kleuring is hetzelfde als de bovenste kleuring, alleen heeft het getal $25$ een andere kleur. Als de som van twee getallen groter is dan 25, dan geldt regel 2 niet. Aangezien de som van $25$ en een ander getal altijd groter is dan 25, voldoet ook deze kleuring aan regel 2.

Nu moet je nog controleren of de kleuringen aan regel 3 voldoen, je begint weer met de bovenste. Als je twee getallen bekijkt met verschillende kleuren, dan is de één een vijfvoud en de ander niet en volgens regel 3 is het product van deze twee getallen rood. Het product van een vijfvoud en een niet-vijfvoud is altijd een vijfvoud. Aangezien alle vijfvouden rood zijn, voldoet deze kleuring aan regel 3. Deze redenatie werkt ook voor de onderste kleuring, maar het getal $25$ is niet meer rood, dus dit kan voor een probleem zorgen. Je kunt $25$ op twee manieren schrijven als het product van twee (natuurlijke) getallen: $5 \cdot 5$ en $25 \cdot 1.$ Het getal $5$ heeft dezelfde kleur als zichzelf, net als de getallen $1$ en $25$ (deze zijn beide blauw), dus nu is regel 3 niet van toepassing. Als je het product van 25 en een getal groter dan 1 bekijkt, wordt dat groter dan 25 waardoor regel 3 niet meer geldt. Dus de onderste kleuring voldoet ook aan regel 3.

De oplossing

Er zijn dus drie kleuringen die voldoen, namelijk:

• Alle getallen zijn rood
• De getallen $5, 10, 15, 20$ en $25$ zijn rood en de rest van de getallen is blauw
• De getallen $5, 10, 15$ en $20$ zijn rood en de rest van de getallen is blauw

Een korte terugblik

Van de ruim 33 miljoen kleuringen die je kunt maken met 25 getallen die ofwel blauw ofwel rood zijn, blijken er uiteindelijk maar 3 aan de drie gestelde regels te voldoen. Door een aanname te doen voor de kleur van het getal $1,$ kon je de kleuren van alle andere getallen achterhalen. Hierbij maak je gebruik van een bekende wiskundige truc ‘bewijzen uit het ongerijmde’. Hierbij neem je iets aan en vervolgens ga je logisch redeneren. Op het moment dat je uitkomt op een bewering die niet waar kan zijn, concludeer je dat je oorspronkelijke aanname niet klopt. In dit geval was dat vaak dat het getal $5$ blauw moest zijn, terwijl je op basis van regel 1 wist dat $5$ rood is. Het is wel wat puzzelen, maar dat scheelt je dan wel ruim 33 miljoen kleuringen controleren.