Οκτώ φοιτητές προσπαθούσαν να λύσουν οκτώ πρoβλήματα. Βεβαιώθηκε άτι κάθε πρόβλημα λύθηκε από ακριβώς πέντε φοιτητές.
Αποδείξτε άτι υπάρχουν δύο φοιτητές που έλυσαν (ο ένας ή ο άλλος) και τα οκτώ προβλήματα. Τι ισχύει στην περίπτωση που κάθε πρόβλημα λύθηκε από τέσσερις ακριβώς φοιτητές;
(Ν. Vasilyev και S. Τokarev)
Αν υπάρχει λύτης που έλυσε και τα 8 προβλήματα, τότε το αποδεικτέο ισχύει χωρίς άλλο.
ΑπάντησηΔιαγραφήΑν ο λύτης Α που έλυσε τα περισσότερα προβλήματα έλυσε ακριβώς 7 από τα 8, τότε υπάρχουν άλλοι 5 λύτες που έλυσαν το πρόβλημα που δεν έλυσε ο Α, οπότε ο Α μαζί με οποιονδήποτε από αυτούς έλυσαν και τα 8.
Αν ο λύτης Α που έλυσε τα περισσότερα προβλήματα έλυσε ακριβώς 6 από τα 8, τότε καθένα από τα 2 προβλήματα που δεν έλυσε ο Α, δε λύθηκε από 2 ακόμα λύτες, άρα υπάρχουν 2*2=4 το πολύ λύτες πλην του Α που δεν έλυσαν κάποιο από τα 2 προβλήματα που δεν έλυσε ο Α. Υπάρχουν επομένως 8-4-1=3 τουλάχιστον λύτες που έλυσαν και τα 2, οπότε ο Α μαζί με οποιονδήποτε από αυτούς έλυσαν και τα 8.
Αν ο λύτης Α που έλυσε τα περισσότερα προβλήματα έλυσε ακριβώς 5 από τα 8, τότε καθένα από τα 3 προβλήματα που δεν έλυσε ο Α, δε λύθηκε από 2 ακόμα λύτες, άρα υπάρχουν 2*3=6 το πολύ λύτες πλην του Α που δεν έλυσαν κάποιο από τα 3 προβλήματα που δεν έλυσε ο Α. Υπάρχει επομένως 8-6-1=1 τουλάχιστον λύτης που έλυσε και τα 3, οπότε ο Α μαζί με αυτόν έλυσαν και τα 8.
Αν ο λύτης που έλυσε τα περισσότερα προβλήματα έλυσε λιγότερα από 5, τότε δεν θα μπορούσε κάθε πρόβλημα να έχει λυθεί από 5 λύτες, άτοπο.
Επομένως σε κάθε περίπτωση υπάρχει ζευγάρι λυτών που έλυσαν μαζί και τα 8 προβλήματα.
Στην περίπτωση που καθένα από τα 8 προβλήματα λύθηκε από 4 ακριβώς λύτες, δεν υπάρχει υποχρεωτικά ζευγάρι λυτών που να έλυσαν μαζί και τα 8. Παράδειγμα (οι λύτες συμβολίζονται με τα γράμματα από Α έως Θ και τα προβλήματα που έλυσαν με τους αριθμούς από 1 έως 8 σε παρένθεση):
A(1,2,3,4), B(2,4,5,7), Γ(3,4,5,6), Δ(4,5,6,7), Ε(1,2,6,8), Ζ(1,3,5,8), Η(1,6,7,8), Θ(2,3,7,8)