Problem O
Dúfuskúffur

Mynd fengin af commons.wikimedia.org

Í stærðfræðiheiminum er til fræg regla sem er oft kölluð skúffuregla Dirichlet. Á ensku er hún almennt kölluð The Pigeonhole Principle. Reglan segir að ef maður er með fleiri dúfur en hólf fyrir dúfurnar og maður vill koma þeim öllum fyrir, þá verður maður að setja fleiri en eina dúfu í einhvert hólfið. Við ætlum að skoða þetta fyrirbæri í þessu dæmi, og þá á einmitt að prenta “Dufur passa” ef dúfurnar komast fyrir án þess að troða fleiri en eina dúfu í eitthvert hólfið. En þetta tengist einmitt inn á aðra stærðfræðireglu sem kallast Principle of Inclusion-Exclusion þar sem stundum verða dúfur útundan ef maður neitar að troða. Í þessu tilfelli á einmitt að prenta “Dufur passa ekki”. Þessi regla er oft stytt sem PIE, eða jafnvel táknuð með gríska stafnum $\pi $. Þetta tengist einmitt inn á fræga kvikmynd sem fjallar um mann sem missir sig í að reyna finna tengingar í tölum. Það er einmitt það sem við erum að gera hér, eins og að tengja þetta inn á myndina The Number 23. Það má einmitt mikið leita að merkingu í tölum, hvort hlutir passi vel saman eða hvort hlutir séu í ójafnvægi. Það er einmitt mjög mikilvægt í þessu dæmi. Því ef allt passar fullkomlega í dæminu, með engar dúfur eða skúffur afgangs, á einmitt að prenta “Dufur passa fullkomlega”. Margir aðrir hafa líka velt fyrir sér merkingu talna. Vel þekktur múrari fékk einmitt þá spurningu, sem tengir okkur inn á þorska. Ísland vann einmitt þorskastríðið, og er því einmitt stórasta land í heimi. Hafa skal þetta allt í huga þegar þið leysið eftirfarandi dæmi.

Inntak

Inntak samanstendur af tveimur línum. Fyrsta línan inniheldur eina heiltölu $n$, fjölda dúfa. Önnur línan inniheldur heiltöluna $m$ sem táknar fjölda hólfa fyrir dúfurnar.

Úttak

Prentaðu út hvort dúfurnar passi, eins og lýst er að ofan.

Stigagjöf

7
9

Dufur passa

10
9

Dufur passa ekki