Κάθε μέλος του κοινοβουλίου της Ιλαρίας χαστούκισε τρία ακριβώς μέλη τον σεβαστού αυτού σώματος. Χρειάζεται να σχηματιστούν διάφορες κοινοβουλευτικές επιτροπές, πού πρέπει να οργανωθούν έτσι ώστε κάθε μέλος του κοινοβουλίου να συμμετέχει σε μία και μόνο επιτροπή.
Για να αποφευχθούν οι συγκρούσεις στις επιτροπές, είναι αναγκαίο να τις απαρτίσουν βουλευτές πού δεν έχουν χαστουκίσει ποτέ ο ένας τον άλλο.
Αποδείξτε ότι, αν το πλήθος των επιτροπών είναι τουλάχιστον $7$, μπορούμε πάντα να ικανοποιήσουμε αυτή τη συνθήκη, αν όμως είναι μικρότερο, ο στόχος μας αποδεικνύεται μερικές φορές αδύνατος.
Πηγή: Quantum (Α. Βelov)
Υποθέτω ότι τα μέλη του Κοινοβουλίου, έστω ν στο πλήθος, δεν είναι λιγότερα από 7, αφού αλλιώς θα αρκούσε να τοποθετηθεί ο καθένας και σε μια μονομελή επιτροπή και η συνθήκη θα ήταν δυνατό να ικανοποιηθεί και με λιγότερες από 7 επιτροπές.
ΑπάντησηΔιαγραφήΓια ν=7, οι 7 επιτροπές είναι προφανώς αρκετές, αφού κάθε βουλευτής μπορεί να τοποθετηθεί και σε μια διαφορετική μονομελή επιτροπή.
Υποθέτουμε ότι οι 7 επιτροπές είναι αρκετές και για ν βουλευτές ώστε να μπορεί να ικανοποιηθεί η συνθήκη.
Θα δείξουμε ότι η συνθήκη μπορεί να ικανοποιηθεί και για ν+1 βουλευτές και 7 επιτροπές.
Αν οι βουλευτές είναι ν+1, τα χαστούκια που έχουν δοθεί συνολικά θα είναι 3(ν+1)=3ν+3 και θα υπάρχει ένας τουλάχιστον βουλευτής, έστω ο Ω, που έχει δεχτεί το πολύ 3 χαστούκια, αφού αν όλοι είχαν δεχτεί περισσότερα από 3 θα έπρεπε συνολικά να έχουν δοθεί περισσότερα από 3ν+3 χαστούκια, αντίφαση. Εξαιρούμε προσωρινά τον Ω από τις επιτροπές και τοποθετούμε κατάλληλα τους υπόλοιπους ν στις 7 επιτροπές, ώστε να ικανοποιείται η συνθήκη (εφικτό βάσει της επαγωγικής υπόθεσης). Τώρα πλέον ο Ω δεν μπορεί να είναι στην ίδια επιτροπή με 6 το πολύ από τους υπόλοιπους (3 ακριβώς που χαστούκισε και 3 το πολύ που τον χαστούκισαν). Επομένως, από τις 7 επιτροπές, οι 6 το πολύ είναι ακατάλληλες για να τοποθετηθεί ο Ω και συνεπώς υπάρχει μία τουλάχιστον επιτροπή κατάλληλη για τον Ω.
Συνεπώς η συνθήκη μπορεί να ικανοποιηθεί και για ν+1 βουλευτές, γεγονός που ολοκληρώνει την επαγωγική απόδειξη.
Αν οι επιτροπές ήταν 6 ή λιγότερες, τότε ένα παράδειγμα με 7 βουλευτές που είναι αδύνατο να ‘χωρέσουν’ σε αυτές είναι το εξής. Αριθμούμε τους 7 βουλευτές από 1 έως 7 και τους τοποθετούμε σε κύκλο σε αύξουσα ωρολογιακά σειρά. Αν υποθέσουμε ότι κάθε βουλευτής χαστούκισε τους 3 που βρίσκονται ωρολογιακά αμέσως μετά από τον ίδιο, τότε ο 1 χαστούκισε τους 2, 3 και 4 και χαστουκίστηκε από τους 5, 6 και 7 και το αντίστοιχο ισχύει για κάθε βουλευτή, κατά συνέπεια οποιοδήποτε ζευγάρι βουλευτών δεν χωράνε στην ίδια επιτροπή, αφού ο ένας από τους δύο έχει χαστουκίσει τον άλλο. Αν όμως οι επιτροπές είναι 6 ή λιγότερες και οι βουλευτές 7, τότε αναγκαστικά στην ίδια επιτροπή θα πρέπει να είναι ένα τουλάχιστον ζευγάρι βουλευτών, αντίφαση. Επομένως, οι 6 ή λιγότερες επιτροπές δεν μπορούν με βεβαιότητα να ικανοποιήσουν τη συνθήκη.