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

Η Αρχή του Περιστερώνα (pigeon principle) αλλιώς γνωστή ως Αρχή του Συρταριού (Schubfachprinzip στα γερμανικά ή principe des tiroirs στα γαλλικά) ή Αρχή του Dirichlet λέει ότι

Αρχή του Περιστερώνα 1: Αν n περιστέρια τοποθετηθούν σε m<n φωλιές, τότε σε τουλάχιστον μία φωλιά υπάρχουν τουλάχιστον 2 περιστέρια.

Μία πιο επίσημη διατύπωση είναι (|A| εκφράζει το πλήθος των στοιχείων του πεπερασμένου συνόλου A):

Αρχή του Περιστερώνα 2: Για τα πεπερασμένα σύνολα A και B, υπάρχει συνάρτηση 1-1, f: A → B , αν-ν |A| = |B|.

Αν και η αρχή αυτή είναι πολύ απλή και προφανής, μερικές φορές οδηγεί σε αντι-διαισθητικά αποτελέσματα ή τουλάχιστον σε αποτελέσματα που δεν είναι προφανή. Μερικά παραδείγματα είναι τα εξής:

Παράδειγμα 1
Στη λύση του προβλήματος Η λειψή σκακιέρα ο Messie χρησιμοποίησε τη Αρχή του Περιστερώνα ("περιστέρια": τα ντόμινο, "φωλιές": τα λευκά τετράγωνα).


Παράδειγμα 2

Στη λύση του προβλήματος Υποσύνολα με ίδιο άθροισμα, ο JR χρησιμοποίησε επίσης την Αρχή του Περιστερώνα ("περιστέρια": το πλήθος των αθροισμάτων των υποσυνόλων, "φωλιές": τα δυνατά αθροίσματα).

Παράδειγμα 3

Σε ένα δωμάτιο υπάρχουν n άνθρωποι, άλλοι χαιρετιούνται με χειραψία κι άλλοι όχι. Τότε υπάρχουν τουλάχιστον δύο άνθρωποι που έχουν κάνει τον ίδιο αριθμό χειραψιών.

Οι δυνατές τιμές χειραψιών για έναν άνθρωπο είναι 0, 1, ..., n-1. Αν υποθέσουμε ότι δεν υπάρχουν δύο άνθρωποι που έχουν κάνει τον ίδιο αριθμό χειραψιών, τότε υπάρχει ένας άνθρωπος που έχει κάνει n-1 χειραψίες (δηλαδή με όλους) και ένας με 0 χειραψίες, που είναι άτοπο.

Παράδειγμα 4
Ας είναι n θετικοί αριθμοί x₁, x₂, …, x_n. Τότε σίγουρα η διαφορά δύο από αυτούς διαιρείται από το n-1.

Αν συμβολίσουμε με r_i το υπόλοιπο της διαίρεσης του x_i με τον n-1, τότε οι r_i μπορούν να πάρουν τις τιμές 0, 1, 2, ..., n-2. Δηλαδή υπάρχουν n-1 δυνατές τιμές για τους r_i αλλά υπάρχουν συνολικά n αριθμοί r_i . Από την Αρχή του Περιστερώνα, δύο από αυτούς, έστω οι r_i και r_j, είναι ίσοι. Δηλαδή οι x_i και x_j είναι ισοϋπόλοιποι (ως προς τη διαίρεση με τον n-1) και συνεπώς η διαφορά τους διαιρείται ακριβώς από τον n-1.


Μία γενικευμένη εκδοχή της αρχής του Περιστερώνα είναι η εξής:

Αρχή του Περιστερώνα 3: Αν n περιστέρια τοποθετούνται σε m φωλιές, τότε τουλάχιστον μία φωλιά περιέχει τουλάχιστον $\lceil\frac{n}{m}\rceil$ περιστέρια και τουλάχιστον μία φωλιά περιέχει το πολύ $\lfloor\frac{n}{m}\rfloor$ περιστέρια.

(Στο παραπάνω $\lceil x\rceil$ εκφράζει το μικρότερο ακέραιο που είναι $\geq x$ ενώ $\lfloor x\rfloor$ εκφράζει το μεγαλύτερο ακέραιο που είναι $\leq x$. Δηλαδή ισχύει $\lfloor x\rfloor\leq x\leq\lceil x\rceil$ με $\lfloor x\rfloor=x=\lceil x\rceil$ αν-ν ο $x$ είναι ακέραιος.)

Άλλες γενικεύσεις περιλαμβάνουν
- σύνολα με άπειρο πλήθος στοιχείων,
- τη θεωρία πιθανοτήτων (τα περιστέρια τοποθετούνται σε κάθε φωλιά με συγκεκριμένη πιθανότητα)
και άλλες

Πρόβλημα
Ας είναι S = {1,2,...,100}. Τότε με οποιονδήποτε τρόπο κι αν επιλέξουμε 55 από τα στοιχεία του S, θα υπάρχουν

• δύο αριθμοί που διαφέρουν κατά 9,
• δύο αριθμοί που διαφέρουν κατά 10,
• δύο αριθμοί που διαφέρουν κατά 12,
• δύο ζεύγη αριθμών που διαφέρουν κατά 13.

Το περίεργο είναι ότι δεν υπάρχουν απαραίτητα δύο αριθμοί που διαφέρουν κατά 11!

