Τετάρτη 1 Φεβρουαρίου 2023

MCWTM

Ο Μιχάλης έχει $377$ σφραγισμένα μπουκάλια, ένα από αυτά τα μπουκάλια περιέχει ωραίο κρασί από κεράσι, ενώ και τα υπόλοιπα $376$ μπουκάλια περιέχουν εξαιρετικά τοξικό χυμό μπελαντόνα. 
Ο Μιχάλης έχει ένα μηχάνημα, το MCWTM, που έχει μια τεράστια θήκη (που μπορεί να χωρέσει έως και $377$ μπουκάλια), ένα κόκκινο κουμπί και μια λάμπα. 
Εάν ο Μιχάλης βάλει μερικά μπουκάλια στο μηχάνημα και στη συνέχεια πατήσει το κόκκινο κουμπί, το MCWTM ξυπνά, αρχίζει να λειτουργεί και καταναλώνει πολλή ενέργεια. 
• Εάν ένα από τα μπουκάλια περιέχει όντως κρασί από κεράσι, το MCWTM καταναλώνει $2$ MWh ενέργειας και η λάμπα ανάβει πράσινη. 
• Εάν κανένα από τα μπουκάλια στο διαμέρισμα δεν περιέχει κρασί κερασιού, το MCWTM καταναλώνει μόνο $1$ MWh ενέργειας και ο λαμπτήρας ανάβει κόκκινο. 
Ο Μιχάλης θα ήθελε να κάνει δώρο στον φίλο του Θανάση ένα μπουκάλι κρασί από κεράσι. 
Πόση ενέργεια πρέπει να χρησιμοποιήσει ο Μιχάλης στη χειρότερη περίπτωση στο πλαίσιο μιας βέλτιστης στρατηγικής εάν θέλει να αναγνωρίσει το μπουκάλι του κρασιού από κεράσι;

