Stapelen

Hoe kan je 15 appelsienen (allemaal even groot) in een zo klein mogelijke vierkante doos schikken? 
Je zou 4 rijen van 4 kunnen nemen en er eentje uitnemen. Dan heeft de doos een lengte gelijk aan vier keer de diameter van de appelsien. Kan het in een kleinere doos? En hoeveel ruimte blijft er dan over?

Vraagstukken over het stapelen van bollen ( appelsienen, knikkers, biljartballen, kanonskogels of moleculen) vormen uitdagende wiskundige problemen.

 In 1587 keek ontdekkingsreiziger Walter Raleigh naar een piramidevormige stapel kanonskogels en vroeg zich af , of er een formule bestond die berekende hoeveel kogels er in zo een stapel waren. Hoe groot waren de gaten tussen de kogels? En kon je de bollen misschien efficiënter opstapelen? Hij speelde zijn vragen door naar de Duitse wiskundige Johannes Kepler die in 1611 het vermoeden formuleerde dat het niet beter kon dan de gebruikelijke manier van stapelen. Deze manier van stapelen vult iets meer dan 74% van de ruimte . Elke andere schikking van even grote bollen zou gemiddeld meer ruimte ongebruikt laten.

Dit kon slechts in 1998 bewezen worden door de Amerikaan Thomas Hales. Het bewijs was gebaseerd op een computercontrole van een groot aantal gevallen en werd pas in 2017 officieel aanvaard.

De huwelijksstelling van Hall

Zes vrouwen vallen elk op een aantal vrijgezelle mannen. Kunnen de zes vrouwen met de zes mannen worden gekoppeld, zó dat elke vrouw een man van haar keuze trouwt?

In sommige gevallen is het eenvoudig om te zien dat er geen oplossing mogelijk is. Als er een dame bij is die niemand leuk vindt, lukt het niet. Ook als er twee vrouwen zijn die enkel één en dezelfde man willen, loopt het mis.

Kan het met de volgende keuze?
Een nodige en voldoende voorwaarde op het bestaan van een oplossing is dat iedere k dames samen met tenminste k  verschillende mannen willen trouwen. Hierbij is 1 \leq k\leq6. Omdat de dames a,c,d en f samen maar drie verschillende mannen willen huwen, namelijk de nummers 2,3 en 6, is het dus onmogelijk alle zes dames uit te huwelijken!

Deze stelling, die dateert uit 1933, werd bewezen door de Engelse wiskundige Philip Hall ( 1904-1982).

Als het zo is dat we niet alle dames kunnen koppelen, dan kunnen we ons wel de vraag stellen: wat is het maximaal aantal dames dat kan gekoppeld worden?

Hiervoor vertalen we het probleem naar een probleem met grafen: Voor iedere vrouw is er een bijhorend punt in A en voor iedere man is er een punt in B. We trekken een lijn tussen een vrouw en een man, als zij met hem wilt trouwen.

De resulterende graaf heet bipartiet omdat de punten zijn opgedeeld in twee groepjes en lijnen altijd punten uit verschillende groepen verbinden. Een aantal lijnen noemt men een matching als geen twee lijnen eenzelfde eindpunt hebben. Een uithuwelijking is dus eigenlijk een matching. In het rood staat hierboven een matching met 4 lijnen. Een betere matching wordt gegeven door volgende figuur, waarin 5 vrouwen kunnen worden uitgehuwelijkt.

Vierkanten en rechthoeken op een schaakbord

Hoeveel vierkanten en rechthoeken kan men vormen op een n x n schaakbord?

  • Nemen we eerst het aantal vierkanten. We noteren V(n) voor het aantal vierkanten dat je kan tekenen op een nxn bord. Voor de 1×1 vierkanten heb je n mogelijke verticale posities en n horizontale, dus n^2 mogelijke vierkanten. Voor de 2×2 vierkanten heb je n – 1 verticale en horizontale mogelijke plaatsingen , dus (n-1)^2 mogelijkheden. Uiteindelijk is het totaal aantal vierkanten gelijk aan n^2+(n-1)^2+\cdots+2^2+1^2

        \[V(n)=\frac{n(n+1)(2n+1)}{6}\]

  • Met R(n) noteren we het aantal rechthoeken dat je kant tekenen op een nxn schaakbord. Voor een rechthoek heb je 2 verticale en twee horizontale lijnen nodig. Er zijn n+1 verticale en n+1 horizontale lijnen op een schaakbord. Om de verticale lijnen te kiezen heb je dus {n+1}\choose{2} =\frac{n(n+1)}{2}  mogelijkheden. Idem voor de keuze van de twee horizontale lijnen. Dus

        \[R(n)=\frac{n^2(n+1)^2}{4}\]

  • Voor een 8×8 schaakbord heb je dus 204 vierkanten en 1296 rechthoeken. Van die rechthoeken zijn er 1092 die geen vierkant zijn.

