εντοπισμός της βαρύτερης σφαίρας

Ανδρέας Πούλος · #1

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

Φιλικά,
Ανδρέας Πούλος

#2

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Ανδρέας Πούλος · #3

Δημήτρη,
υποψιάζομαι ότι στο σχολείο θα ήσουν ο ιδανικός τύπος
για να βοηθάς τους συμμαθητές σου στις αντιγραφές.

Είπαμε, να αφήνουμε τους juniors να δουλεύουν μόνοι τους,
αλλά όχι και στη μαύρη μοναξιά και στην απομόνωση.

Φιλικά,
Ανδρέας Πούλος

Ανδρέας Πούλος · #4

Αγαπητοί juniors,
δεν είδα ενδιαφέρον για το πρόβλημα που έθεσα, ούτε καν για συζήτηση.
Παρ΄ όλα αυτά έχω τη μεγαλοψυχία και την απέραντη καλοσύνη να δώσω μιαν απάντηση
στο πρόβλημα αυτό που απασχολεί και ταλανίζει γενεές μαθηματικών.
Μπορούμε να αποδείξουμε ότι:
Για αριθμό σφαιρών από $3^{0}$ έως $3^{1}$ απαιτούνται 1 ζυγίσεις.
Για αριθμό σφαιρών από $3^{1} + 1$ έως $3^{2}$ απαιτούνται 2 ζυγίσεις.
Για αριθμό σφαιρών από $3^{2} + 1$ έως $3^{3}$ απαιτούνται 3 ζυγίσεις.
Για αριθμό σφαιρών από $3^{3} + 1$ έως $3^{4}$ απαιτούνται 4 ζυγίσεις.
Για αριθμό σφαιρών από $3^{4} + 1$ έως $3^{5}$ απαιτούνται 5 ζυγίσεις.
Επαγωγικά ..
Για αριθμό σφαιρών από $3^{k-1} + 1$ έως $3^{k}$ απαιτούνται k ζυγίσεις.

Συνεπώς, ανάλογα σε ποιο διάστημα της μορφής $3^{n-1} +1$ έως $3^{n}$
βρίσκεται ο αριθμός ν του πλήθους των σφαιρών, μπορούμε να υπολογίσουμε
και τον ελάχιστο αριθμό των ζυγίσεων.
Μένει να αποδειχθεί, για ποιον λόγο επιλέξαμε τα διαστήματα αυτά
και πώς αποδεικνύεται ότι ο ελάχιστος αριθμός των ζυγίσεων
σε κάθε διάστημα είναι αυτός που ισχυρίζομαι.

Φιλικά,
Ανδρέας Πούλος

#5

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

Βάζω μια πλήρη απόδειξη μιας και νομίζω ότι η άσκηση είναι αρκετά σημαντική. Ιδίως ο τρόπος δικαιολόγησης ότι δεν μπορούμε να το πετύχουμε με λιγότερες ζυγίσεις.

Συγκρίνετε επίσης με το πρόβλημα εδώ: viewtopic.php?f=50&t=12672

Ισχυριζόμαστε ότι για

σφαίρες ο ικανός και αναγκαίος αριθμός ζυγίσεων είναι $\lceil \log_3 n \rceil$ . Όπου με $\lceil x \rceil$ ορίζουμε τον μικρότερο ακέραιο που είναι μεγαλύτερος από

. (Ακριβώς δηλαδή η απάντηση που έδωσε ο Ανδρέας που πάνω αλλά πιο συμπυκνωμένη.)

Απόδειξή ότι μπορεί να βρεθεί η βαρύτερη σφαίρα με τόσες ζυγίσεις:

Για n = 1,2,3

είναι προφανές. (Για n=3

, ζυγίζουμε δύο από τις σφαίρες. Αν κάποια είναι βαρύτερη τελειώσαμε. Αν έχουν το ίδιο βάρος τότε βαρύτερη είναι η τρίτη.)

Ας υποθέσουμε ότι αποδείξαμε το ζητούμενο για όλα τα

με $n \leqslant 3^k$ . Έστω τώρα ότι $3^k < n \leqslant 3^{k+1}$ . Χωρίζουμε τις σφαίρες σε τρεις ομάδες A,B,C

με

σφαίρες αντίστοιχα, όπου $a \leqslant b \leqslant c \leqslant a+1$ . (Ο χωρισμός επιτυγχάνεται εύκολα αν ξεκινήσουμε να μοιράζουμε της σφαίρας ανά ομάδα ξεκινώντας από την τρίτη ομάδα.) Παρατηρούμε ότι $c \leqslant 3^k$ αφού αλλιώς θα είχαμε $a,b \geqslant 3^k, c > 3^k$ και άρα $a+b+c > 3^{k+1}$ , άτοπο.

Δύο από τις ομάδες έχουν τον ίδιο αριθμό σφαιρών. Ζυγίζουμε αυτές μεταξύ τους. Μετά το ζύγισμα θα γνωρίζουμε σε ποια από τις τρεις ομάδες θα ανήκει η βαρύτερη σφαίρα και άρα την έχουμε περιορίσει σε ένα σύνολο το πολύ 3^k

σφαιρών. Επαγωγικά (ή αναδρομικά όπως αρέσκονται να λένε οι κομπιουτεράδες) μπορούμε να βρούμε την βαρύτερη σφαίρα με το πολύ άλλες

ζυγίσεις, άρα συνολικά k+1

