Putnam 1990/A6

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

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

Putnam 1990/A6

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Φεβ 15, 2018 2:01 pm

Ονομάζουμε ένα διατεταγμένο ζεύγος (S,T) υποσυνόλων του \{1,2,\ldots,n\} αποδεκτό, αν s > |T| για κάθε s \in S και t > |S| για κάθε t \in T.

Να βρεθεί το πλήθος των αποδεκτών διατεταγμένων ζευγών υποσυνόλων του \{1,2,\ldots,10\}.



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

Re: Putnam 1990/A6

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Πέμ Φεβ 15, 2018 7:07 pm

Έστω πως το S έχει i όρους και το T έχει j όρους.

Τότε όλες οι δυνατές τιμές των στοιχείων του S είναι από j+1 έως n, οι οποίοι είναι n-j αριθμοί. Αφού επιλέγουμε i αριθμούς έχουμε \displaystyle{\binom{n-j}{i}} τρόπους.

Όμοια οι δυνατές τιμές των στοιχείων του T είναι από i+1 έως n, οι οποίοι είναι n-i αριθμοί. Αφού επιλέγουμε j αριθμούς έχουμε \displaystyle{\binom{n-i}{j}} τρόπους.

Επομένως για τα ζεύγη (S, T) έχουμε \displaystyle{\binom{n-j}{i}\cdot \binom{n-i}{j}} περιπτώσεις, με τους περιορισμούς:΄

i,j>0 και n-i\geq j και n-j\geq i (δηλαδή i+j\leq n).

Συνολικά είναι λοιπόν το πλήθος για n=10 είναι:

\displaystyle{\sum \binom{10-j}{i}\cdot \binom{10-i}{j}} για κάθε i, j>0 και i+j\leq 10
τελευταία επεξεργασία από Διονύσιος Αδαμόπουλος σε Πέμ Φεβ 15, 2018 8:36 pm, έχει επεξεργασθεί 1 φορά συνολικά.


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

Re: Putnam 1990/A6

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Φεβ 15, 2018 8:32 pm

Ωραία μέχρι στιγμής, αλλά ζητείται και η τελική απάντηση.

Επεξεργασία: Επιτρέπονται τα i=0 και j=0.


Απάντηση

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

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

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