Το Παράδοξο του Πάρτι: 6 Άτομα → 3 Γνωστοί ή 3 Άγνωστοι

Τρίγωνα Γνωριμιών σε Πάρτι 6 Ατόμων (Ramsey R(3,3)=6)

Σε μια παρέα 6 ατόμων (π.χ. σε ένα πάρτι), ισχύει ότι τουλάχιστον ένα από τα παρακάτω είναι αληθές:

1. Υπάρχει τριάδα ατόμων που όλοι έχουν γνωριστεί μεταξύ τους.
2. Υπάρχει τριάδα ατόμων που κανείς δεν έχει γνωριστεί με τους άλλους δύο.

Δηλαδή, υπάρχει είτε μια τριάδα αμοιβαίων γνωστών, είτε μια τριάδα αμοιβαίων αγνώστων.

Δες μια σύντομη απόδειξη

Βήμα 1 (Αρχή του Περιστερώνα): Διάλεξε ένα άτομο Α. Από τα 5 υπόλοιπα, τουλάχιστον 3 είναι είτε γνωστοί του Α είτε άγνωστοι του Α.

Βήμα 2 (Περίπτωση 3 γνωστοί του Α): Έστω οι Β, Γ, Δ είναι γνωστοί του Α. Αν κάποια δύο από αυτούς έχουν γνωριστεί μεταξύ τους, π.χ. Β–Γ, τότε Α–Β–Γ σχηματίζουν τριάδα αμοιβαίων γνωστών. Αν κανένα ζεύγος τους δεν έχει γνωριστεί, τότε Β, Γ, Δ είναι τριάδα αμοιβαίων αγνώστων.

Βήμα 3 (Περίπτωση 3 άγνωστοι του Α): Η ίδια λογική όπως πάνω δίνει πάλι μία από τις δύο τριάδες.

Άρα σε κάθε διάταξη γνωριμιών μεταξύ 6 ατόμων υπάρχει τριάδα αμοιβαίων γνωστών ή τριάδα αμοιβαίων αγνώστων.