Μαθήματα ευρετικής με υλικά κουζίνας!! 'Ενα πρόβλημα βελτιστοποίησης με..αυγά.

                                                                          

• Η έμπνευση ..
Αναζητώντας στο διαδίκτυο μαθαίνουμε ότι:

  Το 1970, ο Appleton Douglas διευθυντής του δημοτικού σχολείου του Lancashire Carr Mill πραγματοποίησε το εξής πείραμα,έβαλε τους μαθητές του από το παράθυρο του δευτέρου ορόφου του σχολείου να αφήσουν αυγά να πέσουν  στο γρασίδι στο σχολικό προαύλιο , προς έκπληξη όλων τα περισσότερα αυγά δεν..έσπασαν. Στην ίδια πόλη ένας πυροσβέστης ανέβηκε σε μια σκάλα 70 ποδών και άφησε 10 αυγά να πέσουν στο γρασίδι.Το αποτέλεσμα ήταν 7 στα 10 να μην σπάσουν.Ένα αξιωματικός της RΑF πραγματοποίησε το ίδιο πείραμα  ρίχνοντας 18 αυγά  από ένα ελικόπτερο σε ύψος 150 ποδών.Τα 15 δεν έσπασαν.Στο διαδίκτυο διαβάζω ότι μια τοπική εφημερίδα η  Daily Express  μίσθωσε ένα μικρό αεροπλάνο από το οποίο ρίφθηκαν  60 αυγά  με ταχύτητα 150 μιλιών την ώρα.Το αποτέλεσμα;Το 60% των αυγών παρέμειναν άθικτα από την πτώση. 
Αλήθεια ή όχι τα παραπάνω πειράματα αποτέλεσαν την έμπνευση για ένα πολύ γνωστό προβληματάκι βελτιστοποίησης:

• Το πρόβλημα…

Το πρόβλημα τέθηκε σε υποψηφίους για πρόσληψη στην Google και διατυπώνεται ως εξής:

"Δίνονται δυο αυγά και ένα κτίριο 100 ορόφων το οποίο περιβάλλεται από πυκνό γρασίδι .Πως είναι δυνατό με την χρήση των δυο αυγών να βρεθεί- με τον ελάχιστο αριθμό ρίψεων- ο ψηλότερος όροφος από τον οποίο μπορούμε να ρίξουμε αυγό από το κτίριο και να μην σπάσει."

  •Μια προσέγγιση ίσως η απλούστερη που, όμως δεν λαμβάνει υπόψη τον ελάχιστο αριθμό ρίψεων είναι να ξεκινήσει κάποιος να ρίξει το ένα αυγό από τον πρώτο όροφο και αν δεν σπάσει να συνεχίσει να ανεβαίνει όροφο-όροφο και να κάνει ρίψεις μέχρι να σπάσει και έτσι να βρει τον ζητούμενο όροφο. Αν όμως ο όροφος είναι για παράδειγμα ο 80^ος θα πρέπει να κάνει 80 ρίψεις και δεν θα έχει καν χρησιμοποιήσει  το δεύτερο αυγό. Λύση μεν , αλλά όχι η βέλτιστη.

 •Ποια είναι η βέλτιστη λύση;

Το ερώτημα  είναι, ποιος είναι ο ελάχιστος αριθμός ρίψεων; Εστω Ε .

Αν ξεκινήσουμε από το Ε όροφο και ρίξουμε το πρώτο αυγό,

- αν σπάσει  μας μένουν Ε-1 ρίψεις μπορούμε να ξεκινήσουμε από το 1^ο  όροφο και να ανεβαίνουμε μέχρι να βρούμε το όροφο που θα σπάσει το αυγό.

-αν δεν σπάσει μας μένουν Ε-1 ρίψεις , θα ανέβουμε στο όροφο Ε+(Ε-1) και θα ρίξουμε από εκεί το πρώτο αυγό. 

-αν σπάσει τότε με το δεύτερο αυγό ξεκινάμε από τον όροφο Ε+1 και ανεβαίνουμε μέχρι να βρούμε τον ζητούμενο όροφο.

-Αν δεν σπάσει μας μένουν Ε-2 ρίψεις  ανεβαίνουμε στον Ε+(Ε-1)+(Ε-2)  όροφο  και συνεχίζουμε έτσι μ,μέχρι να βρούμε τον όροφο .

 Παρατηρούμε ότι Ε+(Ε-1)+(Ε-2)+(Ε-3)+…+3+2+1 είναι οι όροφοι που απαιτείται το πολύ να ανέβουμε , δηλαδή θα πρέπει να ισχύει:

                      Ε+(Ε-1)+(Ε-2)+(Ε-3)+…+3+2+1>=100

όμως οι όροι Ε,(Ε-1),(Ε-2),(Ε-3),…,3,2,1 είναι διαδοχικοί όροι αριθμητικής προόδου με πρώτο ορό το 1 και διαφορά το 1, οπότε θα ισχύει:

Ε+(Ε-1)+(Ε-2)+(Ε-3)+…+3+2+1=Ε(Ε+1)/2 και η αρχική ανίσωση παίρνει την μορφή:

                              Ε(Ε+1)/2>=100.

Σε αυτό το σημείο μπορούμε να κάνουμε απαλοιφή παρονομαστών , επιμεριστική ιδιότητα , μεταφορά στο πρώτο μέλος και επίλυση δευτεροβάθμιας ανίσωσης ή  αν δεν θυμόμαστε και πολλά από την σχολική άλγεβρα να χρησιμοποιήσουμε το Wolfram alpha και να υπολογίσουμε ότι: Ε>=14.

 Άρα 14 είναι ο ελάχιστος αριθμός ρίψεων.Μπορούμε να ανέβουμε διαδοχικά τους ορόφους 14,27,39,50,60,69,77,84,90,95,100 με την προϋπόθεση ότι το πρώτο αυγό δεν σπάει. Μόλις σπάσει επιστρέφουμε στον προηγούμενο όροφο της παραπάνω ακολουθίας ανεβαίνουμε  ένα όροφο και δοκιμάζουμε ρίψεις με το δεύτερο αυγό οντάς σίγουροι ότι θα μας έχει μείνει επαρκής αριθμός ρίψεων για να βρούμε τον ζητούμενο όροφο.

Άρα με 14 το πολύ ρίψεις μπορούμε να βρούμε τον ψηλότερο όροφο του κτιρίου  από τον οποίο το αυγό δεν σπάει.