ζυγίσεις

[antonis_math]

Έχουμε 12 βόλους, απο τους οποίους οι 11 έχουν το ίδιο βάρος και ένας διαφορετικό. Έχουμε κι έναν ζυγό. Με 3 μόνο ζυγίσεις να βρούμε το διαφορετικό βόλο.

[Καρδαμίτσης Σπύρος]

και το κλασσικό πρόβλημα της ζύγισης

Έχουμε 10 σακκιά με λίρες από τα οποία το 1 περιέχει κάλπικες και τα 9 καλές. Αν η καλή λίρα ζυγίζει 10 γραμμάρια και η κάλπικη 9 πως με μια (1) ζύγιση θα βρούμε το σακί με τις κάλπικες λύρες. ( Η ζυγαριά είναι σύγχρονη)

[antonis_math]

Σπύρο, το πρόβλημα είναι πιο πολύπλοκο γιατι δεν ξέρουμε αν το 'διαφορετικο βάρος' είναι 'λιγότερο' ή 'περισσότερο'.
Όσον αφορά το επιπλέον πρόβλημα δε θα απαντήσω γιατί γνωρίζω την απάντηση απο παλιά.

[Καρδαμίτσης Σπύρος]

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

[despondency]

Πολύ καλός γρίφος.

Χωρίζουμε τις μπάλες σε 3 ομάδες των τεσσάρων έστω Α,Β,Γ.

1ο Ζύγισμα: Α στη μία πλευρά και Β στην άλλη

Έχουμε 3 περιπτώσεις :

* Α=Β, τότε κάποια από τις Γ1,Γ2,Γ3,Γ4 είναι διαφορετική οπότε:

2ο ζύγισμα Γ1 και Γ2 στην μία πλευρά και Γ3 και Α1 στην άλλη πλευρά

-Αν Γ1Γ2 = Γ3Α1 τότε διαφορετική είναι η Γ4 και
3ο ζύγισμα Γ4 στη μία πλευρά και Α1 στην άλλη πλευρά για να δούμε αν η Γ4 είναι βαρύτερη ή ελαφρύτερη

- Αν Γ1Γ2 > Γ3Α1 τότε
ή Γ1 βαρύτερη ή Γ2 βαρύτερη ή Γ3 ελαφρύτερη και
3ο ζύγισμα Γ1 στη μία πλευρά και Γ2 στην άλλη
Αν Γ1 = Γ2 τότε Γ3 ελαφρύτερη
Αν Γ1 > Γ2 τότε Γ1 βαρύτερη
Αν Γ1 < Γ2 τότε Γ2 βαρύτερη

- Αν Γ1Γ2 < Γ3Α1 τότε
ή Γ1 ελαφρύτερη ή Γ2 ελαφρύτερη ή Γ3 βαρύτερη και
3ο ζύγισμα Γ1 στη μία πλευρά και Γ2 στην άλλη
Αν Γ1 = Γ2 τότε Γ3 βαρύτερη
Αν Γ1 > Γ2 τότε Γ1 ελαφρύτερη
Αν Γ1<Γ2 τότε Γ2 ελαφρύτερη

* Αν Α > Β τότε ξέρουμε ότι ή Α1 βαρύτερη ή Α2 βαρύτερη ή Α3 βαρύτερη ή Α4 βαρύτερη ή Β1 ελαφρύτερη ή Β2 ελαφρύτερη ή Β3 ελαφρύτερη ή Β4 ελαφρύτερη.
2ο ζύγισμα Α1Α2Β1 στη μία πλευρά και Α3Β2Γ1 στην άλλη πλευρά

-Αν Α1Α2Β1 = Α3Β2Γ1 τότε ή Α4 βαρύτερη ή Β3 ελαφρύτερη ή Β4 ελαφρύτερη και
3ο ζύγισμα Β3 από τη μία πλευρά και Β4 από την άλλη
Αν Β3 = Β4 τότε Α4 βαρύτερη
Αν Β3 > Β4 τότε Β4 ελαφρύτερη
Αν Β3 < Β4 τότε Β3 ελαφρύτερη

-Αν Α1Α2Β1 > Α3Β2Γ1 τότε ή Α1 βαρύτερη ή Α2 βαρύτερη ή Β2 ελαφρύτερη και
3ο ζύγισμα Α1 στη μία πλευρά και Α2 στην άλλη πλευρά
Αν Α1 = Α2 τότε Β3 ελαφρύτερη
Αν Α1 > Α2 τότε Α1 βαρύτερη
Αν Α1 < Α2 τότε Α2 βαρύτερη

-Αν Α1Α2Β1 < Α3Β2Γ1 τότε ή Β1 ελαφρύτερη ή η Α3 βαρύτερη και
3ο ζύγισμα Β1 στην μία πλευρά και Γ1 στην άλλη
Αν Β1 = Γ1 τότε Α3 βαρύτερη
Αν Β1 < Γ1 τότε Β1 ελαφρύτερη


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


