Μια Ισότητα

sot arm · #1

Έστω $n \geq 3$ και $A_{n}$ , $B_{n}$ τα σύνολα των άρτιων και περιττών μεταθέσεων του $\{1,2,...,n \}$ αντίστοιχα.
Να δειχθεί πως:

$\displaystyle{\sum_{\sigma \in A_{n}} \sum_{i=1}^{n}|i-\sigma(i)|=\sum_{\sigma \in B_{n}} \sum_{i=1}^{n}|i-\sigma(i)|}$

min## · #2

Καλησπέρα Σωτήρη.
Νομίζω βρήκα κάτι στοιχειώδες με επαγωγή:

Για n=3

το ζητούμενο προφανώς ισχύει.
Έστω ότι ισχύει για n=k-1

.

Ας είναι $A'_{k}$ το σύνολο των άρτιων μεταθέσεων για τις οποίες ισχύει πως τα στοιχεία 1,2

βρίσκονται από τη θέση

και πάνω.
Ας είναι και $B'_{k}$ το αντίστοιχο σύνολο για τις περιττές.
Έστω $X_{\sigma }= \sum_{i=1}^{k}\left | i-\sigma (i) \right |,\sigma \in A'_{k}$ και $Y_{\sigma }= \sum_{i=1}^{k}\left | i-\sigma (i) \right |,\sigma \in B'_{k}$
Η αντιμετάθεση των στοιχείων 1,2

δίνει ένα bijection μεταξύ των $A'_{k},B'_{k}$ .
Επιπλέον,μπορούμε εύκολα να δούμε πως διατηρεί τα $X_{\sigma }$ , $Y_{\sigma}$ ,δηλαδή $X_{\sigma }= X_{(1,2)\sigma },Y_{\sigma }= Y_{(1,2)\sigma }$ και αυτό γιατί οι όροι που περιέχουν τα 1,2

