Duiven en coatings
De drie "duivenproblemen" die vorige week werden opgeworpen, riepen ondanks hun relatieve eenvoud veel interessante reacties op.
De eerste is de eenvoudigste: als we 12 keer met een dobbelsteen gooien, kan het gebeuren (hoewel het onwaarschijnlijk is (hoe onwaarschijnlijk?)) dat elk van de zes getallen twee keer valt. We zouden dus 13 keer moeten gooien om er absoluut zeker van te zijn dat een bepaald getal minstens drie keer valt.
De tweede kan op verschillende manieren worden benaderd. Zo deed Luis Ortiz het:
Het 12-cijferige probleem wordt duidelijk geïllustreerd aan de hand van een tabel. We rangschikken de 100 mogelijke tweecijferige getallen in rijen van elk 11 opeenvolgende getallen, beginnend bij 00, als volgt:
00 01 02 03 04 05 06 07 08 09 10
11 12 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29 30 31 32
· · ·
88 89 90 91 92 93 94 95 96 97 98
99
In deze tabel is het verschil tussen twee getallen in dezelfde kolom een veelvoud van 11, oftewel: beide cijfers zijn gelijk. Als we 12 getallen in de tabel kiezen, moeten er minstens twee in dezelfde kolom staan, wat betekent dat hun verschil beide cijfers gelijk zal hebben. Inderdaad: uiteindelijk is het een duivenhok met 11 bakken en 12 duiven.
Aan het einde van mijn vorige bericht schreef ik al dat we met het hokjesprincipe een aantal problemen effectief kunnen aanpakken door het te combineren met de grafentheorie. De oplossing die Manuel Amorós gaf voor het derde probleem van vorige week is daar een goed voorbeeld van:
Het vriendschapsprobleem is duidelijk te zien in een gekleurde graaf waarin de punten mensen voorstellen en de randen de relaties uitdrukken: een blauwe rand als ze elkaar kennen en een rode als ze elkaar niet kennen. Het doel is om het bestaan van een monochrome graaf aan te tonen. Vanuit elk hoekpunt P komen 5 randen tevoorschijn, blauw of rood. Noodzakelijkerwijs zullen er 3 van dezelfde kleur zijn, bijvoorbeeld blauw. De 3 corresponderende hoekpunten zullen op hun beurt met elkaar verbonden zijn, en er zijn twee gevallen mogelijk: ofwel zijn alle 3 randen van de genoemde driehoek rood (we zouden een monochrome driehoek hebben), ofwel is er één blauwe rand. Deze rand vormt samen met de 2 randen die van de uiteinden naar P toe uitstralen een blauwe driehoek.
Coatings met vergelijkbare figurenZonder ons conceptuele duivenhok te verlaten (hoewel de relatie misschien niet duidelijk is), stelde Salva Fuster het volgende dekkingsprobleem voor:
"Gegeven een gelijkzijdige driehoek, hoeveel kleinere gelijkzijdige driehoeken zijn er minimaal nodig om deze te bedekken?"
Deze kleinere driehoeken hoeven niet gelijk te zijn en mogen elkaar overlappen (anders zou het antwoord uiteraard 4 zijn).
Het probleem laat interessante variaties en generalisaties toe: Gegeven een vierkant, hoeveel kleinere vierkanten zijn er minimaal nodig om het te bedekken? Kan het criterium worden gegeneraliseerd naar andere regelmatige veelhoeken? En naar onregelmatige veelhoeken? En naar de cirkel?
En tenslotte nog een probleem (dat op subtiele wijze verband houdt met het SF-probleem) waarin de gelijkzijdige driehoek en het duivengatprincipe samenkomen:
Gegeven de 5 punten in een gelijkzijdige driehoek met zijden van 1 meter, kunnen deze meer dan 50 cm uit elkaar liggen?
Hij is schrijver en wiskundige, lid van de New York Academy of Sciences. Hij heeft meer dan 50 populairwetenschappelijke werken gepubliceerd voor volwassenen, kinderen en jongeren, waaronder "Damn Physics", "Damn Mathematics" en "The Great Game". Hij was de scenarioschrijver van "La bola de cristal".
EL PAÍS
