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


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



(nil): George Papargiris (gpapargi(@)hotmail.com)
Ημερομηνία: Παρ 31 Ιαν 2003 - 10:47:55 EET

Καλημέρα

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

Ας θυμηθούμε πρώτα το 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
Δηλαδή στο πέμπτο βήμα υπάρχει επανάληψη και Κ1, Κ2, Κ3, Κ4, Κ5 διαφορετικά
μεταξύ τους.
Κάτι τέτοιο όμως είναι άτοπο αφού από το πέμπτο βήμα έχουμε Κ2-k=K4, ενώ από
το δεύτερο βήμα έχουμε Κ2-k=Κ1. Η αφαίρεση 2 αριθμών δίνει πάντα το ίδιο
αποτέλεσμα ενώ εδώ έχουμε Κ1 διάφορο του Κ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
...
a(n-1) = (n-1)*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). Αυτό είναι σωστό
αλλά αποτελεί μέρος της αλήθειας. Η πλήρης απάντηση είναι όπως διατυπώνεται
στην αρχή.

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

Φιλικά

Γιώργος

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*.
http://join.msn.com/?page=features/featuredemail

_______________________________________________________________

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

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


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

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