Τελικά με 3 ζυγίσματα βρίσκουμε και την διαφορετική μπάλα και αν είναι ελαφρύτερη ή βαρύτερη

[antonis_math]

Δεν έχω διαβάσει όλη τη λύση σου ακόμα, μέχρι εκεί που έχω δει:
για το Α=Β μπορείς να πας πολύ πιο γρήγορα.
2η ζύγιση: συγκρίνεις δυο απο το Γ,και αν είναι ανάμεσά τους το διαφορετικό, απλά συγκρίνεις (3η ζύγιση) ένα απο αυτά με κάποιο 3ο.
αν δεν είναι ανάμεσά τους, συγκρίνεις κάποιο απο τα άλλα δυο με κάποιο 3ο.

[despondency]

Ναι δεν έχεις άδικο. Μάλλον το έκανα λίγο πιο περίπλοκο από οτι χρειαζόταν εκεί.

Υ.Γ: Τα έγραψα με λευκή γραμματοσειρά για να μην φαίνεται η λύση άμεσα σε κάποιον μου ήθελε να το προσπαθήσει.

[lonis]

Δυστυχώς δεν πρόλαβα να απαντήσω!

'Ιδια λύση με του despondency, αλλά με δεύτερη ζύγιση Α1Α2Β1 και Α3Α4Γ1 (δηλαδή από δύο βόλους της ίδιας ομάδας στο ίδιο ζύγισμα).
Αν υπάρχει ισορροπία, τότε μία από τις Β2,Β3,Β4 είναι ελαφρύτερη. Ζυγίζουμε πχ. Β2 με Β3.
Αν Α1Α2Β1>Α3Α4Γ1, τότε μία από τις Α1, Α2 είναι η βαρύτερη. Τις ζυγίζουμε μεταξύ τους.
Αν Α1Α2Β1<Α3Α4Γ1, τότε μία από τις Α3, Α4 είναι βαρύτερη ή η Β1 ελαφρύτερη. Ζυγίζουμε τις Α3 και Α4 . Η βαρύτερη από τις δύο είναι η ελαττωματική κι αν ισορροπούν η Β1.
Πολύ ωραίος γρίφος πράγματι. Το πρόβλημα της ζύγισης του Σπύρου επίσης το ξέρω. Όσοι δεν το γνωρίζουν ας σκεφτούν με την ησυχία τους.

Λεωνίδας

[antonis_math]

Όλο το ζουμί είναι στη 2η ζύγιση.
Mε τη 1η ζυγιση , αν ισορροπήσει , εύκολο. Το περιέγραψα σε προηγούμενο μήνυμα.
Αν δεν ισορροπησει είναι το θέμα: βρίσκουμε οτι η μια τετράδα έχει "υποψήφια βαριά" (η μεριά που γέρνει προς τα κάτω) και η άλλη "υποψήφια ελαφρυά"
0000 : υποψήφια βαριά
χχχχ : υποψήφια ελαφρυά
---- : απο τα κανονικά
στην 2η ζύγιση αφήνω απέξω ένα χ και δυο 00. Ώστε αν έχω ισορροπία στην ζύγιση των άλλων(2η ζύγιση) να μπορώ να βγάλω μόνο με μια ζύγιση συμπέρασμα για αυτα. όταν έχω 2 απο τη μια ομάδα και 1 απο την άλλη μπορώ με μια ζύγιση να βγάλω συμπέρασμα.
Πως θα τα μοιράσω στη 2η ζύγιση : βάσει του πάνω που έχω υπογραμίσει, θα βάλω 2 απο τη μια ομάδα στη μια πλευρά και 1 απο την άλλη ομάδα στην άλλη πλευρά(δες τα μπλέ->) Και τελικά θα έχω : xx 0 | x 0 -
αν γύρει προς τ αριστερά είναι μεταξύ των μπλε το ζήτημα και βασίζομαι σε αυτό που έχω υπογραμίσει. Αλλιώς μεταξύ των άλλων 2 που ειναι εύκολο επίσης.
οι λεπτομέρειες υπάρχουν στις απαντήσεις πιο πάνω. Αν και του Λεωνίδα ίσως είναι διαφορετική

[Demetres]

Να προσθέσω ακόμη ένα ερώτημα: Τι γίνεται αν έχουμε 13 βόλους;

(Να υπενθυμίσω ότι και το ερώτημα του Σπύρου έχει μείνει αναπάντητο. Θα ακολουθήσω όμως το παράδειγμα του Λεωνίδα και επειδή το έχω ξαναδεί δεν θα βάλω την λύση. Τουλάχιστον όχι ακόμη...)

