Euler 2017/4

#1

Έστω θετικοί ακέραιοι m,n

. Δίνονται mn+1

κλειστά διαστήματα στο $\mathbb{R}$ . Να δειχθεί ότι ισχύει τουλάχιστον ένα από τα πιο κάτω:

(α) Υπάρχουν m+1

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

από αυτά τα διαστήματα τα οποία έχουν τουλάχιστον ένα κοινό σημείο τομής.

gavrilos · #2

Καλησπέρα,

Έστω $\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]$ είναι ανά δύο ξένα,από όπου έπεται το ζητούμενο.

nickthegreek · #3

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

Έστω ένα poset ( μερικώς διατεταγμένο σύνολο) με mn+1

στοιχεία. Να δειχθεί ότι το poset περιέχει ένα chain μεγέθους m+1

ή ένα antichain μεγέθους n+1

.

Φιλικά,
Νίκος

#4

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

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

είναι μικρότερο του διαστήματος J = [c,d]

(όπου

και

) αν

.)

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

nickthegreek · #5

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

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

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

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

#6

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

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

Euler 2017/4

Euler 2017/4

Re: Euler 2017/4

Re: Euler 2017/4

Re: Euler 2017/4

Re: Euler 2017/4

Re: Euler 2017/4

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