Putnam 1990/A6

#1

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

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

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

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

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

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

Έστω πως το

έχει

όρους και το

έχει

όρους.

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

είναι από

έως

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

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

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

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

είναι από

έως

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

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

αριθμούς έχουμε $\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$

#3

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

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

και

.