ΣΥΝΟΛΑ

Συντονιστές: Demetres, silouan

Λάμπρος Κατσάπας
Δημοσιεύσεις: 209
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

ΣΥΝΟΛΑ

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Τετ Ιούλ 11, 2018 8:06 pm

Έστω \Omega ένα σύνολο με n στοιχεία.Να βρεθεί το πλήθος των μη διατεταγμένων ζευγαριών (A,B) όπου A,B\subseteq \Omega και A\cap B=\varnothing .



Λέξεις Κλειδιά:
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 10436
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: ΣΥΝΟΛΑ

#2

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Ιούλ 11, 2018 9:05 pm

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

Πράγματι, για 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\}). Αφού αυτά καλύπτουν όλες τις εκδοχές (άμεσο) και είναι τριπλάσια από τα προηγούμενα, έπεται το ζητούμενο.

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


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 10436
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: ΣΥΝΟΛΑ

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Ιούλ 11, 2018 9:27 pm

Λάμπρος Κατσάπας έγραψε:
Τετ Ιούλ 11, 2018 8:06 pm
Έστω \Omega ένα σύνολο με n στοιχεία.Να βρεθεί το πλήθος των μη διατεταγμένων ζευγαριών (A,B) όπου 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} .

Για κάθε σταθερό k με 0\le k \le n εξετάζουμε τα \binom {n}{k} υποσύνολά του με k στοιχεία. Αν είναι A ένα τυπικό τέτοιο, τότε για ταίρι του B μπορούμε να πάρουμε είτε το A^c (το συμπλήρωμα ως προς \Omega) είτε οποιοδήποτε υποσύνολο του A^c. Επειδή το A^c έχει n-k στοιχεία, σημαίνει ότι έχει 2^{n-k} υποσύνολα. Έτσι, για κάθε σταθερό 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).


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 10436
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: ΣΥΝΟΛΑ

#4

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Ιούλ 11, 2018 9:58 pm

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

Κάθε κάτοικος μιας χώρας \Omega με n κατοίκους είναι οπαδός μιας από τις τρεις ομάδες αυτής της χώρας, τις A,B,C. Είναι σαφές ότι αυτό μπορεί να γίνει με 3^n τρόπους (αφού ο κάθε κάτοικος μπορεί να κάνει 3 επιλογές για ποια ομάδα θα υποστηρίξει). Με άλλα λόγια, υπάρχουν ακριβώς 3^n μερισμοί της χώρας σε οπαδούς (A,B,C), με A,B,C ξένα ανά δύο και A\cup B \cup C = \Omega.

Μα είναι εξίσου σαφές ότι το πλήθος των (A,B) όπως καθορίζεται από το πρόβλημα είναι όσο το πλήθος των (A,B,C) ως άνω, αφού το C προσδιορίζεται κατά μοναδικό τρόπο από τα A,B, συγκεκριμένα είναι C=(A\cup B)^c. Τελειώσαμε.


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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