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

[Demetres]

Έχουμε αριθμημένα χαρτιά τοποθετημένα σε τυχαία διάταξη. Ονομάζουμε ένα ζευγάρι χαρτιών με αντεστραμμένο αν το χαρτί είναι στα αριστερά του χαρτιού . Π.χ. η διάταξη έχει τρία αντεστραμμένα ζεύγη χαρτιών , , και .

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



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

[Anon_Ymos]

Έστω Ν το πλήθος των φύλλων. Σε κάθε διάταξη Δ αντιστοιχούμε ένα διάνυσμα όπου το ν-ιοστό στοχείο είναι 1 αν το χαρτί δεν έχει εκτελέσει τη σειρά του και -1 αν την έχει εκτελέσει. Για παράδειγμα στην αρχή αποτελείται μόνο από 1 ενώ στο τέλος αποτελείται μόνο απο -1. Ορίζουμε το διάνυσμα αν Ν άρτιος και αν Ν περιττός και επίσης τη συνάρτηση

Αρκεί δείξουμε ότι σε κάθε κίνηση όπου ένα φύλλο εκτελεί τη σειρά του (δηλαδή πάμε από τη διάταξη στην ) το πλήθος των inversions στη διάταξη αλλάζει ακριβώς κατά . Αυτό αρκεί επειδή η Φ της τελευταίας και της πρώτης διάταξης είναι ίσες.

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

Στην πρώτη περίπτωση τα inversions που χαλάνε είναι αυτά τα αφού είναι αριθμοί μικρότεροι αυτού που μετακινείται, αφού η μετακίνηση τους έχει γίνει ήδη. Τα inversions που δημιουργούνται είναι αυτά τα αφού είναι αριθμοί μεγαλύτεροι αυτού που μετακινείται, αφού η μετακίνηση τους δεν έχει γίνει ακόμα. Άρα συνολικά το πλήθος των inversions αλλάζει κατά .

Στη δεύτερη περίπτωση με το ίδιο τρόπο έχουμε ότι συνολικά αλλάζει κατά αφού το φύλλο πάει προς τα πίσω.

Όμως . Αυτό προκύπτει με απλές πράξεις αλλά και αν δει κανείς ότι τα έχουν μετακινηθεί μία θέση πιο πίσω οπότε ο συντελεστής τους γίνεται -2 σε σχέση με πριν. Τα 1,-1 φεύγουν. Παρομοίως και . Άρα έχουμε το ζητούμενο.

[Demetres]

Εξαιρετικά!

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