Duvhålsprincipen: definition och exempel i matematik och datavetenskap

Förklaring och tydliga exempel på duvhålsprincipen inom matematik och datavetenskap — definition, bevis, tillämpningar och grafteori förklarade enkelt och visuellt.

Principen om duvhål (även kallad Dirichlets princip eller skåpprincipen) säger i sin enklaste form att om man försöker placera fler objekt än antalet behållare så måste åtminstone en behållare innehålla mer än ett objekt. Ett vanligt vardagligt exempel är att om det finns n hål i en låda och man försöker stoppa in n+1 duvor så kommer minst ett hål att innehålla minst två duvor. Duvorna används här som en metafor för godtyckliga objekt och hålen som behållare eller kategorier.

Formell utsaga

En vanlig, mer generell formuleringsform är: om m objekt fördelas i n lådor så innehåller åtminstone en låda minst ceil(m/n) objekt, där ceil är takfunktionen som avrundar uppåt. Den enkla formen som ofta räcker i bevis är: om m > n så finns en låda med minst två objekt.

Exempel

• Om 13 personer finns i ett rum finns det minst två personer som är födda i samma månad (12 månader → 13 personer → två i samma månad).
• Om 10 brev fördelas i 3 kuvert så innehåller minst ett kuvert minst ceil(10/3) = 4 brev.
• I datavetenskap: om man har fler nycklar än hash-buckets måste minst två nycklar hash:a till samma bucket — det vill säga en kollision är oundviklig om antalet objekt överstiger antalet hinkar.
• I grafteori används principen bland annat för att visa att i en enkel graf med n ≥ 2 noder finns alltid två noder med samma grad (antal kanter ut från noden). Gradvärdena kan vara 0,1,...,n−1 men det är omöjligt att samtidigt ha både en nod med grad 0 och en med grad n−1, så det finns bara n−1 möjliga olika gradvärden — därför måste två noder dela grad.

Bevisidé

Det finns flera enkla sätt att se varför principen är sann:

• Motstridsbevis: anta att varje låda innehåller högst ett objekt. Då kan det totalt finnas högst n objekt, vilket motsäger antagandet att det finns fler än n objekt.
• Genomsnittlighetsargument: om m objekt fördelas i n lådor är medelantalet objekt per låda m/n. Därför finns en låda med minst så många objekt som taket av medelvärdet, alltså minst ceil(m/n).

Varianter och generaliseringar

• Generaliserad duvhålsprincip: om m objekt fördelas i n lådor så finns en låda med minst ceil(m/n) objekt.
• Flerdimensionella eller mer sofistikerade varianter används i analys och kombinatorik, till exempel för att visa att en viss struktur förekommer minst ett visst antal gånger eller för att ge nedre gränser i optimeringsproblem.

Tillämpningar

Principen är enkel men kraftfull och används i många grenar av matematik och datavetenskap. Den kan ge direkta bevis för existenssatser (att något måste existera) utan att konstruktivt ange vilket element det är. Denna sats är viktig inom datavetenskap och matematik, särskilt inom grafteori, kombinatorik och sannolikhetsteori. Exempelvis används den för att visa kollisioner i hashfunktioner, begränsningar i komprimering och för att härleda enkla men viktiga egenskaper i grafer och relationer.

Tips för problemlösning: när du ser ett problem där objekt ska placeras i kategorier eller där antal möjliga värden är begränsat kan du ofta pröva att applicera duvhålsprincipen för att få snabba existensresultat eller nedre gränser.

Sök med bokstav