JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Ο τυχερός βρέθηκε....



(nil): Georgios Galanopoulos (ggalan(@)softlab.ece.ntua.gr)
Ημερομηνία: Tue 15 Feb 2000 - 17:58:16 EET

    ...και επέστρεψε στην επαρχία του για να πεί την ιστορία αυτή στην
περιοχή του!!!

    Κατ' αρχάς ελπίζω να μη φάνηκε δύσκολο και η διατύπωση του να ήταν
αρκετά σαφής. Από τις απαντήσεις που έλαβα συνειδητοποίησα ότι η
διατύπωσή του έπρεπε να είναι ακριβέστερη. Την επόμενη φορά που θα
στείλω θα το προσπαθήσω. Έχω τουλάχιστο το ελαφρυντικό ότι ήταν το πρώτο
κουίζ που έστειλα στη λίστα.
    Παρακάτω σας παραθέτω τη πρόβλημα και τη λύση του.

    Το Πρόβλημα
--------------------
     Οι αρχαίοι Ρωμαίοι χρησιμοποιούσαν την παρακάτω (όχι και τόσο
ανθρώπινη μέθοδο) για να αντιμετωπίσουν τυχόν περιοχές που ήθελαν να
αποσχισθούν από την αυτοκρατορία τους.
    Συνελάμβαναν 1000 άνδρες από την περιοχή και τους τοποθετούσαν σε
μια ευθεία γραμμή. Κατόπιν άρχιζαν να τους εκτελούν ανά δύο. Δηλαδή την
πρώτη φορά εκτελούσαν τον δεύτερο, τον τέταρτο κλπ. Εάν ο τελευταίος της

σειράς επιζούσε, ετοποθετείτο πρώτος στην ευθεία για την επόμενη
εκτέλεση. Με τον τρόπο αυτό επιζούσε μόνο ένας, ο οποίος αφηνόταν
ελεύθερος ώστε να κάνει γνωστή την ιστορία στην επαρχία του.
Μπορείτε να βρείτε ποιος θα ήταν τελικά ο τυχερός;

Λύση
----------
Ο τυχερός είναι ο αιχμάλωτος με αύξοντα αριθμό 977

Υπάρχουν διάφοροι τρόποι να βρεθεί το παραπάνω.
O πιο απλός, για όσους γνωρίζουν κάποια γλώσσα προγραμματισμού, είναι να
κάνουν προσομοίωση. Το πρόβλημα μοντελοποιείται πολύ εύκολα.

Οσοι αρέσκονται σε θεωρητικές προσεγγίσεις προβλημάτων, υπάρχει και η
"θεωρητική" λύση, την οποία και σκέφθηκε ο Κωνσταντίνος Ταμπούρης. Η
λύση αυτή είναι η ακόλουθη.

Με κάθε σειρά εκτελέσεων οι Ρωμαίοι ελάττωναν τον αριθμό των αιχμαλώτων
(προσαυξημένο κατά 1, αν αυτός ήταν περιττός) κατά μία δύναμη του 2.
Συνεπώς είναι καλό να εργαστούμε στο δυαδικό σύστημα παράστασης αριθμών.

    Ο αριθμός 1000 του δεκαδικού συστήματος αναπαρίσταται στο δυαδικό
σύστημα ως 1111101000. Παρατηρούμε ότι ελατώνοντας κατά 3 την τάξη του
αριθμού (δηλαδή με τρεις σειρές εκτελέσεων) παίρνουμε τον περιττό
δυαδικό αριθμό 1111101.(Σημείωση: η διαίρεση ενός δυαδικού αριθμού με το
2, ισοδυναμεί με δεξιά ολίσθηση του αριθμού κατά μία θέση).
    Κατά τη τέταρτη σειρά εκτελέσεων, επειδή ο αριθμός 1111101 είναι
μονός θα περισσέψει ο τελευταίος κρατούμενος. Στο τέλος της σειράς αυτής
οι αιχμάλωτοι θα είναι (1111101+1)>>1 = 1111110>>1 = 111111. (Το
σύμβολο >> σημαίνει ολίσθηση προς τα δεξιά). Ο τελευταίος αιχμάλωτος που
δεν εκτελείται, θα γίνει πρώτος για την επομενη σειρά εκτελέσεων.
    Μετά την πέμπτη σειρά εκτελέσεων και την εκ νέου μετάθεση του
τελευταίου αιχμαλώτου, οι αιχμάλωτοι ελαττώνονται σε
(111111+1)>>1 = 1000000>>1 = 100000. Περαιτέρω υποδιπλασιασμός αφήνει
πάντα άρτιο αριθμό αιχμαλώτων.

    Συνεπώς, ο αιχμάλωτος που θα μείνει ζωντανός είναι αυτός που έγινε
πρώτος με τη δεύτερη μετάθεση.
Η δεύτερη μετάθεση γίνεται αμέσως μετά την 5η σειρά εκτελέσεων. ενώ η
πρώτη μετάθεση γίνεται αμέσως μετά την 4η σειρά.
    Με τις τρεις πρώτες σειρές εκτελέσεων που δεν έχουμε μεταθέσεις, θα
παραμείνουν ζωντανοί ένας στους 2^3=8 αιχμάλωτοι. Εύκολα διαπιστώνεται
ότι οι αιχμάλωτοι αυτοί έχουν αύξοντα αριθμό που υπακούει στη σχέση (8*ν
+ 1) για ν = 0, 1, ..124.
    Συνεπώς οι τρείς τελευταίοι αιχμάλωτοι (μετά τη 3η σειρά εκτελέσεων)
θα είναι οι 977, 985 και 993. Μετα την 4η σειρά στο τέλος θα βρίσκονται
οι 977 και 993. Ο 993 θα μετατεθεί στην αρχή ενώ ο 977 θα παραμείνει
τελευταίος. Αφού τελειώσει και η 5η σειρά εκτελέσεων, ο 977 θα έχει
περισσέψει και θα αποτελεί τη δεύτερη μετάθεση άρα και τον τυχερό που θα
επιζήσει

Στο πρόβλημα αυτό απαντησαν οι παρακάτω :
(Με * όσοι απάντησαν σωστά)

George @nagnostopoulos
Κωνσταντίνος Ταμπούρης*
Δίας
Chris Georgiou
Katrinis Kostas
Peter Alifrangis
Βαγγέλης Καπούλας
John P.*
Alexander Grigoriadhs
Korbas*
Pavlos
Nick Paraskeyioths*
Kyriakos Kyriakou*

______________________________________________________________________

 Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές ... και άλλα ...
 Πληροφορίες --> https://anekdota.duckdns.org/quiz_list.html
______________________________________________________________________


Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου