invarianten | Wiskunde is leuk

Vanuit slechts twee begingetallen groeit het bord elke minuut met één toegestane som. Een invariant beslist welke doelen onmogelijk zijn, terwijl slimme constructies en een groeigrens de bereikbare doelen en hun timing bepalen.

Infobox

Onderwerpen: Getaltheorie, combinatoriek
Probleemoplossingstechnieken: Invariant, constructie, extremale groei
Moeilijkheid: Gemiddeld
Competitie: Olympiade Mathématique Belge, Maxifinale
Jaar: 2026
Opgavenummer: 1

Opgave

Aanvankelijk staan de getallen 10 en 13 op een bord. Vervolgens verschijnt er elke minuut één extra getal: het is gelijk aan de som van twee verschillende getallen die al op het bord staan, en het stond zelf nog niet op het bord (met andere woorden: geen enkel getal staat ooit twee keer op het bord).

a) Bestaat er een uitvoering van dit proces waarbij het getal 2026 op een bepaald moment verschijnt?

b) Bestaat er een uitvoering van dit proces waarbij het getal 68 op een bepaald moment verschijnt?

c) Bestaat er een uitvoering van dit proces waarbij het getal 95 op een bepaald moment verschijnt? Zo ja, na hoeveel minuten op zijn vroegst?

Eerste idee

Elk bordgetal blijft van de vorm $10a+13b$ met niet-negatieve gehele $a$ en $b$ . Die invariant kan een getal uitsluiten, maar om bereikbaarheid te bewijzen zijn expliciete geldige optellingen nodig. Voor de minimale tijd vergelijken we 95 met de grootst mogelijke waarde na elke minuut.

Uitwerking

Een invariant

We bewijzen eerst dat elk getal dat ooit op het bord verschijnt, kan worden geschreven als

$10a+13b$

met $a,b\in\mathbb{Z}_{\ge 0}$ .

Dit geldt aanvankelijk, want

$10=10\cdot 1+13\cdot 0 \qquad\text{en}\qquad 13=10\cdot 0+13\cdot 1.$

Als twee reeds aanwezige getallen respectievelijk gelijk zijn aan $10a+13b$ en $10c+13d$ , dan is hun som

$(10a+13b)+(10c+13d)=10(a+c)+13(b+d),$

opnieuw van de gewenste vorm. De bewering volgt dus voor alle bordgetallen.

a) Het getal 2026

We geven een expliciete realisatie. Begin met 13 en tel er telkens het al aanwezige getal 10 bij op. Zo verschijnen achtereenvolgens

$23,33,43,\ldots,1003,1013,1023.$

Elke stap is toegestaan: het nieuwe getal is de som van 10 en het onmiddellijk voorafgaande getal, die verschillend zijn en beide al op het bord staan. Ook zijn alle nieuw verkregen getallen verschillend.

In deze rij zijn zowel

$1003=13+99\cdot 10$

als

$1023=13+101\cdot 10$

aanwezig. Ze zijn verschillend, en daarom mogen we ze optellen. Dit geeft

$1003+1023=2026.$

Dus 2026 kan verschijnen.

b) Het getal 68

Als 68 zou verschijnen, dan zou de invariant niet-negatieve gehele getallen $a$ en $b$ geven waarvoor

$68=10a+13b.$

Modulo 10 volgt hieruit

$3b\equiv 8\pmod {10}.$

Omdat 7 de inverse van 3 modulo 10 is, krijgen we

$b\equiv 6\pmod {10}.$

In het bijzonder is $b\ge 6$ . Dan zou echter

$10a+13b\ge 13\cdot 6=78,$

in tegenspraak met $10a+13b=68$ . Dus 68 kan niet verschijnen.

c) Het getal 95 en het minimale aantal minuten

De volgende geldige constructie laat 95 na vier minuten verschijnen:

$23=10+13,$

$36=13+23,$

$59=23+36,$

$95=36+59.$

Alle gebruikte termen zijn telkens verschillend en al aanwezig, en elk nieuw getal is nog niet aanwezig.

We bewijzen dat vier minuten minimaal is. Noem de grootste bordwaarde na $k$ minuten $M_k$ . Aanvankelijk zijn de twee grootste waarden 13 en 10. Een nieuw getal is de som van twee verschillende aanwezige getallen en is dus ten hoogste de som van de twee grootste aanwezige getallen.

Na één minuut is de grootste mogelijke waarde daarom

$10+13=23.$

Aan het begin van de tweede minuut zijn de twee grootste waarden ten hoogste 23 en 13. De nieuwe waarde die in die minuut verschijnt, is dus ten hoogste

$23+13=36$

Na twee minuten zijn de twee grootste waarden bijgevolg ten hoogste 36 en 23. De nieuwe waarde die in de derde minuut verschijnt, is dus ten hoogste

$36+23=59$

is. Bijgevolg kan na drie minuten nog geen 95 op het bord staan.

De bovenstaande constructie bereikt 95 wel na vier minuten. Het minimale aantal minuten is dus

$\boxed{4}.$

Samengevat:

$\boxed{\text{a) ja,}\qquad\text{b) nee,}\qquad\text{c) ja, na minimaal 4 minuten.}}$

Probleemoplossingstechnieken

Invariant: Alle bereikbare getallen blijven niet-negatieve gehele lineaire combinaties van 10 en 13.
Constructie: Expliciete reeksen toegestane optellingen tonen aan dat 2026 en 95 bereikbaar zijn.
Extremale groei: De som van de twee grootste aanwezige waarden begrenst wat na elke minuut mogelijk is.

Wiskunde is leuk

Tag archieven: invarianten

OMB Maxi finale 2026 vraag 1