Ενότητα 08.5 – Ερωτήσεις – Ασκήσεις – Σελίδα 103 – ΠΛΗΡΟΦΟΡΙΚΗ Α΄ ΓΥΜΝΑΣΙΟΥ – Απαντήσεις – Λύσεις – ΠΛΗΡΟΦΟΡΙΚΗ Α΄ ΓΥΜΝΑΣΙΟΥ

(Πηγή: Βιβλίο Μαθητή, Πληροφορική Α΄ Γυμνασίου, §8.5 Ερωτήσεις - Ασκήσεις, σελ. 103. Οι εκφωνήσεις είναι αυτούσιες από το σχολικό βιβλίο.)

Ερωτήσεις - Ασκήσεις

Άσκηση 1 (σελ. 103)

Διάσχιση Γέφυρας. Πέντε άνθρωποι θέλουν να περάσουν μια γέφυρα. Είναι όμως νύχτα και διαθέτουν μόνο μια λάμπα με φυτίλι διάρκειας 30 λεπτών. Η γέφυρα αντέχει το πολύ δύο άτομα, οπότε δεν μπορούν να περάσουν όλοι μαζί. Για να περάσουν τη γέφυρα χρειάζονται οπωσδήποτε τη λάμπα. Επίσης, κάθε ένας χρειάζεται διαφορετικό χρόνο για να περάσει τη γέφυρα. Ο πιο γρήγορος χρειάζεται 1 λεπτό, ο επόμενος 3 λεπτά, οι υπόλοιποι 6, 8 και 12 λεπτά αντίστοιχα. Πώς θα περάσουν απέναντι;

Σκέψη / Μεθοδολογία: Το πρόβλημα λύνεται με μια στρατηγική: κάθε φορά που περνούν δύο άτομα μαζί, ο χρόνος που «κοστίζει» είναι ο χρόνος του πιο αργού από τους δύο (γιατί περπατούν μαζί). Άρα, θέλουμε οι δύο πιο αργοί (8΄ και 12΄) να περάσουν μαζί σε ένα μόνο πέρασμα, ώστε το «ακριβό» πέρασμα των 12 λεπτών να πληρωθεί μία μόνο φορά. Για να γίνει αυτό, χρειάζεται κάποιος να έχει ήδη περάσει απέναντι για να φέρει πίσω τη λάμπα πριν περάσουν οι δύο αργοί, και κάποιος να είναι ήδη απέναντι για να πάρει πίσω τη λάμπα μετά. Χρησιμοποιούμε γι' αυτόν τον ρόλο τους δύο πιο γρήγορους (1΄ και 3΄), αφού οι επιστροφές τους «κοστίζουν» λιγότερο.

Λύση:

1. Ονομάζουμε τους πέντε ανθρώπους Α(1΄), Β(3΄), Γ(6΄), Δ(8΄), Ε(12΄), με τον χρόνο διάσχισης τους σε παρένθεση.
2. 1ο πέρασμα: περνούν μαζί οι Α και Β. Κοστίζει max(1,3) = 3 λεπτά. Σύνολο χρόνου: 3΄. Απέναντι: Α, Β. Στην αρχική πλευρά: Γ, Δ, Ε.
3. 2η επιστροφή: επιστρέφει ο Α με τη λάμπα. Κοστίζει 1 λεπτό. Σύνολο: 4΄. Απέναντι: Β. Αρχική πλευρά: Α, Γ, Δ, Ε.
4. 3ο πέρασμα: περνούν μαζί οι Δ και Ε (οι δύο πιο αργοί, μαζί, μία φορά). Κοστίζει max(8,12) = 12 λεπτά. Σύνολο: 16΄. Απέναντι: Β, Δ, Ε. Αρχική πλευρά: Α, Γ.
5. 4η επιστροφή: επιστρέφει ο Β με τη λάμπα. Κοστίζει 3 λεπτά. Σύνολο: 19΄. Απέναντι: Δ, Ε. Αρχική πλευρά: Α, Β, Γ.
6. 5ο πέρασμα: περνούν μαζί οι Α και Β. Κοστίζει max(1,3) = 3 λεπτά. Σύνολο: 22΄. Απέναντι: Α, Β, Δ, Ε. Αρχική πλευρά: Γ.
7. 6η επιστροφή: επιστρέφει ο Α με τη λάμπα. Κοστίζει 1 λεπτό. Σύνολο: 23΄. Απέναντι: Β, Δ, Ε. Αρχική πλευρά: Α, Γ.
8. 7ο (τελευταίο) πέρασμα: περνούν μαζί οι Α και Γ. Κοστίζει max(1,6) = 6 λεπτά. Σύνολο: 29΄. Όλοι απέναντι.
9. Η συνολική διάρκεια είναι 29 λεπτά, δηλαδή 1 λεπτό μέσα στο περιθώριο των 30 λεπτών που αντέχει η λάμπα.

Απάντηση: Με τη σειρά περασμάτων: (Α,Β)→, Α←, (Δ,Ε)→, Β←, (Α,Β)→, Α←, (Α,Γ)→, όλοι περνούν απέναντι σε συνολικά 29 λεπτά, εντός του ορίου των 30 λεπτών της λάμπας.

Πρόσεξε:

• Το «κόστος» ενός περάσματος με δύο άτομα είναι πάντα ο χρόνος του πιο αργού από τους δύο, όχι το άθροισμα των χρόνων τους.
• Το κλειδί της λύσης είναι να περάσουν οι δύο πιο αργοί (8΄, 12΄) μαζί, σε ένα μόνο πέρασμα, ώστε ο μεγάλος χρόνος των 12 λεπτών να «πληρωθεί» μία μόνο φορά και όχι σε δύο ξεχωριστά περάσματα.
• Μια διαφορετική επιλογή στο ποιος επιστρέφει τη λάμπα (π.χ. να επιστρέφει κάθε φορά ο πιο αργός) οδηγεί σε συνολικό χρόνο μεγαλύτερο από 30 λεπτά, οπότε αποτυγχάνει.

Άσκηση 2 (σελ. 103)

Έχουμε ένα μπρίκι με νερό που βράζει και ένα αβγό που πρέπει να βράσουμε για 9 λεπτά ακριβώς. Δυστυχώς, δεν έχουμε κανένα ρολόι παρά μόνο δύο κλεψύδρες: η μία διάρκειας 7 και η άλλη 4 λεπτών. Ποιος είναι ο συντομότερος τρόπος για να μετρήσουμε 9 λεπτά;

Σκέψη / Μεθοδολογία: Καμία από τις δύο κλεψύδρες δεν μετρά απευθείας 9 λεπτά, οπότε πρέπει να συνδυάσουμε τις μετρήσεις τους σε μια αλληλουχία βημάτων (έναν αλγόριθμο μέτρησης χρόνου). Ξεκινάμε τις δύο κλεψύδρες μαζί: όταν αδειάσει η κλεψύδρα των 7΄, ξέρουμε ότι στην κλεψύδρα των 4΄ (που έχει ήδη αναποδογυριστεί μία φορά, στο λεπτό 4) απομένει ακριβώς 1 λεπτό άμμος. Από εκεί και πέρα, αρκεί να μετρήσουμε επιπλέον 1+4+4 = 9 λεπτά με την κλεψύδρα των 4΄, αναποδογυρίζοντάς την κάθε φορά που αδειάζει.

Λύση:

1. Τη στιγμή t=0 ξεκινάμε ταυτόχρονα και τις δύο κλεψύδρες (7΄ και 4΄).
2. Τη στιγμή t=4, αδειάζει η κλεψύδρα των 4΄. Την αναποδογυρίζουμε αμέσως, ώστε να ξεκινήσει 2η μέτρηση 4 λεπτών (θα αδειάσει στο t=8).
3. Τη στιγμή t=7, αδειάζει η κλεψύδρα των 7΄. Ακριβώς εκείνη τη στιγμή βάζουμε το αβγό στο νερό που βράζει — από εδώ μετράμε τα 9 λεπτά βρασμού. Στην κλεψύδρα των 4΄ έχει ήδη περάσει άμμος για 3 από τα 4 λεπτά της 2ης μέτρησης, άρα απομένει ακριβώς 1 λεπτό μέχρι να αδειάσει εντελώς.
4. Τη στιγμή t=8 (δηλαδή 1 λεπτό μετά την είσοδο του αβγού) αδειάζει η κλεψύδρα των 4΄ για 2η φορά. Την αναποδογυρίζουμε αμέσως, ξεκινώντας 3η μέτρηση 4 λεπτών (θα αδειάσει στο t=12).
5. Τη στιγμή t=12, αδειάζει ξανά η κλεψύδρα των 4΄. Την αναποδογυρίζουμε αμέσως, ξεκινώντας 4η μέτρηση 4 λεπτών (θα αδειάσει στο t=16).
6. Τη στιγμή t=16, αδειάζει η κλεψύδρα των 4΄ για 4η φορά. Από τη στιγμή που μπήκε το αβγό (t=7) έχουν περάσει ακριβώς 16−7 = 9 λεπτά. Βγάζουμε το αβγό.

