Επιλογής ΕΜΕ για SEEMOUS 2008/1

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8571
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Επιλογής ΕΜΕ για SEEMOUS 2008/1

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Φεβ 04, 2012 7:29 pm

(α) Δίνεται ένα σύνολο X και 2008 12-μελή υποσύνολά του τα Y_1,\ldots,Y_{2008}. Αποδείξτε ότι μπορούμε να χρωματίσουμε κάποια από τα στοιχεία του X άσπρα και τα υπόλοιπα μαύρα, έτσι ώστε όλα τα υποσύνολα Y_1,Y_2,\ldots, Y_{2008} να μην είναι μονοχρωματικά (δηλαδή κάθε υποσύνολο από τα Y_1,\ldots,Y_{2008} να περιέχει τουλάχιστον ένα άσπρο στοιχείο και τουλάχιστον ένα μαύρο στοιχείο).

(β) Αποδείξτε ότι μπορούμε να χρωματίσουμε κάποια από τα στοιχεία του Y = \{1,2,\ldots,2008\} άσπρα και τα υπόλοιπα μαύρα, ώστε το πλήθος των μονοχρωματικών 11-μελών υποσυνόλων του Y να είναι λιγότερο από \displaystyle{ \binom{2008}{11}2^{-10}}


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης