Hoe stapel je rijen stenen van twee verschillende lengtes zonder dat voegen recht boven elkaar komen? Door elke mogelijke rij als een verzameling voegposities te bekijken, verandert deze bouwvraag in een klein en overzichtelijk graafprobleem.
Infobox
- Onderwerpen: Combinatoriek, grafentheorie
- Probleemoplossingstechnieken: Modelleren, systematisch opsommen, gevalsonderscheid, extremale constructie
- Moeilijkheid: Moeilijk
- Competitie: Vlaamse Wiskunde Olympiade
- Jaar: 2026
- Opgavenummer: 2
Opgave
Bob heeft twee soorten LEGO®-stenen: stenen met 1 bij 2 noppen en stenen met 1 bij 3 noppen. Hij bouwt muren zonder gaten, met rechte zijkanten en met een diepte van 1 nop. Zo’n muur noemen we stevig als er nooit twee uiteinden van stenen boven elkaar staan, behalve aan de zijkanten van de muur. Zo is de muur in de figuur links stevig, maar die in de figuur rechts niet.
Vandaag bouwt Bob enkel stevige muren waarbij elke rij 12 noppen heeft.
(a) Bob bouwt eerst een muur van vier rijen hoog. Een van de rijen bestaat uitsluitend uit stenen van 2 noppen breed. Toon aan dat die muur nog zo’n rij bevat.
(b) Bob bouwt nog een muur van vier rijen hoog. Nu bestaat een van de rijen uitsluitend uit stenen van 3 noppen breed. Toon aan dat die muur nog zo’n rij bevat.
(c) Ten slotte bouwt Bob een muur die geen twee gelijke rijen bevat. Hoeveel rijen kan die muur hoogstens bevatten?
Figuur 1.
Eerste idee
Noteer voor elk rijpatroon de posities van zijn interne voegen. Twee rijen mogen precies op elkaar volgen wanneer hun voegverzamelingen disjunct zijn. Alle mogelijke rijen van lengte 12 vormen zo een kleine compatibiliteitsgraaf; de componenten daarvan dwingen de herhalingen af en bepalen de maximale hoogte zonder gelijke rijen.
Uitwerking
We stellen een rij voor door de opeenvolgende breedtes van zijn stenen. Zo betekent (23223) een rij met stenen van breedte (2,3,2,2,3). Daarnaast noteren we de posities van de interne voegen, geteld vanaf de linkerkant.
Twee opeenvolgende rijen vormen precies dan een stevig geheel als ze geen interne voegpositie gemeen hebben.
Alle composities van 12 met delen 2 en 3, samen met hun voegposities en de rijpatronen waarmee ze verenigbaar zijn, staan in de volgende tabel.
| Naam | Rijpatroon | Interne voegposities | Verenigbaar met |
|---|---|---|---|
| (A) | (222222) | (2,4,6,8,10) | (H) |
| (B) | (22233) | (2,4,6,9) | (I,J) |
| (C) | (22323) | (2,4,7,9) | (J,K) |
| (D) | (22332) | (2,4,7,10) | (L) |
| (E) | (23223) | (2,5,7,9) | (K) |
| (F) | (23232) | (2,5,7,10) | (L) |
| (G) | (23322) | (2,5,8,10) | (L) |
| (H) | (32223) | (3,5,7,9) | (A) |
| (I) | (32232) | (3,5,7,10) | (B) |
| (J) | (32322) | (3,5,8,10) | (B,C) |
| (K) | (33222) | (3,6,8,10) | (C,E) |
| (L) | (3333) | (3,6,9) | (D,F,G) |
Deze lijst is volledig: een rij begint met een steen van breedte 2 of 3, en door alle mogelijkheden verder aan te vullen tot totale breedte 12 krijgen we precies de twaalf vermelde composities. De laatste kolom volgt door voor elk paar te controleren of de twee verzamelingen interne voegposities disjunct zijn.
De compatibiliteitsgraaf heeft bijgevolg drie componenten:
![\[A-H,\]](http://www.wiskundemagie.be/wp-content/ql-cache/quicklatex.com-0ab514fd3d4ee3d802fe6520ffd57842_l3.png "Rendered by QuickLaTeX.com")
![\[D-L-F \quad\text{en}\quad L-G,\]](http://www.wiskundemagie.be/wp-content/ql-cache/quicklatex.com-27c8d5fecbd40e48ad5232dd47d48dc4_l3.png "Rendered by QuickLaTeX.com")
waarbij de tweede component een ster met middelpunt (L) is, en
![\[E-K-C-J-B-I.\]](http://www.wiskundemagie.be/wp-content/ql-cache/quicklatex.com-dd1e2effea1411a41fcde27de1e1802c_l3.png "Rendered by QuickLaTeX.com")
De derde component is een pad met zes knopen.
(a)
Een rij die uitsluitend uit stenen van 2 noppen bestaat, is patroon (A=222222). Volgens de tabel is alleen patroon (H) ermee verenigbaar, en (H) is op zijn beurt alleen met (A) verenigbaar.
Zodra een muur een rij van type (A) bevat, moeten de rijtypes in de hele vier rijen hoge muur dus afwisselen tussen (A) en (H). Onder vier opeenvolgende rijen komen bijgevolg twee rijen van type (A) voor. De muur bevat dus nog een rij die uitsluitend uit stenen van 2 noppen bestaat.
(b)
Een rij die uitsluitend uit stenen van 3 noppen bestaat, is patroon (L=3333). De patronen die met (L) verenigbaar zijn, zijn (D,F) en (G). Elk van die drie patronen is uitsluitend met (L) verenigbaar.
In een muur die een rij van type (L) bevat, wisselen de rijen daarom af tussen (L) en een van de types (D,F,G). Onder vier opeenvolgende rijen komen bijgevolg twee rijen van type (L) voor. De muur bevat dus nog een rij die uitsluitend uit stenen van 3 noppen bestaat.
(c)
Als geen twee rijen gelijk mogen zijn, correspondeert de muur met een eenvoudig pad in een component van de compatibiliteitsgraaf.
De component (A-H) bevat hoogstens een eenvoudig pad met 2 knopen. In de ster met middelpunt (L) kan een eenvoudig pad hoogstens van één buitenste knoop via (L) naar een andere buitenste knoop lopen en dus 3 knopen bevatten. De derde component is zelf een pad met 6 knopen. Een muur zonder gelijke rijen kan daarom hoogstens 6 rijen hebben.
Deze bovengrens wordt bereikt door de volgende zes rijpatronen van onder naar boven te gebruiken:
![\[23223,\quad 33222,\quad 22323,\quad 32322,\quad 22233,\quad 32232.\]](http://www.wiskundemagie.be/wp-content/ql-cache/quicklatex.com-390531893c4e8fde9157dd1d53685ca9_l3.png "Rendered by QuickLaTeX.com")
Dit zijn de patronen (E,K,C,J,B,I). Opeenvolgende patronen zijn volgens de tabel verenigbaar en alle zes patronen zijn verschillend. Er bestaat dus werkelijk een stevige muur van 6 rijen zonder twee gelijke rijen.
Het gevraagde maximale aantal rijen is bijgevolg
![\[\boxed{6}.\]](http://www.wiskundemagie.be/wp-content/ql-cache/quicklatex.com-75fe38201de39687fecae4e5af8154f2_l3.png "Rendered by QuickLaTeX.com")
Probleemoplossingstechnieken
- Modelleren: Een rij wordt vervangen door de verzameling van haar interne voegposities. Daardoor wordt stevigheid de voorwaarde dat twee opeenvolgende verzamelingen disjunct zijn.
- Systematisch opsommen: Alle composities van 12 met delen 2 en 3 worden opgenomen. Zo berust het bewijs niet op een onvolledige selectie van mogelijke rijen.
- Gevalsonderscheid: De drie componenten van de compatibiliteitsgraaf worden afzonderlijk onderzocht. Hun verschillende vormen verklaren de gedwongen herhalingen in (a) en (b).
- Extremale constructie: Naast de bovengrens van 6 wordt een concreet pad van zes verschillende rijpatronen gegeven, zodat de grens scherp is.
Bron
Finale Vlaamse Wiskunde Olympiade 2025–2026, woensdag 22 april 2026. © Vlaamse Wiskunde Olympiade vzw.