Οι Χειραψίες

Σε ένα συνέδριο συμμετείχαν «n» άνθρωποι, άλλοι χαιρετιούνται με χειραψία κι΄ άλλοι όχι. Υπάρχουν, τουλάχιστον, δύο άνθρωποι που έχουν κάνει τον ίδιο αριθμό χειραψιών; (Κατ.32/Νο.40)

Λύση

Λύση του Ε. Αλεξίου. Κλασικό θέμα "περιστερώνα" Ντιριχλέ. Έστω κ σύνεδροι από τους n, κ<=n, αντάλλαξαν χειραψία, οι Σ1, Σ2, Σ3, ...,Σκ. Στην καλύτερη περίπτωση αντάλλαξαν 1,2,2,...,κ-1 χειραψίες, έτσι αν αντιστοιχίσουμε αν αντιστοιχίσουμε τους κ συνέδρους στις (κ-1) χειραψίες, οι (κ-1)σύνεδροι αντιστοιχίζονται στις (κ-1) χειραψίες ένα προς ένα και ο κ-ιοστός θα συμπέσει με έναν από τους (κ-1) σε κάποιο αριθμό χειραψιών από τις (κ-1). Γίνεται πιο κατανοητό αν αντί για χεραψίες-γνωριμίες των συνέδρων το δούμε με αντίστοιχο, ισοδύναμο παράδειγμα. Έχουμε 10 αντικείμενα (αντίστοιχο των κ σ.) και θέλουμε να τα τοποθετήσουμε σε 9 θέσεις, αναγκαστικά το 10ο αντικείμενο θα πάει σε μία από τις 9 που ήδη έχουν από ένα αντικείμενο, άρα σε μία θέση 2 αντικείμενα, πόσο μάλλον αν οι θέσεις είναι 8,7.., τότε 2, 3,.. αντικείμενα θα συμπέσουν. Άρα τελικά τουλάχιστον 2 άνθρωποι θα έχουν κάνει τον ίδιο αριθμό χειραψιών. Λύση του Γ. Ριζόπουλου. Κλασικος περιστερωνας. Οι δυνατες χειραψιες( φωλιες) ειναι n, απο 0 (για οποιον δεν χαιρετα κανεναν) εως n-1 για οποιον χαιρετιεται με ολους. Αλλα η συνυπαρξη 0 και ν-1 ειναι ατοπη. Δεν μπορει να υπαρχει καποιος που εχει χαιρετησει ολους τους αλλους και ταυτοχρονα καποιος που δεν χαιρετησε κανεναν. Υγ. Συγγνωμη για το ατονικο. Ταμπλετας ενεκα. Αρα οι δυνατες χειραψιες ειναι ν-1. Οι ανθρωποι ειναι ν. Αρα σε καποια φωλια(αριθ.χειραψιων) κουρνιαζουν 2 περιστερια(ανθρωποι).