Σάββατο 14 Οκτωβρίου 2017

Ναι ή όχι

'Ενας ντετέκτιβ πρέπει να εξετάσει το μάρτυρα ενός εγκλήματος σχετικά με μια κρίσιμη λεπτομέρεια. Ο ντετέκτιβ έχει επινοήσει μια σειρά $91$ το πολύ ερωιήοεων που πρέπει να απαντηθούν μόνο με ένα «ναι» ή ένα «όχι» και οι οποίες θα του επιτρέψουν να μάθει την κρίσιμη λεπτομέρεια - με ιην προϋπόθεση ότι ο μάρτυρας λέει την αλήθεια (κάθε ερώτηση μπορεί να εξηρτάται από την απάντηση μίας ή περιοπόιερων τιροηγούμενων ερωτήσεων). 
Ας υποθέσουμε όμως ότι ο μάρτυρας είναι δυνατόν να πει ψέματα μία φορά το πολύ.
Αποδείξτε όιι ο ντετέκτιβ μπορεί να αναθεωρήσει τον προγραμμαυομό των ερωτημάτων του και να εκμαιεύσει και πάλι την κρίσιμη λεπτομέρεια χρηοιμοιιοιώνιης 105 το πολύ «ναι-όχι» ερωτήπεις.

1 σχόλιο:

  1. 91=13*7. Χωρίζουμε τις ερωτήσεις σε 13 ομάδες των 7. Η επόμενη ερώτηση(92) είναι: Έχεις πει ψέματα στις ερωτήσεις των ομάδων 1-7; Αν η απάντηση είναι ναι, τότε οι επόμενες 7 ερωτήσεις(93-99) είναι : Έχεις πει ψέματα στις ερωτήσεις της ομάδας x(όπου x=1,2,...,7); Αν οι απαντήσεις είναι αρνητικές, τότε το 'ναι' στην ερώτηση 92 είναι ψέμα και άρα σε όλες τις ερωτήσεις 1-91 ο μάρτυρας έχει απαντήσει αλήθεια. Αν σε κάποια ερώτηση από τις 93-99 η απάντηση είναι 'ναι'(και αυτό μπορεί να γίνει μόνο σε μία από αυτές, διότι διαφορετικά μόνο 1 'ναι' μπορεί να είναι αλήθεια, αλλά τότε έχουμε τουλάχιστον δύο ψέματα-τα υπόλοιπα 'ναι' και το ψέμα της αντίστοιχης ομάδας του αληθινού 'ναι'), τότε το 'ναι' της 92 και το τελευταίο 'ναι' είναι και τα 2 αλήθεια (διότι αν το ένα τουλάχιστον ήταν ψέματα τότε θα είχαμε τουλάχιστον 2 ψέματα). Άρα οι επόμενες 6 ερωτήσεις είναι: Έχεις πει ψέματα στην ερώτηση y(όπου y=1,2,...,6) της αντίστοιχης ομάδας; Αν η απάντηση είναι 'ναι' σε μία από αυτές(και το πολύ σε μία από αυτές μπορεί να είναι) τότε αυτό το 'ναι' είναι απαραίτητα αλήθεια, διότι διαφορετικά θα είχαμε αυτό το ψέμα και το ψέμα στο οποίο αναφέρονται τα δύο προηγούμενα 'ναι'. Αλλιώς το ψέμα έχει ειπωθεί στην ερώτηση y=7 της συγκεκριμένης ομάδας. Αν η απάντηση στην ερώτηση 92 είναι 'όχι' η επόμενη ερώτηση (93) είναι: Έχεις πει ψέματα στις ερωτήσεις των ομάδων 8-13; Αν η απάντηση είναι 'όχι', τότε και τα 2 'όχι' είναι αλήθεια, διότι αν τουλάχιστον το ένα ήταν ψέμα, θα είχαμε τουλάχιστον 2 ψέματα(το ένα 'όχι' και το ψέμα στο αντίστοιχο σύνολο ομάδων). Αν η απάντηση είναι 'ναι' τότε ακολουθείται για τις ομάδες 8-13 η ίδια ακριβώς διαδικασία με το 'ναι' για τις ομάδες 1-7. Επομένως σε οποιαδήποτε περίπτωση οι επιπλέον ερωτήσεις δεν υπερβαίνουν τις 14 (91+14=105).

    ΑπάντησηΔιαγραφή