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

Συντονιστές: Demetres, socrates, silouan

socrates
Επιμελητής
Δημοσιεύσεις: 5799
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

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

#1

Μη αναγνωσμένη δημοσίευση από socrates » Κυρ Ιουν 18, 2017 3:55 pm

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


Θανάσης Κοντογεώργης

Λέξεις Κλειδιά:
Άβαταρ μέλους
ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ
Δημοσιεύσεις: 366
Εγγραφή: Πέμ Νοέμ 22, 2018 9:43 pm

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

#2

Μη αναγνωσμένη δημοσίευση από ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ » Τετ Απρ 10, 2019 6:02 pm

socrates έγραψε:
Κυρ Ιουν 18, 2017 3:55 pm
Σε ένα σύλλογο n\geq 5 μελών, κάθε δύο μέλη που δε γνωρίζονται μεταξύ τους, έχουν ακριβώς ένα κοινό γνωστό, και κανένα μέλος δε γνωρίζει όλα τα υπόλοιπα.
Αποδείξτε ότι υπάρχουν 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 με i<k+1 ένα μέλος,τότε αναγκαστικά από την εκφώνηση υπάρχει a_j με j>k ώστε οι 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_l ένας γνωστός του ο οποίος δεν γνωρίζει τον a_i και a_j ο κοινός γνωστός των a_1,a_i.
Επειδή κάθε άγνωστος του a_1 έχει ακριβώς έναν κοινό γνωστό μαζί του έπεται ότι ή για κάθε a_h,h<k+1 υπάρχει a_g,g<k+1 ώστε να μην γνωρίζονται ή ότι για κάθε a_s,s>k υπάρχει a_r,r>k ώστε να μην γνωρίζονται.
Στην πρώτη περίπτωση επιλέγουμε δύο άγνωστους του a_1 ώστε να μην γνωρίζονται και να μην γνωρίζουν τον a_l έστω a_h,a_g και έχουμε την σειρά 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


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Juniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης