Μαθήματα Ευρετικής. Χαμένοι στην μετάφραση…

                                   

   
 "Όταν τα αλόγα θα πάψουν να τρέχουν θα γκρεμιστεί  ο ουρανός,επίπεδος
   ,απέραντος,ασήκωτος,καταστρέφοντας τα πάντα."
                                                                                               Τσαρλς Μπουκόφσκι
    Διαβάζω σε ένα ιστότοπο σχετικό με την Ευρετική (Problem–solving):"...η επίλυση ενός προβλήματος εξαρτάται από την σαφή του διατύπωση  και από την γνωστική επάρκεια του λύτη."Δεν αντιλέγω, είναι εξαιρετικό για τους λάτρεις των αφορισμών,"κουμπώνει" όμως στην πραγματικότητα; Το πλέον σύνηθες λάθος στην επίλυση προβλημάτων,ανεξάρτητο εν μέρει από τους δυο παραπάνω παράγοντες είναι η παρανόηση στην αποκωδικοποίηση της εκφώνησης.Έχω την αίσθηση ότι κάθε πρόβλημα ή γρίφος που σέβεται τον εαυτό του, μοιάζει λίγο με αστυνομική υπόθεση,δεν αποκαλύπτει με την πρώτη ανάγνωση τα μυστικά του, η διατύπωση εσκεμμένα πρέπει να αφήνει και λίγο μυστήριο.Στην ανάρτηση λοιπόν θα ασχοληθούμε με ένα κλασσικό λογικό πρόβλημα με πολλαπλές αναφορές στο διαδίκτυο.Αναζήτησα στοιχεία για την πατρότητα του, δεν μπόρεσα να βρω κάτι. Ένα αλγοριθμικό προβληματάκι για "παιδιά" από 15 μέχρι 95 ετών που όμως είναι εύκολο να χαθεί κάποιος στην μετάφραση.

 Λοιπόν έχει ως εξής :

   
  Έστω ότι έχουμε 25 άλογα, δεν διαθέτουμε χρονόμετρο και επιτρέπεται να τα βάλουμε να αγωνιστούν  μόνο ανά πέντε. Πόσοι αγώνες απαιτούνται για να βρούμε τα τρία ταχύτερα άλογα. (Θεωρούμε πάντα ότι σε κάθε πεντάδα  που αγωνίζεται η σειρά κατάταξης καθορίζει και την ταχύτητα των αλόγων).

  Η πρώτη απάντηση.Χωρίζουμε τα άλογα τυχαία σε πέντε πενταδες, τα βάζουμε να αγωνιστούν σε πέντε κούρσες ,τα άλογα που νικήσουν σε καθέ κούρσα  θα αποτελούν την πεντάδα που θα τρέξει τον έκτο αγώνα και τα τρία πρώτα άλογα στον έκτο αγώνα θα είναι τα τρία ταχύτερα.Εκεί νομίζει κανείς ότι το πρόβλημα λύθηκε.Λύθηκε;
Αν,για παράδειγμα τα αποτελέσματα του πρώτου αγώνα είναι:

                                                            1. Αστραχάν

                                                            2.Κυρ.Μεντιος

                                                            3.Αστραπή

                                                            4.Κεραυνός

                                                            5. Πετεφρης

  Κανείς δεν μας εξασφαλίζει ότι το άλογο Αστραχάν έχει κάνει καλύτερο χρόνο από άλογα που ήρθαν στην δεύτερη,τρίτη θέση στους άλλους τέσσερεις αγώνες. Από υπόθεση γνωρίζουμε ότι δεν υπάρχει χρονόμετρο. Προκύπτει κάποια πληροφορία από τους πρώτους πέντε παραπάνω αγώνες; Είναι βέβαιο ότι τα άλογα Κεραυνός και Πετεφρής καθώς και όλα τα άλογα στους πέντε πρώτους αγώνες που ήρθαν στην τετάρτη και πέμπτη θέση δεν ανήκουν στα τρία ταχύτερα. Άρα, άμεσα, από τα 25 άλογα ,τα εξαιρούμε, οπότε μένουμε στα 15 άλογα που τερμάτισαν στις τρεις πρώτες θέσεις  στους πρώτους 5 αγώνες .Τώρα από τον έκτο αγώνα με τους νικητές των πρώτων πέντε αγώνων είναι βέβαιο ότι  το άλογο που θα τερματίσει πρώτο θα είναι το ταχύτερο όλων. Για παράδειγμα αν ο εκτός αγώνας είχε ως αποτέλεσμα :

                                                             1. Πήγασος

                                                             2.Μπαμπης

                                                             3. Αστραχάν

                                                             4.Βουκεφάλας

                                                             5. Μωρίς

 
 Ο Πήγασος είναι σίγουρα το ταχύτερο άλογο όλων. Οπότε δεν θα το βάλουμε να αγωνιστεί ξανά. Άρα μένουν 14  άλογα προς εξέταση για να εντοπίσουμε το δεύτερο και το τρίτο ταχύτερο άλογο. Από τον έκτο αγώνα διαπιστώνουμε ότι τα άλογα Βουκεφάλας και Μωρίς δεν διεκδικούν καμιά από τις τρεις πρώτες θέσεις  καθώς επίσης και όλα τα άλογα που νίκησαν στον πρώτο τους αγώνα. Εξαιρούμε ακόμα 6 άλογα  οπότε μένουν 8 άλογα προς εξέταση.

 Ο Αστραχάν τερμάτισε τρίτος στον έκτο αγώνα άρα  κανένα από τα άλογα που ξεπέρασε στον πρώτο του αγώνα  δεν διεκδικεί επίσης θέση στην τριάδα  έχουμε εξαιρέσει ήδη δυο από αυτά εξαιρούμε τα άλλα δυο και καταλήγουμε  στα 6 άλογα προς εξέταση.

  Ο Μπάμπης είναι το άλογο που ήρθε δεύτερο στον έκτο αγώνα ,άρα, από τα άλογα που ξεπέρασε –στον πρώτο του αγώνα- μόνο το επόμενο από αυτόν, αυτό που ήρθε τρίτο διεκδικεί θέση  στην τριάδα τα υπόλοιπα τρία εξαιρούνται. Από αυτά έχουμε εξαιρέσει ήδη τα δυο οπότε μένει να εξαιρέσουμε ακόμα 1 οπότε πέφτουμε στα 5 άλογα προς εξέταση.θα τα βάλουμε να τρέξουν σε ένα αγώνα (τον έβδομο). Το πρώτο και το δεύτερο άλογο κατά την κατάταξη στον αγώνα θα καλύψουν αντίστοιχα την δεύτερη και την τρίτη θέση της ζητούμενης τριάδας.
Αρα απαιτούνται τουλάχιστον 7 κούρσες για να βρούμε τα 3 ταχύτερα αλόγα από 25.

Μια γενίκευση  του προβλήματος στον σύνδεσμο:
http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle