30 Απρ 2011

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

Η Αρχή του Περιστερώνα (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 θετικοί αριθμοί x1, x2, …, xn. Τότε σίγουρα η διαφορά δύο από αυτούς διαιρείται από το n-1.

Αν συμβολίσουμε με ri το υπόλοιπο της διαίρεσης του xi με τον n-1, τότε οι ri μπορούν να πάρουν τις τιμές 0, 1, 2, ..., n-2. Δηλαδή υπάρχουν n-1 δυνατές τιμές για τους ri αλλά υπάρχουν συνολικά n αριθμοί ri . Από την Αρχή του Περιστερώνα, δύο από αυτούς, έστω οι ri και rj, είναι ίσοι. Δηλαδή οι xi και xj είναι ισοϋπόλοιποι (ως προς τη διαίρεση με τον 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$ είναι ακέραιος.)

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

Πρόβλημα
Ας είναι = {1,2,...,100}. Τότε με οποιονδήποτε τρόπο κι αν επιλέξουμε 55 από τα στοιχεία του S, θα υπάρχουν
  • δύο αριθμοί που διαφέρουν κατά 9,
  • δύο αριθμοί που διαφέρουν κατά 10,
  • δύο αριθμοί που διαφέρουν κατά 12,
  • δύο ζεύγη αριθμών που διαφέρουν κατά 13.
Το περίεργο είναι ότι δεν υπάρχουν απαραίτητα δύο αριθμοί που διαφέρουν κατά 11!

9 σχόλια:

  1. csar,

    Μήπως υπάρχει κάποιο λαθάκι στην εκφώνηση?
    Υπάρχουν τουλάχιστον 3 ζεύγη αριθμών που διαφέρουν κατά 13.

    Επίσης για μένα το ποιο εντυπωσιακό είναι ότι αν επιλέξεις 56 αριθμούς δεν υπάρχουν απαραίτητα δύο αριθμοί που να διαφέρουν κατά 14!

    JR

    ΑπάντησηΔιαγραφή
  2. Όλα τα "θα υπάρχουν δύο" είναι "θα υπάρχουν τουλάχιστον δύο".

    ΑπάντησηΔιαγραφή
  3. Αναφέρομαι στην περίπτωση 13. Μήπως είναι τουλάχιστον 3 και όχι δύο τα ζεύγη?

    ΑπάντησηΔιαγραφή
  4. Φαντάζομαι ότι αυτό εξαρτάται από τη λύση σου.

    ΑπάντησηΔιαγραφή
  5. Η απόδειξη που θα επιχειρήσω είναι κάπως "κατασκευαστική".
    Έστω ότι θέλουμε να επιλέξουμε αριθμoύς από το σύνολο $S=\{1,2,...,100\}$, έτσι ώστε η απόσταση οποιουδήποτε ζεύγους επιλεχθέντων αριθμών να μην είναι ίση με $k$. Κατά την επιλογή ενός αριθμού $x$ δεσμεύεται μία θέση, η $x$, από το σύνολο $S$ ως επιλεχθείσα, καθώς και δύο άλλες θέσεις οι $x+k$ και $x-k$ ως απαγορευμένες θέσεις επιλογής κατά τη διαδικασία μελλοντικών επιλογών. Θα προσπαθήσουμε να επιλέξουμε το μέγιστο πλήθος αριθμών που να ικανοποιούν το κριτήριο που αναφέραμε. Αν ξεκινήσουμε να επιλέγουμε από τον αριθμό 1 και συνεχίσουμε τις επιλογές των αριθμών με διαδοχική αύξηση κατά ένα, τότε μετά από $k$ επιλογές αριθμών θα έχουμε δεσμεύσει από το $S$, $k$ διαδοχικές επιλεχθείσες θέσεις τις {1,2,...,k} καθώς και $k$ απαγορευμένες θέσεις τις {k+1,k+2,...,2k}. Αυτή η διαδικασία των $k$ επιλογών είναι ο πρώτος γύρος επιλογών. Στο δεύτερο γύρο επιλογών θα δεσμευτούν ως επιλεχθείσες θέσεις οι {2k+1,2k+2,...,3k} και ως απαγορευμένες θέσεις οι {3k+1,3k+2,...,4k}.
    Δεδομένου ότι σε κάθε γύρο επιλογών δεσμεύονται $2k$ θέσεις, τότε το συνολικό πλήθος πλήρων γύρων που χωρούν στο διάστημα {1,2,...100} θα είναι $q=\lfloor \frac{100}{2k} \rfloor$ και το πλήθος των επιλεγέντων αριθμών που ικανοποιούν το κριτήριο θα είναι $p_1=q*k$. Μετά το πέρας των $q$ πλήρων γύρων επιλογών θα περισσέψουν $w=100-q*2k$ θέσεις του $S$ με τις οποίες δεν έχουμε ασχοληθεί ακόμη. Αν $w>k$, τότε μπορούμε να επιλέξουμε ακόμη $p_2=k$ αριθμούς που ικανοποιούν το κριτήριο. Αν $w\leq k$, τότε μπορούμε να επιλέξουμε ακόμη $p_2=w$ αριθμούς που ικανοποιούν το κριτήριο.
    Συνεπώς το μέγιστο πλήθος επιλεχθέντων αριθμών που ικανοποιούν το κριτήριο "κανένα ζεύγος τους να μην έχει απόσταση $k$" θα είναι $P=p_1+p_2$.
    1. Για $k=9$ έχουμε $q=\lfloor \frac{100}{18} \rfloor=5$, $p_1=45$, $w=10$, $p_2=9$, άρα $P=54$. Συνεπώς η επιλογή ενός ακόμη αριθμού από το $S$ ώστε να επιλεγούν συνολικά 55 οδηγεί αμέσως στην μη ικανοποίηση του κριτηρίου. "Στους 55, Τουλάχιστον ένα ζεύγος έχει απόσταση 9"
    2. Για $k=10$ έχουμε $q=\lfloor \frac{100}{20} \rfloor=5$, $p_1=50$, $w=0$, $p_2=0$, άρα $P=50$. Συνεπώς η επιλογή 5 ακόμη αριθμών από το $S$ ώστε να επιλεγούν συνολικά 55 οδηγεί αμέσως στην μη ικανοποίηση του κριτηρίου. "Στους 55, Τουλάχιστον πέντε ζεύγη έχουν απόσταση 10".
    3. Για $k=11$ έχουμε $q=\lfloor \frac{100}{22} \rfloor=4$, $p_1=44$, $w=12$, $p_2=11$, άρα $P=55$. "Στους 55, είναι δυνατό κανένα ζεύγος να μην έχει απόσταση 11".
    4. Για $k=12$ έχουμε $q=\lfloor \frac{100}{24} \rfloor=4$, $p_1=48$, $w=4$, $p_2=4$, άρα $P=52$. Συνεπώς η επιλογή 3 ακόμη αριθμών από το $S$ ώστε να επιλεγούν συνολικά 55 οδηγεί αμέσως στην μη ικανοποίηση του κριτηρίου. "Στους 55, Τουλάχιστον έξι! (προσοχή) ζεύγη έχουν απόσταση 12".
    5. Για $k=13$ έχουμε $q=\lfloor \frac{100}{26} \rfloor=3$, $p_1=39$, $w=22$, $p_2=13$, άρα $P=52$. Συνεπώς η επιλογή 3 ακόμη αριθμών από το $S$ ώστε να επιλεγούν συνολικά 55 οδηγεί αμέσως στην μη ικανοποίηση του κριτηρίου. "Στους 55, Τουλάχιστον τρία ζεύγη έχουν απόσταση 13".
    6. Για $k=14$ έχουμε $q=\lfloor \frac{100}{28} \rfloor=3$, $p_1=42$, $w=16$, $p_2=14$, άρα $P=56$. "Ακόμη και αν επιλέξουμε 56 αριθμούς, είναι δυνατό κανένα ζεύγος να μην έχει απόσταση 14".


    JR

    ΑπάντησηΔιαγραφή
  6. Με προβληματίζει το γεγονός ότι έχεις διαλέξει ένα συγκεκριμένο τρόπο με τον οποίο επιλέγεις τους αριθμούς.

    Για παράδειγμα για την περίπτωση k=12, μπορούμε να επιλέξουμε τους αριθμούς ως εξής:
    1-14, 27-38, 51-62, 75-86, 96-100
    Σε αυτήν την περίπτωση υπάρχουν 5 ζεύγη (κι όχι 6) που απέχουν μεταξύ τους κατά 12.

    Εμείς ζητάμε να ισχύουν τα ζητούμενα για "οποιονδήποτε" τρόπο επιλογής των αριθμών

    Παρόμοια και στις άλλες περιπτώσεις, ίσως με κάποιον πιο "έξυπνο" τρόπο επιλογής των αριθμών να μην ισχύουν τα νούμερα που βγάζεις.

    ΑπάντησηΔιαγραφή
  7. " τότε οι ri μπορούν να πάρουν τις τιμές 0, 1, 2, ..., n-1. Δηλαδή υπάρχουν n-1 δυνατές τιμές για τους ri "
    Το πλήθος των ri , δεν θα έπρεπε να είναι n ;

    ΑπάντησηΔιαγραφή
  8. Σωστά, έπρεπε να είναι "οι r_i μπορούν να πάρουν τις τιμές 0, 1, 2, ... n-2", αφού πρόκειται για διαίρεση με τον n-1,

    ΑπάντησηΔιαγραφή