Tag archieven: duivenhok principe

Nootje 51

Geplaatst op door

20 leerlingen van een zelfde klas versturen  in december elk 10 wenskaarten naar 10 verschillende klasgenoten. Toon aan dat er minstens twee leerlingen zijn die een kaart naar elkaar sturen.

“Antwoord“

  • Dit doet me denken aan het duivenhokprincipe of principe van Dirichlet:  Wanneer n + 1 duiven in n hokken neerstrijken, dan is er altijd minstens 1 hok met minstens twee duiven.
  • De hokken zijn de koppels leerlingen: hiervoor moet je het aantal 2-combinnatir nemen van 20 elementen en dat is \binom{20}{2}=190.
  • De duiven zijn de brieven: zo zijn er 20*10=200
  • Bijgevolg heeft minstens 1 koppel twee brieven en zijn er dus zeker twee leerlingen die aan elkaar geschreven hebben.

Vrijdag de dertiende

Geplaatst op door

 

Toon aan dat er in ieder jaar minstens 1  en hoogstens 3 keer vrijdag de dertiende   voorkomt.

  • De dertiende van elke maand in een niet-schrikkeljaar hebben als dagnummer:13,44,72,103,133,164,194,225,256,286,317,347.
  • De resten bij deling door 7 zijn: 6,2,2,5,0,3,5,1,4,6,2,4
  • Twee maanden A en B worden in hetzelfde vakje geplaatst als de dertiende van die maanden op dezelfde dag van de week vallen. Omdat elk getal, van 0 tot 6, voorkomt in de laatste rij, zijn de maanden over de 7 vakjes verdeeld.
  • Elk van de 7 vakjes stelt één van de dagen van de week voor. Omdat elk vakje bezet is, komt er minstens 1 vrijdag de dertiende voor in een niet-schrikkeljaar.
  • Een zelfde waarde in dat rijtje resten komt hoogstens 3 maal voor, dus kunnen er hoogstens 3 vrijdagen de dertiende voorkomen.
  • Voor een schrikkeljaar zijn de dagnummers van de dertiende: 13,44,73,104,134,165,195,226,257,287,318 en 348.
  • De resten bij deling door 7 zijn: 6,2,3,6,1,4,6,2,5,0,3 en 5. De redenering is analoog als hierboven

 6 januari 2023 is een vrijdag, dus zijn er in 2023 twee vrijdagen de dertiende, namelijk in januari en oktober: de dagnummers moeten modulo 7 gelijk zijn aan 6 en er komt in het rijtje dagnummers bij niet-schrikkeljaren inderdaad 2 keer een 6 voor.

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\]

 

 

Bewijstechnieken

Geplaatst op door

De geschiedenis van ’Bewijs dat …’ begint, net als een sprookje, vele,
vele jaren geleden met ’Er was eens…’. Er was inderdaad eens een tijd
waarin geen bewijzen bestonden nl, tijdens de Babylonische periode,
want in de Babylonische wiskunde – 4000 jaar geleden – was er geen
spoor te vinden van het begrip bewijs, noch van enige deductieve redenering.
Babylonische wiskunde, zoals ook deze tijdens de Egyptische farao’s,
bestond uit recepten om een concreet probleem met concrete gegevens
op te lossen. Het was een wiskunde zonder bewijzen, zonder verklaringen!
Toch bleek na verloop van tijd ergens de noodzaak voor meer
structuur omdat elk gelijkaardig probleem telkens moest worden hernomen
volgens het gegeven recept.

Lees hier over de verschillende bewijstechnieken.
bewijzen