Prinsippet om skuffer

Skuffeprinsippet , også kalt duehullloven , sier at dersom n + k objekter plasseres i n skuffer, så må minst én skuff inneholde mer enn én gjenstand. En annen måte å se prinsippet på er at et duehus med m bokser maksimalt kan inneholde m duer, hvis du ikke ønsker å legge mer enn én i en boks: en ekstra fugl må nødvendigvis dele boksen med en medfugl. Formelt sier prinsippet at hvis A og B er to endelige sett og B har kardinalitet strengt mindre enn A , så er det ingen injektiv funksjon fra A til B.

Skuffeprinsippet er et eksempel på et kombinatorisk argument , som kan brukes på mange formelle problemer, inkludert de som er knyttet til uendelige sett som ikke kan settes i en-til-en-korrespondanse. I den diofantiske tilnærmingen går den kvantitative anvendelsen av prinsippet på eksistensen av heltallsløsninger av et system av lineære ligninger under navnet " Siegels lemma ".

Det antas at prinsippet først ble stavet av Dirichlet i 1834 under navnet Schubfachprinzip ("skuffeprinsippet"). På noen språk (f.eks. russisk) er dette prinsippet derfor kjent som "Dirichlet-prinsippet", for ikke å forveksle med prinsippet med samme navn om harmoniske funksjoner . På engelsk snakker vi imidlertid om duehullsprinsippet , hvor " duehullet " refererer til de åpne postkassene som er i bruk på enkelte kontorer og universiteter.

Eksempler

Selv om skuffprinsippet ved første øyekast kan virke som en triviell observasjon, kan det brukes til å demonstrere uventede resultater, som «Minst to personer med like mange hår bor i Roma». Bevis: En gjennomsnittlig person har rundt 150 000 hår. Det er rimelig å anta at ingen har mer enn en million: men Roma har mer enn en million innbyggere. Hvis vi forbereder et enormt arkivskap med en million skuffer, og knytter tilsvarende antall hår til hver av dem, og tildeler hver person - eller mer pragmatisk et dokument deres - til den tilsvarende skuffen, må det være to personer i samme skuff, og derfor med samme antall hår.

Et annet eksempel er tilfellet der det er fem personer som ønsker å spille fotball i en turnering, og fire lag til stede. Dette ville ikke vært et problem hvis det ikke var at ingen av de fem ønsker å spille på samme lag som noen av de fire andre: men på grunn av prinsippet om skuffene er det umulig å dele dem på de forskjellige lagene.

Innen datavitenskap er det mange praktiske eksempler på skuffeprinsippet. Ta for eksempel en hash-tabell: kollisjoner av verdier oppstår fordi antallet mulige nøkler er langt større enn for hash-indekser. Ingen algoritme , uansett hvor sofistikert, vil være i stand til å eliminere kollisjoner med sikkerhet. På samme måte er det vist at det ikke kan eksistere en "perfekt" tapsfri komprimeringsalgoritme, det vil si en som reduserer størrelsen på en fil til en hvilken som helst størrelse - eller til og med større enn et visst antall M biter - gitt til den som input . Faktisk er filer som består av M +1 biter 2 M +1 , men summen av alle mulige filer med bitstørrelse er 2 M +1 - 2: derfor må det være minst to inndatafiler tilordnet den samme utdatafilen . Men da mislykkes antakelsen om at komprimeringen er tapsfri, siden man ikke kunne skille mellom de to konverterte filene i samme utdatafil.

Andre eksempler er gitt i Grimaldis tekst. [1]

Generaliseringer

En generalisert versjon av prinsippet sier at hvis det er n diskrete objekter som må tildeles i m containere, så vil det være minst én container som vil inneholde minst objekter (symbolet  angir det øverste heltall ).

En probabilistisk generalisering av skuffeprinsippet sier at hvis n duer er tilfeldig plassert i et duehus fra m steder med ensartet sannsynlighet 1/ m , så vil minst ett sted i duehuset inneholde mer enn én due med sannsynlighet

hvor er en synkende faktoriell . For n = 0 og for n = 1 (med m > 0) er denne sannsynligheten null, mens for n > m er den én, og dermed sammenfallende med det ordinære skuffprinsippet.

I kvantemekanikk

I 2014 demonstrerte en gruppe forskere ( Yakir Aharonov et al. ) at i kvantemekanikk kan prinsippet om skuffer brytes, og foreslo også noen interferometriske eksperimenter for mulig eksperimentell verifikasjon. [2]

Merknader

  1. ^ Grimaldi,  diskret og kombinatorisk matematikk: en anvendt introduksjon .
  2. ^ Kvantedue? Kom igjen , på media.inaf.it . Hentet 15. juli 2016 .

Bibliografi

Relaterte elementer

Eksterne lenker