Ενότητα 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 λεπτών να «πληρωθεί» μία μόνο φορά και όχι σε δύο ξεχωριστά περάσματα.
• Αν, αντίθετα, ο πιο γρήγορος (1΄) συνοδεύει κάθε φορά έναν από τους υπόλοιπους και επιστρέφει μόνος του τη λάμπα, ο συνολικός χρόνος γίνεται 12+1+8+1+6+1+3 = 32 λεπτά, περισσότερο από τα 30 λεπτά της λάμπας — γι' αυτό χρειάζεται να περάσουν μαζί οι δύο πιο αργοί.

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

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

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

Λύση:

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

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

Πρόσεξε:

• Το κλειδί είναι το δεύτερο αναποδογύρισμα της κλεψύδρας των 7΄ στο λεπτό 8: εκείνη τη στιγμή έχει κατέβει άμμος μόνο 1 λεπτού, άρα αναποδογυρίζοντάς την μετράμε ακριβώς 1 λεπτό ακόμα.
• Υπάρχει και πιο αργός τρόπος (το αβγό μπαίνει στο λεπτό 7 και βγαίνει στο λεπτό 16, με διαδοχικά αναποδογυρίσματα της κλεψύδρας των 4΄), που επίσης μετράει 9 λεπτά βρασμού, αλλά χρειάζεται συνολικά 16 λεπτά — η άσκηση ζητά τον συντομότερο τρόπο.

Άσκηση 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λιτρο μετά από κάθε μετάγγιση αυξάνεται κατά 3 λίτρα ανά κύκλο (3, 6, 9), γιατί ο ελεύθερος χώρος του 7λιτρου μικραίνει (7, 4, 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 λίτρα.

Πρόσεξε:

• Σε κάθε «μετάγγιση» το νερό περνάει από το ένα δοχείο στο άλλο μόνο μέχρι είτε να αδειάσει το δοχείο-πηγή είτε να γεμίσει το δοχείο-προορισμός· δεν χύνεται ποτέ νερό εκτός δοχείων.
• Το μοτίβο «γέμισε το μεγάλο, άδειασέ το στο μικρό, άδειασε το μικρό, ξαναγέμισε το μεγάλο» επαναλαμβάνεται· σε κάθε επανάληψη το νερό που μένει στο μεγάλο δοχείο αυξάνεται κατά 3 λίτρα (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 είναι θεωρητικά εφικτές.