Delannoy getallen

Beschouw in het vlak de punten P(x,y) met  natuurlijke getallen als coördinaten .Je kan je verplaatsen in het vlak volgens de vectoren (1,0) , (0,1)  en (1,1). Het aantal manieren waarop men vanuit de oorsprong het punt P(m,n) kan bereiken noemt men het Delannoy getal d(m,n), vernoemd naar de Franse legerofficier en amateur wiskundige Henri-Auguste Delannoy (28 sept 1833 – 5 febr 1915). Bij definitie stellen we d(0,0)=1.

Onderstaande tekening laat zien dat er bijvoorbeeld 13 mogelijke manieren zijn om het punt P(2,2) te bereiken:

Een tabel met enkele waarden van de Delannoy getallen :

We geven enkele eigenschappen:

  • d(m,0) = d(0,n) = 1
  • Er is een recursief verband tussen deze getallen: d(m,n) = d(m – 1,n) + d(m,n – 1) + d(m – 1,n – 1): elk getal in bovenstaande tabel is de som van zijn linkerbuur, zijn bovenbuur en het getal linksboven. Dit wordt beter geïllustreerd als we de tabel geven in de vorm van de driehoek van Pascal. ( teken de diagonalen van bovenstaande tabel). Nu is elk getal de som van de driehoek erboven.
  • We stellen de verplaatsingen over (1,0), (0,1) en (1,1) respectievelijk voor door O,N en D. Wanneer we k keer D gebruiken om P(m,n) te bereiken,  moeten we m – k keer O en n – k keer N gebruiken. Om te berekenen op hoeveel manieren dit kan, maken we gebruik van de formule van de herhalingspermutaties : we moeten
    k + (m – k) + (n – k ) = m + n – k symbolen rangschikken, waarvan er k van het soort D zijn , m – k van het soort O en  n – k van het soort N. We vinden dus voor elke waarde van k kleiner of gelijk aan het minimum van m en n als aantal mogelijkheden:

        \[\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

    In het totaal heb je dan :

        \[\sum_{k=0}^{ min(m,n)}\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

  • Op de tweede rij en tweede kolom vinden we alle oneven getallen :
    d(m,1) = 2m+1. Dit is gemakkelijk te bewijzen met bovenstaande formule

Een combinatorisch probleem

Je beschikt over 7 verschillende flessen wijn en je hebt 7 proevers.  Het is niet praktisch alle 7 proevers alle 7 flessen te laten beoordelen, dus besluiten we volgende test te doen:

  • Iedereen proeft van  eenzelfde aantal flessen.
  • Elk paar van flessen wordt door exact 1 gemeenschappelijke persoon geproefd.
  • Elk paar van proevers proeft exact 1 gemeenschappelijke wijn.

Kan die test worden uitgevoerd? En wat als je de 7 vervangt door een ander aantal? Dit type van problemen is van groot belang voor statistici en behoort tot de tak van de combinatorische ontwerp theorie. Voor 7 is het probleem oplosbaar. Geef de 7 proevers een nummer van 1 tot 7 en de flessen een label A tot G. De test kan dan worden uitgevoerd door iedereen 3 flessen te laten proeven:
1:{A,B,C}   2:{A,D,F}   3: {B,D,E}   4:{A,E,G}   5: {C,E,F}    6:{B,F,G}   7:{C,D,G}

Deze oplossing heeft ook een mooie grafische voorstelling in volgende figuur waar de proevers voorgesteld worden door lijnen en de flessen door punten. Je moet dus 7 lijnen tekenen tussen 7 punten zodat elk paar punten juist 1 lijn gemeen heeft en zodat elk paar lijnen juist 1 punt gemeen heeft.

 

Je kan in ons voorbeeld 7 veranderen door een getal n van de vorm : n=q^2+q+1 met q een priemmacht. De overeenkomstige voorstelling geeft dan een projectief vlak van orde q+1. Dit vlak heeft q^2+q+1 punten en q^2+q+1 lijnen . Elke lijn bevat juist q+1 punten en door elk punt gaan exact q+1 lijnen. In bovenstaand voorbeeld is q=2.