JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Γενίκευση ενός γνωστού quiz



(nil): George Papargiris (gpapargi(@)hotmail.com)
Ημερομηνία: Παρ 01 Νοέ 2002 - 09:51:25 EET

Καλημέρα

Μια που είναι η πρώτη μου αποστολή μηνύματος στη λίστα, θα ήθελα καταρχήν να
συχγαρώ όλα τα μέλη για τα όμορφα quiz που εμφανίζονται κατά καιρούς και
ιδιαίτερα τον Άκη Καρνούσκο που συγκέντρωσε τις σκόρπιες προσπάθειες όλων
μας μέσα σ’ αυτό το site.

Το πρόβλημα που σκοπεύω να βάλω μου προέκυψε στην προσπάθεια να γενικεύσω
μια γνωστή σπαζοκεφαλιά. Αλλά ας πάρουμε τα πράγματα από την αρχή:

Λίγο-πολύ όλοι θα έχουμε ακούσει το παρακάτω quiz:
« Έχουμε 2 δοχεία χωρητικότητας 8 και 5 λίτρων και μια βρύση συνεχούς ροής.
Να γεμίσετε ένα δοχείο ακριβώς με 7 λίτρα».

Για τη λύση υπάρχουν 2 αλγόριθμοι:

Αλγόριθμος 1

Γεμίζουμε συνεχώς το μικρό δοχείο με νερό και το αδειάζουμε στο μεγάλο
δοχείο. Κάθε φορά που το μεγάλο δοχείο γεμίζει, το αδείαζουμε και ρίχνουμε
μέσα στο μεγάλο δοχείο το υπόλοιπο νερό που έχει μείνει μέσα στο μικρό
δοχείο. Η διαδικασία αυτή επαναλαμβάνεται συνεχώς μέχρι να παραχθεί στο
μεγάλο δοχείο (αν παραχθεί) η ποσότητα που ζητάμε.

Αλγόριθμος 2.

Γεμίζουμε συνεχώς το μεγάλο δοχείο με νερό και το αδείαζουμε μέσα στο μικρό
δοχείο. Κάθε φορά που το μικρό δοχείο γεμίζει, το αδειάζουμε και ρίχνουμε
μέσα στο μικρό δοχείο το υπόλοιπο νερό που έχει μείνει μέσα στο μεγάλο
δοχείο. Η διαδικασία αυτή επαναλαμβάνεται συνεχώς μέχρι να παραχθεί στο
μεγάλο δοχείο (αν παραχθεί) η ποσότητα που ζητάμε.

Έτσι ο αλγόριθμος 1 δημιουργεί μέσα στο μεγάλο δοχείο διαδοχικά τις
ποσότητες 5, 2, 7, 4 ενώ ο αλγόριθμος 2 δημιουργεί διαδοχικά τις ποσότητες
3, 6, 1, 4.

Άν τώρα υποθέσουμε ότι έχουμε 2 δοχεία χωρητικότητας 8 και 6 λίτρων και
ζητάμε να φτιάξουμε την ποσότητα 3, τότε ... εγώ τουλάχιστον όσο κι αν
παιδεύτικα δεν μπόρεσα να βρω λύση. Έτσι λοιπόν το ερώτημα που γεννιέται
εντελώς φυσιολογικά είναι το να βρούμε σε ποιες περιπτώσεις το πρόβλημα
λύνεται και σε ποιες περιπτώσεις το πρόβλημα είναι άλυτο. Καταλήγουμε λοιπόν
στο ακόλουθο quiz στο οποίο καλείστε να δώσετε λύση:

QUIZ

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

Έχουμε δηλαδή να κάνουμε με μια ευθεία γενίκευση του γνωστού quiz με τα
δοχεία 8 και 5 λίτρων.

Κλέβοντας την ιδέα του Βαγγέλη Καπούλα στο quiz με τους φυλακισμένους,
έπαινος θα δωθεί σε όσους αποδείξουν τη λύση που θα δώσουν. Εδώ που τα λέμε
αυτό είναι και το πιο δύσκολο αλλά και πιο ενδιαφέρον κομμάτι. Άλλωστε μια
λύση αναπόδεικτη είναι λογικό να προκαλέσει αμφισβήτηση.

Σημείωση: Κατά τη δική μου αντίληψη οι 2 αλγόριθμοι παραγωγής ποσοτήτων
νερού που αναφέρθηκαν πιο πάνω είναι οι μοναδικοί. Οποιαδήποτε άλλη
παραλλαγή που τυχόν προκύπτει, ουσιαστικά εκφυλίζεται στους παραπάνω 2
τρόπους. Στην πραγματικότητα και οι 2 αυτοί τρόποι είναι μεταξύ τους
ισοδύναμοι αφού παράγουν τις ίδιες ποσότητες με άλλη σειρά. Παρόλα αυτά για
να εξαλείψω την περίπτωση να μου έχει ξεφύγει κάτι, ζητάω να βρεθούν οι
ποσότητες νερού που μπορούν να παραχθούν χρησιμοποιώντας τους παραπάνω 2
αλγορίθμους. Άν κάποιος ξέρει/βρει ριζικά διαφορετικό τρόπο παραγωγής
ποσοτήτων νερού ας με ενημερώσει.

Απαντήσεις σε προσωπικό mail στη διεύθυνση gpapargi(@)hotmail.com
Προτείνω τυχόν απορίες/διευκρινήσεις να σταλούν επίσης με προσωπικό mail
έτσι ώστε όσες είναι αρκετά γενικές και αφορούν όλους να τις συγκεντρώσω και
να τις απαντήσω συνολικά με ένα post στη λίστα.

Θα ήθελα να ξεκαθαρίσω ότι για μένα δε μετράει καθόλου η ταχύτητα που θα
λυθεί το πρόβλημα αλλά μόνο η ορθότητα και η πληρότητα της λύσης. Χρόνος
υπάρχει άφθονος. Σκεφτήτε με την ησυχία σας.

Καλή επιτυχία σε όλους.

Γιώργος

_________________________________________________________________
Get faster connections -- switch to MSN Internet Access!
http://resourcecenter.msn.com/access/plans/default.asp

_______________________________________________________________

      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org

        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________


Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου