Συνδυαστική

2nisic · #1

Να βρεθεί το πλήθος στοιχείων του πολυπληθέστερο σύνολο θετικών ακεραίων με της ακόλουθες συνθήκες

οι ακέραιοι αριθμοί αποτελούνται από τα ψηφία {1,2,3,4,5,6}

Δεν εμφανίζεται ψηφίο περισσότερες από μία φορά στον ίδιο αριθμό

Τα ψηφία σε κάθε αριθμό είναι σε αύξουσα σειρά

οποιαδήποτε

αριθμοί του συνόλου έχουν τουλάχιστον ένα κοινό ψηφίο

Δεν υπάρχει ψηφίο πού να ανήκει σε όλους τούς αριθμούς

#2

Μπορούμε κάθε τέτοιο ακέραιο να τον αντιστοιχίσουμε με μοναδικό τρόπο σε ένα υποσύνολο του $S = \{1,2,3,4,5,6\}$ . Π.χ. αντιστοιχούμε τον 2346

στο υποσύνολο $\{2,3,4,6\}$ . Η αντιστοίχιση είναι μοναδική λόγω των (2) και (3).

Από το (4), για κάθε δύο υποσύνολα A,B

θέλουμε $A \cap B \neq \emptyset$ . Συνολικά έχουμε 2^6 = 64

υποσύνολα τα οποία μπορούμε να χωρίσουμε σε

ζεύγη υποσυνόλων της μορφής $\{A,A'\}$ όπου

το συμπλήρωμα του

στο

. Από κάθε ζεύγος μπορούμε να επιλέξουμε το πολύ ένα υποσύνολο. Άρα έχουμε το πολύ

υποσύνολα. Θα δείξουμε ότι μπορούμε να έχουμε τόσα ώστε να ικανοποιούνται επίσης οι (4) και (5).

Παίρνουμε όλα τα υποσύνολα μεγέθους 4,5,6

καθώς επίσης και όλα τα υποσύνολα μεγέθους

τα οποία περιέχουν το στοιχείο

. Η (5) προφανώς ικανοποιείται από για κάθε στοιχείο

επέλεξα και το υποσύνολο $S \setminus \{i\}$ που δεν περιέχει το

. Η (4) ικανοποιείται αφού για κάθε δυο υποσύνολα A,B

που επέλεξα, είτε θα έχω $|A| + |B| \geqslant 7 = |S|$ που δίνει απευθείας $|A \cap B| \geqslant 1$ , είτε θα έχω |A|=|B|=1

οπότε και θα έχω $1 \in A \cap B$ . Τέλος επέλεξα συνολικά $\displaystyle \binom{6}{4} + \binom{6}{5} + \binom{6}{6} + \binom{5}{2} = 15+6+1+10 = 32$ υποσύνολα όπως ήθελα.

Συνδυαστική

Συνδυαστική

Re: Συνδυαστική

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