Categorie archieven: Discrete wiskunde

Een combinatorisch probleem

Geplaatst op door

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.

Pythagorese drietallen

Geplaatst op door

Een Pythagorees drietal is een drietal positieve gehele getallen (a,b,c) waarvoor geldt dat

    \[a^2+b^2=c^2\]

Deze afbeelding heeft een leeg alt-attribuut; de bestandsnaam is pyt1.png

Zo zijn (3,4,5) en (5,12,13) allebei Pytagorese drietallen.
Het is duidelijk dat als (a,b,c) een Pythagorees drietal is, dat dan ook (ad,bd,cd) een Pythagorees drietal is. Oplossingen van a^2+b^2=c^2 die relatief ondeelbaar zijn, noemen we primitieve Pythagorese drietallen. Hiervoor kennen we volgend resultaat:


Als m en n relatief ondeelbare postieve gehele getallen zijn met m>n en waarbij één ervan even is en de andere oneven, dan vormen  a=m^2-n^2, b=2mn en c=m^2+n^2 een primieteve oplossing van a^2+b^2=c^2. Bovendien geldt dat elke primitief Pythagorees drietal van die vorm moet zijn, op een mogelijke permutatie van a en b na.

Spelen met kralen

Geplaatst op door

Hoeveel snoeren kan je maken met 3 rode en 5 witte kralen? Als je het snoer draait (cyclisch) of omkeert ( spiegeling), krijg je geen ander snoer.

We stellen een snoer voor als een combinatie van 3 R-en en 5 W’s. We weten dat WRRRWWWW en RRRWWWWW dezelfde ketting voorstelt. We kunnen er dus steeds voor zorgen dat we eindigen met een R. Maar ook RRWRWWWW en RWRRWWWW stellen hetzelfde snoer voor, want als je de laatste 4 W’s vooraan zet, zijn de twee snoeren elkaars spiegelbeeld.

