Σελίδα 1 από 1

Putnam 2016/B4

Δημοσιεύτηκε: Τρί Ιαν 03, 2017 9:45 pm
από Demetres
Έστω ένας 2n \times 2n πίνακας A. Τα στοιχεία του A επιλέγονται ανεξάρτητα στην τύχη με κάθε στοιχείο να ισούται είτε με 0 είτε με 1 κάθε ένα με πιθανότητα 1/2.

Να υπολογιστεί η προσδοκόμενη τιμή του \det(A-A^t).

Re: Putnam 2016/B4

Δημοσιεύτηκε: Σάβ Ιαν 21, 2017 12:16 pm
από dement
Για τον πίνακα D \equiv A - A^t ισχύει D_{mm} = 0 και, για m \neq k, (D_{mk}, D_{km}) = (0, 0) με πιθανότητα 1/2, (D_{mk}, D_{km}) = (1, -1) με πιθανότητα 1/4 και(D_{mk}, D_{km}) = (-1, 1) με πιθανότητα 1/4.

Θυμίζω ότι \displaystyle \det D = \sum_{p \in S_{2n}} (-1)^{k(p)} \prod_{i=1}^{2n} D_{i,p(i)} όπου k(p) = 0 για άρτια και k(p) = 1 για περιττή μετάθεση.

Έστω p \in S_{2n}. Θεωρούμε την προσδοκώμενη τιμή E(p) του όρου \displaystyle t = (-1)^{k(p)} \prod_{i=1}^n D_{i,p(i)}. Ισχύει \displaystyle \overline{D_{ab}} = 0, \overline{D_{ab} D_{ba}} = - 1/2 για a \neq b.

Αν η p έχει σταθερό σημείο k τότε \displaystyle t = (-1)^{k(p)} D_{kk} \cdot \prod_{i \neq k} D_{i,p(i)} = 0.

Επίσης, αν ισχύει p(k) = m και p(m) \neq k για κάποια m, k, τότε \displaystyle E(p) = (-1)^{k(p)} \overline{D_{km}} \cdot \overline{\prod_{i \neq k} D_{i,p(i)}} = 0.

Έτσι, περιοριζόμαστε στις μεταθέσεις που αποτελούνται από n εναλλαγές (το πλήθος τους είναι (2n-1)!!). Ισχύει \displaystyle E(p) = (-1)^n \overline{D_{m,p(m)} D_{p(m),m}} \cdot \overline{\prod_{i \neq m,p(m)} D_{i,p(i)}} = \frac{1}{2^n}.

Οπότε \displaystyle \overline{\det D} = \frac{(2n-1)!!}{2^n}.

(Παρεμπιπτόντως, για πίνακα περιττής διάστασης δεν υπάρχει κατάλληλη μετάθεση και η αντίστοιχη τιμή είναι 0).