Η γενίκευση του αλγορίθμου για τον γρίφο των μεταγγίσεων και ένα παιδικό ποίημα με εφτάρια που ήταν πολύ σκληρό για να..πεθάνει

   Στην κινηματογραφική ταινία Πολύ σκληρός για πεθάνει:Η εκδίκηση, ο Σάιμον Γκρούμπερ- ο κακός της ταινίας-θέτει στους δυο ήρωες της ταινίας μια σειρά γρίφων προκείμενου να απασφαλίσουν  ισαρίθμους εκρηκτικούς μηχανισμούς.Ο πρώτος γρίφος είναι ένα παιδικό ποιηματάκι που δεσπόζει το επτά από το βιβλίο του Χάουαρντ Ίβς, Μεγάλες στιγμές των μαθηματικών.

           «Καθώς πήγαινα στο Σαιντ Ιβς

             Συνάντησα ένα άνδρα με επτά  γυναίκες.

             Κάθε γυναίκα κουβαλούσε επτά  σάκους.

             Κάθε σάκος είχε μέσα επτά  γάτες.

             Κάθε γάτα  είχε  επτά  γατάκια.

             Γατάκια,γάτες,σάκοι,και γυναίκες.

              Πόσοι πηγαίνουν στο  Σαιντ Ιβς;»

 Είναι προφανές ότι μόνο ο αφηγητής πηγαίνει στο Σαιντ Ιβς. Ακολούθως, στην συνέχεια της ταινίας, ο σατανικός Σάιμον Γκρούμπερ θέτει στους πρωταγωνιστές και ένα πρόβλημα  κατάλληλο για συνταξιούχους υπάλληλους της ΕΥΔΑΠ, πολιτικούς που βάζουν νερό στο κρασί τους, την Κυρά Βαγγελιώ και εν γένει όσους δεν πάσχουν από υδρωπικία.Τον γρίφο των…μεταγγίσεων.

  Πως από μια πηγή με τρεχούμενο νερό, μπορούμε να λάβουμε ακριβώς 4 λίτρα νερού χρησιμοποιώντας ένα δοχείο 3 λίτρων και ένα δοχείο 5 λίτρων;

Ένα κλασσικό πρόβλημα που η λύση του μπορεί να γενικευτεί με τον παρακάτω αλγόριθμο:

Αλγόριθμος μεταγγίσεων δυο δοχείων

  Έστω δυο δοχεία χωρητικότητας μ και ν λίτρων όπου μ και ν θετικοί ακέραιοι αριθμοί πρώτοι μεταξύ τους και μια πηγή με τρεχούμενο νερό.Ο στόχος είναι να βρεθεί κατάλληλη ακολουθία μεταγγίσεων  ώστε να λάβουμε σε ένα από τα δοχεία ακριβώς κ λίτρα νερό με κ θετικό ακέραιο τέτοιο ώστε 1< = κ  < =μ+ν-1

Εκτελούμε τα παρακάτω βήματα:

1^ο Αν το μεγαλύτερο δοχείο είναι άδειο, το γεμίζουμε από την πηγή.

2^ο Αν το μικρότερο δοχείο δεν είναι άδειο τότε αδειάζουμε το νερό στο έδαφος.

3^ο Αν υπάρχει νερό στο μεγαλύτερο δοχείο το μεταγγίζουμε στο μικρότερο δοχείο μέχρι ότου να αδειάσει ή να γεμίσει το μικρότερο δοχείο.

4^o Επαναλαμβάνουμε τα παραπάνω βήματα μέχρι να λάβουμε σε ένα από τα δυο δοχεία τα κ λίτρα νερού.

Στην εν λόγω ταινία το πρόβλημα που τίθεται αφορά δυο δοχεία 5 και 3 λίτρων  και θέλουμε να λάβουμε σε ένα από τα δυο δοχεία ακριβώς 4 λίτρα νερό.