From: George Papargiris (gpapargi(@)hotmail.com)
Date: Παρ 01 Νοε 2002 - 09:51:25 EET

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]

Καλημέρα

Μια που είναι η πρώτη μου αποστολή μηνύματος στη λίστα, θα ήθελα καταρχήν να συχγαρώ όλα τα μέλη για τα όμορφα 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 στη λίστα.

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

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

Γιώργος

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

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

• Next message: George Papargiris: "Γενίκευση ενός γνωστού quiz-Τυπογραφικό λάθος"
• Previous message: Yiannis Papagrigorakis: "1-10 (διευκρίνηση)"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]