Αρχή του περιστερώνα

Στα μαθηματικά, η αρχή του περιστερώνα δηλώνει πως αν τοποθετήσουμε n αντικείμενα σε m δοχεία, με n > m, τότε τουλάχιστον ένα δοχείο πρέπει να περιέχει περισσότερα από ένα αντικείμενα. Το κλασσικό παράδειγμα περιγράφει 9 περιστερώνες με 10 περιστέρια, οπότε και κάποιος περιστερώνας θα έχει τουλάχιστον 2 περιστέρια. Πρόκειται για μια αρχή όπου αν και επιφανειακά δηλώνει το προφανές, μπορεί να χρησιμοποιηθεί έμπρακτα ως αποδεικτικό εργαλείο στην συνδυαστική, στη θεωρία κανονικών γλωσσών, και στη στατιστική, μεταξύ άλλων. Η αρχή του περιστερώνα αποδίδεται κυρίως στον Γερμανό μαθηματικό G. Lejeune Dirichlet, οπού στην εργασία του χρησιμοποιούσε την αρχή με το όνομα Schubfachprinzip ("αρχή του συρταριού" ή "αρχή του ραφιού").

Η αρχή του περιστερώνα έχει πολλές γενικεύσεις και μπορεί να διατυπωθεί με διάφορους τρόπους. Η συνηθισμένη γενίκευση είναι η εξής:

Αν $n,m\in \mathbb {N}$, και $n$ αντικείμενα κατανέμονται σε $m$ δοχεία, τότε τουλάχιστον ένα δοχείο περιέχει τουλάχιστον $\lceil n/m\rceil$αντικείμενα.

Αν και η πιο απλή εφαρμογή είναι σε πεπερασμένα σύνολα (όπως περιστέρια και κουτιά), χρησιμοποιείται επίσης με άπειρα σύνολα που δεν μπορούν να τεθούν σε αντιστοιχία ένα προς ένα . Για να γίνει αυτό απαιτείται η επίσημη δήλωση της αρχής του περιστερώνα: δεν υπάρχει "ένα-προς-ένα" συνάρτηση της οποίας το σύνολο τιμών είναι μικρότερο από πεδίο ορισμού της. Προηγμένες μαθηματικές αποδείξεις όπως το λήμμα του Siegel βασίζονται σε αυτή τη γενικότερη ιδέα.