Ενδιαφέρουσα διάλεξη

#1

Κατά τη διάρκεια μιας διάλεξης, καθένας από τους 5 επιστήμονες κοιμήθηκε ακριβώς 2 φορές.
Για κάθε ζευγάρι επιστημόνων, υπήρχε μια στιγμή που και οι δύο κοιμόντουσαν ταυτόχρονα.
Αποδείξτε ότι, κάποια στιγμή, υπήρχαν 3 επιστήμονες που κοιμόντουσαν ταυτόχρονα.

stranger · #2

Έστω $A_n =[x_n,y_n]\cup[a_n,b_n]$ ώστε το A_n

να είναι το χρονικό διάστημα που ο

επιστήμονας κοιμήθηκε. x_n<y_n<a_n<b_n

.
Πρέπει να δείξουμε ότι υπάρχουν i,j,k

διακεκριμένα ώστε $A_i \cap A_j \cap A_k \neq \emptyset.$ .
Βάζουμε τα σύνολα στη σειρά ώστε $A \leq B$ αν και μόνο αν $min(A) \leq min(B)$ .
Αν το σύνολο

είναι κενό ορίζουμε $min(A) = +\infty$ .
Αν A,B

δύο σύνολα τότε $A \leq B$ και

ώστε $C \geq B$ συνεπάγεται $AC \leq BC$ .
Έχουμε $A_1 \leq A_2 \leq A_3 \leq A_4$ .
Τότε έχουμε $A_1 A_2 \leq A_3 A_4$ το οποίο δίνει ότι $A_1 A_2 A_4 \leq A_3 A_4 A_4 = A_3 A_4$ , το οποίο είναι άτοπο αφού το A_3 A_4

δεν είναι κενό από υπόθεση.
Σημείωση: Η παραπάνω απόδειξη δείχνει ότι το αποτέλεσμα ισχύει αν ο αριθμός των επιστημόνων είναι μεγαλύτερος η ίσος του 4.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #3

stranger έγραψε: ↑
Δευ Αύγ 31, 2020 12:35 pm
Έστω $A_n =[x_n,y_n]\cup[a_n,b_n]$ ώστε το να είναι το χρονικό διάστημα που ο επιστήμονας κοιμήθηκε..
Πρέπει να δείξουμε ότι υπάρχουν διακεκριμένα ώστε $A_i \cap A_j \cap A_k \neq \emptyset.$ .
Βάζουμε τα σύνολα στη σειρά ώστε $A \leq B$ αν και μόνο αν $min(A) \leq min(B)$ .
Αν το σύνολο είναι κενό ορίζουμε $min(A) = +\infty$ .
Αν δύο σύνολα τότε $A \leq B$ και ώστε $C \geqA$ και $C \geq B$ συνεπάγεται $AC \leq BC$ .
Έστω ότι για κάθε διακεκριμμένα $A_i A_j A_k = \emptyset$ .
Έχουμε ότι $A_1 \leq A_2 \leq A_3$ .
Άρα $A_3 A_1 A_2 \leq A_2 A_3 A_3 = A_2 A_3$ .
Όμως το σύνολο είναι μη κενό από υπόθεση, το οποίο φέρνει το άτοπο και το συμπέρασμα έπεται.

Σημείωση: Η παραπάνω απόδειξη δείχνει ότι το αποτέλεσμα ισχύει αν ο αριθμός των επιστημόνων είναι μεγαλύτερος η ίσος του 3.

για

δεν ισχύει.
Πάρε
ο πρώτος να κοιμήθηκε στο $[1,2]\cup [4,5]$
ο δεύτερος να κοιμήθηκε στο $[2,3]\cup [7,8]$
και ο τρίτος να κοιμήθηκε στο $[0,1]\cup [8,9]$

stranger · #4

Σταύρο σε ευχαριστώ. Την διόρθωσα την απόδειξή μου (δες παραπάνω). Πρέπει να έχουμε ότι ο αριθμός των επιστηνόνων να είναι μεγαλύτερος η ίσος του 4.

