From: Georgios Galanopoulos (ggalan(@)softlab.ece.ntua.gr)
Date: Τρι 15 Φεβ 2000 - 17:58:16 EET
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
- Mail actions: [ respond to this message ] [ mail a new topic ]
...και επέστρεψε στν επαρχία του για να πεί την ιστορία αυτή στην περιοχή του!!!
Κατ' αρχάς ελπίζω να μη φάνηκε δύσκολο και η διατύπωση του να ήταν αρκετά σαφής. Από τις απαντήσεις που έλαβα συνειδητοποίησα ότι η διατύπωσή του έπρεπε να είναι ακριβέστερη. Την επόμενη φορά που θα στείλω θα το προσπαθήσω. Έχω τουλάχιστο το ελαφρυντικό ότι ήταν το πρώτο κουίζ που έστειλα στη λίστα.
Παρακάτω σας παραθέτω τη πρόβλημα και τη λύση του.
Το Πρόβλημα
Οι αρχαίοι Ρωμαίοι χρησιμοποιούσαν την παρακάτω (όχι και τόσο ανθρώπινη μέθοδο) για να αντιμετωπίσουν τυχόν περιοχές που ήθελαν να αποσχισθούν αό την αυτοκρατορία τους.
Συνελάμβαναν 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
- Next message: George Haloulos: "Η απάντηση στα δύο κουιζάκια..."
- Previous message: John Kerkines: "Re: Re: Quiz 1,2,3: Analush (fwd)"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
- Mail actions: [ respond to this message ] [ mail a new topic ]