[lonis]

Για να καταλάβω, Δημήτρη. Η ερώτηση είναι:
Πώς θα βρούμε με τρεις (το πολύ ) ζυγίσεις ποιος από τους 13 βόλους έχει διαφορετικό βάρος; Ή βρείτε το ελάχιστο πλήθος ζυγίσεων για να εντοπίσετε τον ελαττωματικό;
Ισχύουν τα ίδια; 12 βόλοι ίδιου βάρους κι ένας διαφορετικού, χωρίς να ξέρουμε αν είναι βαρύτερος ή ελαφρύτερος;

Λεωνίδας

[Demetres]

Για να καταλάβω, Δημήτρη. Η ερώτηση είναι:
Πώς θα βρούμε με τρεις (το πολύ ) ζυγίσεις ποιος από τους 13 βόλους έχει διαφορετικό βάρος; Ή βρείτε το ελάχιστο πλήθος ζυγίσεων για να εντοπίσετε τον ελαττωματικό;
Ισχύουν τα ίδια; 12 βόλοι ίδιου βάρους κι ένας διαφορετικού, χωρίς να ξέρουμε αν είναι βαρύτερος ή ελαφρύτερος;

Λεωνίδας

Να βρείτε τον ελάχιστο αριθμό ζυγίσεων. Ισχύουν ακριβώς τα ίδια όπως και με τους 12 βόλους.

[lonis]

Για να δούμε...
Ζυγίζω 4 με άλλους 4 βόλους. Αν δεν ισορροπούν, συνεχίζω όπως στις περιπτώσεις με τους 12 βόλους.
Αν ισορροπούν όμως, πρέπει να εντοπίσω τον ελαττωματικό βόλο ανάμεσα σε 5 τέτοιους - αυτούς που απέμειναν. Έστω 1, 2, 3, 4, 5 οι βόλοι.
Στη 2η ζύγιση, συγκρίνω τους 1, 2, 3 με τρεις από τους οχτώ της 1ης ζύγισης που ήταν εντάξει. Αν δεν ισορροπούν, ο λάθος βόλος είναι ένας από τους 1, 2, 3 και μάλιστα ξέρω αν είναι βαρύτερος ή ελαφρύτερος. Οπότε (3η ζύγιση) συγκρίνω τους 1 και 2 κλπ.
Αν ισορροπούν, τότε ο ελαττωματικός βόλος είναι ένας από τους 4 και 5. 3η ζύγιση, λοιπόν οι βόλοι 4 και πχ 6 (που είναι οκ). Εύκολα κι εδώ
Βγαίνει με τρεις ζυγίσεις ή έκανα λάθος;

Λεωνίδας

[Demetres]

Για να δούμε...
Ζυγίζω 4 με άλλους 4 βόλους. Αν δεν ισορροπούν, συνεχίζω όπως στις περιπτώσεις με τους 12 βόλους.
Αν ισορροπούν όμως, πρέπει να εντοπίσω τον ελαττωματικό βόλο ανάμεσα σε 5 τέτοιους - αυτούς που απέμειναν. Έστω 1, 2, 3, 4, 5 οι βόλοι.
Στη 2η ζύγιση, συγκρίνω τους 1, 2, 3 με τρεις από τους οχτώ της 1ης ζύγισης που ήταν εντάξει. Αν δεν ισορροπούν, ο λάθος βόλος είναι ένας από τους 1, 2, 3 και μάλιστα ξέρω αν είναι βαρύτερος ή ελαφρύτερος. Οπότε (3η ζύγιση) συγκρίνω τους 1 και 2 κλπ.
Αν ισορροπούν, τότε ο ελαττωματικός βόλος είναι ένας από τους 4 και 5. 3η ζύγιση, λοιπόν οι βόλοι 4 και πχ 6 (που είναι οκ). Εύκολα κι εδώ
Βγαίνει με τρεις ζυγίσεις ή έκανα λάθος;

Λεωνίδας

Ωραία. Με 4 ζυγίσεις βγαίνει μπορούμε να τα καταφέρουμε. Με (το πολύ) 3 ζυγίσεις μπορούμε πάντα να εντοπίσουμε τον ελαττωματικό βόλο; Αν ναι θέλω αλγόριθμο. Αν όχι θέλω απόδειξη.

EDIT: Συγνώμη Λεωνίδα. Το δίαβασα βιαστικά και δεν πρόσεξα ότι χρησιμοποιείς 3 ζυγίσεις. Ναι σωστή η λύση σου.

[lonis]

Νομίζω έδωσα τρεις ζυγίσεις και όχι τέσσερις. Είναι εντάξει; Έχεις καλύτερη λύση σε αυτή την περίπτωση;
Για τη γενίκευση θα το δω
Λεωνίδας