Κυριακή 7 Απριλίου 2013

▪ Όλοι στη σειρά

Δέκα άνθρωποι στέκονται στη σειρά. Ο πρώτος πηγαίνει στο πίσω μέρος της σειράς και το επόμενο άτομο κάθεται κάτω, έτσι ώστε το άτομο που ήταν τρίτο στη σειρά είναι τώρα πρώτο στη σειρά. Στη συνέχεια το άτομο που είναι πρώτο στη σειρά πηγαίνει στο πίσω μέρος της γραμμής και το επόμενο άτομο κάθεται κάτω. Αυτή η διαδικασία επαναλαμβάνεται έως ότου παραμείνει μόνο ένα άτομο  Ποια ήταν η αρχική θέση του ατόμου αυτού στη σειρά;

3 σχόλια:

  1. 5 αν θεωρήσουμε την αρχή της ουράς τον αριθμό 1 και 6 αν θεωρήσουμε την αρχή της ουράς το 10. Δυστυχώς έπρεπε να τρέξω όλο τον αλγόρυθμο για να το δω. Αν το δούμε ως μαθηματικό πρόβλημά, λογικά το 5(ή αντίστοιχα το 6) λογικά θα πρέπει να είναι κάποιο σταθερό σημείο μετάθεσης?

    ΑπάντησηΔιαγραφή
  2. @fractalmaster
    Πολύ σωστά. Με μετάθεση των ατόμων λύνεται αμέσως.

    ΑπάντησηΔιαγραφή
  3. Δεν είναι σταθερό το σημείο μετάθεσης. Το πρόβλημα είναι (μια έξυπνα καμουφλαρισμένη ,θα έλεγα :-)) παραλλαγή του κλασσικού προβλήματος του Ιώσηπου (The Josephus game) μια άλλη παραλλαγή του οποίου πόσταρε πρόσφατα ο Σωκράτης στο πρόβλημα με τους Έλληνες και Γερμανούς που πέφτουν από το καράβι.
    ο νο 5 όντως ο τελευταίος "επιζών" (για ν=10 και βήμα 2) .
    Αν το βήμα γίνει 3, δηλαδή ο πρώτος και δεύτερος πηγαίνουν πίσω και κάθεται (εκτελείται ή πέφτει στη θάλασσα) ο 3ος, ο τελευταίος επιζών είναι ο νο 4.
    Για βήμα=4 ,ο τελευταίος είναι πάλι ο 5.
    Για βήμα=5 , ο τελευταίος είναι ο 3
    ...κ.ο.κ
    http://mathworld.wolfram.com/JosephusProblem.html

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