Μάρκος Βασίλης · #5

Το πρόβλημα μπορεί να επανδιατυπωθεί ως εξής: παίρνουμε 5 σπίρτα, a,b,c,d,e

, και τα τοποθετούμε έτσι ώστε ανά δύο να τέμνονται σε κάποιο από τα άκρα τους. Θα δείξουμε ότι υπάρχει τριάδα σπίρτων που να τέμνονται.

Αρχικά, παίρνουμε το σπίρτο

το οποίο, από υπόθεση θα τέμνει το σπίρτο

. Στη συνέχεια, παίρνουμε το σπίρτο

. Αυτό θα τέμνει και τα δύο άλλα σπίρτα σε κάποια άκρη τους. Αν αυτή είναι η κοινή άκρη των a,b

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

το οποίο θα πρέπει να τέμνει το σπίρτο

σε κάποιο από τα άκρα του, συνεπώς θα τέμνει είτε το

είτε το

και η απόδειξη καταλήγει.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #6

Μάρκος Βασίλης έγραψε: ↑
Δευ Αύγ 31, 2020 4:13 pm
Το πρόβλημα μπορεί να επανδιατυπωθεί ως εξής: παίρνουμε 5 σπίρτα, , και τα τοποθετούμε έτσι ώστε ανά δύο να τέμνονται σε κάποιο από τα άκρα τους. Θα δείξουμε ότι υπάρχει τριάδα σπίρτων που να τέμνονται.

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

Μάρκος Βασίλης έγραψε: ↑
Δευ Αύγ 31, 2020 4:13 pm
Το πρόβλημα μπορεί να επανδιατυπωθεί ως εξής: παίρνουμε 5 σπίρτα, , και τα τοποθετούμε έτσι ώστε ανά δύο να τέμνονται σε κάποιο από τα άκρα τους. Θα δείξουμε ότι υπάρχει τριάδα σπίρτων που να τέμνονται.

Δεν είναι έτσι γιατί κοιμούνται δύο φορές.
Αρα ο καθένας θα έπρεπε να αντιστοιχεί σε δύο σπίρτα και τα σπίρτα πάνω σε μια ευθεία κλπ.
Αν κάνω λάθος διορθωσε με .

Υπάρχει ενα σημείο στο πρόβλημα που δεν είναι καθαρό τουλάχιστον για μένα.
Οταν λέει
υπήρχε μια στιγμή που και οι δύο κοιμόντουσαν ταυτόχρονα
θεωρώ ότι εννοεί τουλάχιστον μια.
Δηλαδή θα μπορούσαν να κοιμόντουσαν ταυτόχρονα για ένα διάστημα.

Εσύ θεωρείς ότι

Οταν λέει
υπήρχε μια στιγμή που και οι δύο κοιμόντουσαν ταυτόχρονα

εννοεί ακριβώς μία.

Μάρκος Βασίλης · #7

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: ↑
Δευ Αύγ 31, 2020 9:18 pm
Δεν είναι έτσι γιατί κοιμούνται δύο φορές.
Αρα ο καθένας θα έπρεπε να αντιστοιχεί σε δύο σπίρτα και τα σπίρτα πάνω σε μια ευθεία κλπ.
Αν κάνω λάθος διορθωσε με .

Υπάρχει ενα σημείο στο πρόβλημα που δεν είναι καθαρό τουλάχιστον για μένα.
Οταν λέει
υπήρχε μια στιγμή που και οι δύο κοιμόντουσαν ταυτόχρονα
θεωρώ ότι εννοεί τουλάχιστον μια.
Δηλαδή θα μπορούσαν να κοιμόντουσαν ταυτόχρονα για ένα διάστημα.

Εσύ θεωρείς ότι

Οταν λέει
υπήρχε μια στιγμή που και οι δύο κοιμόντουσαν ταυτόχρονα

εννοεί ακριβώς μία.

Εγώ σκέφτηκα ότι ένας επιστήμονας αντιστοιχεί σε ένα σπίρτο και τα δύο άκρα του σπίρτου είναι οι δύο «ύπνοι» του επιστήμονα, οπότε και μετράει η θέση στην οποία τέμνονται.