Απάντηση: Ξεκινάμε ταυτόχρονα τις δύο κλεψύδρες. Όταν αδειάσει η των 4΄ (στο λεπτό 4), την αναποδογυρίζουμε. Όταν αδειάσει η των 7΄ (στο λεπτό 7), βάζουμε το αβγό στο νερό. Από εκεί, αφήνουμε την κλεψύδρα των 4΄ να ολοκληρώσει το τρέχον πέρασμά της (1 λεπτό ακόμα, μέχρι το λεπτό 8) και μετά την αναποδογυρίζουμε δύο ακόμη φορές πλήρως (4΄+4΄). Συνολικά περνούν 1+4+4=9 λεπτά από τη στιγμή που μπήκε το αβγό, οπότε το βγάζουμε στο λεπτό 16 της συνολικής μέτρησης.

Πρόσεξε:

• Το κλειδί είναι ότι τη στιγμή που αδειάζει η κλεψύδρα των 7΄, η κλεψύδρα των 4΄ δεν είναι στην αρχή της μέτρησής της αλλά έχει ήδη «καταναλώσει» 3 από τα 4 λεπτά της — γι' αυτό απομένει ακριβώς 1 λεπτό, όχι 4.
• Χωρίς τον συνδυασμό των δύο κλεψυδρών δεν θα μπορούσαμε να πετύχουμε ακριβώς 9 λεπτά, αφού ούτε το 7 ούτε το 4 μας δίνουν απευθείας αυτόν τον αριθμό.

Άσκηση 3 (σελ. 103)

Έχουμε 9 όμοια κέρματα από τα οποία το ένα είναι κάλπικο, δηλαδή πιο ελαφρύ. Επίσης, διαθέτουμε μια ζυγαριά ισορροπίας, όπως αυτή της εικόνας, με την οποία μπορούμε να συγκρίνουμε μεταξύ τους 2 βάρη. α) Θέλουμε με 2 μόνο ζυγίσεις να εντοπίσουμε το κάλπικο κέρμα. β) Πόσες ζυγίσεις θα χρειαστούμε για 81 κέρματα και πόσες για 36;

Σκέψη / Μεθοδολογία: Η εικόνα δείχνει απλώς μια τυπική δίζυγη ζυγαριά ισορροπίας (τα δύο δισκάκια), χωρίς αριθμητικά δεδομένα πάνω της — η πληροφορία που χρειάζεται η λύση βρίσκεται εξ ολοκλήρου στο κείμενο. Σε κάθε ζύγιση χωρίζουμε τα κέρματα σε 3 περίπου ίσες ομάδες και ζυγίζουμε δύο από αυτές: αν ζυγίζουν το ίδιο, το κάλπικο είναι στην τρίτη ομάδα (αυτή που αφήσαμε στην άκρη)· αν δεν ζυγίζουν το ίδιο, το κάλπικο είναι στην ελαφρύτερη από τις δύο. Κάθε ζύγιση, δηλαδή, περιορίζει τις πιθανές θέσεις του κάλπικου κέρματος στο 1/3 των κερμάτων που εξετάζαμε. Με k ζυγίσεις μπορούμε να ξεχωρίσουμε το κάλπικο ανάμεσα σε το πολύ 3^k κέρματα.

Λύση:

