mathematica.gr

Δημοσιεύτηκε: **Πέμ Αύγ 27, 2009 4:11 pm**

Δίνεται ένα σύνολο Α 2009 θετικών ακεραίων με την ιδιότητα ότι για κάθε πέντε ακεραίους από το Α υπάρχουν δύο ώστε κανένας να μην διαιρεί τον άλλο. Να δειχθεί ότι υπάρχει υποσύνολο Β του Α με 500 ακεραίους με την ιδιότητα ότι για κάθε δύο ακεραίους από το Β κανένας δεν διαιρεί τον άλλο.

Δημοσιεύτηκε: **Τρί Σεπ 01, 2009 11:03 am**

Γενικευουμε :

Εστω συνολο

με

στοιχεια και σχεση μερικης διαταξης $\leq$ τετοια ωστε να μην υπαρχουν αλυσοι

στοιχειων. Τοτε υπαρχει υποσυνολο του

με $\lceil \frac{m}{n-1} \rceil$ στοιχεια, ανα δυο μη συγκρισιμα.

Αποδειξη :

Εστω συνολο

οπως στην υποθεση. Οριζουμε σχεση ισοδυναμιας $\equiv$ στο

ως εξης:

$x \equiv y \Longleftrightarrow \max \{ n(C) : C$ αλυσος με ελαχιστο $x \} = \max \{ n(C) : C$ αλυσος με ελαχιστο $y \}$ , οπου n(C)

ο αριθμος των στοιχειων του

Ετσι, π.χ., ολα τα $\leq -$ μεγιστικα στοιχεια ειναι ισοδυναμα μεταξυ τους. Ομοιως ολα τα 'παρα ενα μεγιστικα' και ουτω καθεξης.

Υπαρχουν το πολυ n-1

κλασεις ισοδυναμιας (αφου δεν υπαρχουν αλυσοι

στοιχειων) και κατα συνεπεια τουλαχιστον μια κλαση θα περιεχει τουλαχιστον $\lceil \frac{m}{n-1} \rceil$ στοιχεια. Επισης, δυο διακριτα ισοδυναμα στοιχεια ειναι μη συγκρισιμα (γιατι αν $x \leq y$ τοτε η μεγιστη αλυσος με ελαχιστο

θα ειναι αυστηρα μεγαλυτερη απο αυτη με ελαχιστο

).

Ετσι, επιλεγουμε το υποσυνολο μας να ταυτιζεται με την $\equiv -$ κλαση με τα περισσοτερα στοιχεια και εχουμε το ζητουμενο.

(Για το προβλημα μας θετουμε m = 2009, n = 5

και εχουμε 503 > 500

ως απαντηση).

Δημητρης Σκουτερης

Δημοσιεύτηκε: **Τρί Σεπ 01, 2009 11:56 am**

Δημήτρη πολύ σωστά. Ακριβώς αυτά που γράφεις είχα υπόψη μου όταν έφτιαχνα το πρόβλημα. Πιο συγκεκριμένα:

Δυϊκή μορφή θεωρήματος Dilworth: Σε κάθε μερικώς διατεταγμένο σύνολο

το μέγιστο μέγεθος αλυσίδας ισούται με τον ελάχιστο αριθμό αντιαλυσίδων που διαμερίζουν το

.

Την απόδειξη την έχεις ουσιαστικά γράψει. Υπάρχει και το

Θεώρημα Dilworth: Σε κάθε μερικώς διατεταγμένο σύνολο

το μέγιστο μέγεθος αντιαλυσίδας ισούται με τον ελάχιστο αριθμό αλυσίδων που διαμερίζουν το

.

Η απόδειξη αυτού του θεωρήματος είναι κάπως πιο δύσκολη. (Αποδεικνύεται με επαγωγή στο |X|

.) Ελπίζω να επανέλθω με μια απόδειξη του σε κάποιο άλλο θέμα.

-------------------------------------------------------------------------

Να γράψω την λύση του Δημήτρη αποφεύγωντας την ορολογία των μερικώς διατεταγμένων συνόλων:

Ορίζουμε $f:A \to \{1,2,3,4\}$ ώς εξής: Το f(x)