Waiting for Godot to join the zoom meeting

Για να τα θυμόμαστε, μετά από χρόνια, το στριπάκι του Tom Gauld στο Guardian Review της 30/1/2021

Waiting for Godot to join the zoom meeting, cartoon by Tom Gauld

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

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.