Σε στρογγυλό τραπέζι

#1

Σε ένα σύλλογο $n\geq 5$ μελών, κάθε δύο μέλη που δε γνωρίζονται μεταξύ τους, έχουν ακριβώς ένα κοινό γνωστό, και κανένα μέλος δε γνωρίζει όλα τα υπόλοιπα.
Αποδείξτε ότι υπάρχουν

μέλη τα οποία μπορούν να καθίσουν σε ένα στρογγυλό τραπέζι έτσι ώστε καθένα από αυτά να κάθεται ανάμεσα σε δύο μέλη
(α) που γνωρίζει.
(β) που δε γνωρίζει.

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #2

socrates έγραψε: ↑
Κυρ Ιουν 18, 2017 3:55 pm
Σε ένα σύλλογο $n\geq 5$ μελών, κάθε δύο μέλη που δε γνωρίζονται μεταξύ τους, έχουν ακριβώς ένα κοινό γνωστό, και κανένα μέλος δε γνωρίζει όλα τα υπόλοιπα.
Αποδείξτε ότι υπάρχουν μέλη τα οποία μπορούν να καθίσουν σε ένα στρογγυλό τραπέζι έτσι ώστε καθένα από αυτά να κάθεται ανάμεσα σε δύο μέλη
(α) που γνωρίζει.
(β) που δε γνωρίζει.

Γεια σας!

Έστω a_1...a_n

τα μέλη .

Έστω ότι για τον a_1

$\left\{\begin{matrix} & a_2,a_3..a_k \,\,\acute{\alpha }\gamma \nu \omega \sigma \tau o\iota & \\ & a_{k+1},a_{k+2},...a_n \,\,\gamma \nu \omega \sigma \tau o\acute{\iota} & \end{matrix}\right.$

Αν k=n-1

τότε όλοι οι άγνωστοι του a_1

γνωρίζουν τον $a_{n}$ άτοπο!
Άρα βλέπουμε ότι $3\leq k\leq n-2$
Έστω a_i

με

ένα μέλος,τότε αναγκαστικά από την εκφώνηση υπάρχει a_j

με

ώστε οι

να γνωρίζονται και για κάθε a_l

με $l> k,l\neq j$ οι a_i,a_l

δεν γνωρίζονται.
Οπότε τοποθετούμε τα μέλη ως a_l,a_1,a_j,a_i

και επειδή οι a_i,a_l

δεν γνωρίζονται θα έχουν κοινό γνωστό έστω a_m

και προκύπτει η σειρά a_l,a_1,a_j,a_i,a_m

Για το β)

Έστω a_i

ένας άγνωστος του a_1

και

ένας γνωστός του ο οποίος δεν γνωρίζει τον a_i

και

ο κοινός γνωστός των a_1,a_i

.
Επειδή κάθε άγνωστος του a_1

έχει ακριβώς έναν κοινό γνωστό μαζί του έπεται ότι ή για κάθε a_h,h<k+1

υπάρχει

ώστε να μην γνωρίζονται ή ότι για κάθε a_s,s>k

υπάρχει

ώστε να μην γνωρίζονται.
Στην πρώτη περίπτωση επιλέγουμε δύο άγνωστους του a_1

ώστε να μην γνωρίζονται και να μην γνωρίζουν τον a_l

έστω

και έχουμε την σειρά a_1,a_i,a_l,a_g,a_h

Στην δεύτερη περίπτωση επιλέγουμε a_s

γνωστό του a_1

,άγνωστο του a_l

και ενός ακόμα άγνωστου του a_1,a_g

και έχουμε την σειρά a_1,a_i,a_l,a_s,a_g

Σε στρογγυλό τραπέζι

Σε στρογγυλό τραπέζι

Re: Σε στρογγυλό τραπέζι

Μέλη σε σύνδεση