1. α) Χωρίζουμε τα 9 κέρματα σε 3 ομάδες των 3: Ομάδα Α, Ομάδα Β, Ομάδα Γ.
2. 1η ζύγιση: βάζουμε την Ομάδα Α σε ένα δισκάκι και την Ομάδα Β στο άλλο.
3. Αν ισορροπήσουν, το κάλπικο είναι στην Ομάδα Γ (που δεν ζυγίστηκε)· αν όχι, το κάλπικο είναι στην ελαφρύτερη από τις Α, Β. Σε κάθε περίπτωση, εντοπίζουμε μια ομάδα των 3 κερμάτων που περιέχει σίγουρα το κάλπικο.
4. 2η ζύγιση: παίρνουμε την ομάδα των 3 «ύποπτων» κερμάτων, βάζουμε 1 κέρμα σε κάθε δισκάκι και το τρίτο το αφήνουμε στην άκρη.
5. Αν τα δύο κέρματα στη ζυγαριά ισορροπήσουν, το κάλπικο είναι το κέρμα που αφήσαμε στην άκρη· αν όχι, το κάλπικο είναι το ελαφρύτερο από τα δύο στη ζυγαριά.
6. Έτσι, με ακριβώς 2 ζυγίσεις εντοπίζουμε πάντα το κάλπικο κέρμα ανάμεσα σε 9 κέρματα.
7. β) Με την ίδια λογική, κάθε ζύγιση περιορίζει τις υποψίες στο 1/3 των κερμάτων, άρα με k ζυγίσεις μπορούμε να ξεχωρίσουμε το κάλπικο ανάμεσα σε το πολύ 3^k κέρματα.
8. Για 81 κέρματα: 3^4 = 81, άρα χρειαζόμαστε ακριβώς 4 ζυγίσεις (81 → 27 → 9 → 3 → 1 κέρμα σε κάθε βήμα).
9. Για 36 κέρματα: με 3 ζυγίσεις καλύπτουμε το πολύ 3^3 = 27 κέρματα, που δεν αρκούν για τα 36· με 4 ζυγίσεις καλύπτουμε το πολύ 3^4 = 81 κέρματα, που αρκούν. Άρα και για τα 36 κέρματα χρειαζόμαστε 4 ζυγίσεις.

Απάντηση: α) Χωρίζουμε τα 9 κέρματα σε 3 ομάδες των 3 και ζυγίζουμε δύο από αυτές: εντοπίζουμε την ομάδα των 3 «ύποπτων» κερμάτων. Στη 2η ζύγιση βάζουμε 1 από τα 3 «ύποπτα» κέρματα σε κάθε δισκάκι, αφήνοντας το τρίτο στην άκρη, και εντοπίζουμε το κάλπικο. β) Για 81 κέρματα χρειάζονται 4 ζυγίσεις (3^4=81)· για 36 κέρματα χρειάζονται επίσης 4 ζυγίσεις, αφού 3 ζυγίσεις καλύπτουν το πολύ 27 κέρματα (λιγότερα από 36), ενώ 4 καλύπτουν έως 81.

Πρόσεξε:

• Η εικόνα της άσκησης δείχνει μόνο τον τύπο της ζυγαριάς (ισορροπίας, με δύο δισκάκια) — δεν κουβαλάει επιπλέον αριθμητική πληροφορία πέρα από αυτή του κειμένου.
• Ο γενικός κανόνας είναι «με k ζυγίσεις ξεχωρίζουμε έως 3^k κέρματα», όχι «3 φορές το k» — προσοχή στη σύγχυση ανάμεσα σε δύναμη και πολλαπλασιασμό.
• Για τα 36 κέρματα, ο αριθμός των ζυγίσεων δεν υπολογίζεται διαιρώντας το 36 με το 9 (που θα έδινε λανθασμένα «διπλάσιες ζυγίσεις»)· υπολογίζεται βρίσκοντας το μικρότερο k για το οποίο 3^k ≥ 36.

Άσκηση 4 (σελ. 103)

Μετρήστε ακριβώς 9 λίτρα, αν έχετε στη διάθεσή σας ένα δοχείο των 10 λίτρων, ένα των 7 λίτρων και μια πηγή με άφθονο νερό. Μπορείτε μόνο να γεμίζετε μέχρι πάνω και να αδειάζετε εντελώς τα δοχεία όσες φορές θέλετε.

Σκέψη / Μεθοδολογία: Έχουμε δύο δοχεία (10 και 7 λίτρα) και απεριόριστη πρόσβαση σε νερό, οπότε επιτρέπονται τρεις κινήσεις: γέμισμα ενός δοχείου εντελώς από την πηγή, άδειασμα ενός δοχείου εντελώς, και μεταγγίσεις από το ένα δοχείο στο άλλο μέχρι είτε να αδειάσει το πρώτο είτε να γεμίσει το δεύτερο. Το δοχείο των 7 λίτρων δεν μπορεί ποτέ να κρατήσει 9 λίτρα, άρα ο στόχος είναι να καταλήξουμε με 9 λίτρα στο δοχείο των 10 λίτρων. Παρατηρούμε ότι, αν γεμίσουμε το 10λιτρο και αδειάσουμε το περιεχόμενό του στο 7λιτρο, περισσεύουν πάντα 10−7=3 λίτρα στο 10λιτρο· επαναλαμβάνοντας αυτή τη διαδικασία με ενδιάμεσα αδειάσματα του 7λιτρου, το «υπόλοιπο» στο 10λιτρο μειώνεται σταδιακά κατά 1 λίτρο ανά κύκλο, μέχρι να φτάσουμε ακριβώς στα 9.

