IMC 2021/1/2

#1

Έστω σταθεροί θετικοί ακέραιοι n,k

και έστω

ένας αυθαίρετος μη αρνητικός ακέραιος.

Επιλέγουμε τυχαία και ομοιόμορφα ένα υποσύνολο

του $\{1,2,\ldots,k+a\}$ μεγέθους

. (Δηλαδή όλα τα υποσύνολα μεγέθους

επιλέγονται με την ίδια πιθανότητα.)

Ανεξάρτητα του

επιλέγουμε τυχαία και ομοιόμορφα ένα υποσύνολο

του $\{1,2,\ldots,k+n+a\}$ μεγέθους

.

Να δειχθεί ότι η πιθανότητα

$\displaystyle P(\min{Y} > \min{X})$

είναι ανεξάρτητη του

sot arm · #2

Βάζω την λύση που έδωσα στον διαγωνισμό, είναι διαφορετική από την επίσημη, αλλά δεν έχει κάτι το κομψό πιστεύω, είναι απλά πράξεις.

Αρχικά γνωρίζουμε ότι:

$\displaystyle{ \sum_{s \geq 0 } \binom{s+t}{t}x^{s} = \frac{1}{(1-x)^{t+1}} }$

Η απόδειξη είναι παραγωγίζοντας

φορές την γεωμετρική και λίγη απλή άλγεβρα. Διαλέγοντας πρώτα το μέγιστο στοιχείο του

βρίσκουμε ότι το πλήθος των ευνοϊκών περιπτώσεων ισούται με:

$\displaystyle{\displaystyle{ \sum_{i=0}^{a } \binom{k-1 +i }{k -1 } \binom{ n + a - i }{ n } = \sum_{i=0}^{a} [x^{i}] (\frac{1}{(1-x)^{k}}) [x^{a-i}] (\frac{1}{(1-x)^{n+1}}) = [x^{a}] (\frac{1}{(1-x)^{n+k+1}}) = \binom{n+k+a}{a} } }$

Το πλήθος όλων των περιπτώσεων ισούται με:

$\displaystyle{ \binom{k+a}{k } \cdot \binom{k+n+a}{n}}$

Συνεπώς η ζητούμενη πιθανότητα ισούται με:

$\displaystyle{ \frac{ \binom{n+k+a}{a} }{\binom{k+a}{k } \cdot \binom{k+n+a}{n}} = \frac{1}{\binom{n+k}{k }}}$

που είναι προφανώς ανεξάρτητη του

.

IMC 2021/1/2

IMC 2021/1/2

Re: IMC 2021/1/2

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