Μια Ισότητα

Συντονιστής: Demetres

sot arm
Δημοσιεύσεις: 204
Εγγραφή: Τρί Μάιος 03, 2016 5:25 pm

Μια Ισότητα

#1

Μη αναγνωσμένη δημοσίευση από sot arm » Κυρ Μαρ 15, 2020 8:23 pm

Έστω 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##
Δημοσιεύσεις: 310
Εγγραφή: Τρί Απρ 18, 2017 3:40 pm

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

#2

Μη αναγνωσμένη δημοσίευση από min## » Κυρ Μαρ 15, 2020 11:15 pm

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

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

Ας είναι A'_{k} το σύνολο των άρτιων μεταθέσεων για τις οποίες ισχύει πως τα στοιχεία 1,2 βρίσκονται από τη θέση 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.
Για αυτές με δυάρι στην πρώτη θέση μπορούμε να αλλάξουμε τον άσσο σε δυάρι χωρίς να πειραχθεί η σχέση των αθροισμάτων των απολύτων (ο άσσος είναι το μικρότερο στοιχείο οπότε αν γίνει δυάρι/και επειδή η αρίθμηση αρχίζει από τη θέση 2/κάθε απόλυτο ελαττώνεται κατά 1) και έπειτα κάνοντας την παραπάνω μετατροπή να χρησιμοποιήσουμε ξανά την επαγωγική υπόθεση.


sot arm
Δημοσιεύσεις: 204
Εγγραφή: Τρί Μάιος 03, 2016 5:25 pm

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

#3

Μη αναγνωσμένη δημοσίευση από sot arm » Κυρ Μαρ 15, 2020 11:54 pm

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

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

Ας είναι A'_{k} το σύνολο των άρτιων μεταθέσεων για τις οποίες ισχύει πως τα στοιχεία 1,2 βρίσκονται από τη θέση 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.
Για αυτές με δυάρι στην πρώτη θέση μπορούμε να αλλάξουμε τον άσσο σε δυάρι χωρίς να πειραχθεί η σχέση των αθροισμάτων των απολύτων (ο άσσος είναι το μικρότερο στοιχείο οπότε αν γίνει δυάρι/και επειδή η αρίθμηση αρχίζει από τη θέση 2/κάθε απόλυτο ελαττώνεται κατά 1) και έπειτα κάνοντας την παραπάνω μετατροπή να χρησιμοποιήσουμε ξανά την επαγωγική υπόθεση.
:coolspeak: :coolspeak: Πολύ κομψά, ωραία λύση!

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


Αρμενιάκος Σωτήρης
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8444
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Μαρ 16, 2020 7:49 pm

Ας γράψουμε 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')| και |B_n(i,j)| = |B_n(i,j')| για κάθε j,j' \neq i.

Άρα |A_n(i,j)| = |B_n(i,j)| για κάθε 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
Δημοσιεύσεις: 204
Εγγραφή: Τρί Μάιος 03, 2016 5:25 pm

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

#5

Μη αναγνωσμένη δημοσίευση από sot arm » Δευ Μαρ 16, 2020 8:36 pm

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

Θεωρούμε τον πίνακα A με (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)}

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

Άρα x-1|(detA)' παραγωγίζοντας λοιπόν την (Ι) και θέτοντας όπου x=1 προκύπτει η ζητούμενη.

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


Αρμενιάκος Σωτήρης
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης