Σε κάποια χώρα, μπορούμε να ταξιδέψουμε από κάθε πόλη σε οποιαδήποτε άλλη παρακάμπτοντας τις υπόλοι-πες πόλεις. Είναι γνωστό το κόστος κάθε τέτοιας διαδρομής. Έχουν σχεδιαστεί δύο διαδρομές ταξιδιού στις πόλεις της χώρας. Σε καθεμιά από τις διαδρομές αυτές, κάθε πόλη περιλαμβάνεται ακριβώς μία φορά. Ο σχεδιασμός της διαδρομής καθοδηγείται από την εξής αρχή:
ο αρχικός σταθμός (αφετηρία) της διαδρομής επιλέγεται αυθαίρετα, ενώ σε κάθε επόμενο βήμα μεταξύ των πόλεων στις οποίες δεν έχει φτάσει ακόμη η διαδρομή επιλέγεται εκείνη η πόλη στην οποία η διαδρομή από την προηγούμενη πόλη έχει ελάχιστο κόστος (αν τέτοιες πόλεις είναι πολλές επιλέγεται οποιαδήποτε από αυτές) αυτό συνεχίζεται μέχρι να περάσουμε από όλες τις πόλεις. Κατά το σχεδιασμό της δεύτερης διαδρομής ο αρχικός σταθμός επιλέγεται επίσης αυθαίρετα, ενώ σε κάθε επόμενο βήμα μεταξύ των πόλεων από τις οποίες η διαδρομή δεν έχει περάσει ακόμη, επιλέγεται η πόλη για την οποία η διαδρομή από την προηγούμενη πόλη έχει το μέγιστο κόστος. Αποδείξτε ότι το συνολικό κόστος της πρώτης διαδρομής δεν είναι μεγαλύτερο από το συνολικό κόστος της δεύτερης.
11η Πανενωσιακή Μαθηματική Ολυμπιάδα 1977 (Τάλλιν)
Κατά πάσα πιθανότητα, θα υπάρχει κάποιο μαγικό κόλπο που οδηγεί σε λύση των 3-5 σειρών, αλλά εγώ δεν μπόρεσα να σκεφτώ κάτι καλύτερο και μικρότερο από τα παρακάτω, που θα χρειαστεί μάλιστα να το σπάσω και σε δόσεις για να χωρέσει.
ΑπάντησηΔιαγραφήΈστω ν ο συνολικός αριθμός των πόλεων.
Οι συνολικές μετακινήσεις από πόλη σε πόλη που περιλαμβάνει κάθε διαδρομή είναι ν-1.
Έστω ότι, με τον τρόπο που ορίζεται, ως 1η διαδρομή επιλέγεται η ΑΒΓΔ…ΦΧΨΩ. Αυτό συνεπάγεται τα εξής:
Ως πρώτη μετακίνηση επιλέγεται η φθηνότερη (έστω η ΑΒ) από ν-1 δυνατές μετακινήσεις και απορρίπτονται ως μεγαλύτερου ή ίσου κόστους οι υπόλοιπες ν-2 (ΑΓ, ΑΔ, … , ΑΨ, ΑΩ). Επομένως, αν η 2η διαδρομή ξεκινούσε από την πόλη Α, θα υπήρχαν ν-2 δυνατές μετακινήσεις μεγαλύτερου ή ίσου κόστους της ΑΒ, και 1 ίσου κόστους (η ίδια η ΑΒ).
Ως επόμενη μετακίνηση επιλέγεται η φθηνότερη (έστω η ΒΓ) από ν-2 δυνατές μετακινήσεις και απορρίπτονται ως μεγαλύτερου ή ίσου κόστους οι υπόλοιπες ν-3 (ΒΔ, ΒΕ, … , ΒΨ, ΒΩ). Επομένως, αν η 2η διαδρομή ξεκινούσε από την πόλη Β, θα υπήρχαν ν-3 τουλάχιστον δυνατές μετακινήσεις μεγαλύτερου ή ίσου κόστους της ΒΓ, και 1 τουλάχιστον ίσου κόστους (η ίδια η ΒΓ). Επίσης γνωρίζουμε ότι η επίσης πιθανή μετακίνηση ΒΑ της 2ης διαδρομής είναι ίσου κόστους με τη μετακίνηση ΑΒ της 1ης διαδρομής.
Ως επόμενη επιλέγεται η φθηνότερη (έστω η ΓΔ) από ν-3 δυνατές μετακινήσεις και απορρίπτονται ως μεγαλύτερου ή ίσου κόστους οι υπόλοιπες ν-4 (ΓΕ, ΓΖ, … , ΓΨ, ΓΩ). Επομένως, αν η 2η διαδρομή ξεκινούσε από την πόλη Γ, θα υπήρχαν ν-4 τουλάχιστον δυνατές μετακινήσεις μεγαλύτερου ή ίσου κόστους της ΓΔ, και 1 τουλάχιστον ίσου κόστους (η ίδια η ΓΔ). Επίσης γνωρίζουμε ότι η πιθανή μετακίνηση ΓΒ της 2ης διαδρομής είναι ίσου κόστους με τη μετακίνηση ΒΓ της 1ης διαδρομής, ενώ η επίσης πιθανή ΓΑ της 2ης είναι μεγαλύτερου ή ίσου κόστους της ΑΒ της 1ης.
…………………………………………………………………………………………………………………………………
Ως (ν-2)η επιλέγεται η φθηνότερη (έστω η ΧΨ) από 2 δυνατές μετακινήσεις και απορρίπτεται ως μεγαλύτερου ή ίσου κόστους η άλλη (ΧΩ). Επομένως, αν η 2η διαδρομή ξεκινούσε από την πόλη Χ, θα υπήρχε 1 τουλάχιστον δυνατή μετακίνηση μεγαλύτερου ή ίσου κόστους της ΧΨ, και 1 τουλάχιστον ίσου κόστους (η ίδια η ΧΨ). Επίσης γνωρίζουμε ότι η πιθανή μετακίνηση ΧΦ της 2ης διαδρομής είναι ίσου κόστους με τη μετακίνηση ΦΧ της 1ης διαδρομής, ενώ οι επίσης πιθανές ΧΥ, ΧΤ,…ΧΓ, ΧΒ, ΧΑ της 2ης είναι μεγαλύτερου ή ίσου κόστους αντίστοιχων τμημάτων της 1ης.
ΑπάντησηΔιαγραφήΩς (ν-1)η και τελευταία επιλέγεται αναγκαστικά η μόνη απομένουσα δυνατή ΨΩ. Επομένως, αν η 2η διαδρομή ξεκινούσε από την πόλη Ψ, θα υπήρχε 1 τουλάχιστον δυνατή μετακίνηση ίσου κόστους (η ίδια η ΨΩ). Επίσης γνωρίζουμε ότι η πιθανή μετακίνηση ΨΧ της 2ης διαδρομής είναι ίσου κόστους με τη μετακίνηση ΧΨ της 1ης διαδρομής, ενώ οι επίσης πιθανές ΨΦ, ΨΥ,…,ΨΓ, ΨΒ, ΨΑ της 2ης είναι μεγαλύτερου ή ίσου κόστους αντίστοιχων τμημάτων της 1ης.
Τέλος, αν η 2η διαδρομή ξεκινούσε από την πόλη Ω, όπως φαίνεται από τα παραπάνω, όλες οι δυνατές μετακινήσεις ΩΨ, ΩΧ,…,ΩΓ, ΩΒ, ΩΑ είναι η καθεμιά τους μεγαλύτερου ή ίσου κόστους με αντίστοιχα τμήματα της 1ης διαδρομής.
Διαπιστώνεται επομένως ότι από οποιαδήποτε πόλη και αν ξεκινήσει η 2η διαδρομή, θα υπάρχουν ν-1 υποψήφιες επιλογές πρώτων μετακινήσεων, που είναι μεγαλύτερου ή ίσου κόστους από ένα αντίστοιχο τμήμα της 1ης διαδρομής, και από αυτές επιλέγεται αυτή που έχει το μέγιστο κόστος. Στην εξέλιξη της 2ης διαδρομής προς τις επόμενες πόλεις διαγράφονται κάθε φορά από υποψήφιες επόμενες μετακινήσεις εκείνες (από τις αρχικές ν-1) που περιλαμβάνουν ως προορισμούς πόλεις από τις οποίες έχει ήδη περάσει η 2η διαδρομή και από τις απομένουσες επιλέγεται αυτή που έχει το μέγιστο κόστος. Θα υπάρχουν πάντως σε κάθε πόλη αρκετές (περισσότερες από 1 ενδιάμεσα έως τουλάχιστον 1 στο τέλος) υποψήφιες μετακινήσεις, ώστε να είναι εφικτή η επιλογή κάποιας που να είναι μεγαλύτερου ή ίσου κόστους από ένα διαφορετικό κάθε φορά τμήμα της 1ης διαδρομής.
Όπως λοιπόν προκύπτει από τα πιο πάνω, οπωσδήποτε κι αν ξεκινήσει και εξελιχθεί η 2η διαδρομή, κάθε τμήμα της μπορεί να αντιστοιχιστεί με ένα διαφορετικό κάθε φορά τμήμα της 1ης διαδρομής, έτσι ώστε τα τμήματα της 2ης διαδρομής να είναι μεγαλύτερου ή ίσου κόστους των αντίστοιχων τμημάτων της 1ης διαδρομής και κατά συνέπεια η 2η διαδρομή θα είναι αναγκαστικά μεγαλύτερου ή ίσου κόστους της 1ης.