Όλα τα παιδιά στην αίθουσα!

https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/SARS-CoV-2_without_background.png/220px-SARS-CoV-2_without_background.pngΘεώρημα
Μια σχολική τάξη με ν μαθητές είναι ασφαλής, οι μαθητές δεν κολλάνε ο ένας τον άλλον, για κάθε ν > 0.

Απόδειξη
Για ν = 1 είναι προφανές ότι ένας μαθητής δεν κολλάει τον εαυτό του, άρα η τάξη είναι ασφαλής.

Έστω ότι οποιαδήποτε τάξη με κ μαθητές είναι ασφαλής, και κανένας μαθητής δεν κολλάει άλλους. Θα αποδείξουμε ότι οποιαδήποτε τάξη με κ+1 μαθητές είναι επίσης ασφαλής.

Από την τάξη με τους κ+1 μαθητές αφαιρούμε έναν μαθητή, έστω τον μικρό Γκίκα. Είναι προφανές, βάσει της υπόθεσης, ότι οι κ μαθητές που απομένουν δεν κολλούν μεταξύ τους, σχηματίζοντας ασφαλή τάξη με κ μαθητές. Συνεπώς αν η τάξη των κ+1 μαθητών δεν είναι ασφαλής, πηγή μετάδοσης δεν μπορεί παρά να είναι ο Γκίκας. Ας επιστρέψουμε τον μικρό Γκίκα στην τάξη, και αντί για αυτόν, ας αφαιρέσουμε τώρα την Ελενίτσα. Είναι και πάλι προφανές, βάσει της υπόθεσης, ότι οι κ μαθητές που απομένουν δεν κολλούν μεταξύ τους, σχηματίζοντας ασφαλή τάξη με κ μαθητές. Όμως μέσα σε αυτήν την τάξη είναι και ο Γκίκας, άρα αποκλείεται να αποτελεί αυτός πηγή μετάδοσης. Η Ελενίτσα δε, που θα έπρεπε να είναι τώρα αυτή η πηγή, στην περίπτωση που η τάξη των κ+1 μαθητών δεν είναι ασφαλής, ξέρουμε ότι προέρχεται από μια ασφαλή τάξη των κ μαθητών, άρα ούτε αυτή αποτελεί πηγή μετάδοσης.

Καθώς ο Γκίκας και η Ελενίτσα αποτελούν μαθητές της τάξης που επιλέχθηκαν τυχαία, συμπεραίνουμε ότι και οποιαδήποτε τάξη με κ+1 μαθητές είναι ασφαλής, ο.ε.δ.

Λήμμα 1: Ούτε σε γάμους και πανηγύρια κολλάει
Λήμμα 2: Ούτε το κουταλάκι κολλάει
Λήμμα 3: Μια επιτροπή ν σοφών απαρτίζεται από λακέδες, για κάθε ν > 0.

Βιβλιογραφία
Wikipedia (2020). Mathematical induction. Πρόσβαση στο https://en.wikipedia.org/wiki/Mathematical_induction στις 30/8/2020, 13:00.
Łukowski, Piotr (2011). All horses are the same color. Paradoxes. Springer. pp. 15.

Σημ: Η έρευνα υποστηρίχθηκε από τα εκλεκτορικά σώματα κορυφαίου πανεπιστημίου.
Για τις δικές σας χορηγίες, ζητήστε μας το IBAN.

 

Τι είπες;

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Google

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s

Ο ιστότοπος χρησιμοποιεί το Akismet για την εξάλειψη των ανεπιθύμητων σχολίων. Μάθετε πως επεξεργάζονται τα δεδομένα των σχολίων σας.