skip to main |
skip to sidebar
στις
7:40 μ.μ.
Ποιος είναι ο ελάχιστος αριθμός
ζυγίσεων που απαιτούνται προκειμένου να διαπιστώσουμε, ποια είναι τα δύο
βαρύτερα αντικείμενα από ένα πλήθος 128 αντικειμένων; (Κατ.27/Νο.359)
Πηγή:http://eisatopon.blogspot.gr/2013/07/128.html
Λύση του Ε. Αλεξίου.
Το πρόβλημα είναι δυσεπίλυτο, για μένα τουλάχιστον και ακόμα πιο δύσκολο
αν όχι άλυτο είναι το πρόβλημα της συνολικής κατάταξης και των 128 αντικειμένων .
Μέχρι 11 αντικείμενα μπορείτε να δείτε εδώ:
http://mathhmagic.blogspot.gr/2011/06/hugo-steinhaus.html
Θα κάνω μόνο μία πιο απλή προσέγγιση στο θέμα των δύο βαρύτερων από 128.
Με μία ζύγιση συγκρίνουμε 2 αντικείμενα και μετά ένα 3ο με αυτά τα 2 και βρίσκουμε
τα δύο βαρύτερα, μετά συγκρίνουμε-ζυγίζουμε το 4ο με το βαρύτερο ή και δύο βαρύτερα
και βρίσκουμε τα νέα δύο βαρύτερα, μετά το συγκρίνουμε το 5ο με το βαρύτερο ή και
τα 2 βαρύτερα ανάλογα με το αποτέλεσμα της 1ης ζύγισης κ.ο.κ μέχρι και
το 128ο αντικείμενο.
Οι ζυγίσεις που απαιτούνται είναι:
Α)Στην πλέον ευνοϊκή περίπτωση (με ελάχιστη πιθανότητα να συμβεί), το κάθε νέο αντικείμενο που θα σταθμίζουμε με το προηγούμενο βαρύτερο να βγαίνει σε όλες τις περιπτώσεις βαρύτερο, είναι:
1(η πρώτη) +126=127. Η πιθανότητα να συμβεί αυτό είναι:
(1/2)*(1/2)*(1/2)*...*(1/2)(126 φορές)=(1/2)^126
Β) Στην πλέον δυσμενή περίπτωση, μετά την 1η ζύγιση, το κάθε νέο αντικείμενο που θα σταθμίζεται, να χρειάζονται 2 ζυγίσεις , άρα σύνολο ζυγίσεων 1+126*2=253 ζυγίσεις.
Η πιθανότητα να συμβεί αυτό είναι επίσης (1/2)^126
Γ) Μέσος αριθμός ζυγίσεων (με κάθε επιφύλαξη)
Μετά την 1η ζύγιση το κάθε νέο αντικείμενο για να καταταγεί χρειάζεται κατά μέσο όρο (0.5*1+0.5*2)/2=1.5 ζυγίσεις, άρα σύνολο ζυγίσεων:
1+126*1.5= 190 ζυγίσεις.
Αναρτήσεις
5 σχόλια:
Επτά έχω την εντύπωση ότι είναι αρκετές. (2^7=128) θα το διερευνήσω και θα επανέλθω αργότερα.
Το πρόβλημα είναι δυσεπίλυτο, για μένα τουλάχιστον και ακόμα πιο δύσκολο
αν όχι άλυτο είναι το πρόβλημα της συνολικής κατάταξης και των 128 αντικειμένων .
Μέχρι 11 αντικείμενα μπορείτε να δείτε εδώ:
http://mathhmagic.blogspot.gr/2011/06/hugo-steinhaus.html
Θα κάνω μόνο μία πιο απλή προσέγγιση στο θέμα των δύο βαρύτερων από 128.
Με μία ζύγιση συγκρίνουμε 2 αντικείμενα και μετά ένα 3ο με αυτά τα 2 και βρίσκουμε
τα δύο βαρύτερα, μετά συγκρίνουμε-ζυγίζουμε το 4ο με το βαρύτερο ή και δύο βαρύτερα
και βρίσκουμε τα νέα δύο βαρύτερα, μετά το συγκρίνουμε το 5ο με το βαρύτερο ή και
τα 2 βαρύτερα ανάλογα με το αποτέλεσμα της 1ης ζύγισης κ.ο.κ μέχρι και
το 128ο αντικείμενο.
Οι ζυγίσεις που απαιτούνται είναι:
Α)Στην πλέον ευνοϊκή περίπτωση (με ελάχιστη πιθανότητα να συμβεί), το κάθε νέο αντικείμενο που θα σταθμίζουμε με το προηγούμενο βαρύτερο να βγαίνει σε όλες τις περιπτώσεις βαρύτερο, είναι:
1(η πρώτη) +126=127. Η πιθανότητα να συμβεί αυτό είναι:
(1/2)*(1/2)*(1/2)*...*(1/2)(126 φορές)=(1/2)^126
Β) Στην πλέον δυσμενή περίπτωση, μετά την 1η ζύγιση, το κάθε νέο αντικείμενο που θα σταθμίζεται, να χρειάζονται 2 ζυγίσεις , άρα σύνολο ζυγίσεων 1+126*2=253 ζυγίσεις.
Η πιθανότητα να συμβεί αυτό είναι επίσης (1/2)^126
Γ) Μέσος αριθμός ζυγίσεων (με κάθε επιφύλαξη)
Μετά την 1η ζύγιση το κάθε νέο αντικείμενο για να καταταγεί χρειάζεται κατά μέσο όρο (0.5*1+0.5*2)/2=1.5 ζυγίσεις, άρα σύνολο ζυγίσεων:
1+126*1.5= 190 ζυγίσεις.
Το ξαναστέλνω μήπως δεν ήρθε την πρώτη φορά.
Το πρόβλημα είναι δυσεπίλυτο, για μένα τουλάχιστον και ακόμα πιο δύσκολο αν όχι άλυτο είναι το πρόβλημα της συνολικής κατάταξης και των 128 αντικειμένων .
Μέχρι 11 αντικείμενα μπορείτε να δείτε εδώ:
http://mathhmagic.blogspot.gr/2011/06/hugo-steinhaus.html
Θα κάνω μόνο μία πιο απλή προσέγγιση στο θέμα των δύο βαρύτερων από τα 128.
Με μία ζύγιση συγκρίνουμε 2 αντικείμενα και μετά ένα 3ο με αυτά τα 2 και βρίσκουμε
τα δύο βαρύτερα, μετά συγκρίνουμε-ζυγίζουμε το 4ο με το βαρύτερο ή και δύο βαρύτερα
και βρίσκουμε τα νέα δύο βαρύτερα, μετά συγκρίνουμε το 5ο με το βαρύτερο ή και
τα 2 βαρύτερα αναάλογα με το αποτέλεσμα της 1ης ζύγισης κ.ο.κ μέχρι και
το 128ο αντικείμενο.
Οι ζυγίσεις που θα απαιτηθούν είναι:
Α)Στην πλέον ευνοϊκή περίπτωση (με ελάχιστη πιθανότητα να συμβεί), το κάθε νέο αντικείμενο που θα σταθμίζουμε με το προηγούμενο βαρύτερο να βγαίνει σε όλες τις περιπτώσεις βαρύτερο είναι:
1(η πρώτη) +126=127. Η πιθανότητα να συμβεί αυτό είναι:
(1/2)*(1/2)*(1/2)*...*(1/2)(126 φορές)=(1/2)^126
Β) Στην πλέον δυσμενή περίπτωση, μετά την 1η ζύγιση, το κάθε νέο αντικείμενο που θα σταθμίζεται, να χρειάζονται 2 ζυγίσεις , άρα σύνολο ζυγίσεων 1+126*2=253 ζυγίσεις.
Η πιθανότητα να συμβεί αυτό είναι επίσης (1/2)^126
Γ) Μέσος αριθμός ζυγίσεων (με κάθε επιφύλαξη)
Μετά την 1η ζύγιση το κάθε νέο αντικείμενο για να καταταγεί χρειάζεται κατά μέσο όρο (0.5*1+0.5*2)/2=1.5 ζυγίσεις, άρα σύνολο ζυγίσεων:
1+126*1.5= 190 ζυγίσεις.
@ΕΑΛΕΞΙΟΥ
Κύριε Αλεξίου νομίζω ότι είναι σωστή η λήση σας βάσει του hugo Steinhaus. Ούτε κιέγώ μπόρεσα να το λύσω.
Οι σκέψεις για το μέγιστο και το ελάχιστο των ζυγίσεων, πιθανοτικά, μπορεί να ήταν σωστές αλλά δεν ήταν Η ΛΥΣΗ του προβλήματος "Ελάχιστος αριθμός ζυγίσεων για την εύρεση των 2 βαρύτερων αντικειμένων από 128(=2^7) αντικείμενα. Την ΛΥΣΗ την "χρωστούσα" και σε μένα τον ίδιο και στο ιστολόγιο και την παραθέτω.
Τα 128 αντικείμενα τα χωρίζουμε σε 64 ομάδες των 2 αντικειμένων και τα ζυγίζουμε ανά 2 και κρατάμε τα 64 βαρύτερα των ομάδων και σημειώνουμε τις ζυγίσεις που κάναμε (πχ το 1 με το 2 1>2, το 3 με το 4 3>4 κλπ).
Τα 64 βαρύτερα τα χωρίζουμε σε 32 ομάδες των 2 αντικειμένων και τα ζυγίζουμε ανά 2, κρατάμε τα 32 βαρύτερα, σημειώνουμε τις ζυγίσεις που κάναμε (πχ 1 με το 3, 5 με το 7 κλπ) και τα χωρίζουμε με την ίδια λογική σε 16 ομάδες των 2, τα ζυγίζουμε ανά 2 και τα βαρύτερα 16 σε 8 των 2, τα 8 βαρύτερα σε 4 ομάδες των 2, τα 4 σε 2 ομάδες των 2 και τα 2 βαρύτερα των 2 ομάδων τα ζυγίζουμε μεταξύ τους και έχουμε βρεί το βαρύτερο αντικείμενο από τα 128
Ζυγίσεις που κάναμε 64+32+16+8+4+2+1=127(=128-1) και το βαρύτερο που προέκυψε ζυγίσθηκε 7 φορές. Το 2ο βαρύτερο είναι ένα εκ των 7 που ζυγίσθηκαν με το βαρύτερο στις αλληλεπάλληλες ομαδοποιήσεις και ζυγίσεις. Τα 7 αυτά νομίσματα(γιαυτό χρειαζόταν να σημειώνουμε τις ζυγίσεις, για να ξέρουμε ποιά 7 ζυγίστηκαν με το βαρύτερο των 128). Για την εύρεση του βαρύτερου των 7 αντικειμένων χρειάζονται 6 ζυγίσεις (=(7-1))
Τελικό Σύνολο ζυγίσεων για την εύρεση των 2 βαρύτερων από τα 128, 127+6=133 ζυγίσεις.
Και γενικά για την εύρεση των 2 βαρύτερων αντικειμένων από 2^ν αντικείμενα απαιτούνται κατ'ελάχιστον (2^ν-1)+(ν-1)=2^ν+ν-2 ζυγίσεις
Δημοσίευση σχολίου