Σε ένα πολυσύχναστο τελωνείο φτάνει ένα έγγραφο από τη διοίκηση που ζητά να γίνονται τυχαίοι έλεγχοι στα εισερχόμενα για τυχόν απαγορευμένα εμπορεύματα.
Για λόγους νομικούς η διοίκηση ζητά να κρατούνται για έλεγχο κάθε μέρα «100 αντικείμενα επιλεγμένα απολύτως τυχαία από τα αντικείμενα της ημέρας«.
Ο διευθυντής του τελωνείου είναι πολύ προβληματισμένος αφού δεν ξέρει πώς να επιλέξει αυτά τα 100 αντικείμενα τυχαία χωρίς να περιμένει να μπουν μέσα όλα τα εμπορεύματα της ημέρας. Αν ήξερε στην αρχή της ημέρας πόσα αντικείμενα θα μπουν θα μπορούσε να κάνει την τυχαία επιλογή του το πρωί, και να ξέρει ποια αντικείμενα θα πρέπει να κρατήσει για έλεγχο και ποια να διεκπεραιώσει αμέσως.
Όμως δεν ξέρει. Κατά τη διάρκεια της ημέρας φθάνουν αντικείμενα για επεξεργασία στην υπηρεσία του απροειδοποίητα και δεν έχει χώρο να κρατήσει πάνω από 100 αντικείμενα στην αποθήκη του.
Τι θα πρέπει να κάνει;
Προβλήματα Μαθηματικών 
Υπόδειξη: Κάνει το μόνο πράγμα που θα μπορούσε να κάνει!
Μου αρέσει!Μου αρέσει!
Σχόλιο από Δημήτρης — 18 Απριλίου, 2009 @ 12:51 μμ
Υπόδειξη:
Ας πούμε ότι ο διευθυντής του τελωνείου έχει βρει ένα τρόπο να λύσει το πρόβλημά του και στο τέλος της ημέρας έχει μαζέψει100 αντικείμενα τα οποία πραγματικά επιλέχτηκαν τυχαία από όσα
του ήρθαν εκείνη τη μέρα. Πάνω που έκλεινε την πόρτα φτάνει όμως τρέχοντας ένας εκτελωνιστής και του φέρνει ακόμη ένα αντικείμενο πριν κλείσει την πόρτα.
Τι θα πρέπει να κάνει ο διευθυντής του τελωνείου ώστε να έχει 100 αντικείμενα που έχουν επιλεγεί τυχαία από τα
της ημέρας;
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 19 Απριλίου, 2009 @ 12:38 μμ
Μπορεί να κάνει το εξής, να βάλει τα 100 πρώτα αντικείμενα που θα έρθουν στην αποθήκη του και για κάθε επόμενο να κάνει την εξής διαδικασία:
αν αυτό που έρχεται είναι το ν-ιοστό τότε θα το βάλει στην αποθήκη με πιθανότητα 100/ν και σε περίπτωση που το βάλει θα βγάλει τυχαία ένα από τα 100 που βρίσκονται ήδη μέσα στην αποθήκη.
Επαγωγικά τώρα αποδεικνύεται ότι αν έχουμε τυχαίο δείγμα από 100 αντικείμενα για τα ν πρώτα τότε με αυτή τη μέθοδο και για τα ν+1 πρώτα αντικείμενα θα έχουμε τυχαίο δείγμα από 100. Άρα και στο τέλος της διαδικασίας θα έχει 100 αντικείμενα επιλεγμένα με ίδια πιθανότητα το καθένα.
Από την πρακτική πλευρά τώρα του ζητήματος, για να αποφασίσει αν το ν-ισοστό αντικείμενο θα το κρατήσει ή όχι μπορεί να βάλει μέσα σε ένα κουτί ν χαρτάκια από τα οποία τα 100 αντιπροσωπεύουν την απόφαση του να το κρατήσει και να διαλέξει τυχαία 1 χαρτάκι. Όμοια για να αποφασίσει ποιο θα βγάλει από την αποθήκη θα τραβήξει κλήρο ανάμεσα σε 100 χαρτάκια.
Μου αρέσει!Μου αρέσει!
Σχόλιο από stedes — 23 Απριλίου, 2009 @ 7:21 μμ
Πολύ σωστά.
Η μέθοδος αυτή ονομάζεται reservoir sampling.
Μ’αρέσει ιδιαίτερα που περιέγραψες με λεπτομέρεια το πώς θα υλοποιηθεί η μέθοδος (χαρτάκια σε κουτάκια).
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 23 Απριλίου, 2009 @ 8:40 μμ