ζυγίσεις, όπως ισχυριστήκαμε.

Απόδειξή ότι χρειάζονται τόσες ζυγίσεις:

Ας υποθέσουμε ότι έχουμε n > 3^k

μπάλες και ότι υπάρχει αλγόριθμος ο οποίος να βρίσκει την βαρύτερη μπάλα με

(το πολύ) ζυγίσεις. Απαριθμούμε τις σφαίρες από το 1 ως το

και επαναλαμβάνουμε τον αλγόριθμο με κάθε φορά και διαφορετική βαρύτερη σφαίρα. Κάθε φορά φυσικά ο αλγόριθμος πρέπει να δίνει διαφορετικό αποτέλεσμα. Καταγράφουμε σε κάθε ζύγιση το αποτέλεσμα. Θα είναι ένα εκ τριών αποτελεσμάτων: "Αριστερός ζυγός βαρύτερος", "Δεξιός ζυγός βαρύτερος", "Οι ζυγοί έχουν ίσο βάρος". Καταγράφουμε τις απαντήσεις σε ένα διάνυσμα. Π.χ. το διάνυσμα $(-1,0,1,1,0,\ldots)$ συμβολίζει ότι στην πρώτη ζύγιση ο αριστερός ζυγός ήταν βαρύτερος, στην δεύτερη και πέμπτη ζύγιση είχαν το ίδιο βάρος κ.τ.λ. Αν ο αλγόριθμος εντοπίζει σωστά την βαρύτερη σφαίρα θα πρέπει από το διάνυσμα να μπορούμε να πούμε ποια από τις σφαίρες είναι η βαρύτερη. Έχουμε όμως μόνο 3^k

διανύσματα αλλά περισσότερες από 3^k

σφαίρες, άρα αυτά είναι αδύνατος. (Διαφορετικά: Υπάρχουν τουλάχιστον δύο σφαίρες οι οποίες αν είναι βαρύτερες θα μας δώσουν ακριβώς το ίδιο διάνυσμα. Αλλά τότε θα ο αλγόριθμος θα είχε κάνει ακριβώς τις ίδιες ζυγίσεις με ακριβώς τα ίδια αποτελέσματα και άρα δεν θα μπορούσε να ξεχωρίσει μεταξύ των δυο αυτών σφαιρών.)

Προσπάθησα να γράψω την απάντηση αρκετά αναλυτικά επειδή θεωρώ την ιδέα της λύσης αρκετά σημαντική. Η απάντηση είναι ουσιαστικά μια γραμμή.

«Με

ζυγίσεις έχουμε μόνο 3^k

πιθανά αποτελέσματα και άρα μπορούμε να βρούμε την βαρύτερη μπάλα μόνο αν $n \leqslant 3^k$ .»

Δίνω και μια διαφορετική απόδειξη ότι αν έχουμε περισσότερες από 3^k

σφαίρες τότε χρειάζονται περισσότερες

ζυγίσεις. Για k = 0

είναι προφανές. (Αν έχουμε περισσότερες από μία σφαίρες πρέπει να ζυγίσουμε κάτι.) Θα προχωρήσουμε επαγωγικά. Ας υποθέσουμε ότι πως έχετε ένα αλγόριθμο που δουλεύει με

ζυγίσεις. Εγώ (ο κακός και πονηρός

) σας λέω «Εντάξει δώστε μου τις σφαίρες και θα τις ζυγίσω εγώ.» Χωρίζεται εσείς τις σε τρεις ομάδες A,B,C και μου λέτε να ζυγίσω τις σφαίρες της ομάδας Α με αυτές τις Β. Μια από τις τρεις ομάδες έχει περισσότερες από $3^{k-1}$ σφαίρες. Εγώ, γνωρίζοντας την βαρύτερη σφαίρα (έχω κάνει από πριν αρκετές ζυγίσεις), αν δεν βρίσκεται στην ομάδα με τις περισσότερες σφαίρες την κάνω αλλαγή στα κρυφά με μια σφαίρα από εκεί (αν είναι αριθμημένες τους αλλάζω και τις ταμπέλες για να μην το καταλάβετε) και μετά σας λέω ότι η βαρύτερη σφαίρα βρίσκεται στην ομάδα που έχει περισσότερες από $3^{k-1}$ σφαίρες. Επαγωγικά όμως θέλετε τουλάχιστον άλλες

ζυγίσεις για να την βρείτε.

Ανδρέας Πούλος · #6

Δημήτρη,
την τεχνική αυτή της απόδειξης την είχα υπ' όψη μου.
Ζητούσα όμως μιά πιο σχολική απόδειξη.
Είχα δώσει το περίγραμμα της, αλλά δεν είδα ανταπόκριση από τους Juniors.
Θα περιμένω λίγο, αν δεν βαρεθώ όπως αυτοί, θα δώσω μία (σχετικά) πλήρη απόδειξη.

Φιλικά,
Ανδρέας

εντοπισμός της βαρύτερης σφαίρας

εντοπισμός της βαρύτερης σφαίρας

Re: εντοπισμός της βαρύτερης σφαίρας

Re: εντοπισμός της βαρύτερης σφαίρας

Re: εντοπισμός της βαρύτερης σφαίρας

Re: εντοπισμός της βαρύτερης σφαίρας

Re: εντοπισμός της βαρύτερης σφαίρας

Μέλη σε σύνδεση