Dueslagsprincippet

Dueslagsprincippet er en klassisk tælleteknik i matematik og kombinatorik. Det siger, at hvis man har flere elementer end kasser at lægge dem i, så må mindst én kasse indeholde mere end ét element.

 

Princippet er overraskende enkelt, men meget kraftfuldt. Det bruges til at bevise, at visse situationer er uundgåelige, uanset hvordan man fordeler elementerne. Der findes en simpel og en generel udgave.

 

 

Simpelt dueslagsprincip

Hvis man har k + 1 elementer, der skal fordeles i k kasser, så vil mindst én kasse indeholde mere end et element.

 

Eksempel 1: Fødselsdage

I en gruppe på 13 personer må mindst to have fødselsdag i samme måned, da der kun er 12 måneder.

 

Eksempel 2: Sokker

Hvis du har 3 sokker, men kun 2 farver (fx sort og hvid), så vil mindst to sokker have samme farve.

 

Bevis (simpelt)

Antag det modsatte: at ingen kasse indeholder mere end ét element. Så kan der højst ligge k elementer i k kasser. Men vi har k + 1 elementer. Dette er en modstrid, og dermed må mindst én kasse have mere end et element.

 

 

Generelt dueslagsprincip

Hvis man fordeler N elementer i k kasser, vil mindst én kasse indeholde mindst:

 

$$ \large \left\lceil \frac{N}{k} \right\rceil $$

 

Det betyder, at man altid kan garantere en vis minimumsfordeling, uanset hvordan man placerer elementerne.

 

 

Eksempel 1: Fodboldkamp

Der er 40.000 tilskuere til en kamp og 365 mulige fødselsdage. Mindst én fødselsdag deles af:

 

$$ \large \left\lceil \frac{40000}{365} \right\rceil = 110 $$

 

Det betyder, at mindst 110 personer deler fødselsdag.

 

 

Eksempel 2: Kortspil

I et spil kort uden jokere er der 52 kort fordelt på 4 kulører. Hvis man trækker 21 kort, vil mindst én kulør have:

 

$$ \large \left\lceil \frac{21}{4} \right\rceil = 6 $$

 

Altså er man sikker på at have mindst 6 kort i samme kulør.

 

 

Bevis (generelt)

Hvis alle kasser havde højst \(\large \left\lfloor \frac{N}{k} \right\rfloor \) elementer, ville det samlede antal elementer højst være \( \large k \cdot \left\lfloor \frac{N}{k} \right\rfloor \leq N \). Men hvis dette var tilfældet, ville der mangle plads til nogle elementer. Derfor må mindst én kasse have \(\large \left\lceil \frac{N}{k} \right\rceil \) elementer.

 

 

Anvendelser

Dueslagsprincippet virker simpelt, men bruges i mange avancerede sammenhænge:

 

• Kombinatorik: Beviser om permutationer og kombinationer.
• Sandsynlighed: At vise at visse udfald er uundgåelige.
• Grafteori: At garantere, at en graf har noder med bestemte forbindelser.
• Computer science: Hashfunktioner og datalagring – hvis man har flere elementer end pladser, må der optræde kollisioner.

 

 

Opsummering

Dueslagsprincippet siger, at hvis man har flere elementer end kasser, så må mindst én kasse indeholde mere end ét element. Den generelle version giver os formlen:

 

$$ \large \left\lceil \frac{N}{k} \right\rceil $$

 

Princippet kan bevises enkelt, men har dybe anvendelser i matematik og datalogi. Det sikrer, at vi kan forstå, hvornår noget er uundgåeligt, og det er et vigtigt redskab i kombinatorik og sandsynlighed.