Σελίδα 1 από 1

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

Δημοσιεύτηκε: Πέμ Μάιος 11, 2017 4:20 pm
από Demetres
Έστω φυσικοί k,n με 1 \leqslant k \leqslant n. Έστω μια οικογένεια \mathcal{A} υποσυνόλων του \{1,2,\ldots,n\} μεγέθους k ώστε αν A,B \in \mathcal{A} τότε είτε το A είτε το B περιέχει τα k μικρότερα στοιχεία την ένωσης A \cup B

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

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

Δημοσιεύτηκε: Πέμ Μάιος 11, 2017 6:15 pm
από Demetres
Διορθώθηκε η εκφώνηση!

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

Δημοσιεύτηκε: Παρ Μάιος 12, 2017 2:20 pm
από dement
Ας μην χαθεί...

Χρησιμοποιούμε τη σχέση \leqslant \in \mathcal{A} \times \mathcal{A} για να υποδηλώσουμε με το A \leqslant B ότι το A περιέχει τα k μικρότερα στοιχεία του 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. Τότε το m ανήκει στα k μικρότερα στοιχεία του 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} υπάρχουν;

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

Δημοσιεύτηκε: Κυρ Μάιος 14, 2017 10:24 am
από Demetres
dement έγραψε:
Ενδιαφέρον επιπλέον ερώτημα: Πόσες μεγιστικές \mathcal{A} υπάρχουν;
Υπάρχουν k^{n-k} μεγιστικές οικογένειες. Αν A_r \in \mathcal{A} το σύνολο με μέγιστο στοιχείο το r τότε τα στοιχεία του A_r είναι το r μαζί με οποιαδήποτε άλλα k-1 στοιχεία από τα k στοιχεία του A_{r-1}. (Αν είχε κάποιο στοιχείο που δεν ανήκε στο A_{r-1} τότε η ένωση A_{r-1} \cup A_r θα είχε τουλάχιστον k στοιχεία μικρότερα του r-1 οπότε το r-1 \in A_{r-1} δεν θα ανήκε στην ένωση, άτοπο. Από την άλλη, αν επιλέξουμε τα στοιχεία με τον πιο πάνω τρόπο για κάθε r, τότε για οποιαδήποτε A_s,A_t με s < t και οποιοδήποτε x \in A_t θα έχουμε ότι είτε x \in A_s, είτε x > s. Άρα τα k μικρότερα στοιχεία της ένωσης θα είναι αυτά του A_s.