Πανέμορφη συνδυαστική

Συντονιστές: Demetres, socrates, silouan

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

Πανέμορφη συνδυαστική

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Μάιος 13, 2018 8:26 pm

Έχουμε n αριθμημένα χαρτιά 1,2,3,\dots,n τοποθετημένα σε τυχαία διάταξη. Ονομάζουμε ένα ζευγάρι χαρτιών (a,b) με a>b αντεστραμμένο αν το χαρτί a είναι στα αριστερά του χαρτιού b. Π.χ. η διάταξη 3,1,4,2 έχει τρία αντεστραμμένα ζεύγη χαρτιών (3,1), (3,2), και (4,2).

Αφαιρούμε το χαρτί 1 και το επανατοποθετούμε πίσω στην διάταξη αλλά στην αντίθετη θέση: Δηλαδή, αν το χαρτί 1 βρισκόταν στην θέση i από αριστερά, τώρα θα βρίσκεται στην θέση i από δεξιά. Μετά αφαιρούμε το χαρτί 2 και το επανατοποθετούμε με τον ίδιο τρόπο κ.ο.κ. μέχρι να αφαιρέσουμε και να επανατοποθετήσουμε το χαρτί n. Π.χ. αν ξεκινήσουμε από την διάταξη 3,1,4,2 τότε θα πάρουμε κατά σειρά τις διατάξεις

\displaystyle 3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1.

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



Λέξεις Κλειδιά:
Anon_Ymos
Δημοσιεύσεις: 1
Εγγραφή: Τρί Νοέμ 06, 2018 5:37 pm

Re: Πανέμορφη συνδυαστική

#2

Μη αναγνωσμένη δημοσίευση από Anon_Ymos » Τρί Νοέμ 06, 2018 7:00 pm

Έστω Ν το πλήθος των φύλλων. Σε κάθε διάταξη Δ αντιστοιχούμε ένα διάνυσμα \overrightarrow{X(\Delta )}=\begin{bmatrix} -1 & 1 & ... & -1 \end{bmatrix} όπου το ν-ιοστό στοχείο είναι 1 αν το χαρτί δεν έχει εκτελέσει τη σειρά του και -1 αν την έχει εκτελέσει. Για παράδειγμα στην αρχή αποτελείται μόνο από 1 ενώ στο τέλος αποτελείται μόνο απο -1. Ορίζουμε το διάνυσμα A^{T} =\begin{bmatrix} -N+1& ...& -3& -1& 1& 3& ...& N-1 \end{bmatrix} αν Ν άρτιος και A^{T} =\begin{bmatrix} -N+1& ...& -2& 0& 2& 4& ...& N-1 \end{bmatrix} αν Ν περιττός και επίσης τη συνάρτηση \Phi (\overrightarrow{X})=\overrightarrow{X}^{Τ} \cdot A

Αρκεί δείξουμε ότι σε κάθε κίνηση όπου ένα φύλλο εκτελεί τη σειρά του (δηλαδή πάμε από τη διάταξη \Delta ^{-1} στην \Delta ) το πλήθος των inversions στη διάταξη αλλάζει ακριβώς κατά \frac{\Phi(\overrightarrow{X(\Delta^{-1})}-\Phi(\overrightarrow{X(\Delta)}}{2}. Αυτό αρκεί επειδή η Φ της τελευταίας και της πρώτης διάταξης είναι ίσες.

Εφόσον μια κίνηση αφορά μόνο τα εσωτερικά φύλλα (δηλαδή αν το πέμπτο από αριστερά μετακινείται τότε τα τέσσερα δεξιότερα και τέσσερα αριστερότερα μένουν αμετάβλητα) μπορούμε να θεωρήσουμε ότι η διάταξη είναι της μορφής 1 X_{1} X_{2} X_{3} ... X_{k} και γίνεται X_{1} X_{2} X_{3} ... X_{k} -1. Αλλίως είναι X_{1} X_{2} X_{3} ... X_{k} 1 και γίνεται -1 X_{1} X_{2} X_{3} ... X_{k} .

Στην πρώτη περίπτωση τα inversions που χαλάνε είναι αυτά τα X_{i}=-1 αφού είναι αριθμοί μικρότεροι αυτού που μετακινείται, αφού η μετακίνηση τους έχει γίνει ήδη. Τα inversions που δημιουργούνται είναι αυτά τα X_{i}=1 αφού είναι αριθμοί μεγαλύτεροι αυτού που μετακινείται, αφού η μετακίνηση τους δεν έχει γίνει ακόμα. Άρα συνολικά το πλήθος των inversions αλλάζει κατά \sum X_{i}.

Στη δεύτερη περίπτωση με το ίδιο τρόπο έχουμε ότι συνολικά αλλάζει κατά -\sum X_{i} αφού το φύλλο πάει προς τα πίσω.

Όμως \Phi (1 X_{1} X_{2} X_{3} ... X_{k})-\Phi (X_{1} X_{2} X_{3} ... X_{k} -1) = 2*X_{1}+2*X_{2}+...+2*X_{k}. Αυτό προκύπτει με απλές πράξεις αλλά και αν δει κανείς ότι τα X_{i} έχουν μετακινηθεί μία θέση πιο πίσω οπότε ο συντελεστής τους γίνεται -2 σε σχέση με πριν. Τα 1,-1 φεύγουν. Παρομοίως και \Phi (X_{1} X_{2} X_{3} ... X_{k} 1)-\Phi (-1 X_{1} X_{2} X_{3} ... X_{k}) = -2*X_{1}-2*X_{2}-...-2*X_{k}. Άρα έχουμε το ζητούμενο.


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

Re: Πανέμορφη συνδυαστική

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Νοέμ 07, 2018 9:39 am

Εξαιρετικά!

Μπήκε στον διαγωνισμό junior των Αμερικανών πέρυσι. Η επίσημη λύση είναι η εξής: Όταν μετακινούμε το χαρτί k αυτό σκεφτόμαστε ότι αλλάζει και γίνεται n+k. Πως αλλάζουν τα αντεστραμμένα ζεύγη; Αλλάζουν μόνο αυτά που περιέχουν το k ή αργότερα το n+k. Αρχικά έχουμε ένα της μορφής (a,k) για κάθε a που είναι πριν το k. (Όλα τα χαρτιά είναι μεγαλύτερά του k!) Τελικά, έχουμε ένα της μορφής (k,b) για κάθε b μετά το k. (Όλα τα χαρτιά είναι μεγαλύτερά του n+k) Άρα δεν υπάρχει καμία αλλαγή. Αν τώρα στην τελική διάταξη αλλάξουμε τα n+k πίσω σε k πάλι δεν θα προκύψει αλλαγή.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

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

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