Focussen we ons even op de rode kralen en bekijken we een snoer als
…R…R…R, dan rest ons de 5 witte kralen te verdelen over de drie aangegeven vakjes (na de laatste R is er geen vakje meer wegens het cyclisch zijn van het snoer. We coderen het snoer door de aantallen witte kralen in die vakjes. De combinatie WRRRWWWW en RRRWWWWW of WWWWWRRR stellen we dan voor als 500 en de gelijke snoeren RRWRWWWW en RWRRWWWW worden dan 401 en 410. We kiezen voor  die getallencombinatie die een niet -stijgende rij is.

Welke mogelijkheden houden we uiteindelijk over?

RRRWWWWW=500
RRWRWWWW=401=410
RRWWRWWW=302=320
WRWRWWWR=113=311
WRWWRWWR=122=221

En dus is het aantal snoeren gelijk aan het aantal partities van 5 in hoogstens 3 delen, dit is het aantal manieren om 5 te schrijven als de som van hoogstens 3 postieve getallen. Kunnen we dit veralgemenen?  3 rode en n witte kralen? Lees hierover meer in volgens artikel.

Duivenhok principe

Geplaatst op door

Verdeel je meer dan n duiven over n hokken, dan bevat minstens één hok minstens 2 van die duiven. Over dit duivenhok principe hebben we het gehad op een andere pagina van deze website. Het is niet altijd even gemakkelijk om de juiste ‘hokken’ te kiezen om alzo het principe te kunnen toepassen. Volgende opgaven lijken op elkaar, maar toch is de keuze van de ‘hokken’ totaal anders.

Kies 51 getallen uit de verzameling {1,2,3,…,100}. Toon aan dat :

  • er in die 51 getallen  twee getallen bestaan die geen gemeenschappelijke priemdeler hebben.

  • er in die 51 getallen twee getallen  bestaan zodat de ene een deler is van de andere.

 

Voor de eerste vraag neem je 50 paar opeenvolgende koppels: (1,2),(3,4),…,(99,100). Vermits er 51 getallen gekozen worden, moet er daartussen dus zeker een paar (k,k+1) zitten. Als k en k+1 een zelfde priemdeler p zouden hebben zou p ook een deler zijn van (k+1)-k=1 en dat kan niet. Dus k en k+1 hebben geen gemeenschappelijke priemdeler.

Voor het tweede probleem neem je de 50 oneven getallen 1,3,5,…,99. Voor elk van die getallen vorm je een ‘hok’ met daarin het oneven getal en alle producten ervan met machten van 2. Zo bevat het eerste hok de elementen 1,2,4,8,16,32,64 en het tweede hok de elementen 3,6,12,24,48,96. Volgens het duivenhok principe moeten er tussen de 51 gekozen getallen er zeker twee zijn die in hetzelfde hok zitten. Die twee getallen zijn dan van de vorm 2^m.k en 2^n.k met k een oneven getal. Het is duidelijk dat het ene getal het andere deelt.

 

Vrienden of niet

Geplaatst op door

 

In elke groep van 6 personen zijn er altijd 3 die elkaar kennen of 3
die elkaar niet kennen.

Dit is niet noodzakelijk waar in een groep van 5
personen.

Het probleem is ook gekend met 6 punten waarbij alle verbindingslijnstukken ofwel in het rood ofwel in het blauw gekleurd worden. Bewijs dat minstens één  driehoek kan gevonden worden die drie gelijkgekleurde zijden heeft. We hebben hier te maken met een volledige graaf waarvan de zijden in twee mogelijke kleuren worden ingekleurd.

Wij gaan het probleem aanpakken in een iets moeilijker versie:

Gegeven 17 punten: A_1, A_2, A_3, . . . . , A_{17} die willekeurig in
het vlak  liggen. Men trekt tussen deze punten alle verbindingslijnstukken, hetzij rood, hetzij blauw, hetzij groen. Bewijs dat minstens één  driehoek kan gevonden worden die drie gelijkgekleurde zijden heeft.

 

 

  • Kies een willekeurig punt uit het zeventiental en beschouw de zestien verbindingslijnstukken die dat punt met de zestien andere punten verbindt.
  • Volgens het duivenhokprincipe is het steeds mogelijk uit die zestiental lijnstukken een zestal te vinden die dezelfde kleur hebben. Laten we aannemen dat de zes gekozen lijnstukken allemaal rood
    zijn.
  • De zes rode lijnstukken verbinden het eerstgekozen punt met een zestal andere punten. We richten nu onze aandacht op dat zestal en in het bijzonder op hun verbindingslijnstukken.
  • Vinden we bij die verbindingslijnstukken een rood exemplaar, dan vormt dit met de beide rode liinstukken  een rode driehoek en dan zijn we klaar.
  • Het ergste, wat ons overkomen kan, is  dat die zes punten alleen groene en blauwe verbindingslijnstukken hebben. Laten we dus aannemen, dat dit het geval is.
  • Kies uit het zestal punten nu een willekeurig punt uit en beschouw de vijf verbindingslijnstukken van dit punt met de vijf andere punten van het zestal.  Kies er drie uit die dezelfde kleur hebben .Dat dit mogelijk is volgt weerom uit het duivenhokprincipe.
  • Laten we aannemen, dat ze alle drie groen zijn. Tenslotte letten we op de verbindingslijnstukken van die drie andere punten. Deze
    zijn groen of blauw. Is er een van die verbindingslijnstukken groen, hebben we een groene driehoek gevonden. En er is geen groene bij, dan vormen ze zelf een blauwe driehoek.

 

We kunnen dit veralgemenen voor n kleuren . Noteer met a_n het aantal punten dat er nodig is om met n kleuren steeds een driehoek te vinden met gelijkgekleurde zijden. Dan geldt:

    \[a_n=n.a_{n-1}+2-n\]