Laatikkoperiaate (pigeonhole): määritelmä, esimerkit ja sovellukset

Laatikkoperiaate (kyyhkyläperiaate): selkeä määritelmä, käytännön esimerkit ja sovellukset matematiikassa ja tietojenkäsittelyssä — ymmärrä periaate nopeasti.

Kyyhkyläperiaate (myös laatikko- tai pigeonhole-periaate) sanoo yksinkertaisesti, että jos sinulla on n laatikkoa (tai "reikää") ja enemmän kuin n esinettä (tai "kyyhkysiä"), niin ainakin yhdessä laatikossa on enemmän kuin yksi esine. Tämä on intuitiivinen olemassaololauseke, joka kertoo, että jakaminen rajoitettuun määrään osia pakottaa päällekkäisyyteen, jos esineitä on liikaa yhden laatikon kantokyvyn näkökulmasta.

Tämä lause on tärkeä tietojenkäsittelytieteessä ja matematiikassa, erityisesti graafiteoriassa. Sitä käytetään usein selittämään olemassaolon tuloksia — eli osoittamaan, että jokin ominaisuus on pakko esiintyä ainakin yhdessä ryhmän jäsenistä, vaikka sitä ei osattaisi suoraan konstruoida.

Määritelmä (formaalinen muoto)

Perusmuodossaan: jos N esinettä sijoitetaan k laatikkoon ja N > k, niin ainakin yksi laatikko sisältää vähintään kaksi esinettä. Yleistetty muoto kuuluu: jos N esinettä sijoitetaan k laatikkoon, niin ainakin yhdessä laatikossa on vähintään ceil(N/k) esinettä (eli suurin kokonaisluku, joka ei ole pienempi kuin N/k).

Yksinkertainen todistus

Todistus perustuu vastaoletukseen. Oleta, että kukin laatikko sisältää korkeintaan t esinettä. Tällöin k laatikkoa voi yhteensä sisältää enintään k·t esinettä. Jos N > k·t, oletus johtaa ristiriitaan, joten jossain laatikossa on oltava enemmän kuin t esinettä. Perusmuoto saadaan valitsemalla t = 1.

Helppoja esimerkkejä

• Kuukausiesimerkki: Jos huoneessa on 13 ihmistä, kahdella heistä on sama syntymakuukausi, koska kuukausia on 12 ja 13 > 12.
• Syntymäpäivien variantti: Jos ihmisiä on 367, kaksi heistä on varmasti syntynyt samana päivänä (ottamatta huomioon karkausvuoden erikoisuuksia), koska päivässä on 366 vaihtoehtoa.
• Värisukat: Jos sinulla on 10 sukkaa kolmessa eri värissä, ainakin ⌈10/3⌉ = 4 sukkaa ovat samansävyisiä.
• Jäännösluokat: Jos on n+1 kokonaislukua, kahdella niistä on sama jakojäännös modulo n, joten niiden erotus on jaollinen n.

Lisämuotoja ja laajennuksia

• Yleinen raja: jos N objektia ja k laatikkoa, jokin laatikko sisältää vähintään ⌈N/k⌉ objektia.
• Useampiosainen periaate: jos haluat varmistaa, että jokin laatikko sisältää vähintään t esinettä, riittää että N > k·(t−1).
• Puutteellinen versio (ominaisuuksien jako): kun joukon jäsenet jaetaan m luokkaan, ja jäseniä on enemmän kuin k·(m−1), jonkin luokan täytyy sisältää vähintään k jäsentä.

Sovelluksia

• Tietojenkäsittely: hajautustauluissa (hashing) periaate selittää törmäysten väistämättömyyden, kun avaruus avaimille on suurempi kuin mahdollisten tulosten määrä. Myös kuorman tasaamisessa (load balancing) ja resurssien jakamisessa käytetään vastaavia argumentteja.
• Yhdistelmällinen todistusmenetelmä: monissa olemassaolotodistuksissa käytetään laatikkoperiaatetta osoittamaan, että jokin haluttu rakenne tai ominaisuus pitää löytyä ainakin yhdeltä jäseneltä.
• Lukuteoria ja diophantiset approksimaatiot: esimerkiksi Dirichletin approksimaatiolauseen todistuksessa hyödynnetään usein laatikkoperiaatteen ideoita (jakamalla yksikköväli sopiviin osiin ja vertaamalla murtolukujäännöksiin).
• Graafiteoria ja kombinatoriikka: monissa laskelmissa ja rakenne-eroissa hyödynnetään periaatteen yksinkertaisia mutta tehokkaita seuraamuksia.

Esimerkkitehtävä ja ratkaisu

Tehtävä: Todista, että joukossa, jossa on 51 eri kokonaislukua väliltä 1–100, on aina kaksi lukua niin, että toinen on toisen summa (eli a + b = c) — huom: tämänkaltaisia väittämiä ei aina pidä paikkaansa; alla oleva on vain esimerkkitapauksesta, jossa kriteerit valitaan oikein.

Ratkaisuidea: Yksi tapa lähestyä vastaavia ongelmia on ryhmitellä lukuja ominaisuuden mukaan (esimerkiksi parillisuus, modulo-jäännökset, tai esitykset tietyssä muodossa) ja käyttää laatikkoperiaatetta osoittamaan päällekkäisyys, joka johtaa haluttuun suhteeseen. (Tarkempi ratkaisu riippuu ongelman täsmällisestä muotoilusta.)

Huomioita

• Laatikkoperiaate on olemassaololause: se takaa, että jokin tapahtuu, mutta ei kerro, mikä tai missä — usein tarvitaan lisäargumentteja löytämään tai rakentamaan konkreettinen esimerkki.
• Vaikka periaate on yksinkertainen, sen sovellukset voivat olla hyvin kekseliäitä ja johtaa syvällisiin tuloksiin useilla matematiikan ja tietojenkäsittelyn aloilla.

Hae kirjaimella