Δευτέρα, 15 Δεκεμβρίου 2014

Ανθρωποκυνηγητό

Δεκαέξι σπηλιές βρίσκονται στη σειρά, η μία μετά την άλλη. Ο σερίφης Μεγαλοφρύδης γνωρίζει ότι ένας ληστής, ο Φευγάτος Τζο, κρύβεται σε μία από τις σπηλιές. Ο σερίφης γνωρίζει επίσης ότι οι φίλοι του Φευγάτου Τζο τον έχουν συμβουλεύσει να μετακινείται κάθε νύχτα στη διπλανή σπηλιά, είτε αριστερά είτε δεξιά. Ο σερίφης και οι βοηθοί του μπορούν να ερευνήσουν μία μόνο σπηλιά κάθε ημέρα. Αν αρχίσουν να ερευνούν την 1η Μαΐου, θα συλλάβουν τον κακοποιό πριν το τέλος Μαΐου;
Περιοδικό Quantum

4 σχόλια:

  1. Αν αριθμήσουμε τις σπηλιές από το 1 έως το 16 και υποθέσουμε ότι ο σερίφης ξεκινά να επισκέπτεται τις σπηλιές με τη σειρά, αν δεν έχει βρει τον ληστή φτάνοντας στη 16, θα πει ότι κάποια στιγμή αντάλλαξαν σπηλιές. Δηλαδή όταν ο σερίφης ήταν σε σπηλιά με μονό αριθμό, ο Τζο ήταν σε σπηλιά με ζυγό ή το ανάποδο. Αν ο σερίφης λοιπόν ερευνήσει τη σπηλιά 16 για δύο συνεχόμενες ημέρες, από κει και πέρα οι αριθμοί των σπηλιών του σερίφη και του Τζο θα είναι της ίδιας αρτιότητας (και οι δύο άρτιοι ή και οι δύο περιττοί). Έτσι, στη χειρότερη περίπτωση στις 30 του μήνα ο σερίφης θα είναι στη σπηλιά 3 και ο Τζο στην 1 και στις 31 θα τον πιάσει στην 2.

    ΑπάντησηΔιαγραφή
  2. Ποια είναι η πιθανότητα ο σερίφης να χρειαστεί περισσότερες από $2n-1$ ημέρες, αν ερευνά σπηλιές στην τύχη;

    ΑπάντησηΔιαγραφή
  3. Υπάρχει δυνατότητα να συλληφθεί ο Τζό σε λιγότερες από 31 ημέρες, και συγκεκριμένα σε 28 το πολύ.

    Ας υποθέσουμε ότι ο Τζό κρύβεται αρχικά σε ζυγή σπηλιά. Τότε ξεκινώντας από τη σπηλιά 2 και πηγαίνοντας διαδοχικά στις σπηλιές 3,4,5....15, θα τον εντοπίσουμε μέσα σε 14 μέρες.
    Αν φθάνοντας στη σπηλιά 15 δεν τον έχουμε εντοπίσει,σημαίνει ότι ο Τζό αρχικά ήταν σε μονή σπηλιά. Τότε όμως, την 14η μέρα θα βρίσκεται σε ζυγή σπηλιά και την επόμενη μέρα θα είναι πάλι σε μονή. Οπότε αρκεί να κάνουμε την αντίστροφη διαδρομή 15,14,13.....2 οπότε θα τον εντοπίσουμε σε άλλες 14 μέρες το πολύ, σύνολο 28 μέρες

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Σωστά! Να κι ένα ενδιαφέρον σχετικό λίνκ http://checkmyworking.com/2011/12/solving-the-princess-on-a-graph-puzzle/

      Διαγραφή