Λύση:

1. Ονομάζουμε Α το δοχείο των 10 λίτρων και Β το δοχείο των 7 λίτρων. Ξεκινάμε με Α=0, Β=0.
2. Γεμίζουμε το Α από την πηγή: Α=10, Β=0.
3. Αδειάζουμε το Α μέσα στο Β μέχρι να γεμίσει το Β: το Β παίρνει 7 λίτρα, στο Α μένουν 10−7=3. Κατάσταση: Α=3, Β=7.
4. Αδειάζουμε εντελώς το Β στην πηγή: Α=3, Β=0.
5. Αδειάζουμε το Α μέσα στο Β (χωράει, αφού το Α έχει μόνο 3 λίτρα): Α=0, Β=3.
6. Γεμίζουμε ξανά το Α από την πηγή: Α=10, Β=3.
7. Αδειάζουμε το Α μέσα στο Β μέχρι να γεμίσει το Β: στο Β χωράνε ακόμα 7−3=4 λίτρα, άρα στο Α μένουν 10−4=6. Κατάσταση: Α=6, Β=7.
8. Αδειάζουμε εντελώς το Β στην πηγή: Α=6, Β=0.
9. Αδειάζουμε το Α μέσα στο Β (χωράει, αφού το Α έχει μόνο 6 λίτρα): Α=0, Β=6.
10. Γεμίζουμε ξανά το Α από την πηγή: Α=10, Β=6.
11. Αδειάζουμε το Α μέσα στο Β μέχρι να γεμίσει το Β: στο Β χωράει ακόμα 7−6=1 λίτρο, άρα στο Α μένουν 10−1=9. Κατάσταση: Α=9, Β=7.
12. Το δοχείο των 10 λίτρων περιέχει τώρα ακριβώς 9 λίτρα.

Απάντηση: Γεμίζουμε επανειλημμένα το δοχείο των 10 λίτρων και το αδειάζουμε στο δοχείο των 7 λίτρων (αδειάζοντας ενδιάμεσα το 7λιτρο στην πηγή όποτε γεμίζει), ακολουθώντας τη σειρά: γέμισμα 10λιτρου → μετάγγιση στο 7λιτρο → άδειασμα 7λιτρου → μετάγγιση υπολοίπου στο 7λιτρο → γέμισμα 10λιτρου → μετάγγιση στο 7λιτρο → άδειασμα 7λιτρου → μετάγγιση υπολοίπου → γέμισμα 10λιτρου → μετάγγιση στο 7λιτρο. Μετά από αυτά τα 10 βήματα, στο δοχείο των 10 λίτρων μένουν ακριβώς 9 λίτρα.

Πρόσεξε:

• Σε κάθε «μετάγγιση» το νερό περνάει από το ένα δοχείο στο άλλο μόνο μέχρι είτε να αδειάσει το δοχείο-πηγή είτε να γεμίσει το δοχείο-προορισμός· δεν χύνεται ποτέ νερό εκτός δοχείων.
• Το μοτίβο «γέμισε το μεγάλο, άδειασέ το στο μικρό, άδειασε το μικρό, ξαναγέμισε το μεγάλο» επαναλαμβάνεται· σε κάθε επανάληψη το υπόλοιπο στο μεγάλο δοχείο μειώνεται κατά 1 λίτρο (3, μετά 6, μετά 9), αφού 10−7=3.

Άσκηση 5 (σελ. 103)

