From: George Papargiris (gpapargi(@)hotmail.com)
Date: Παρ 31 Ιαν 2003 - 10:47:55 EET

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

Καλημέρα

Ήρθε η ώρα για τη δημοσιοποίηση της λύσης στο γενικευμένο πρόβλημα με τα δοχεία.

Ας θυμηθούμε πρώτ το quiz όως είχε δημοσιευτεί στις 1/11/2002:

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

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

Για τη λύση υπάρχουν 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 δοχεία με χωρητικότητα n και k με n>k, οι ποσότητες που μπορούμε παράγουμε είναι όλα τα πολλαπλάσια του μέγστου κοινού διαιρέτη των n και k που είναι μικρότερα ή ίσα με n.

Ας δούμε την παραπάνω πρόταση «σε δράση».

’ν τα δοχεία έχουν χρητικότητες 8 και 5 λίτρα ισχύει ΜΚΔ(8,5)=1. ’ρα οι ποσότητες που μπορούμε να κατασκευάσουμε είναι τα πολλαπλάσια του 1 που είναι μικρότερα ή ίσα με 8, δηλαδή οι αριθμοί 0,1,2,3,4,5,6,7,8. ’ν τα δοχεία έχουν χωρητικότητες 8 και 6 λίτρα ισχύει ΜΚΔ(8,6)=2. ’ρα οι ποσότητες που κατασκευάζονται είναι οι 0,2,4,6,8. Κάθε προσπάθεια κατασκευής των 1,3,5,7 είναι μάταιη.

Ο αναδρομικός τύπος παραγωγής των δυνατών είναι Χ[ι+1]=(Χ[ι]+k)modn με Χ[0]=0.
Όπου mod η συνάρτηση «υπλοιπο διαιρέσεως». Διαφορετικά ο τύπος παραγωγής των ποσοτήτων γράφεται και Χ[ι]=(ι*κ)modn

Σχηματικά μπορούμε να δούμε τις λύσει αν φτιάξουμε ένα n-γωνο και βάλουμε τους αριθμούς 1,2...n έναν σε κάθε κορυφή. Ξεκινάμε από τον αριθμό n που ταυτίζεται με το 0 και μετακινούμαστε συνεχώς k κορυφές δεξιά ή αριστερά (συνέχεια προς την ίδια φορά). Οι λύσεις του αλγόριθμου 1 προκύπτουν από μετακίνηση πος τα δεξιά ενώ οι λύσεις του αλγορίθμου 2 προκύπτουν από μετακίνηση προς τα αριστερά. Παρατηρήστε ότι στην περίπτωση των δοχείων χωρητικότητας 8 και 6 λίτρων, κανένα βήμα δεν παιρνάει από τα 1,3,5,7.

Και τώρα οι απόδειξεις για τα παραπάνω:

Απόδειξη 1

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

Αντί λοιπόν να έχουμε ένα δοχείο χωρητικότητας n, θεωρούμε ότι έχουμε ένα δοχείο άπειρης χωρητικότητας που έχει τα εξής 2 χαρακτηριστικά:

1) Κάθε 1 λίτρο έχει χαραγμένη μία λεπτή γραμμή (ένδειξη λίτρων).
2) Κάθε n λίτρα έχει χαραγμένη μια χοντρή γραμμή (ένδειξη πολλαπλασίων του 
n). Η πρώτη χοντρή γραμμή βρίσκεται στο 0.

Λειτουργούμ ως εξής: κάθε φορά γεμίζουμε το μικρό δοχείο και το αδειάζουμε μέσα στο μεγάλο. Μετράμε πόσες λεπτές γραμμές υπάρχουν μεταξύ τς στάθμης το νερού (που πάντα πέφτει πάνω σε κάποια γραμμή) και της πρώτης χοντρής γραμμής που είναι αμέσως κάτω από τη στάθμη και αυτός είναι ο παραγόμενος αριθμός. Μετράμε δηλαδή πόσα λίτρα παραπάνω είναι η στάθμη του νερού από το αμέσως μικρότερο πολλαπλάσιο του μεγάλου δοχείου n (που υποδηλώνεται από την χοντρή γραμμή).
Είναι ξεκάθαρο ότι τα παραγόμενα νούμερα είναι τα ίδια με αυτά που παράγει ο αλγόριθμος 1.

Αρχικά θα θεωήσουμε ότι οι αριθμοί n και k είναι πρώτοι μεταξύ τους δηλ ΜΚΔ(n,k)=1. Θα πρέπει να δείξουμε ότι παράγονται όλοι οι αριθμοί από 0 ως n.

Το απείρων διστάσεων δοχείο είναι αρχικά άδειο. Δηλαδή έχουμε παράγει τον αριθμό 0 (τετριμένη λύση). Γεμίζουμε συνεχώς το μικρό δοχείο και το αδειάζουμε στο μεγάλο καταγράφοντας τον παραγόμενο αριθμό. Για να αποδείξουμε το ζητούμενο αρκεί να δείξουμε ότι τις πρώτες n φορές, παράγεται και ένας διαφορετικός κάθε φορά αριθμός που είναι μικρότερος ή ίσος με n:

Το ότι είναι μικρότερος από n είναι προφανές αφού κάθε φορά μετράμε πόσες γραμμές υπάρχουν μεταξύ στάθμης και τελευταίας χοντρής γραμμής και οι χοντρές γραμμές είναι χαραγμένες κάθε n λίτρα ( n λεπτς γραμμές).

Τώα πρέπει να δείξουμε ότι οι n πρώτοι παραγόμενοι αριθμοί είναι διαφορετικοί μεταξύ τους. Είναι ξεκάθαρο ότι μόλις η στάθμη του νερού συμπέσει για πρώτη φορά με μια χοντρή γραμμή, τότε από ‘κει και μετά όλοι οι παραγόμενοι αριθμοί θα επαναλαμβάννται ακριβώς οι ίδιοι και με την ίδια σειρά, αφού η διαδικασία θα είναι όμοια. Το ερώτημα που γεννιέται είναι πότε η στάθμη θα συμπέσει για πρώτη φορά με μια χοντρή γραμμή. Η χοντρή γραμμή χαράσεται κάθε n και η στάθμη ανεβαίνει κάθε k άρα η πρώτη συνάντηση θα γίνει στο ελάχιστο κοινό πολλαπλάσιο των n και k δηλαδή το γινόμενο nk (αφού οι αριθμοί είναι πρώτοι μεταξύ τους). Ξέρουμε λοιπόν ότι μετά τα πρώτα n γεμίσματα θα έχουμε σίγουρα επανάληψη των παραγόμενων αριθμών. Θα πρέπει όμως να δείξουμε ότι κατά τη διάρκεια των πρώτων n γεμισμάτων δεν έχουμε επανάληψη κάποιου αριθμού. Χρησιμοποιούμε την εις άτοπο απαγωγή: Έστω ότι πριν τα n πρώτα γεμίσματα έχουμε κάποια επανάληψη. Χωρίς βλάβη της γενικότητας υποθέτουμε το επόμενο παράδειγμα:

Βήμα 1	Ποσότητα Κ1
Βήμα 2	Ποσότητα Κ2
Βήμα 3	Ποσότητα Κ3
Βήμα 4	Ποσότητα Κ4
Βήμα 5	Ποσότητα Κ2
Βήμα 6	Ποσότητα Κ3
Βήμα 7	Ποσότηα Κ4

Έτσι λοιπόν δείξαμε ότι οι παραγόμενοι κατά τα n πρώτα γεμίσματα αριθμοί είναι διαφορετικοί μεταξύ τους και μικρότεροι ή ίσοι με n. ’ρα είναι οι αριθμοί 0,1,,,,n.

Εξετάζουμε τώρα την περίπτωση που οι n και k δεν είναι πρώτοι μεταξύ τους αλλά έχουν μέγιστο κοινό διαιρέτη πχ τον d που είναι ιάφορος του 1.

Καταρχήν διαιρούμε τους n και k με d. Έτσι αναγόμαστε σε ένα πρόβλημα με ένα μεγάλο δοχείο χωρητικότητας n/d=α ένα μικρό δοχείο χωρητικότητας k/d=β. Οι α και β είναι πρώτοι μεταξύ τους και σύμφωνα με αυτά που είπαμε στην προηγούμενη περίπτωση οι πααγόμενοι αριθμοί είναι οι 0,1,...α.

Ας συλλογiστούμε τώρα τι θα γίνει στο πρόβλημα με δοχεία χωρητικότητας n και   k με ΜΚΔ(n,k)=d.

Τα δοχεία έχουν d φορές μεγαλύτερη χωρητικότητα. Το κάθε γέμισμα βάζει στο μεγάλο δοχείο ποσότητα βd (d φορές μεγαλύτερη από ότι πριν).
Το ελάχιστο κοινό πολλαπλάσιο των n και k δεν είναι πια το γνόμενο τους nk=αdβd αλλά είναι αβd.
Αυτό είναι και το λεπτό σημείο: με συλλογισμούς παρόμοιους με τους παραπάνω, μπορούμε να δείξουμε ότι οι παραγόμενοι αριθμοί θα αρχίσουν να επαναλαμβάνονται όταν (με βήμα βd) φτάσουμε στο στο ΕΚΠ των n και k που είναι το αβd. Δηλαδή οι επαναλήψεις θα αρχίσουν μετά από α γεμίσματα που είναι μικρότερο του n. ’ρα θα έχουμε α διαφορετικούς παραγόμενους αριθμούς που είναι βέβαια οι 1d, 2d, 3d …αd=n.

Δείξαμε λοιπόν ότι οι αν τα δοχεία έχουν χωρητικότητες n και k με ΜΚΔ(n,k)=d τότε οι παραγόμενοι αριθμοί είναι τα πολλαπάσια του d που είνι μικρότερα ή ίσα με n. Το πλήθος των διαφορετικών αριθμών που παράγονται από τον αλγόριθμο είναι n/d. Είναι φανερό ότι το παραπάνω συμπέρασμα ισχύει και στην περίπτωση που οι n και k είναι πρώτοι μεταξύ τους (d=1).

Απόδειξη 2

Βασιζόμαστε πάλι το ισοδύναμο μοντέλο με τα δοχείο άπειρης χωρητικότητας όπως ακριβώς περιγράφεται στην απόδειξη 1.

Όπως αναφέρθηκε στην απόδειξη 1, αν γεμίζουμε το μικρό δοχείο και το αδεάζουμε στο δοχείο άπειρης χωρητικότητας παράγουμε τις λύσεις του αλγόριθμου 1.
Εύκολα μπορεί να παρατηρήσει κανείς ότι η παραγόμενη ποσότητα λ μπορεί να γραφεί στη μορφή xk-yn=λ
όπου x οι φορές που αδειάσαμε το μικρό δοχείο (k λίτρα) στο δοχείο άπειρης χωρητικότητας
και y το πλήθος των πολλαπλασίων του n (εκτός του 0) που έχει υπερβεί η στάθμη.
Στο σημείο αυτό θα χρησιμοποιήσουμε έτοιμη τη λύση της διοφαντικής εξίσωσης ax+by=c. Η εξίσωση αυτή έχει λύση αν και μόνο αν ο ΜΚΔ των a και b διαιρεί το c. Με άλλα λόγια λύση υπάρχει αν και μόνο αν το c είναι πολλαπλάσιο του ΜΚΔ των a και b. Όποιος ενδιαφέρεται μπορεί να βρει την απόδειξη γι αυτό στη βιβλιογραφία των διοφαντικών εξισώσεων ή γενικότερα τω διακριτών μαθημαικών.
Στην περίπτωσή μας, η διαφορά στο πρόσημο (- αντί για +) δε μας ενοχλεί: Η εξίσωση για τα συγκεκριμένα n και k θα αναδείξει από μόνη της λύσεις με αρνητικό y.

Παρακάτω γράφω και την πολύ όμορφη απόδειξη του Βαγγέλη Καπούλα. Πρόκυτε για ια πιο συμπαγή έκδοση της απόδειξης 1. Ιδιαίτερα μου άρεσε το σημείο στο οποίο αποδεικνύεται ότι στα πρώτα n βήματα έχουμε n διαφορετικούς αριθμούς.

«Εξετάξω πρώτα την περίπτωση που n και k είναι πρώτοι μεταξύ τους (δηλαδή, έχουν μέγιστο κοινό διαιρέτη το 1).

Κατ' αρχάς, όλες οι μεταβολές που μπορούν να γίνουν στον όγκο του νεού μέσα στα δοχεία και οι οποίες μας επιτρέπουν να γνωρίζουμε τι τελικά έχουμε σε κάθε δοχείο είναι σε ακέραι πολλαπλάσια του λίτρου. Αυτό προκύπτει από το γεγονός οτι οι ενέργειες που μπορούμε να κάνουμε (χωρίς να χάσουμε το λογαριασμό) είναι να συμπληρώσουμε εντελώς ένα δοχείο ή να αδειάσουμε εντελώς ένα δοχείο. Σε κάθε περίπτωση η μεταβολή είναι ακέραιος αριθμός λίτρων. Επομένως σε καμμιά περίπτωση δεν μορούμε να παράγουμε γνωστό όγκο νερού σε κάποιο δοχείο που να μην είναι ακέραιος αριθμός λίτρων.