Υποσύνολα με το ίδιο άθροισμα

Παίρνουμε 10 διαφορετικούς ακεραίους από το 1 μέχρι και το 100. Ζητούμε να εξετάσουμε αν από αυτό το σύνολο με τους 10 διαφορετικούς ακεραίους μπορούμε να βρούμε πάντα δύο υποσύνολα, το άθροισμα των στοιχείων των οποίων να είναι ίσο.

Για παράδειγμα ας είναι S = {1, 4, 5, 14, 17, 33, 41, 49, 68, 79, 88}.
Τότε αν θεωρήσουμε τα υποσύνολα Α₁ και Α₂ του S με Α₁ = {5, 14, 17, 33} και Α₂ = {1, 68}, παρατηρούμε ότι

5+14+17+33 = 1+68.  

Η τετράγωνη τούρτα

Η Ιωάννα έφτιαξε μία τετράγωνη τούρτα για τα γενέθλιά του Δημήτρη, την οποία είχε αλείψει με σοκολάτα από πάνω και στο πλάι.

Οι δικαιούχοι κομματιού τούρτας ήταν 9 (ο Δημήτρης και οι 8 φίλοι του).

Πώς μπορούμε να κόψουμε την τούρτα, ώστε να πάρουν όλοι την ίδια ποσότητα τούρτας και την ίδια ποσότητα σοκολάτας; (ακριβέστερα πώς πρέπει να κοπεί η τούρτα ώστε να πάρουν όλοι τον ίδιο όγκο τούρτας και την ίδια επιφάνεια σοκολάτας)

Ψηφιακό άθροισμα δίδυμων πρώτων

Το ψηφιακό άθροισμα ενός αριθμού υπολογίζεται αν υπολογίσουμε το άθροισμα των ψηφίων του αριθμού. Αν το άθροισμα δεν είναι μονοψήφιος, τότε συνεχίζουμε τη διαδικασία μέχρι να φτάσουμε σε μονοψήφιο αριθμό. Για παράδειγμα το ψηφιακό άθροισμα του 4857 είναι (4+8+5+7 = 24 → 2+4 =) 6.

Δίδυμοι πρώτοι είναι δύο πρώτοι που διαφέρουν κατά 2. Για παράδειγμα οι 5 και 7 είναι δίδυμοι πρώτοι.

Να δειχθεί ότι το ψηφιακό άθροισμα του γινομένου δύο δίδυμων πρώτων (με εξαίρεση το ζεύγος (3,5)) είναι πάντα ίσο με 8.

Για παράδειγμα για το ζεύγος (29,31) έχουμε 29×31 = 899 με ψηφιακό άθροισμα
(8+9+9 = 26 → 2+6 = ) 8.

π ≈ 256/81

Μία προσέγγιση του $$\pi$$, που χρησιμοποιούσαν συστηματικά οι αρχαίοι Αιγύπτιοι είναι η

$$ \pi = \frac{256}{81}$$

Είναι ενδιαφέρον πώς οι αρχαίοι Αιγύπτιοι κατέληξαν σε αυτήν την προσέγγιση.
Στο Σχ. (α) φαίνεται ένας κύκλος με διάμετρο 9 εγεγραμμένος σε τετράγωνο πλευράς 9. Στο Σχ. (β) φαίνεται ένα (όχι κανονικό) οκτάπλευρο που έχει εμβαδό περίπου ίσο με αυτό του κύκλου.

Σχήμα

Εφόσον το τετράγωνο έχει εμβαδό 9² = 81, το εμβαδό του 8πλεύρου είναι (Σχ. (γ))

$$ 81-4\times\frac12\times3\times3 = \frac63$$

Για ευκολία (και αφού ούτως ή άλλως μιλάμε πάντα προσεγγιστικά) ας πούμε ότι το εμβαδό του 8πλεύρου είναι ίσο με 64, δηλαδή είναι ίσο με το εμβαδό ενός τετραγώνου πλευράς 8 (Σχ. (δ))

Καταλήξαμε δηλαδή στο ότι

εμβαδό του κύκλου ≈ εμβαδό οκταπλεύρου ⇔

$$\pi\left(\frac92\right)^2\approx 64$$ ή $$\pi\approx\frac{256}{81}$$

Η τιμή αυτή είναι περίπου ίση με 3,1605 και είναι κατά περίπου 0,6% μεγαλύτερη από την κανονική.

Πηγή: Mathematics in the time of the Pharaohs του R.J. Gillings.

Κορώνα ή γράμματα

Κάθεσαι σε ένα σκοτεινό δωμάτιο και μπροστά σου βρίσκεται ένα τραπέζι με 12 κέρματα από τα οποία τα 7 δείχνουν κορώνα και τα 5 γράμματα.

Πώς μπορείς να ταξινομήσεις τα 12 κέρματα σε 2 στήλες, ώστε η κάθε μία να έχει τον ίδιο αριθμό από κέρματα "κορώνα";

Μπορείς να γυρίσεις ένα ή περισσότερα κέρματα αλλά δεν μπορείς να καταλάβεις αν κάποιο είναι κορώνα ή γράμματα κοιτάζοντάς το (σκοτεινό δωμάτιο λέμε) ή ψηλαφίζοντάς το ή με κάποιον άλλο τρόπο.

Πηγή: Math wonders to inspire teachers and students του A.S. Posamentier.