Προβλήματα Μαθηματικών

Μαρτίου 24, 2008

Πόσους ελέγχους;

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Mihalis Kolountzakis @ 12:19 πμ

Σ’ένα μικροβιολογικό εργαστήριο έχουν 100 φιάλες αίματος από διαφορετικά άτομα και γνωρίζουν ότι ακριβώς μια από αυτές περιέχει αίμα μολυσμένο με μια ουσία Α. Ο έλεγχος για το αν ένα δείγμα αίματος περιέχει την ουσία Α είναι πολύ ακριβός και το εργαστήριο θέλει να ελαχιστοποιήσει τον αριθμό δειγμάτων που θα ελέγξει για να βρει τη μολυσμένη φιάλη.

Γι’ αυτό το λόγο το εργαστήριο δημιουργεί N μίγματα από τα 100 μπουκάλια που θέλει να ελέγξει και στέλνει αυτά τα N δείγματα σε ένα εργαστήριο στην Αμερική το οποίο στέλνει πίσω τις απαντήσεις. (Τα ταχυδρομικά είναι επίσης πανάκριβα, οπότε το εργαστήριο στέλνει και τα N μίγματα με μια αποστολή.)

Αν κάποιο από αυτά τα μίγματα προκύψει θετικό αυτό σημαίνει ότι κάποιο από τα μπουκάλια που χρησιμοποιήθηκαν στο μίγμα αυτό είναι μολυσμένο.

Ποιος είναι ο ελάχιστος αριθμός μιγμάτων N που πρέπει να στείλει το εργαστήριο για να βρει τη μολυσμένη φιάλη;

Advertisements

2 Σχόλια »

  1. Ο ελάχιστος αριθμός είναι 7. Αν υπήρχε λύση με 6 δείγματα τότε θα μπορουσαμε να πάρουμε 2^6=64 διαφορετικούς συνδιασμούς αποτελεσμάτων που δεν επαρκούν για να εντοπίσουμε το μολυσμένο δείγμα σε από τα 100 αρχικά.

    Θα δείξουμε τώρα ότι μπορούμε να διαλέξουμε 7 μίγματα έτσι ώστε να μπορούμε να εντοπίσουμε το μολυσμένο δείγμα.

    Το πρώτο μείγμα θα περιέχει όλα τα δείγματα που ο κωδικός αριθμός τους περιέχει το 2^0 στη δεκαδική του μορφή

    Το δεύτερο μείγμα θα περιέχει όλα τα δείγματα που ο κωδικός αριθμός τους περιέχει το 2^1 στη δεκαδική του μορφή

    Το 3ο το 2^2, το 4ο το 2^3, …, το 7ο το 2^6.

    Οπότε όποιες και αν είναι οι απαντήσεις μπορούμε να βρούμε πάντα την δυαδική αναπαράσταση του αριθμού μας επομένως και τον ίδιο τον αριθμό του μολυσμένου δείγματος

    Μου αρέσει!

    Σχόλιο από ctzamos — Μαρτίου 24, 2008 @ 7:43 μμ

  2. ctzamos:

    Πολύ ωραία.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 25, 2008 @ 1:53 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: