Περιστερώνας, αναλλοίωτα, ακραία στοιχεία: θεωρία για μαθηματικούς διαγωνισμούς

Ιδέες που λύνουν προβλήματα ύπαρξης («να δείξετε ότι υπάρχει…») και παιχνίδια.

τα βασικά

Αρχή του περιστερώνα: αν \(n+1\) αντικείμενα μπουν σε \(n\) κουτιά, κάποιο κουτί έχει τουλάχιστον 2. Γενικά, \(kn+1\) αντικείμενα σε \(n\) κουτιά δίνουν κουτί με τουλάχιστον \(k+1\).
Αναλλοίωτο: βρες μια ποσότητα (π.χ. άρτιο ή περιττό ενός αθροίσματος, υπόλοιπο με το 3) που δεν αλλάζει με τις επιτρεπτές κινήσεις. Αν διαφέρει μεταξύ αρχικής και τελικής κατάστασης, η τελική κατάσταση είναι αδύνατη.
Χρωματισμός: η σκακιέρα με εναλλασσόμενα χρώματα αποδεικνύει πολλά «αδύνατα» πλακοστρωσίματα.
Αρχή ακραίου: εξέτασε το μεγαλύτερο ή το μικρότερο στοιχείο. Συχνά οδηγεί σε άτοπο.

Να δείξετε ότι ανάμεσα σε 13 ανθρώπους δύο έχουν γενέθλια τον ίδιο μήνα.

Λύση. 12 μήνες είναι τα κουτιά, 13 άνθρωποι τα αντικείμενα. Από την αρχή του περιστερώνα, κάποιος μήνας έχει τουλάχιστον δύο.

Να δείξεις ένα παράδειγμα αντί για απόδειξη. Σε προβλήματα του τύπου «να δείξετε ότι πάντα…» ένα παράδειγμα δεν αρκεί.