-οι μοναδικοί που αλλάζουν- είναι θετικοί (εξ'ορισμού των $A'_{k},B'_{k}$ ) με αποτέλεσμα το άθροισμα των απολύτων να μένει ίδιο.
Επομένως,μπορούμε να διαγράψουμε τα σύνολα $A'_{k},B'_{k}$ και να ασχοληθούμε με τα υπόλοιπα.
Τώρα,από επαγωγική υπόθεση μπορούμε να διαγράψουμε τις άρτιες/περιττές με άσσο στην πρώτη θέση :Διαγράφουμε τον άσσο/την πρώτη θέση,αλλάζουμε αναλόγως την αρίθμηση των υπόλοιπων θέσεων και θέτουμε $2\rightarrow 1,3\rightarrow 2..k\rightarrow k-1$ .
Για αυτές με δυάρι στην πρώτη θέση μπορούμε να αλλάξουμε τον άσσο σε δυάρι χωρίς να πειραχθεί η σχέση των αθροισμάτων των απολύτων (ο άσσος είναι το μικρότερο στοιχείο οπότε αν γίνει δυάρι/και επειδή η αρίθμηση αρχίζει από τη θέση

/κάθε απόλυτο ελαττώνεται κατά

) και έπειτα κάνοντας την παραπάνω μετατροπή να χρησιμοποιήσουμε ξανά την επαγωγική υπόθεση.

sot arm · #3

min## έγραψε: ↑
Κυρ Μαρ 15, 2020 11:15 pm
Καλησπέρα Σωτήρη.
Νομίζω βρήκα κάτι στοιχειώδες με επαγωγή:

Για το ζητούμενο προφανώς ισχύει.
Έστω ότι ισχύει για .

Ας είναι $A'_{k}$ το σύνολο των άρτιων μεταθέσεων για τις οποίες ισχύει πως τα στοιχεία βρίσκονται από τη θέση και πάνω.
Ας είναι και $B'_{k}$ το αντίστοιχο σύνολο για τις περιττές.
Έστω $X_{\sigma }= \sum_{i=1}^{k}\left | i-\sigma (i) \right |,\sigma \in A'_{k}$ και $Y_{\sigma }= \sum_{i=1}^{k}\left | i-\sigma (i) \right |,\sigma \in B'_{k}$
Η αντιμετάθεση των στοιχείων δίνει ένα bijection μεταξύ των $A'_{k},B'_{k}$ .
Επιπλέον,μπορούμε εύκολα να δούμε πως διατηρεί τα $X_{\sigma }$ , $Y_{\sigma}$ ,δηλαδή $X_{\sigma }= X_{(1,2)\sigma },Y_{\sigma }= Y_{(1,2)\sigma }$ και αυτό γιατί οι όροι που περιέχουν τα -οι μοναδικοί που αλλάζουν- είναι θετικοί (εξ'ορισμού των $A'_{k},B'_{k}$ ) με αποτέλεσμα το άθροισμα των απολύτων να μένει ίδιο.
Επομένως,μπορούμε να διαγράψουμε τα σύνολα $A'_{k},B'_{k}$ και να ασχοληθούμε με τα υπόλοιπα.
Τώρα,από επαγωγική υπόθεση μπορούμε να διαγράψουμε τις άρτιες/περιττές με άσσο στην πρώτη θέση :Διαγράφουμε τον άσσο/την πρώτη θέση,αλλάζουμε αναλόγως την αρίθμηση των υπόλοιπων θέσεων και θέτουμε $2\rightarrow 1,3\rightarrow 2..k\rightarrow k-1$ .
Για αυτές με δυάρι στην πρώτη θέση μπορούμε να αλλάξουμε τον άσσο σε δυάρι χωρίς να πειραχθεί η σχέση των αθροισμάτων των απολύτων (ο άσσος είναι το μικρότερο στοιχείο οπότε αν γίνει δυάρι/και επειδή η αρίθμηση αρχίζει από τη θέση /κάθε απόλυτο ελαττώνεται κατά ) και έπειτα κάνοντας την παραπάνω μετατροπή να χρησιμοποιήσουμε ξανά την επαγωγική υπόθεση.

Πολύ κομψά, ωραία λύση!

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

#4

Ας γράψουμε A_n(i,j)

για το σύνολο των άρτιων μεταθέσεων $\sigma$ του $[n] = \{1,2,\ldots,n\}$ με $\sigma(i) = j$ . Ομοίως ορίζουμε και το B_n(i,j)

.

Έχουμε |A_n(i,j)| = (n-1)!/2

, το πλήθος των άρτιων μεταθέσεων του $[n] \setminus \{i\}$ . Ομοίως |B_n(i,j)| = (n-1)!/2 = |A_n(i,j)|

.

Επίσης από συμμετρία είναι |A_n(i,j)| = |A_n(i,j')|

και

για κάθε $j,j' \neq i$ .

Άρα |A_n(i,j)| = |B_n(i,j)|

για κάθε

και

$\displaystyle \sum_{\sigma \in A_n} \sum_{i=1}^{n} |i-\sigma(i)| = \sum_{j=1}^{n} \sum_{i=1}^{n} \sum_{j \in A_n(i,j)} |i-j| = \sum_{j=1}^{n} \sum_{i=1}^{n} \sum_{j \in B_n(i,j)} |i-j|\sum_{\sigma \in B_n} \sum_{i=1}^{n} |i-\sigma(i)|$

sot arm · #5

Μετά την ωραία λύση του κυρίου Δημήτρη, βάζω και την δικιά μου.

Θεωρούμε τον πίνακα

με $(a_{ij}) = x^{|i-j|}$ , τότε:

$\displaystyle{det(A)=\sum_{\sigma \in S_{n}}\epsilon(\sigma)x^{|1-\sigma(1)|}\cdot...x^{|n-\sigma(n)|}=\sum_{\sigma \in A_{n}}x^{\sum_{i=1}^{n}|i-\sigma(i)|} - \sum_{\sigma \in B_{n}}x^{\sum_{i=1}^{n}|i-\sigma(i)|} (I)}$

Στον πίνακα

με γραμμοπράξεις αφαιρώ απο την 2η γραμμή την 1η και από την τρίτη γραμμή την πρώτη, βλέπω ότι: $(x-1)^{2} | det(A)$ .

Άρα x-1|(detA)'

παραγωγίζοντας λοιπόν την (Ι) και θέτοντας όπου x=1

προκύπτει η ζητούμενη.

Υ.Γ. Συγχωρέστε μου που δεν γράφω τον πίνακα, αλλά με ζορίζει αρκετά να γράψω πίνακες σε Latex

Μια Ισότητα

Μια Ισότητα

Re: Μια Ισότητα

Re: Μια Ισότητα

Re: Μια Ισότητα

Re: Μια Ισότητα

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