ΣΥΝΟΛΑ

Λάμπρος Κατσάπας · #1

Έστω $\Omega$ ένα σύνολο με

στοιχεία.Να βρεθεί το πλήθος των μη διατεταγμένων ζευγαριών (A,B)

όπου $A,B\subseteq \Omega$ και $A\cap B=\varnothing .$

#2

Λάμπρος Κατσάπας έγραψε: ↑
Τετ Ιούλ 11, 2018 8:06 pm
Έστω $\Omega$ ένα σύνολο με στοιχεία.Να βρεθεί το πλήθος των μη διατεταγμένων ζευγαριών όπου $A,B\subseteq \Omega$ και $A\cap B=\varnothing .$

Απάντηση:

.

Πράγματι, για n=1

, έστω δηλαδή $\Omega = \{1\}$ , έχουμε τα τρία ζεύγη $(\varnothing , \varnothing) \, (\varnothing , \{1\}) \, (\{1\} , \varnothing).$

Για το επαγωγικό βήμα για $\Omega$ με n+1

στοιχεία, σβήνουμε το τελευταίο. Ας το πούμε $\omega$ . Το $\Omega - \{\omega\}$ έχει 3^n

διατεταγμένα ζεύγη (A,B)

όπως οριοθετεί το πρόβλημα. Για καθένα από αυτά κατασκευάζουμε τρία διαφορετικά διατεταγμένα ζεύγη για την περίπτωση του $\Omega$ , τα $(A,B), \, (A\cup \{\omega\},B)\, (A,B \cup \{\omega\})$ . Αφού αυτά καλύπτουν όλες τις εκδοχές (άμεσο) και είναι τριπλάσια από τα προηγούμενα, έπεται το ζητούμενο.

Από κάτω θα βάλω διαφορετική λύση, μόλις μπορέσω.

#3

Λάμπρος Κατσάπας έγραψε: ↑
Τετ Ιούλ 11, 2018 8:06 pm
Έστω $\Omega$ ένα σύνολο με στοιχεία.Να βρεθεί το πλήθος των μη διατεταγμένων ζευγαριών όπου $A,B\subseteq \Omega$ και $A\cap B=\varnothing .$

Αλλιώς, με χρήση του αναπτύγματος διωνύμου $\displaystyle {(1+x)^n= \sum _{k=0}^n\binom {n}{k}x^k = \sum _{k=0}^n\binom {n}{k}x^{n-k} .$

Για κάθε σταθερό

με $0\le k \le n$ εξετάζουμε τα $\binom {n}{k}$ υποσύνολά του με

στοιχεία. Αν είναι

ένα τυπικό τέτοιο, τότε για ταίρι του

μπορούμε να πάρουμε είτε το A^c

(το συμπλήρωμα ως προς $\Omega$ ) είτε οποιοδήποτε υποσύνολο του A^c

. Επειδή το A^c

έχει

στοιχεία, σημαίνει ότι έχει $2^{n-k}$ υποσύνολα. Έτσι, για κάθε σταθερό

έχουμε $2^{n-k}\binom {n}{k}$ ζεύγη (A,B)

όπως ζητά το πρόβλημα. Αθροίζοντάς τα όλα θα βρούμε

$\displaystyle {\sum _{k=0}^n\binom {n}{k}2^{n-k} = (1+2)^n=3^n$

ζητούμενα ζεύγη (A,B)

.

#4

Και αλλιώς αλλιώς.

Κάθε κάτοικος μιας χώρας $\Omega$ με

κατοίκους είναι οπαδός μιας από τις τρεις ομάδες αυτής της χώρας, τις A,B,C

. Είναι σαφές ότι αυτό μπορεί να γίνει με 3^n

τρόπους (αφού ο κάθε κάτοικος μπορεί να κάνει

επιλογές για ποια ομάδα θα υποστηρίξει). Με άλλα λόγια, υπάρχουν ακριβώς 3^n

μερισμοί της χώρας σε οπαδούς (A,B,C)

, με

ξένα ανά δύο και $A\cup B \cup C = \Omega$ .

Μα είναι εξίσου σαφές ότι το πλήθος των (A,B)

όπως καθορίζεται από το πρόβλημα είναι όσο το πλήθος των (A,B,C)

ως άνω, αφού το

προσδιορίζεται κατά μοναδικό τρόπο από τα A,B

, συγκεκριμένα είναι $C=(A\cup B)^c$ . Τελειώσαμε.

ΣΥΝΟΛΑ

ΣΥΝΟΛΑ

Re: ΣΥΝΟΛΑ

Re: ΣΥΝΟΛΑ

Re: ΣΥΝΟΛΑ

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