Έχουμε οκτώ κομμάτια μιας αλυσίδας που αποτελούνται από επτά κρίκους το καθένα. Οι ακριανοί κρίκοι του κάθε τμήματος είναι κλειστοί. Θέλουμε να ενώσουμε και τα οκτώ τμήματα και να φτιάξουμε μια μεγάλη κυκλική αλυσίδα (οι άκρες της να ενώνονται).
Ένας τεχνίτης αναλαμβάνει να ανοίξει και να κλείσει όσους κρίκους του πούμε με κόστος 1 ευρώ ανά κρίκο (άνοιγμα – πέρασμα – κλείσιμο). Ποιο είναι το ελάχιστο κόστος που απαιτείται για να φτιάξουμε την αλυσίδα και ποιους κρίκους θα ζητήσουμε να μας ανοίξει;
Λύση:
Ο προφανής τρόπος είναι να ανοίξουμε έναν ακριανό κρίκο σε κάθε τμήμα της αλυσίδας και μέσα του να περάσουμε την κλειστή άκρη του επόμενου τμήματος. Αφού έχουμε οκτώ τέτοια τμήματα, το κόστος αυτής της εργασίας είναι 8 ευρώ.
Υπάρχει όμως και καλύτερος τρόπος:
Ανοίγουμε όλους τους κρίκους του ενός τμήματος με κόστος 7 ευρώ. Έτσι έχουμε τώρα επτά κομμάτια αλυσίδας και επτά ανοικτούς κρίκους. Ενώνουμε τα άκρα δύο τμημάτων της αλυσίδας με κάθε έναν από τους επτά κρίκους και φτάνουμε στο επιθυμητό αποτέλεσμα.
Πηγή: pantsik.awardspace.com
