Συνδιαστική στα καλύτερά της!

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

Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Συνδιαστική στα καλύτερά της!

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Κυρ Φεβ 05, 2017 12:56 pm

Δίνεται το σύνολο A={1,2,......,n}, όπου n περιττός μεγαλύτερος ή ίσος του 3. Από το A επιλέγουμε ακριβώς [\frac{n}{2}]+1 στοιχεία για την δημιουργία μιας διατεταγμένης [\frac{n}{2}]+1-άδας. Αν στα στοιχεία αυτά δεν πρέπει να υπάρχουν 2 στοιχεία με άθροισμα n, να βρείτε με πόσους τρόπους μπορεί να γίνει η δημιουργία της διατεταγμένης [\frac{n}{2}]+1-άδας. Ας αφεθεί για μαθητές.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.

Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 794
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Συνδιαστική στα καλύτερά της!

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Κυρ Φεβ 05, 2017 2:04 pm

Ο τύπος νομίζω πως είναι:

\displaystyle{2^{\lfloor \dfrac{n}{2} \rfloor} \cdot (\lfloor \dfrac{n}{2} \rfloor +1)!}

Επανέρχομαι μετά το φαγητό...


Houston, we have a problem!
Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Συνδιαστική στα καλύτερά της!

#3

Μη αναγνωσμένη δημοσίευση από JimNt. » Κυρ Φεβ 05, 2017 2:31 pm

Διονύσιος Αδαμόπουλος έγραψε:Ο τύπος νομίζω πως είναι:

\displaystyle{2^{\lfloor \dfrac{n}{2} \rfloor} \cdot (\lfloor \dfrac{n}{2} \rfloor +1)!}

Επανέρχομαι μετά το φαγητό...
Ακριβώς! :coolspeak:


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 794
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Συνδιαστική στα καλύτερά της!

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Κυρ Φεβ 05, 2017 4:01 pm

Χωρίζουμε όλα τα στοιχεία του A εκτός του τελευταίου σε \lfloor \dfrac{n}{2} \rfloor ζευγάρια ως εξής:

\{1, n-1\}, \{2, n-2\}, \ldots ,\{\lfloor \dfrac{n}{2} \rfloor, n- \lfloor \dfrac{n}{2} \rfloor\}

Κάθε ένα ζευγάρι από αυτά έχει άθροισμα n. Άρα δεν πρέπει να επιλέγονται ποτέ και τα δύο στοιχεία ενός ζευγαριού. Επομένως για τη δημιουργία κάποιας \lfloor \dfrac{n}{2} \rfloor +1-άδας θα πρέπει να επιλέγεται ένα στοιχείο από κάθε ζευγάρι, καθώς και το τελευταίο στοιχείο n του συνόλου A.

Από κάθε ζευγάρι έχουμε 2 διαφορετικές επιλογές. Άρα έχουμε 2^{\lfloor \dfrac{n}{2} \rfloor} διαφορετικές επιλογές για τη δημιουργία κάποιας μη διατεταγμένης \lfloor \dfrac{n}{2} \rfloor +1-άδας.

Επειδή θέλουμε να υπολογιστούν και οι μεταθέσεις τους, έχουμε συνολικά: \boxed{2^{\lfloor \dfrac{n}{2} \rfloor} \cdot (\lfloor \dfrac{n}{2} \rfloor +1)!} τρόπους.


Houston, we have a problem!
Άβαταρ μέλους
JimNt.
Δημοσιεύσεις: 562
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Συνδιαστική στα καλύτερά της!

#5

Μη αναγνωσμένη δημοσίευση από JimNt. » Κυρ Φεβ 05, 2017 4:07 pm

Διονύσιος Αδαμόπουλος έγραψε:Χωρίζουμε όλα τα στοιχεία του A εκτός του τελευταίου σε \lfloor \dfrac{n}{2} \rfloor ζευγάρια ως εξής:

\{1, n-1\}, \{2, n-2\}, \ldots ,\{\lfloor \dfrac{n}{2} \rfloor, n- \lfloor \dfrac{n}{2} \rfloor\}

Κάθε ένα ζευγάρι από αυτά έχει άθροισμα n. Άρα δεν πρέπει να επιλέγονται ποτέ και τα δύο στοιχεία ενός ζευγαριού. Επομένως για τη δημιουργία κάποιας \lfloor \dfrac{n}{2} \rfloor +1-άδας θα πρέπει να επιλέγεται ένα στοιχείο από κάθε ζευγάρι, καθώς και το τελευταίο στοιχείο n του συνόλου A.

Από κάθε ζευγάρι έχουμε 2 διαφορετικές επιλογές. Άρα έχουμε 2^{\lfloor \dfrac{n}{2} \rfloor} διαφορετικές επιλογές για τη δημιουργία κάποιας μη διατεταγμένης \lfloor \dfrac{n}{2} \rfloor +1-άδας.

Επειδή θέλουμε να υπολογιστούν και οι μεταθέσεις τους, έχουμε συνολικά: \boxed{2^{\lfloor \dfrac{n}{2} \rfloor} \cdot (\lfloor \dfrac{n}{2} \rfloor +1)!} τρόπους.
Πολύ ωραία. Αυτή ήταν η βασική ιδέα.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

If you are not sure it is magic then it probably is.
Απάντηση

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

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

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