Τα 4 βράδια δεν αρκούν για να επισκεφθούν όλοι οι μαθητές τα σπίτια όλων των συμμαθητών τους. Η απόδειξη βασίζεται στη θεωρία συνόλων και το Θεώρημα του Sperner (ή την αρχή του περιστερώνα στις συγκρίσεις). Μαθηματική Μοντελοποίηση: Ας συμβολίσουμε τις επιλογές κάθε μαθητή για τα 4 βράδια με μια ακολουθία 4 ψηφίων από (0) και (1): • (0): Ο μαθητής μένει σπίτι του. • (1): Ο μαθητής βγαίνει έξω για επισκέψεις. Για παράδειγμα, η ακολουθία (1, 0, 1, 0) σημαίνει ότι ο μαθητής βγήκε έξω το 1ο και το 3ο βράδυ, και έμεινε σπίτι το 2ο και το 4ο βράδυ. Η Συνθήκη για την Επίσκεψη: Για να μπορέσει ο μαθητής (A\ να επισκεφθεί τον μαθητή (B), πρέπει να υπάρξει τουλάχιστον ένα βράδυ όπου: Ο (A) βγαίνει έξω (1) και ο (B) μένει σπίτι (0). Αν για όλα τα βράδια ισχύει ότι κάθε φορά που ο (A) έχει (1), έχει και ο (B) (1) (δηλαδή οι θέσεις των άσσων του (A) είναι υποσύνολο των άσσων του (B), τότε ο (A) δεν θα καταφέρει ποτέ να επισκεφθεί τον (B), διότι κάθε φορά που ο (A) βγαίνει, ο (B) θα λείπει επίσης από το σπίτι του. Συνεπώς, για να μπορούν όλοι οι μαθητές να επισκεφθούν ο ένας τον άλλον, οι ακολουθίες επιλογών τους πρέπει να είναι μη συγκρίσιμες μεταξύ τους (καμία να μην είναι «υποσύνολο» μιας άλλης). Εφαρμογή του Θεωρήματος Sperner: Το πλήθος των δυνατών συνδυασμών (ακολουθιών) για 4 βράδια είναι: 2^4 = 16 Σύμφωνα με το Θεώρημα του Sperner, ο μέγιστος αριθμός ακολουθιών μήκους (n) που μπορούν να επιλεγούν έτσι ώστε καμία να μην είναι υποσύνολο μιας άλλης (μέγιστη αντι-αλυσίδα), δίνεται από τον διωνυμικό συντελεστή: (n, [n/2]) Για (n = 4) βράδια, ο μέγιστος αριθμός μαθητών που μπορούν να έχουν πλήρως ανεξάρτητες και μη συγκρίσιμες ακολουθίες είναι: (n, [n/2])=(4,[4/2])=(4, 2)=4!/2!*(4-2)!=4!/2!*2!= =4*3*2*1/2*1*2*1= =4*3*2*1/4=3*2*1=6 Συμπέρασμα Οι 30 μαθητές της τάξης είναι πολύ περισσότεροι από το μέγιστο όριο των 6 μαθητών. Από την Αρχή του Περιστερώνα, αν προσπαθήσουμε να μοιράσουμε ακολουθίες στους 30 μαθητές, θα υπάρξουν οπωσδήποτε τουλάχιστον δύο μαθητές (A) και (B) των οποίων οι επιλογές θα είναι συγκρίσιμες (π.χ. ο (A) θα έχει άσσους μόνο εκεί που έχει και ο (B). Σε αυτή την περίπτωση, ο μαθητής (A) δεν θα μπορέσει ποτέ να επισκεφθεί τον μαθητή (B). Επομένως, τα 4 βράδια δεν είναι αρκετά.
Τα 4 βράδια δεν αρκούν για να επισκεφθούν όλοι οι μαθητές τα σπίτια όλων των συμμαθητών τους. Η απόδειξη βασίζεται στη θεωρία συνόλων και το Θεώρημα του Sperner (ή την αρχή του περιστερώνα στις συγκρίσεις).
ΑπάντησηΔιαγραφήΜαθηματική Μοντελοποίηση:
Ας συμβολίσουμε τις επιλογές κάθε μαθητή για τα 4 βράδια με μια ακολουθία 4 ψηφίων από (0) και (1):
• (0): Ο μαθητής μένει σπίτι του.
• (1): Ο μαθητής βγαίνει έξω για επισκέψεις.
Για παράδειγμα, η ακολουθία (1, 0, 1, 0) σημαίνει ότι ο μαθητής βγήκε
έξω το 1ο και το 3ο βράδυ, και έμεινε σπίτι το 2ο και το 4ο βράδυ.
Η Συνθήκη για την Επίσκεψη:
Για να μπορέσει ο μαθητής (A\ να επισκεφθεί τον μαθητή (B), πρέπει να υπάρξει τουλάχιστον ένα βράδυ όπου:
Ο (A) βγαίνει έξω (1) και ο (B) μένει σπίτι (0).
Αν για όλα τα βράδια ισχύει ότι κάθε φορά που ο (A) έχει (1), έχει και
ο (B) (1) (δηλαδή οι θέσεις των άσσων του (A) είναι υποσύνολο των άσσων
του (B), τότε ο (A) δεν θα καταφέρει ποτέ να επισκεφθεί τον (B), διότι κάθε φορά που ο (A) βγαίνει, ο (B) θα λείπει επίσης από το σπίτι του.
Συνεπώς, για να μπορούν όλοι οι μαθητές να επισκεφθούν ο ένας τον άλλον, οι ακολουθίες επιλογών τους πρέπει να είναι μη συγκρίσιμες μεταξύ τους (καμία να μην είναι «υποσύνολο» μιας άλλης).
Εφαρμογή του Θεωρήματος Sperner:
Το πλήθος των δυνατών συνδυασμών (ακολουθιών) για 4 βράδια είναι:
2^4 = 16
Σύμφωνα με το Θεώρημα του Sperner, ο μέγιστος αριθμός ακολουθιών μήκους (n) που μπορούν να επιλεγούν έτσι ώστε καμία να μην είναι υποσύνολο μιας άλλης (μέγιστη αντι-αλυσίδα), δίνεται από τον διωνυμικό συντελεστή:
(n, [n/2])
Για (n = 4) βράδια, ο μέγιστος αριθμός μαθητών που μπορούν να έχουν πλήρως ανεξάρτητες και μη συγκρίσιμες ακολουθίες είναι:
(n, [n/2])=(4,[4/2])=(4, 2)=4!/2!*(4-2)!=4!/2!*2!= =4*3*2*1/2*1*2*1= =4*3*2*1/4=3*2*1=6
Συμπέρασμα
Οι 30 μαθητές της τάξης είναι πολύ περισσότεροι από το μέγιστο όριο των 6 μαθητών. Από την Αρχή του Περιστερώνα, αν προσπαθήσουμε να μοιράσουμε ακολουθίες στους 30 μαθητές, θα υπάρξουν οπωσδήποτε τουλάχιστον δύο μαθητές (A) και (B) των οποίων οι επιλογές θα είναι συγκρίσιμες (π.χ. ο (A) θα έχει άσσους μόνο εκεί που έχει και ο (B). Σε αυτή την περίπτωση, ο μαθητής (A) δεν θα μπορέσει ποτέ να επισκεφθεί τον μαθητή (B). Επομένως, τα 4 βράδια δεν είναι αρκετά.