Σε κάποια χώρα, μπορούμε να ταξιδέψουμε από κάθε πόλη σε οποιαδήποτε άλλη παρακάμπτοντας τις υπόλοιπες πόλεις. Είναι γνωστό το κόστος κάθε τέτοιας διαδρομής.
Έχουν σχεδιαστεί δύο διαδρομές ταξιδιού στις πόλεις της χώρας. Σε καθεμιά από τις διαδρομές αυτές, κάθε πόλη περιλαμβάνεται ακριβώς μία φορά. Ο σχεδιασμός της διαδρομής καθοδηγείται από την εξής αρχή:
ο αρχικός σταθμός (αφετηρία) της διαδρομής επιλέγεται αυθαίρετα, ενώ σε κάθε επόμενο βήμα μεταξύ των πόλεων στις οποίες δεν έχει φτάσει ακόμη η διαδρομή επιλέγεται εκείνη η πόλη στην οποία η διαδρομή από την προηγούμενη πόλη έχει ελάχιστο κόστος (αν τέτοιες πόλεις είναι πολλές επιλέγεται οποιαδήποτε από αυτές) αυτό συνεχίζεται μέχρι να περάσουμε από όλες τις πόλεις.
ο αρχικός σταθμός (αφετηρία) της διαδρομής επιλέγεται αυθαίρετα, ενώ σε κάθε επόμενο βήμα μεταξύ των πόλεων στις οποίες δεν έχει φτάσει ακόμη η διαδρομή επιλέγεται εκείνη η πόλη στην οποία η διαδρομή από την προηγούμενη πόλη έχει ελάχιστο κόστος (αν τέτοιες πόλεις είναι πολλές επιλέγεται οποιαδήποτε από αυτές) αυτό συνεχίζεται μέχρι να περάσουμε από όλες τις πόλεις.
Κατά το σχεδιασμό της δεύτερης διαδρομής ο αρχικός σταθμός επιλέγεται επίσης αυθαίρετα, ενώ σε κάθε επόμενο βήμα μεταξύ των πόλεων από τις οποίες η διαδρομή δεν έχει περάσει ακόμη, επιλέγεται η πόλη για την οποία η διαδρομή από την προηγούμενη πόλη έχει το μέγιστο κόστος.
Αποδείξτε ότι το συνολικό κόστος της πρώτης διαδρομής δεν είναι μεγαλύτερο από το συνολικό κόστος της δεύτερης.
11η Πανενωσιακή Μαθηματική Ολυμπιάδα 1977 (Τάλλιν)