Θα δείξουμε οτι στην περίπτωση μας (n και k πρώτοι μετξύ τους) μπορούμε να παράγουμε όλους του ακέραιους σε λίτρα όγκους. Εφαρμόζουμε τη μία από τις μεθόδους που περιέγραψες στο αρχικό σου μήνυμα. Π.χ. γεμίσουμε διαδοχικά από τη βρύση το μικρό δοχείο και μετά αδειάζουμε το μικρό δοχείο στο μεγάλο φρονίζοντας να αδειάζουμε εντελώς το μεγάλο δοχείο όταν γεμίζει. Οι όγκοι σε λίτρα που θα έχουμε στο μεγάλο δοχείο μετά από κάθε άδειασμα του μικρού είναι (έστω n > k):

a(0) = 0 (αρχικά)
a(1) = k = 1*k mod n
a(2) = 2*k mod n
a(3) = 3*k mod n

Εστω οτι υπάρχουν i<n και j<n, με i>j, ώστε a(i)=a(j). Τότε, όμως, i*k mod n = j*k mod n ==> (i-j)*k = c*n για κάποιο ακέραι c. Ομως, αφού το ελάχιστο κοινό πολλαπλάσιο των n και k είναι n*k θα πρέπει c>=k. Αυτό δίνει i-j>=n, το οποίο μας οδηγεί σε άτοπο.

Επομένως, δεν υπάρχουν i<n και j<n, με i>j, ώστε a(i)=a(j). Τότε όμως έχουμε n διαφορετικούς ακέραιους που έχουν τιμές από 0 έως και n-1. Αρα, για κάθε ακέραιος από το 0 έως και το n-1 εμφανίζεται μία φορά μέσα στις τιμές a(0), ..., a(n-1) (από το pigeonhole principle).

Για να πάρουμε τον όγκο n απλά γεμίζουμε το μεγάλο δοχείο, ή προσθέτουμε αδειάζουμε k λίτρα από το μικρό στο μεγάλο όταν το τελευταίο έχει a(n-1) = (n-1)*k mod n λίτρα. Είναι εύκολο να δει κανείς οτι το μεγάλο δοχείο θα εναι τότε γεμάτο.

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

Για την περίπτωση που ο μέγιστος κοινός διαιρέτης των n και k είναι x>1 θεωρούμε ως μονάδα όγκου τα x λίτρα (την ονομάζουμε x-λιτρο) και εφαρμόζουμε την προηγούμενη απόδειξη. Ετσι δείχνουμε οτι μπορούμε να παράγουμε όλα τα ακέραια x-λιτρα αλλά καμμια υποδιαίρεσή τους.»

Σωστά απάντησαν οι:

Βαγγέλης Καπούλας
Δημήτρης Σκουτέρης
Θεοφάνης Γκούντρας
Unknown technologies (πρώην trabukos)

Τώρα στο θέμα των αποδείξεων:

Ο Βαγγέλης Καπούλας έδωσε μια παραλλαγή της απόδειξης 1 Ο Δημήτρης Σκουτέρης έδωσε μια παραλλαγή της απόδειξης 2 Ο Θεοφάνης Γκούντρας έδωσε μια παραλλαγή της απόδειξης 1 στηριζόμενος στο θεώρημα της περιοδικότητας με αναφορά στο έγκρο περιοδικό Quantum

Οι τρείς αυτοί φίλοι έστειλαν πλήρεις αποδείξεις και λαμβάνουν τον υποσχεθέντα έπαινο.

Επίσης ο "Unknown technologies" απέδειξε ότι κάθε παραγόμενη ποσότητα είναι πολλαπλάσιο του ΜΚΔ ενώ δεν έδειξε το αντίστροφο, οτι δηλαδή όλα τα πολλαπλάσια του ΜΚΔ είναι δυνατό να παραχθούν. Για να είμαστε δίαιοι λαμβάνει μισό έπαινο.

Αρκετοί εντόπισαν το γεγονός ότι όλες οι ποσότητες παράγονται αν οι αριθμοί n και k είναι πρώτοι μεταξύ τους (δηλαδή ο ΜΚΔ είναι το 1). Αυτό είναι σωστό αλλά αποτελεί μέρος της αλήθειας. Η πλήρης απάντηση είναι όπως διατυπώνεται στην αρχή.

Όσοι θέλουν από μένα κάποια διευκρίνηση ή θέλουν οι ίδιοι να κάνουν κάποιο σχόλιο είμαι στη διάθεσή τους.

Φιλικά

Γιώργος

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

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

• Next message: Fanurgakis Manolis: "��� ���������� �� ���������� [����: Quiz... ������� �.�.]"
• Previous message: Katerina Boukorou: "Re: ΠΡΑΣΙΝΟ Ε.Τ. ΔΙΕΥΚΡΙΝΗΣΗ"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]