Euler 2017/4

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

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Euler 2017/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Νοέμ 28, 2017 3:25 pm

Έστω θετικοί ακέραιοι m,n. Δίνονται mn+1 κλειστά διαστήματα στο \mathbb{R}. Να δειχθεί ότι ισχύει τουλάχιστον ένα από τα πιο κάτω:

(α) Υπάρχουν m+1 από αυτά τα διαστήματα τα οποία είναι ξένα μεταξύ τους.
(β) Υπάρχουν n+1 από αυτά τα διαστήματα τα οποία έχουν τουλάχιστον ένα κοινό σημείο τομής.



Λέξεις Κλειδιά:
gavrilos
Δημοσιεύσεις: 1022
Εγγραφή: Παρ Δεκ 07, 2012 4:11 pm

Re: Euler 2017/4

#2

Μη αναγνωσμένη δημοσίευση από gavrilos » Πέμ Δεκ 07, 2017 7:42 pm

Καλησπέρα,

Έστω \left[a_1,b_1\right],\ldots,\left[a_{mn+1},b_{mn+1}\right] τα διαστήματα,όπου a_1\leq a_2\leq \ldots \leq a_{mn+1},και έστω ότι δεν ισχύει η δεύτερη συνθήκη.Διατάσουμε τους αριθμούς a_1,a_2,\ldots,a_{mn+1} σε αύξουσα σειρά.Η υπόθεσή μας,μας εξασφαλίζει ότι,αν επιλέξουμε δείκτες k_1<k_2<\ldots<k_{n+1},τότε υπάρχει ένας από αυτούς,έστω ο k_i \ , \ i\leq n που είναι τέτοιος ώστε b_{k_i}< a_{k_{n+1}},γιατί διαφορετικά τα διαστήματα \left[a_{k_1},b_{k_1}\right],\ldots,\left[a_{k_{n+1}},b_{k_{n+1}}\right] θα είχαν μη κενή τομή.Συνεπώς:

\bullet Επιλέγουμε τους 1,2,\ldots ,n+1 και βρίσκουμε ότι υπάρχει 1\leq t_1\leq n τέτοιος ώστε b_{t_1}<a_{n+1}.
\bullet Επιλέγουμε τους n+1,n+2,\ldots ,2n+1 και βρίσκουμε ότι υπάρχει n+1\leq t_2\leq 2n τέτοιος ώστε b_{t_2}< a_{2n+1}.
\bullet \ \ldots
\bullet Επιλέγουμε τους (m-1)n+1,(m-1)n+2,\ldots ,mn+1 και βρίσκουμε ότι υπάρχει (m-1)n+1 \leq t_m \leq mn τέτοιος ώστε b_{t_m}<a_{mn+1}.

Τα διαστήματα \left[a_{t_1},b_{t_1}\right],\ldots ,\left[a_{t_m},b_{t_m}\right],\left[a_{mn+1},b_{mn+1}\right] είναι ανά δύο ξένα,από όπου έπεται το ζητούμενο.


Αν τα γεγονότα δεν συμφωνούν με τη θεωρία, τότε αλίμονο στα γεγονότα.

Albert Einstein
nickthegreek
Δημοσιεύσεις: 394
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Euler 2017/4

#3

Μη αναγνωσμένη δημοσίευση από nickthegreek » Παρ Δεκ 08, 2017 2:49 am

Ενδιαφέρον θέμα και ωραία λύση. Προτείνω την ακόλουθη παραλλαγή (δυστυχώς δεν είναι γενίκευση, καθώς δεν νομίζω ότι μπορούμε να δημιουργήσουμε poset με κατάλληλες ιδιότητες στην παραπάνω άσκηση):

Έστω ένα poset ( μερικώς διατεταγμένο σύνολο) με mn+1 στοιχεία. Να δειχθεί ότι το poset περιέχει ένα chain μεγέθους m+1 ή ένα antichain μεγέθους n+1.

Φιλικά,
Νίκος
τελευταία επεξεργασία από nickthegreek σε Παρ Δεκ 08, 2017 3:04 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Νίκος Αθανασίου
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Euler 2017/4

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Δεκ 08, 2017 2:19 pm

Νίκο, χρόνια πολλά και για προχθές.

Μπορούμε να κατασκευάσουμε ένα poset ως εξής: Λέμε ότι το διάστημα I = [a,b] είναι μικρότερο του διαστήματος J = [c,d] (όπου a<b και c < d) αν b < c.)


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


nickthegreek
Δημοσιεύσεις: 394
Εγγραφή: Δευ Μαρ 01, 2010 2:07 pm
Τοποθεσία: Oxford

Re: Euler 2017/4

#5

Μη αναγνωσμένη δημοσίευση από nickthegreek » Παρ Δεκ 08, 2017 2:52 pm

Δημήτρη έχεις δίκαιο. Το σκέφτηκα κι εγώ αυτό το relation, αλλά τότε βέβαια έχουμε strict partial order. Δεν ήμουν σίγουρος αν το Dilworth εφαρμόζεται σε strict partial orders γιατί όλες οι εκφωνήσεις που θυμάμαι είχαν να κάνουν με non-strict posets.

Anyway, το φινάλε έπεται και άμεσα από το θεώρημα του Helly για κυρτά σύνολα :
https://en.wikipedia.org/wiki/Helly%27s_theorem

Σε ευχαριστώ για τις ευχές!!

Χαιρετισμούς,
Νίκος


Νίκος Αθανασίου
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Euler 2017/4

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Δεκ 08, 2017 2:57 pm

Ναι έπεται άμεσα και από το θεώρημα του Helly.

Το Dilworth ισχύει για όλα τα partial orders.


Απάντηση

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

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

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