Πόσοι γνωρίζονται

[ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ]

Έχουμε άτομα .
Σε κάθε τετράδα από αυτούς τουλάχιστον ένας γνωρίζει τους άλλους 3.
Ποιος είναι ο ελάχιστος αριθμός ατόμων που γνωρίζουν όλους τους υπόλοιπους ;
(Αν ο Α γνωρίζει τον Β τότε και ο Β γνωρίζει τον Α)

[Mihalis_Lambrou]

Έχουμε άτομα .
Σε κάθε τετράδα από αυτούς τουλάχιστον ένας γνωρίζει τους άλλους 3.
Ποιος είναι ο ελάχιστος αριθμός ατόμων που γνωρίζουν όλους τους υπόλοιπους ;
(Αν ο Α γνωρίζει τον Β τότε και ο Β γνωρίζει τον Α)

.
Άλλη μία πάρα πολλή ωραία άσκηση του Σταύρου.

Απάντηση: Ο ελάχιστος αριθμός ατόμων που ξέρουν όλους τους άλλους είναι .

Πρώτα απ' όλα παρατηρούμε ότι αυτό είναι εφικτό: Παίρνουμε άτομα που ξέρουν όλους και τρία ακόμα που δεν ξέρουν ο ένας το άλλο.

Για την απόδειξη εργαζόμαστε με επαγωγή στο για . Η αρχική περίπτωση είναι η υπόθεσή μας. Έστω τώρα, για το επαγωγικό βήμα, ότι ισχύει το αποτέλεσμα για κάποιο . Θα το αποδείξουμε για τον , ως εξής:

Διώχνουμε έναν από την παρέα, τον Αρχιμήδη. Για τους υπόλοιπους ισχύει η επαγωγική υπόθεση, δηλαδή υπάρχουν άτομα που ξέρουν όλους τους υπόλοιπους (το αν ξέρουν και τον Αρχιμήδη, δεν μας αφορά για την ώρα). Διακρίνουμε περιπτώσεις.

α) Τυχαίνει και τα άτομα της ομάδας να ξέρουν όλους τους άλλους (*). Παίρνουμε οποιουδήποτε τρεις από αυτούς, και τον Αρχιμήδη. Από την υπόθεση κάποιος από τους ξέρει και τους υπόλοιπους. Είτε είναι ο Αρχιμήδης αυτός είτε κάποιος από τους υπόλοιπους τρεις συμπεραίνουμε ότι υπάρχει κάποιος, ας τον πούμε Ευκλείδη, που ξέρει τον Αρχιμήδη.

Διώχνουμε τώρα τον Ευκλείδη από την παρέα και ξαναβάζουμε τον Αρχιμήδη. Από την επαγωγική υπόθεση υπάρχουν άτομα που ξέρουν όλους τους υπόλοιπους. Αλλά και ο Ευκλείδης τους ξέρει όλους λόγω της υπόθεσης (*) και γιατί, επιπλέον, ξέρει τον Αρχιμήδη. Τελικά, σε αυτή την περίπτωση, βρήκαμε άτομα (στα ) που ξέρουν όλους τους υπόλοιπους, όπως θέλαμε.

β) Έστω τώρα ότι υπάρχουν άτομα της ομάδας των (χωρίς τον Αρχιμήδη, που τον διώξαμε) που δεν ξέρουν κάποιον από τους υπόλοιπους. Παρατηρούμε ότι στην ομάδα αυτή των δεν μπορεί να υπάρχει μόνο ένας που δεν ξέρει κάποιον, διότι οι γνωριμίες είναι αμοιβαίες. Οπότε, σε αυτήν την περίπτωση, σίγουρα υπάρχουν δύο άτομα (ας μην τους δώσω όνομα) που δεν ξέρουν όλους τους υπόλοιπους. Από την επαγωγική υπόθεση υπάρχουν άτομα που ξέρουν όλους τους υπόλοιπους. Παίρνουμε έναν από αυτούς. Τον Σωκράτη. Εξετάζουμε την τετράδα που αποτελείται από τους δύο που δεν τους έδωσα όνομα, συν τον Αρχιμήδη, συν τον Σωκράτη. Από την υπόθεση κάποιος από τους τέσσερις ξέρει τους υπόλοιπους τρεις. Σίγουρα αυτός δεν είναι κάποιος από τους δύο χωρίς όνομα (αφού δεν ξέρει τον άλλον), άρα είναι κάποιος από τους Αρχιμήδη ή Σωκράτη. Ειδικά, ο Αρχιμήδης και ο Σωκράτης αλληλογνωρίζονται. Διώχνουμε τώρα τον Σωκράτη από την παρέα των και ξαναβάζουμε τον Αρχιμήδη. Από την επαγωγική υπόθεση υπάρχουν άτομα (από την παρέα των ) που ξέρουν όλους τους υπόλοιπους. Αλλά και ο Σωκράτης τους ξέρει όλους (τους ) γιατί έτσι τον επιλέξαμε. Eπιπλέον o Σωκράτης, ξέρει τον Αρχιμήδη. Τελικά, σε αυτή την περίπτωση, βρήκαμε άτομα (στα ) που ξέρουν όλους τους υπόλοιπους, όπως θέλαμε.

Έχω και άλλη απόδειξη του παραπάνω, τελείως διαφορετική, όχι με επαγωγή, αλλά είναι μακροσκελής. Ελπίζω να βρω τον χρόνο να την γράψω, αν και το βλέπω δύσκολο γιατί την επόμενη εβδομάδα θα βρίσκομαι εκτός έδρας για ομιλίες σε παιδιά στο Καστελλόριζο, και για το Φεστιβάλ Γρίφων.