10 σχόλια:

  1. Αυτό το κρασί από κεράσι μού αρέσει απίστευτα, Μιχάλη. Αλλά θέλω να βρεις εσύ ο ίδιος και σωστά το μπουκάλι! Αλίμονό σου αν κάνεις τυπογραφικό και με φαρμακώσεις..🎃

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Βλέπω το Μιχάλη πελαγωμένο μάλλον στο κελάρι, οπότε ας βοηθήσει όποιος άλλος φίλος έχει μια καλή ιδέα..☺

      Διαγραφή
  2. Μια καλή ιδέα νομίζω πως θα ήταν η εξής:
    Ο Μιχάλης μπορεί να ελέγχει κάθε φορά στο μηχάνημα ένα μέρος από τα 'υποψήφια' μπουκάλια (π.χ. τα μισά), να βρίσκει σε ποιο από τα δύο μέρη είναι το καλό μπουκάλι (στο ελεγμένο ή στο άλλο) και έτσι περιορίζοντας σταδιακά το πεδίο αναζήτησης να καταλήξει στο καλό μπουκάλι, όπως με μια διαδικασία ερωτήσεων ναι/όχι..

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Θανάση, εχω την αίσθηση ότι η προσέγγιση «μισά μπουκάλια κάθε φορά», δεν είναι η βέλτιστη. Θα χρειαστούν 8 δοκιμές, με συνολική κατανάλωση, στη χειρότερη περίπτωση 16 Mwh.
      Θα πρότεινα να εκμεταλλευτούμε το γεγονός ότι μία θετική δοκιμή καταναλώνει διπλάσια ενέργεια από μία αρνητική δοκιμή, και να ξεκινήσουμε με το 1/3 των μπουκαλιών.
      Αν η δοκιμή δείξει πράσινο, έχουμε καταναλώσει 2 Mwh, έχοντας όμως περιορίσει το εύρος αναζήτησης στο 1/3 των μπουκαλιών, σε σύγκριση με το ½ των μπουκαλιών που απαιτούν την ίδια κατανάλωση με την προηγουμενη μέθοδο.
      Αν η δοκιμή δείξει κόκκινο, έχουμε καταναλώσει 1 Mwh και έχουμε περιορίσει την αναζήτηση στα 2/3 των μπουκαλιών. Στη περίπτωση αυτή, η επόμενη δοκιμή θα είναι με το 1/3 των μπουκαλιών που απομένουν (δηλαδή με τα 2/9 του συνόλου)
      Αν η δεύτερη δοκιμή δείξει πράσινο, θα έχουμε καταναλώσει για την δοκιμή αυτή άλλες 2 Mwh (και συνολικά 3 Mwh), έχοντας περιορίσει την αναζήτηση στα 2/9 των μπουκαλιών, που είναι πιο οικονομική, καθώς με την προηγούμενη μέθοδο θέλουμε 4 Mwh για περιορισμό στο 1/4 των μπουκαλιών.
      Αν και η δεύτερη δοκιμή δείξει κόκκινο, θα έχουμε καταναλώσει άλλη 1 Mwh (και συνολικά 2 Mwh), έχοντας περιορίσει την αναζήτηση στα 4/9 των μπουκαλιών, που είναι πιο οικονομική, καθώς με την προηγούμενη μέθοδο θέλουμε 2 Mwh για περιορισμό στο 1/2 των μπουκαλιών
      Επομένως η μέθοδος του 1/3 είναι πιο οικονομική. Με έναν πρόχειρο υπολογισμό εκτιμώ ότι θα χρειαστουν maximum 12 Mwh, σε σύγκριση με τις 16 που απαιτούνται με τη προηγούμενη μέθοδο

      Διαγραφή
    2. Ένα μέρος έγραψα, Στράτο, τα μισά ήταν μια ένδειξη της προσέγγισης, όχι αναγκαστικά η βέλτιστη στρατηγική..
      Η απάντηση 12 Kwh είναι η τελική σου;

      Διαγραφή
    3. Οχι, είναι απλά μία βελτιωμένη προσέγγιση. Θέλω να δω αν υπάρχει και καλύτερη

      Διαγραφή
    4. Στράτο, δε θέλω να επηρεάσω τον ειρμό της σκέψης σου, αλλά νομίζω ότι η διάταξη του γενεαλογικού δένδρου του Ντένις (δες τη σχετική ανάρτηση) είναι που δίνει την καλύτερη ιδέα..☺

      Διαγραφή
  3. Η βέλτιστη στρατηγική νομίζω, όταν έχουμε μπροστά μας F(n) στον αριθμό υποψήφια μπουκάλια (όπου F αριθμός της ακολουθίας Fibonacci), με F(n)=F(n-2)+F(n-1), είναι να βάζουμε αρχικά στο μηχάνημα F(n-2) μπουκάλια και έπειτα, ανάλογα με το αποτέλεσμα, να συνεχίζουμε βάζοντας την επόμενη φορά F(n-4) ή F(n-3) μπουκάλια κ.ο.κ. (κάθε φορά, τον προ-προηγούμενο F του υποψήφιου πλήθους μπουκαλιών που έδειξε η τελευταία μέτρηση).
    Η κατανάλωση ενέργειας στη δυσμενέστερη περίπτωση είναι, σε Mwh, η σειρά του αρχικού αριθμού F στην ακολουθία Fibonacci (για F>1, αφού για F=1 δεν υπάρχουν δηλητηριασμένα μπουκάλια). Ο 377 είναι ο 13ος στη σειρά (με 1ο τον 1 και 2ο τον 2), οπότε καταναλώνονται το πολύ 13 Mwh.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Πολύ ωραία και κομψή ανάλυση Θανάση! Συμφωνώ απόλυτα! Εκανες μήπως καμμία διερεύνηση για τη γενική περίπτωση τυχαίου αριθμού μπουκαλιών, που δεν υπακούει σε κάποιο πρότυπο;

      Διαγραφή
    2. Όχι Στράτο, δε βούτηξα τόσο βαθιά☺..
      Θα είχε πολύ ενδιαφέρον ίσως η περαιτέρω διερεύνηση της στρατηγικής των τρίτων που σκέφτηκες ή της ανάλυσης του αρχικού αριθμού μπουκαλιών στον αμέσως μικρότερό του Fibonacci και ό,τι περισσεύει (ξεκινώντας τους ελέγχους από το μικρότερο από τους δύο?)

      Διαγραφή