Σε κάθε κορυφή ενός κανονικού πενταγώνου αντιστοιχίζουμε έναν ακέραιο αριθμό, έτσι ώστε το άθροισμα των πέντε αριθμών να είναι θετικό.
Αν σε τρεις διαδοχικές κορυφές βρίσκονται οι αριθμοί \(x,y,z\), με \(y<0\), επιτρέπεται η αντικατάσταση
\[(x,y,z)\longmapsto(x+y,-y,z+y).\]Η πράξη επαναλαμβάνεται όσο υπάρχει αρνητικός αριθμός. Να αποδειχθεί ότι η διαδικασία τερματίζεται αναγκαστικά ύστερα από πεπερασμένο αριθμό πράξεων.
Δείτε τη λύση
1. Οι αριθμοί ως διαφορές
Έστω \(a_1,a_2,a_3,a_4,a_5\) οι αριθμοί στις κορυφές, με κυκλική σειρά, και
\[S=a_1+a_2+a_3+a_4+a_5>0.\]Κατασκευάζουμε μια ακολουθία \((b_i)_{i\in\mathbb Z}\) έτσι ώστε
\[a_i=b_{i+1}-b_i\qquad\text{και}\qquad b_{i+5}=b_i+S.\]Αυτό είναι δυνατό: επιλέγουμε αυθαίρετα το \(b_1\), ορίζουμε διαδοχικά \(b_{i+1}=b_i+a_i\) και επεκτείνουμε την ακολουθία με τη σχέση \(b_{i+5}=b_i+S\).
2. Τι σημαίνει η επιτρεπτή πράξη
Αν \(a_i=y<0\), τότε
\[b_{i+1}-b_i=y<0,\]άρα \(b_i>b_{i+1}\): δύο γειτονικοί όροι βρίσκονται σε λανθασμένη σειρά.
Αν ανταλλάξουμε τους \(b_i\) και \(b_{i+1}\), οι τρεις επηρεαζόμενες διαφορές μετατρέπονται ως εξής:
\[(x,y,z)\longmapsto(x+y,-y,z+y).\]Επομένως κάθε επιτρεπτή πράξη στο πεντάγωνο ισοδυναμεί με την ανταλλαγή δύο γειτονικών όρων \(b_i,b_{i+1}\) που αποτελούν αναστροφή.
3. Ο μετρητής που πάντα μειώνεται
Μετράμε τις αναστροφές της διπλά άπειρης ακολουθίας, θεωρώντας ίδιες δύο αναστροφές που προκύπτουν η μία από την άλλη με μετατόπιση πέντε θέσεων. Ισοδύναμα, μετράμε τα ζεύγη
\[(i,j),\qquad 1\le i\le5,quad i<j,quad b_i>b_j.\]Ο αριθμός τους είναι πεπερασμένος. Πράγματι, επειδή \(b_{j+5}=b_j+S\) και \(S>0\), για κάθε σταθερό \(i\) οι όροι \(b_j\) γίνονται τελικά μεγαλύτεροι από το \(b_i\).
Κάθε επιτρεπτή κίνηση ανταλλάσσει ένα γειτονικό ανεστραμμένο ζεύγος. Όπως στη γνωστή ταξινόμηση με διαδοχικές ανταλλαγές, η συγκεκριμένη αναστροφή εξαφανίζεται, ενώ η σχετική διάταξη με όλους τους άλλους όρους δεν αλλάζει. Άρα ο αριθμός των αναστροφών μειώνεται ακριβώς κατά 1.
Δεν μπορεί, όμως, ένας μη αρνητικός ακέραιος να μειώνεται κατά 1 επ' άπειρον. Συνεπώς, ύστερα από πεπερασμένο αριθμό πράξεων, δεν απομένει καμία αναστροφή, δηλαδή κανένα \(a_i<0\). Η διαδικασία επομένως τερματίζεται.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου