"Δεν μετράει (αξίζει) πάντα κάτι που μετριέται. Και κάτι που μετράει δεν μετριέται πάντα".
Άλμπερτ Άινστάιν
Έχουμε $Ν(>2)$ πανομοιότυπα νομίσματα. Ένα από αυτά όμως είναι διαφορετικό,δηλαδή είναι ελαφρύτερο ή βαρύτερο.
Πόσες ζυγίζεις (και με ποιο τρόπο θα τις εκτελέσουμε;) χρειαζόμαστε σε έναν ζυγό με δύο σκέλη-δίσκους, ώστε να προσδιορίσουμε σίγουρα αν το διαφορετικό είναι βαρύτερο ή ελαφρύτερο;
Αν γνωρίζουμε αρχικά ότι το κάλπικο είναι ελαφρύτερο ή βαρύτερο τότε για Ν νομίσματα θα χρειασθούν Κ ζυγίσεις όπου Κ αμέσως μεγαλύτερος φυσικός αριθμός του χ=log3(N) και είναι λυμένο εδώ:
ΑπάντησηΔιαγραφήhttp://eisatopon.blogspot.gr/2013/07/64.html#comment-form
Επειδή εδώ δεν γνωρίζουμε αν το κάλπικο είναι βαρύτερο ή ελαφρύτερο θα χρειασθεί ένα επιπλέον βήμα(μία επιπλέον ζύγιση) για να προσδιορισθεί η στίβα με το κάλπικο βαρύτερο ή ελαφρύτερο νόμισμα
πχ έστω ότι έχουμε 8 νομίσματα, να γνωρίζαμε αν είναι βαρύτερο ή ελαφρύτερο το κάλπικο θα χρειάζονταν 2 ζυγίσεις (3^2=9>8>3^1
Εδώ, δεν το γνωρίζουμε, και οι ζυγίσεις που απαιτούνται είναι:
α) 3 και 3 ισορροπούν, άρα είναι στα άλλα 2 και θα χρειασθούν άλλες 2 για τον προσδιορισμό του ελαφρύτερου ή βαρύτερου, σύνολο 3(2+1)
β) 3 και 3 και δεν ισορροπούν, άρα θα είναι ή στα 3 που ο δίσκος πήγε προς τα πάνω και θα είναι ελαφρύτερο ή στον δίσκο πού πήγε προς τα κάτω και θα είναι βαρύτερο. Ζυγίζουμε τα 2, ας πούμε πιθανά βαρύτερα με τα άλλα εναπομείναντα 2 και γνήσια, και έστω ότι ισορροπεί η ζυγαριά, το κάλπικο θα είναι στα 3 που αφαιρέσαμε ως πιθανόν περιέχοντα το ελαφρύτερο και τώρα είμαστε σίγουροι και απαιτείται άλλη μία για την εύρεση του. Σύνολον ζυγίσεων πάλι τρεις(3)(2+1). Αν δεν ισορροπήσει θα είναι στα 2 με το πιθανόν βαρύτερο, που τώρα είμαστε σίγουροι ότι είναι βαρύτερο και με 3η ζύγιση μεταξύ τους βρίσκουμε το βαρύτερο. Ζυγίσεις πάλι τρεις(3)
Και με 3 νομίσματα εξόφθαλμα χρειάζονται 2 ζυγίσεις αντί μιας αν γνωρίζαμε (+1)
Παρατήρηση: Αν το Ν = 3^(β)+1, νομίζω ότι δεν χρειάζεται η μία επιπλέον αλλά (β+1) όσες δηλαδή και αν γνωρίζαμε να είναι βαρύτερο ή ελαφρύτερο. Ίσως να θέλει λίγο ψάξιμο αυτό, αλλά δεν έχω άλλο χρόνο!
Πολύ ωραία η ανάλυσή σου ("προληπτική" λύση θα τη χαρακτήριζα σε μελλοντικό πρόβλημα),μόνο που απαντάει σε άλλο πρόβλημα. Το ζητούμενο δεν είναι πόσες ζυγίσεις χρειάζονται για να βρούμε ΤΟ διαφορετικό, αλλά πόσες χρειάζονται για να βρούμε ΑΝ το διαφορετικό είναι βαρύτερο ή ελαφρύτερο.
Διαγραφή2 ζυγίσεις, η ταχύτητα μερικές φορές μας εκτροχιάζει!,
ΑπάντησηΔιαγραφήαλλά δεν χρειάζεται να "φωνάζεις", καταλαβαίνω έστω και εκ των υστέρων και χωρίς κεφαλαία γράμματα!-:)
Ανάλυση
ΔιαγραφήΈστω Ν άρτιος
Ζυγίζουμε Ν/2 και Ν/2 (1η ζύγιση), ένας δίσκος πάει κάτω(πιθανόν περιέχει τα βαρύτερο) και ένας πάνω (πιθανόν περιέχει το ελαφρύτερο)
Χωρίζουμε τα Ν/2 ενός δίσκου, (όποιου δεν έχει σημασία), έστω αυτά που πήγαν προς τα κάτω (με το πιθανόν βαρύτερο) στα δύο, (Ν/4 και Ν/4) και τα ζυγίζουμε, αφαιρώντας αυτά που πήγαν προς τα πάνω, (2η ζύγιση)
2α Αν ισορροπήσει η ζυγαριά το κάλπικο είναι σε αυτά που αφαιρέσαμε και άρα ελαφρύτερο και
2β Αν γείρει προς την μία πλευρά είναι σε αυτήν και άρα βαρύτερο. Σύνολο 2 ζυγίσεις!
Ν =περιττός
Αφαιρώ το ένα και τα Ν-1(Ν-1 άρτιος) τα χωρίζω σε (Ν-1)/2 και (Ν-1)/2 και τα ζυγίζω(1η ζύγιση)
Αν η ζυγαριά ισορροπήσει το κάλπικο είναι το ένα που αφαιρέσαμε και το οποίο το ζυγίζω με ένα από τα γνήσια (2η ζύγιση) και το αποτέλεσμα της ζύγισης μας δείχνει αν είναι ελαφρύτερο ή βαρύτερο. Άρα 2 ζυγίσεις!
ΑΝ η ζυγαριά δεν ισορροπήσει, αναγόμαστε στην παραπάνω περίπτωση Κ=Ν-1, Κ=άρτιος, άρα πάλι 2 ζυγίσεις!
@E.Aλεξίου: Σωστός ο αλγόριθμος! 2 ζυγίσεις αρκούν για κάθε Ν>2
ΑπάντησηΔιαγραφήΌσον αφορά το πρόβλημα που λόγω ταχύτητας έθιξες στο πρώτο σου σχόλιο, αν το σκάρτο νόμισμα(βαρύτερο ή ελαφρύτερο) είναι 1 , τότε ο μέγιστος αριθμός νομισμάτων, έστω Ν, που μπορεί να διελευκανθεί με ζ ζυγίσεις σε Ζ Ζυγούς είναι:
maxN <= (((2Z +1)^ζ -1)/2) - Ζ
Στην περίπτωσή μας ,που οι ζυγοί είναι ένας (Ζ=1)ο τύπος γίνεται: maxN <=(3^ζ -1)/2 -1
Για ζ=3 ...maxN=26/2 -1=12 (το γνωστό σε όλους πρόβλημα) Για ζ=2 Ν=3, για ζ=4 Ν=39 κ.λ.π.
Φυσικά αυτή η γενίκευση-τύπος αποδεικνύεται,αλλά δεν είναι του παρόντος(εκ μέρους μου τουλάχιστον. Αν κάποιος θέλει να το κάνει, ευχαρίστως!)
Άρα δεν "κερδίζουμε" μόνο ένα, όπως φευγαλέα και στα γρήγορα είδα αλλά 1/4 έως 1/3 από την επόμενη δύναμη και κυρίως το θέμα των ζυγίσεων έχει μαθηματικό πλάτος και βάθος! Περιττό να γράψω ότι δεν έχω θεωρητικές γνώσεις πάνω στο θέμα, πέραν 4 -5 προβλημάτων που έχω λύσει και από ότι διαπιστώνω σήμερα ήταν σε απλή μορφή. Μου άρεσε το θέμα των ζυγίσεων (όχι το να βρούμε με πόσες ζυγίσεις αν είναι ελαφρύτερο ή βαρύτερο, ήταν εύκολο, αν δεν την "πατούσα" με την λάθος ανάγνωση πιθανόν και να μην ασχολιόμουν) αλλά αυτό που προέκυψε τυχαία επειδή δεν διάβασα όλη την "εκφώνηση" και κυρίως με την προέκταση που έδωσες με τους παραπάνω τύπους και για Ζ(ζυγαριές)=1,2,..,ν. Το σημειώνω, ούτως ώστε αν βρω κάποιο βιβλίο(στο διαδίκτυο) με ζυγίσεις να το αγοράσω. Να δούμε στο τέλος τι και πόσα βιβλία θα αγοράσω!!!
ΔιαγραφήΚάνουμε δυο ζυγίσεις.
ΑπάντησηΔιαγραφήΧωρίζουμε τα νομίσματα σε δυο ομάδες Ν/2 η καθεμία αν Ν είναι άρτιος ή Ν/2 + 0,5 η μία και Ν/2 - 0,5 η άλλη στην περίπτωση που ο Ν είναι περιττός.
Ζυγίζουμε την κάθε ομάδα ξεχωριστά και βρίσκουμε έστω α γρ. η μία και β γρ. η άλλη,διαιρούμε τα αποτελέσματα των ζυγίσεων με το αντίστοιχο αριθμό των νομισμάτων.
Η μία εκ των δυο διαιρέσεων θα είναι τέλεια (ομάδα με τα όμοια νομίσματα)ενώ η άλλη διαίρεση θα είναι ατελής.Προσθέτουμε τις δυο ζυγίσεις (α+β)γρ.και επιλύουμε την εξίσωση για να βρούμε το βάρος του δια φορετικού νομίσματος: (α+β)=(Ν-1)*(πηλίκο της τέλειας διαίρεσης)+(βάρος διαφ.νομίσματος)και έχουμε
Βάρος διαφ.νομίσματος=(α+β)-(Ν-1)*(πηλίκο της τέλειας διαίρεσης).
Θα ήθελα να συμπληρώσω στην παραπάνω λύση μου ότι ο αριθμός των νομισμάτων ανά ομάδα μπορεί να είναι και τυχαίος.
ΑπάντησηΔιαγραφήΜαρίνο, ευχαριστώ για το σχόλιο.
ΑπάντησηΔιαγραφήΟ ζυγός είναι παλάντζα. Δεν μπορεί να μας δείξει απόλυτη τιμή βάρους. Μόνο συγκρίσεις μαζών(βαρών) μπορεί να κάνει. Και το 0,5 (;).Θα σπάσεις το νόμισμα στη μέση;
Ο Αλγόριθμος είναι αυτός που έγραψε ο Ε.Αλεξίου. Δεν νομίζω πως υπάρχει άλλος,εκτός από τον (ουσιαστικά ίδιο)ελαφρώς παραλαγμένο.
1.Αν Ν περιττός, αφήνουμε 1 νόμισμα έξω...(βλέπε λύση Αλεξίου)
2. Αν Ν άρτιος ,αφήνουμε 2 νομίσματα (για τις συγκρίσεις ανά περίσταση) έξω...κ.λ.π
Λύση δίνει και ο χωρισμός των Ν Νομισμάτων σε τρεις στοίβες. Το Ν μπορεί να εκφρασθεί σε αυτή την περίπτωση είτε ως Ν=3Κ ή 3Κ+1ή 3Κ+2
ΑπάντησηΔιαγραφήΑν Ν=3Κ τα χωρίζουμε σε Κ,Κ,Κ, αν Ν=3Κ+1 τα χωρίζουμε σε Κ,Κ,Κ+1, και αν Ν=3Κ+2 τα χωρίζουμε σε Κ+1,Κ+1,Κ
Έστω Ν=3Κ+1(Ίδιο θα είναι και για τις άλλες 2 περιπτώσεις)
Ζυγίζουμε τα Κ και Κ
-Αν ισορροπήσει η ζυγαριά το κάλπικο θα είναι στην στοίβα με τα Κ+1 νομίσματα, ζυγίζουμε αυτήν την στοίβα(με το κάλπικο) με Ν+1 γνήσια και ανάλογα με το πού θα γείρει η πλάστιγγα καταλαβαίνουμε αν το κάλπικο είναι ελαφρύτερο ή βαρύτερο από τα γνήσια. Χρειάσθηκαν 2 ζυγίσεις.
-Αν δεν ισορροπήσει, θα γείρει ο ένας δίσκος προς τα κάτω (με το πιθανόν βαρύτερο) και ο άλλος θα πάει προς τα πάνω (με το πιθανόν ελαφρύτερο) και συμπεραίνουμε ότι τα Κ+1 είναι γνήσια.
Ζυγίζουμε τα Κ νομίσματα, ας πούμε αυτά που ο δίσκος έγειρε προς τα κάτω, με Κ νομίσματα από τα γνήσια.
-Αν η ζυγαριά ισορροπήσει το κάλπικο είναι στα άλλα Κ (που ήταν στον δίσκο που πήγε προς τα πάνω στην 1η ζύγιση) και συμπεραίνουμε ότι το κάλπικο είναι ελαφρύτερο.
-Αν δεν ισορροπήσει η ζυγαριά, θα γείρει προς τα κάτω ο δίσκος με την στοίβα με τα Κ με το πιθανόν βαρύτερο και άρα το κάλπικο είναι βαρύτερο. Πάλι 2 ζυγίσεις!
Το 0.5 δεν είναι μισό νόμισμα απλά αν έχουμε 13 νομίσματα(περιττό αριθμό)για παράδειγμα έχουμε 13/2 + 0.5=7 νομίσματα η μία ομάδα και 13/2 - 0.5 = 6 νομίσματα η δεύτερη ομάδα.
ΑπάντησηΔιαγραφήΤώρα ο ζυγός δεν συγκρίνει μόνο βάρη υπολογίζει κιόλας αν στον άλλο δίσκο βάλουμε αντίβαρα γνωστού βάρους.