mathematica.gr • Putnam 1990/A6

Σελίδα 1 από 1

Putnam 1990/A6

Δημοσιεύτηκε: Πέμ Φεβ 15, 2018 2:01 pm

από Demetres

Ονομάζουμε ένα διατεταγμένο ζεύγος (S,T)

(S,T)

υποσυνόλων του $\{1,2,\ldots,n\}$ αποδεκτό, αν s > |T|

s > |T|

για κάθε $s \in S$ και t > |S|

t > |S|

για κάθε $t \in T$ .

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

Re: Putnam 1990/A6

Δημοσιεύτηκε: Πέμ Φεβ 15, 2018 7:07 pm

από Διονύσιος Αδαμόπουλος

Έστω πως το

έχει

όρους και το

έχει

όρους.

Τότε όλες οι δυνατές τιμές των στοιχείων του

είναι από

j+1

έως

, οι οποίοι είναι n-j

n-j

αριθμοί. Αφού επιλέγουμε

αριθμούς έχουμε $\displaystyle{\binom{n-j}{i}}$ τρόπους.

Όμοια οι δυνατές τιμές των στοιχείων του

είναι από

i+1

έως

, οι οποίοι είναι n-i

n-i

αριθμοί. Αφού επιλέγουμε

αριθμούς έχουμε $\displaystyle{\binom{n-i}{j}}$ τρόπους.

Επομένως για τα ζεύγη (S, T)

(S, T)

έχουμε $\displaystyle{\binom{n-j}{i}\cdot \binom{n-i}{j}}$ περιπτώσεις, με τους περιορισμούς:΄

i,j>0

i,j>0

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

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

n=10

είναι:

$\displaystyle{\sum \binom{10-j}{i}\cdot \binom{10-i}{j}}$ για κάθε i, j>0

i, j>0

και $i+j\leq 10$

Re: Putnam 1990/A6

Δημοσιεύτηκε: Πέμ Φεβ 15, 2018 8:32 pm

από Demetres

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

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

i=0

και

j=0

.