Έχετε τρία δοχεία, ένα των 12 λίτρων, ένα των 8 και ένα των 5. Το δοχείο των 12 λίτρων είναι γεμάτο, ενώ τα άλλα δύο άδεια. Δεν έχετε άλλο νερό, μόνο τα 12 λίτρα. Να χωρίσετε την ποσότητα του νερού στη μέση, δηλαδή 6 λίτρα στο 12λιτρο και 6 λίτρα στο 8λιτρο. Μπορείτε μόνο να γεμίσετε ή να αδειάσετε τα δοχεία μέχρι τέλους, όσες φορές θέλετε. Τα δοχεία δεν έχουν καμία ογκομετρική ένδειξη επάνω τους. Σας δίνεται μια γλώσσα προγραμματισμού για τον πρόβλημα των δοχείων η οποία έχει μόνο μια εντολή: Αδειασε(Δοχείο1, Δοχείο2): Μετακινεί το περιεχόμενο του δοχείου 1 στο δοχείο 2. π.χ. η εντολή Αδειασε(12, 5) όταν αρχικά το 12λιτρο είναι γεμάτο και το 5λιτρο άδειο, αδειάζει το 12λιτρο στο 5λιτρο, άρα στο 12λιτρο θα μείνουν 7 λίτρα.

Σκέψη / Μεθοδολογία: Σε αντίθεση με την προηγούμενη άσκηση, εδώ δεν υπάρχει εξωτερική πηγή νερού· τα 12 λίτρα είναι σταθερό, κλειστό σύνολο που μοιράζεται ανάμεσα στα τρία δοχεία. Η μόνη διαθέσιμη ενέργεια είναι η εντολή Αδειασε(Δοχείο1, Δοχείο2), η οποία μεταφέρει νερό από το πρώτο δοχείο στο δεύτερο μέχρι είτε να αδειάσει το πρώτο είτε να γεμίσει το δεύτερο (ό,τι συμβεί πρώτο). Πρέπει να βρούμε μια αλληλουχία τέτοιων εντολών που να καταλήξει με 6 λίτρα στο 12λιτρο και 6 λίτρα στο 8λιτρο (οπότε το 5λιτρο θα έχει αναγκαστικά μείνει άδειο, αφού 6+6+0=12).

Λύση:

1. Συμβολίζουμε την κατάσταση ως (12λιτρο, 8λιτρο, 5λιτρο). Αρχική κατάσταση: (12, 0, 0).
2. Εντολή Αδειασε(12, 8): το 12λιτρο αδειάζει στο 8λιτρο μέχρι να γεμίσει (8 λίτρα χωρούν, 12−8=4 μένουν). Κατάσταση: (4, 8, 0).
3. Εντολή Αδειασε(8, 5): το 8λιτρο αδειάζει στο 5λιτρο μέχρι να γεμίσει (5 λίτρα χωρούν, 8−5=3 μένουν). Κατάσταση: (4, 3, 5).
4. Εντολή Αδειασε(5, 12): το 5λιτρο αδειάζει εντελώς στο 12λιτρο, αφού χωράει (4+5=9 ≤ 12). Κατάσταση: (9, 3, 0).
5. Εντολή Αδειασε(8, 5): το 8λιτρο (έχει 3 λίτρα) αδειάζει εντελώς στο 5λιτρο, αφού χωράει. Κατάσταση: (9, 0, 3).
6. Εντολή Αδειασε(12, 8): το 12λιτρο (έχει 9 λίτρα) αδειάζει στο 8λιτρο μέχρι να γεμίσει (8 λίτρα χωρούν, 9−8=1 μένει). Κατάσταση: (1, 8, 3).
7. Εντολή Αδειασε(8, 5): το 8λιτρο αδειάζει στο 5λιτρο μέχρι να γεμίσει (το 5λιτρο έχει ήδη 3, χωράει ακόμα 2, άρα 8−2=6 μένουν). Κατάσταση: (1, 6, 5).
8. Εντολή Αδειασε(5, 12): το 5λιτρο αδειάζει εντελώς στο 12λιτρο, αφού χωράει (1+5=6 ≤ 12). Κατάσταση: (6, 6, 0).
9. Καταλήξαμε στην επιθυμητή κατάσταση: 6 λίτρα στο 12λιτρο και 6 λίτρα στο 8λιτρο (το 5λιτρο έμεινε άδειο).

Απάντηση: Με τη σειρά εντολών Αδειασε(12,8), Αδειασε(8,5), Αδειασε(5,12), Αδειασε(8,5), Αδειασε(12,8), Αδειασε(8,5), Αδειασε(5,12) καταλήγουμε στην κατάσταση (12λιτρο=6, 8λιτρο=6, 5λιτρο=0), δηλαδή το νερό έχει χωριστεί ακριβώς στη μέση.

Πρόσεξε:

• Η εντολή Αδειασε(Δοχείο1, Δοχείο2) δεν αδειάζει πάντα εντελώς το πρώτο δοχείο· αν το δεύτερο δοχείο γεμίσει πρώτο, στο πρώτο δοχείο μένει το υπόλοιπο (όπως ακριβώς στο παράδειγμα της εκφώνησης: Αδειασε(12,5) αφήνει 7 λίτρα στο 12λιτρο).
• Το σύνολο των 12 λίτρων παραμένει σταθερό σε όλη τη διαδικασία — καλό είναι να το ελέγχουμε ως «δικλείδα ασφαλείας» μετά από κάθε εντολή (άθροισμα και των τριών δοχείων = 12).

Άσκηση 6 (σελ. 103)

Αν είχατε μια κανάτα των 6 λίτρων και μια των 2 λίτρων, θα μπορούσατε να μετρήσετε ακριβώς 5 λίτρα; Αιτιολογήστε την απάντησή σας.

Σκέψη / Μεθοδολογία: Στα δύο προηγούμενα προβλήματα δοχείων (Άσκηση 4 και 5) βρίσκαμε πάντα μια αλληλουχία βημάτων που πετύχαινε τον στόχο. Εδώ όμως πρέπει πρώτα να ελέγξουμε αν ο στόχος είναι καν εφικτός, πριν αναζητήσουμε αλγόριθμο επίλυσης. Όποια ποσότητα και αν βρεθεί, σε οποιαδήποτε στιγμή, μέσα σε οποιοδήποτε από τα δύο δοχεία (6 και 2 λίτρων) προκύπτει πάντα με γεμίσματα, αδειάσματα και μεταγγίσεις ανάμεσα σε δοχεία των 6 και 2 λίτρων. Επειδή και οι δύο χωρητικότητες (6 και 2) είναι πολλαπλάσια του 2, κάθε ποσότητα νερού που μπορεί να βρεθεί σε ένα από τα δοχεία σε οποιαδήποτε στιγμή είναι κι αυτή πολλαπλάσιο του 2 (δηλαδή άρτιος αριθμός λίτρων). Το 5 όμως είναι περιττός αριθμός, άρα δεν μπορεί ποτέ να προκύψει.

Λύση:

1. Ο μέγιστος κοινός διαιρέτης (ΜΚΔ) των δύο χωρητικοτήτων είναι ΜΚΔ(6, 2) = 2.
2. Κάθε ποσότητα νερού που μπορεί να εμφανιστεί σε ένα από τα δύο δοχεία, μετά από οποιονδήποτε συνδυασμό γεμισμάτων, αδειασμάτων στην πηγή ή μεταξύ τους μεταγγίσεων, είναι πάντα ακέραιο πολλαπλάσιο του ΜΚΔ των δύο χωρητικοτήτων, δηλαδή πολλαπλάσιο του 2.
3. Οι δυνατές ποσότητες που μπορούν λοιπόν να προκύψουν είναι μόνο: 0, 2, 4, 6 λίτρα.
4. Το 5 δεν είναι πολλαπλάσιο του 2 (είναι περιττός αριθμός), άρα δεν περιλαμβάνεται στις δυνατές ποσότητες.
5. Επομένως, με κανάτες 6 και 2 λίτρων δεν μπορούμε ποτέ να μετρήσουμε ακριβώς 5 λίτρα, όσα βήματα κι αν εκτελέσουμε.

Απάντηση: Όχι, δεν είναι δυνατό. Με δοχεία 6 και 2 λίτρων μπορούμε να πετύχουμε μόνο ποσότητες που είναι πολλαπλάσια του ΜΚΔ(6,2)=2, δηλαδή 0, 2, 4 ή 6 λίτρα — ποτέ το 5, που είναι περιττός αριθμός.

Πρόσεξε:

• Δεν αρκεί να δοκιμάσουμε μερικούς συνδυασμούς και να «μην τα καταφέρουμε» — η σωστή αιτιολόγηση δείχνει γιατί ΚΑΜΙΑ αλληλουχία βημάτων δεν μπορεί ποτέ να πετύχει το 5, μέσω του επιχειρήματος του ΜΚΔ.
• Το ίδιο πρόβλημα με δοχεία 10 και 7 λίτρων (Άσκηση 4) πετυχαίνει το 9, γιατί ΜΚΔ(10,7)=1: αφού το 1 διαιρεί κάθε ακέραιο, όλες οι ακέραιες ποσότητες από 0 έως 10 είναι θεωρητικά εφικτές.