"Η ερμηνεία είναι ο τρόπος που χρησιμοποιεί η διανόηση για να εκδικηθεί την τέχνη"
Susan Sontag
Ένα κουτί περιέχει 1359 νομίσματα τριών ειδών: Χρυσά,ασημένια και χάλκινα. Η πλειοψηφία των νομισμάτων (τουλάχιστον τα 680) είναι χρυσά. Δεν έχουμε όμως τρόπο (ας πούμε ότι είναι "καμουφλαρισμένα" ή βαμμένα) να ξεχωρίσουμε το είδος τους. Έχουμε όμως μία μηχανή που δέχεται 2 νομίσματα κάθε φορά, και μας απαντάει αν τα νομίσματα είναι από το ίδιο είδος ή όχι.
Ας ορίσουμε έναν αλγόριθμο που βρίσκει ένα χρυσό νόμισμα, να έχει έστω "Βάθος ν", αν κάθε νόμισμα που εισάγεται στη μηχανή, εισάγεται το πολύ ν φορές.
Βρείτε έναν αλγόριθμο (το σύστημα δηλαδή με το οποίο θα "τροφοδοτηθεί" με νομίσματα η μηχανή) που να έχει το μικρότερο δυνατό (το ελάχιστο) "βάθος ν", και βρίσκει σίγουρα κάποιο χρυσό νόμισμα.
Μια λύση είναι να αφήσουμε ένα κέρμα στην άκρη και να έλεγξουμε 1358/2=679 ζεύγη κερμάτων
ΑπάντησηΔιαγραφήΑπό αυτά εν συνεχεία θα ελέγξουμε τα ζεύγη που είναι ίδιου είδους.Σε αυτή την περίπτωση τα ζεύγη με τα χρυσά(εφόσον είναι τουλάχιστον 680) είναι πάντα περισσότερα
Στην πιο δυσμενή περίπτωση:
Εστω 2 χάλκινα 677 ασημένια και 680 χρυσά
Αν αφήσουμε έξω κάποιο(έστω ένα ασημένιο)
έχουμε 2-676-680
Τα βάζουμε σε ζεύγη και έστω πως όλα μας βγαίνουν από το ίδιο είδος-η δυσμενέστερη περίπτωση(άρα μέχρι τώρα το καθένα έχει ελεγχθει μια φορά)
Άρα ζεύγη 1(χάλκινων) 338(ασημένιων) 340(χρυσών)
(έσω όλα από το ίδιο είδος)
Για να τα ξεχωρίσουμε παίρνουμε 1 μέλος από ένα ζεύγος και τσεκάρω με 1 μέλος με καθένα από τα υπόλοιπα ζεύγη άρα 338+340=678 έλεγχοι το 1 νόμισμα
Από τα νέα ζεύγη παίρνω τα μέλη αυτών που προέκυψαν πλειοψηφικά( είτε από το ίδιο είτε από διαφορετικό είδος) .Σε αυτό το σύνολο έχουμε 2 διαφορετικά είδη νομισμάτων μόνο(στην περίπτωση που πλειοψηφικός είναι ο διαφορετικός αριθμός ζευγών-διαφορετικά ο όμοιος αριθμός ζευγών αν είναι πλειοψηφικός μας δείχνει χρυσό)
Από αυτά παίρνω ένα και ελέγχω με καθένα από τα υπόλοιπα 337+338=675 φορές
Ο μεγαλύτερος αριθμός είτε ομοίων είτε διαφορετικών δείχνει χρυσά νομίσματα
Άρα στην πιο δυσμενή περίπτωση έχουμε
1(1ος όλα σε ζεύγη)+338+340(2ος έλεγχος)+337+338(3ος έλεγχος)=1354 το ν
Αυτό είναι μία λύση.Δεν ξέρω αν είναι η βέλτιστη.Να ξαναπροσπαθήσω?
Ντονάλτιε ,ξεκινάς πολύ σωστά,αλλά στην πορεία λίγο τα μπλέκεις. Το κλειδί είναι όντως η "δυαδικές" συγκρίσεις και το ότι τα χρυσά είναι "τουλάχιστον τα μισά" πάντα. Ο ακριβής αριθμός όλων των νομισμάτων δεν έχει σημασία. Μπορούμε λοιπόν όντως να "πετάμε" νομίσματα καθόσον ξέρουμε ότι τα μισά τουλάχιστον απ'αυτά που μένουν είναι και πάλι χρυσά!
ΑπάντησηΔιαγραφήΟ 1ος γύρος λοιπόν ,είναι ακριβώς όπως το είπες. Χωρίζουμε αυθαίρετα σε ζευγάρια και κρατάμε μόνο τα ζευγάρια όμοιων νομισμάτων. Τα άλλα τα πετάμε.Έτσι είναι βέβαιο ότι πετάμε τουλάχιστον τόσα "μη-χρυσά" όσα και "χρυσά" ,άρα η πλειοψηφία των χρυσών παραμένει. Τώρα λοιπόν έχουμε μόνο ταιριαστά ζευγαράκια.
Στο δεύτερο γύρο, παίρνουμε ένα νόμισμα απο κάποιο ζευγάρι και το συγκρίνουμε με κάποιο απο ενα άλλο ζευγάρι. Αν είναι διαφορετικά, πετάμε και τα 2 ζευγάρια. Και πάλι ξέρουμε ότι η πλειοψηφία των χρ. διατηρείται.
Τώρα λοιπόν (πριν αρχίσουμε τον 3ο γύρο) έχουμε ομάδες των 4 που ταιριάζουν...
(η συνέχεια επί της οθόνης, από τον Ντονάλτιο. :-) )
ΥΓ. Το ν είναι τελικά πολύ μικρός αριθμός!
Προχωρώ λίγο παρακάτω την ..ταινία από εκεί που την σταμάτησα πριν.
ΑπάντησηΔιαγραφή3ος γύρος: Κάθε ομάδα των 4 νομισμάτων περιέχει 2 νομίσματα που δεν υπέστησαν σύγκριση στον 2ο γύρο. Συγκρίνοντας λοιπόν αυτά μεταξύ τους ανά 2...
ΠΡΟΣΟΧΗ: To ζητούμενο "ν" δεν είναι ο αριθμός των γύρων, αλλά ΠΟΣΕΣ φορές μπαίνει ΤΟ ΠΟΛΥ κάθε νόμισμα στη μηχανή.
Παέι με τη λογική 2^ν(γενική δυαδική λογική)
ΑπάντησηΔιαγραφήΣτον 1ο γύρο έχουμε 2^0=1 σε όλα τα τα νομίσματα
Στο 2ο γύρο έχουμε 2^1=2 φορές στα μισά νομίσματα
Στον 3ο γύρο ελέγχουμε 4-άδες για 1 από τα 2νομίσματα κάθε τετράδας που δεν ελέγχθηκε στο 2ο άρα πάλι 2 φορές το πολύ
Στον 4ο γύρο ομοίως
Νομίζω σε καθε γύρο θα έχουμε 2 νομίσματα που δεν έχουνε ελεγχθεί αφου για κάθε έλεγχω μας χρειάζεται μόνο 1 νόμισμα μιας κ-άδας με ένα άλλο μιας άλλης κ-άδας.Σωστά?
Άρα η απάντηση μήπως είναι 2 φορές το πολύ κάθε νόμισμα?
Oh yes! βάθος ν = 2
ΔιαγραφήΌπως το λες. Σε κάθε γύρο 1 (νέο) νόμισμα από τα συγκρίσιμα γκρουπάκια...τα άλλα στον κάλαθο (λέμε τώρα) και έχουμε : 2άδες, 4άδες,8άδες...κ.λ.π μπορούμε να "ταιριάζουμε" ομάδες κατά βούληση (ανάλογα με το μέγεθος του αρχικού μας δείγματος) μέχρις ότου ξεμείνουμε από ομάδες ίδιου μεγέθους.
Μιας και κάθε γκρουπ είναι δύναμη του 2, το μέγιστο γκρουπ θα περιέχει μόνο χρυσά!
Χρησιμοποιήσαμε οποιοδήποτε νόμισμα ΤΟ ΠΟΛΥ 2 φορές στη μηχανή, άρα ν=2
Καλό ,έ; :-)
Πολύ καλό κ. Ριζόπουλε!!!Μου αρεσε σαν πρόβλημα(εξίσου με αυτό των καπέλων με τα 2 μέρη).Γιατί το εντάξατε στη θεωρία αριθμών?Έχει να κάνει με το pigeonhole principle?
ΑπάντησηΔιαγραφήΕ ναι. Μπορείς να το δεις κι έτσι, μπορείς και ανισοτικά-αλγεβρικά. Με ακέραιους έχει να κάνει, με δυαδικό σύστημα (ουσιαστικά ο αλγόριθμος που χρησιμοποιούμε αποτελεί την δυιαδική έκφραση καθε φορά των εναπομεινάντων νομισμάτων) ...Θεωρία Αριθμών! Η Βασίλισσα των Μαθηματικών! (ο Γκάους τόλεγε έτσι; όχι εγώ.. :-) )
Διαγραφή