Σε σχέση, τώρα, με την ύπαρξη, πράγματι το αντιμετωπίσαμε διαφορετικά.

stranger · #8

To ποστ μου νούμερο 2 είναι λανθασμένο. Ευχαριστώ το Σταύρο για την επισήμανση.
Ας κάνω άλλη μια προσπάθεια.Έστω ότι δεν υπάρχει στιγμή που να κοιμήθηκαν τρεις επιστήμονες μαζί.
Παρατηρούμε ότι τα σύνολα $A_n = [x_n,y_n] \cup [a_n,b_n]$ καθώς και οι ενώσεις τους η οι τομές τους τέμνονται αν και μόνο αν τέμνονται σε κάποιο άκρο τους. Άρα μπορούμε να ταυτίσουμε ένα τέτοιο σύνολο με τα άκρα τους.
Χρησιμοποιώντας την αρχή εγκλεισμού- αποκλεισμού έχουμε
$|\cup_{n=1}^{5}A_n| = \sum_{J \subseteq \{1,..,5\}}(-1)^{|J|+1} |\cap_{j \in J}A_j|$ .
Αν |J|=1

τότε $|\cap_{j \in J}A_j| = 4$ .
Επίσης έχουμε αν |J|=2

τότε $|\cap_{j \in J}A_j| \geq 1$ επειδή κάθε ζεύγος συνόλων τέμνονται από υπόθεση.
Επίσης από υπόθεση, αν $|J| \geq 3$ τότε $|\cap_{j \in J}A_j| = 0$ .
Επίσης το πλήθος των υποσυνόλων του $\{1,..,5\}$ που περιέχουν δύο στοιχεία είναι ${5} \choose{2}$ =

.
Άρα $|\cup_{n=1}^{5}A_n| \leq 20-10=10$ .
Νομίζω από αυτό μπορούμε να πάρουμε άτοπο. Δεν είμαι σίγουρος. Ας την συνεχίσει κάποιος άλλος.

Ορέστης Λιγνός · #9

Έστω, $t_{ij}$ ή πρώτη στιγμή που ο επιστήμονας

κοιμόταν ταυτόχρονα με τον επιστήμονα

, με $i \neq j$ και $i,j \in \{1,2,3,4,5 \}$ .
Είναι προφανές ότι υπάρχουν

ακριβώς τέτοιες στιγμές.
Επίσης, θεωρούμε s_k

με $k \in \{1,2 \ldots, 10 \}$ τις χρονικές στιγμές όπου ένας επιστήμονας αρχίζει να κοιμάται (

τέτοιες στιγμές για κάθε έναν από τους

).

Αν για κάποια i,j,p,q

ισχύει $t_{ij}=t_{pq}$ τότε το ζητούμενο είναι προφανές (ακόμα και αν i=p

ή

). Ας υποθέσουμε λοιπόν ότι όλα τα $t_{ij}$ είναι διαφορετικά μεταξύ τους.
Τότε, σε κάθε μια από αυτές τις στιγμές, αντιστοιχεί μία από τις στιγμές s_i

. Πράγματι, αν η χρονική στιγμή $t_{ij}$ δεν είναι μια από τις s_k, s_j

, τότε θα μπορούσαμε να θεωρήσουμε μια άλλη στιγμή $m<t_{ij}$ όπου οι επιστήμονες i,j

κοιμούνται ταυτόχρονα. Αυτό όμως αντιβαίνει στον ορισμό των $t_{ij}$ .

Άρα, και αφού τα $t_{ij}$ είναι διαφορετικά μεταξύ τους και αφού το πλήθος των $t_{ij}$ είναι ίσο με το πλήθος των s_k

, σε κάθε ένα από τα $t_{ij}$ πρέπει να αντιστοιχεί ακριβώς ένα από τα s_k

.

Ας θεωρήσουμε τώρα τους δύο επιστήμονες x,y

