Σύνολο ακεραίων και διαιρετότητα

#1

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

dement · #2

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

Εστω συνολο

με

στοιχεια και σχεση μερικης διαταξης $\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

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

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

#3

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

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

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

.

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

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

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

.

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

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

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

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

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

είναι το μεγαλύτερο

για το οποίο υπάρχουν $x_1,x_2,\ldots,x_k \in A$ με x_k = x

ώστε $x_1|x_2, x_2|x_3, \ldots, x_{k-1}|x_k$ . Παρατηρούμε από την δεδομένη συνθήκη ότι πράγματι $f:A \to \{1,2,3,4\}$ . Έστω A_i

το υποσύνολο του

που απεικονίζεται στο

. Παρατηρούμε ότι κάθε A_i

έχει την ιδιότητα που θέλουμε (αν $x,y \in A_i$ και x|y

τότε $y \in A_j$ για j>i

, άτοπο) και κάποιο από αυτά θα έχει μέγεθος τουλάχιστον 503 > 500.

dement · #4

Δεν ειχα υποψη μου τον ορο 'αντιαλυσιδα' ! Θα μου ειχε γλυτωσει ενα σωρο γραψιμο...

Δημητρης

#5

dement έγραψε:Δεν ειχα υποψη μου τον ορο 'αντιαλυσιδα' ! Θα μου ειχε γλυτωσει ενα σωρο γραψιμο...

Δημητρης

Να πω την αλήθεια, στο λεξικό που έχω δεν υπάρχει η μετάφραση. Πάντως το antichain είναι καθιερωμένος όρος στην αγγλική ορολογία.

Σύνολο ακεραίων και διαιρετότητα

Σύνολο ακεραίων και διαιρετότητα

Re: Σύνολο ακεραίων και διαιρετότητα

Re: Σύνολο ακεραίων και διαιρετότητα

Re: Σύνολο ακεραίων και διαιρετότητα

Re: Σύνολο ακεραίων και διαιρετότητα

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