Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

#1

Έστω φυσικοί k,n

με $1 \leqslant k \leqslant n$ . Έστω μια οικογένεια $\mathcal{A}$ υποσυνόλων του $\{1,2,\ldots,n\}$ μεγέθους

ώστε αν $A,B \in \mathcal{A}$ τότε είτε το

είτε το

περιέχει τα

μικρότερα στοιχεία την ένωσης $A \cup B$

Να βρεθεί το μέγιστο δυνατό μέγεθος της $\mathcal{A}$ .

#2

Διορθώθηκε η εκφώνηση!

dement · #3

Ας μην χαθεί...

Χρησιμοποιούμε τη σχέση $\leqslant \in \mathcal{A} \times \mathcal{A}$ για να υποδηλώσουμε με το $A \leqslant B$ ότι το

περιέχει τα

μικρότερα στοιχεία του $A \cup B$ (παρεμπιπτόντως, η $\leqslant$ είναι γραμμική διάταξη).

Θα αποδείξουμε ότι, για κάθε $A, B \in \mathcal{A}$ , ισχύει $A \neq B \implies \max(A) \neq \max(B)$ . Πράγματι, έστω $A \leqslant B$ και $\max(A) = \max(B) = \max(A \cup B) = m$ . Τότε το

ανήκει στα

μικρότερα στοιχεία του $A \cup B$ και $A \cup B \subseteq A \implies A = B$ (αφού τα A, B

είναι ισοπληθή και πεπερασμένα).

Έτσι, η $\mathcal{A}$ μπορεί να έχει το πολύ n-k+1

στοιχεία (όσα και τα δυνατά μέγιστα στοιχεία). Μια πιθανή κατασκευή είναι η $\mathcal{A} = \left\{ \{ p + q : 1 \leqslant q \leqslant k \} : 0 \leqslant p \leqslant n-k \right\}$ .

Ενδιαφέρον επιπλέον ερώτημα: Πόσες μεγιστικές $\mathcal{A}$ υπάρχουν;

#4

dement έγραψε:
Ενδιαφέρον επιπλέον ερώτημα: Πόσες μεγιστικές $\mathcal{A}$ υπάρχουν;

Υπάρχουν $k^{n-k}$ μεγιστικές οικογένειες. Αν $A_r \in \mathcal{A}$ το σύνολο με μέγιστο στοιχείο το

τότε τα στοιχεία του A_r

είναι το

μαζί με οποιαδήποτε άλλα k-1

στοιχεία από τα

στοιχεία του $A_{r-1}$ . (Αν είχε κάποιο στοιχείο που δεν ανήκε στο $A_{r-1}$ τότε η ένωση $A_{r-1} \cup A_r$ θα είχε τουλάχιστον

στοιχεία μικρότερα του r-1

οπότε το $r-1 \in A_{r-1}$ δεν θα ανήκε στην ένωση, άτοπο. Από την άλλη, αν επιλέξουμε τα στοιχεία με τον πιο πάνω τρόπο για κάθε

, τότε για οποιαδήποτε A_s,A_t

με

και οποιοδήποτε $x \in A_t$ θα έχουμε ότι είτε $x \in A_s$ , είτε x > s

. Άρα τα

μικρότερα στοιχεία της ένωσης θα είναι αυτά του A_s

.

Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

Re: Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

Re: Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

Re: Μικρότερα στοιχεία της ένωσης ανήκουν στο ένα σύνολο

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