ώστε το $t_{xy}$ να είναι ελάχιστο. Από προηγούμενα, την στιγμή $t_{xy}$ ακριβώς ένας από τους x,y

άρχισε να κοιμάται. Έστω ο

.
Ο

τότε, προφανώς δεν μπορεί να άρχισε να κοιμάται την ίδια στιγμή με τον

. Άρα, όταν άρχισε να κοιμάται ο

, κανείς άλλος δεν κοιμόταν ήδη (αφού το $t_{xy}$ είναι ελάχιστο). Αυτό όμως αντιβαίνει στο γεγονός ότι σε κάθε s_k

(στα οποία περιλαμβάνεται η στιγμή που άρχισε να κοιμάται ο

), αντιστοιχεί ένα $t_{ij}$ .

Η απόδειξη ολοκληρώθηκε.

#10

Δείτε και εδώ https://artofproblemsolving.com/communi ... 68p2403861
Πίσω από το πρόβλημα κρύβεται το Θεώρημα Helly.

stranger · #11

stranger έγραψε: ↑
Τρί Σεπ 01, 2020 9:59 pm
To ποστ μου νούμερο 2 είναι λανθασμένο. Ευχαριστώ το Σταύρο για την επισήμανση.
Ας κάνω άλλη μια προσπάθεια.Έστω ότι δεν υπάρχει στιγμή που να κοιμήθηκαν τρεις επιστήμονες μαζί.
Παρατηρούμε ότι τα σύνολα $A_n = [x_n,y_n] \cup [a_n,b_n]$ καθώς και οι ενώσεις τους η οι τομές τους τέμνονται αν και μόνο αν τέμνονται σε κάποιο άκρο τους. Άρα μπορούμε να ταυτίσουμε ένα τέτοιο σύνολο με τα άκρα τους.
Χρησιμοποιώντας την αρχή εγκλεισμού- αποκλεισμού έχουμε
$|\cup_{n=1}^{5}A_n| = \sum_{J \subseteq \{1,..,5\}}(-1)^{|J|+1} |\cap_{j \in J}A_j|$ .
Αν τότε $|\cap_{j \in J}A_j| = 4$ .
Επίσης έχουμε αν τότε $|\cap_{j \in J}A_j| \geq 1$ επειδή κάθε ζεύγος συνόλων τέμνονται από υπόθεση.
Επίσης από υπόθεση, αν $|J| \geq 3$ τότε $|\cap_{j \in J}A_j| = 0$ .
Επίσης το πλήθος των υποσυνόλων του $\{1,..,5\}$ που περιέχουν δύο στοιχεία είναι $5 \choose{2}$ = .
Άρα $|\cup_{n=1}^{5}A_n| \leq 20-10=10$ .
Νομίζω από αυτό μπορούμε να πάρουμε άτοπο. Δεν είμαι σίγουρος. Ας την συνεχίσει κάποιος άλλος.

Να ολοκληρώσω την απόδειξη. Έστω $t_{i,j}$ το ελάχιστο σημείο τομής των A_i

και

.
Τότε επειδή δεν υπάρχει σημείο τομής τριών συνόλων έχουμε ότι το πλήθος των $t_{i,j}$ είναι $5 \choose 2$ =10

.
Άρα σύμφωνα με τα παραπάνω που έγραψα έχουμε $|\cup_{n=1}^{5}A_n| = 10$ , το οποίο σημαίνει ότι υπάρχουν ακριβώς 10 διακεκριμμένα άκρα $a_1 < a_2 <...< a_{10}$ .
Άρα έχουμε ότι το $a_{10}$ είναι το ελάχιστο σημείο τομής ενός A_i

και

, όπου $A_i = [x_i,y_i] \cup [k_i,a_{10}]$ και $A_j = [x_j,y_j] \cup [k_j,a_{10}]$ . Όμως τα δύο αυτά σύνολα τέμνονται στο $max(k_i,k_j) < a_{10}$ το οποίο είναι άτοπο και το συμπέρασμα έπεται.

Ενδιαφέρουσα διάλεξη

Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

Re: Ενδιαφέρουσα διάλεξη

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