Γίνε μέλος στο grifoi.org

Στους γρίφους με τη σήμανση ".Άλυτοι 1-100" μπορούν να στέλνουν τις λύσεις τους μόνο τα Μέλη του site grifoi.org. Πληροφορίες για το πως θα γίνετε μέλος μπορείτε να διαβάσετε εδώ.

Δευτέρα, 26 Οκτωβρίου 2009

Συνδυαστικής Σκέψης - Το μοίρασμα του χρυσού (*****)

Πέντε πειρατές έκλεψαν ένα σεντούκι με 100 χρυσά νομίσματα. Επειδή όμως είχαν διαφορά στην ιεραρχία, ο αρχηγός τους δεν θεώρησε δίκαιο να πάρει ο καθένας από 20 και γι' αυτό πρότεινε την ακόλουθη δημοκρατική διαδικασία για να μοιράσουν τα νομίσματα:

Ξεκινώντας, ο τελευταίος πειρατής στην ιεραρχία, ο Νο 5, θα προτείνει μία κατανομή των νομισμάτων που τον συμφέρει. Εάν συμφωνήσει μαζί του η πλειοψηφία των πειρατών (οι μισοί συν ένας), συμπεριλαμβανομένου και του εαυτού του, τότε η μοιρασιά θα γίνει σύμφωνα με τον τρόπο που υπέδειξε. Αλλιώς δεν παίρνει τίποτα, χάνει το δικαίωμα ψήφου του και η διαδικασία επαναλαμβάνεται με τον πειρατή Νο 4 να κάνει μια πρόταση, κ.ο.κ., μέχρι η πλειοψηφία των εναπομεινάντων πειρατών να συμφωνήσει σε κάτι.

Λαμβάνοντας υπ' όψιν ότι όλοι οι πειρατές είναι εξαιρετικά άπληστοι, σκέφτονται λογικά και γνωρίζουν καλά ο ένας τον άλλο, ποια θα πρέπει να είναι η πρόταση του πειρατή Νο 5;

23 σχόλια:

pantsik είπε...

Λύση :

Ο πειρατής Νο 5 θα πρέπει να φέρει τον εαυτό του στη θέση των άλλων πειρατών, ξεκινώντας ανάποδα, δηλαδή από την περίπτωση που μόνο ένας πειρατής έχει απομείνει:
1) Αν απομείνει μόνο ο πειρατής Νο 1, θα προτείνει (στον εαυτό του) να πάρει και τα 100 νομίσματα, θα ψηφίσει την πρότασή του και αφού θα συγκεντρώνει την πλειοψηφία, θα τα πάρει όλα.
2) Αν έμεναν μόνο δύο, ότι και να πρότεινε ο Νο 2, δεν θα το ψήφιζε ο Νο 1 γιατί αν βγει ο Νο 2 απ' την μοιρασιά θα έπαιρνε όλα τα νομίσματα αυτός βάσει της πρώτης περίπτωσης. Έτσι ο Νο 2 δεν συγκεντρώνει την πλειοψηφία μόνο με την δική του ψήφο και συνεπώς δεν παίρνει τίποτα.
3) Αν έμεναν τρεις, ο Νο 3 χρειάζεται δύο ψήφους για να γίνει αποδεκτή η πρότασή του. Εάν όμως δεν γίνει, ο Νο 2 ξέρει πως δεν θα πάρει τίποτα, όπως είδαμε στη δεύτερη περίπτωση. Γι' αυτό πρέπει να δώσει στον Νο 2 τον ελάχιστο αριθμό νομισμάτων για να κερδίσει την ψήφο του, δηλαδή 1 νόμισμα. Προτείνει λοιπόν να πάρει αυτός 99 νομίσματα, 1 ο Νο 2 και κανένα ο Νο 1 και η πρότασή του γίνεται αποδεκτή με τις ψήφους των Νο 2 και Νο 3.
4) Αν έμεναν τέσσερις πειρατές, ο Νο 4 χρειάζεται τρεις ψήφους. Ψάχνει λοιπόν και βρίσκει τους δύο πιο αδικημένους πειρατές της προηγούμενης περίπτωσης και τους δίνει ένα νόμισμα παραπάνω στον καθένα για να πάρει την ψήφο τους, που μαζί με τη δική του θα κάνουν την πρότασή του αποδεκτή. Προτείνει λοιπόν 1 νόμισμα για τον Νο 1, 2 για τον Νο 2, 0 για τον Νο 3 και 97 για τον εαυτό του.
5) Και ερχόμαστε στην πραγματικότητα, όπου ο κάθε πειρατής θα πρέπει να έχει υπολογίσει τις παραπάνω πιθανές περιπτώσεις. Ο Νο 5 χρειάζεται και αυτός τρεις ψήφους για να γίνει αποδεκτή η πρότασή του. Ακολουθώντας λοιπόν την ίδια τακτική, βρίσκει τους δύο πιο αδικημένους πειρατές της προηγούμενης περίπτωσης και αυξάνει το κέρδος τους κατά 1 νόμισμα. Έτσι τελικά προτείνει 2 νομίσματα για τον Νο 1, 0 για τον Νο 2, 1 για τον Νο 3, 0 για τον Νο 4 και 97 για τον εαυτό του και η πρότασή του γίνεται αποδεκτή με τις ψήφους των Νο 1, Νο 3 και Νο 5.

civil είπε...

Καταρχήν συγχαρητήρια για το μπλογκ (έχω πωρωθεί). Δεν έχω βρει τόσο καλό σάιτ ούτε στα αγγλικά. Έχω διαβάσει αυτό το γρίφο στο Scientific american με την μικρή διαφορά ότι α) αν η πρόταση ενός πειράτη καταψηφιστεί, οι υπόλοιποι τον πετούν στη θάλασσα και β) στην ισοψηφία, η πρόταση περνάει. Οπότε η λύση του 1ου πειρατή είναι να δώσει από ένα νόμισμα στον 3, τον 5, τον 7 και τον 9 (5-5 ψήφοι, περνάει η πρόταση). Υπάρχει και η εξέλιξη αυτού του γρίφου (που είναι ο αγαπημένος μου) που ρωτάει τι θα γίνει αν αντί για 10 οι πειρατές ήταν 500. Τα νομίσματα παραμένουν 100.

pantsik είπε...

@civil: Σ’ ευχαριστώ για τα καλά σου λόγια. Τι κρίμα που σταμάτησε η κυκλοφορία του Scientific American… Φαίνεται πως στη χώρα μας δεν ευδοκιμεί ότι έχει να κάνει με σκέψη και επιστήμη. Όσοι ασχολούνται με αυτά τα εξωτικά σπορ είναι απλά πολύ λίγοι.
Ενδιαφέρουσα η παραλλαγή που αναφέρεις με τους 500 πειρατές. Θα κάνω μια προσπάθεια να σου απαντήσω: Καταρχήν θεωρώ πως ισχύουν οι δικοί σου κανόνες. Για αριθμό πειρατών έως και 200, το αποτέλεσμα είναι πως αν ο αριθμός των πειρατών είναι ζυγός, θα πάρει από ένα νόμισμα κάθε πειρατής που έχει ζυγό αριθμό στην ιεραρχία και τα υπόλοιπα νομίσματα θα τα πάρει ο τελευταίος πειρατής. Αντίστοιχα για μονό αριθμό πειρατών.
Αν οι πειρατές είναι 201, τότε ο τελευταίος πειρατής θα δώσει από ένα νόμισμα σε όλους τους μονούς πειρατές στην ιεραρχία (σύνολο 100 νομίσματα) και ο ίδιος δεν θα ζητήσει κανένα. Θα ψηφίσει όμως την πρότασή του (μαζί με όλους τους μονούς) γιατί έτσι τουλάχιστον δεν θα πεταχτεί στη θάλασσα. Έτσι με 101 ψήφους η πρότασή του γίνεται αποδεκτή. Αντίστοιχα και για 202 πειρατές, όπου ο τελευταίος δεν θα ζητήσει κανένα νόμισμα για να μην τον φάνε τα ψάρια.
Για 203 πειρατές, η πρόταση του τελευταίου γίνεται αποδεκτή με 102 ψήφους, αλλά ακόμα και αν αυτός δεν ζητήσει κανένα νόμισμα χρειάζεται να τον ψηφίσουν άλλοι 101 πειρατές, ενώ έχει μόνο 100 νομίσματα να τους εξαγοράσει. Οπότε προτείνει πάλι να πάρουν από ένα νόμισμα οι μονοί πειρατές μέχρι τον 199 και κανένα νόμισμα ο 201, ο 202 και ο ίδιος.
Στο σημείο αυτό νομίζω πως είναι ασαφές πως θα σκεφτούν οι πειρατές Νο 202 και 201: Με δεδομένο πως ότι και να ψηφίσουν θα καταλήξουν να μην πάρουν τίποτα, αν θέλουν να παραμείνει o 203 στη συμμορία τότε θα υπερψηφίσουν την πρότασή του. Ακολουθώντας την ίδια λογική για όλους τους πειρατές, ο Νο 500 θα προτείνει να πάρουν από ένα νόμισμα οι πειρατές Νο 2, 4, 6, …, 200 (ή οι 1, 3, 5, …, 199) και κανένα νόμισμα όλοι οι υπόλοιποι και η πρότασή του θα γίνει αποδεκτή από τους 100 που θα πάρουν νόμισμα συν του πειρατές με Νο 201 έως 500 που ούτως ή άλλως δεν παίρνουν τίποτα.
Το ενδιαφέρον όμως παρουσιάζεται στην περίπτωση που οι πειρατές Νο 202 και 201 προτιμήσουν να πεταχτεί ο Νο 203 στη θάλασσα παρόλο που οι ίδιοι δεν θα έχουν κάποιο άμεσο όφελος. Τότε θα καταψηφίσουν την πρότασή του και ο Νο 203 θα καταλήξει στη θάλασσα καθώς οι 101 ψήφοι που συγκεντρώνει δεν είναι αρκετοί για πλειοψηφία. Τότε τα Νο 201 και 202 σχηματίζουν μια νοητή ομάδα αντίδρασης, με την έννοια ότι από το σημείο αυτό και πάνω καταψηφίζουν κάθε πρόταση πειρατή με νούμερο μεγαλύτερο απ’ το δικό τους, μιας και όταν μείνουν τελευταίοι οι ίδιοι, έχουν εξασφαλίσει την επιβίωσή τους.
Ο Νο 204 όμως θα πάρει την ψήφο του Νο 203 γιατί σε διαφορετική περίπτωση ο τελευταίος καταλήγει στη θάλασσα. Έτσι με 102 ψήφους ο Νο 204 καταφέρνει να παραμείνει στο πλοίο αν και χωρίς μερίδιο από το χρυσό. Οπότε τα Νο 203 και 204 σχηματίζουν τη δεύτερη νοητή ομάδα αντίδρασης και καταψηφίζουν όλες τις επόμενες προτάσεις.
Τα Νο 205, 206 και 207, αν είναι οι τελικοί πειρατές, δεν θα έχουν την ίδια τύχη, μιας και οι προτάσεις τους δεν συγκεντρώνουν την απαραίτητη πλειοψηφία. Το Νο 208 όμως, θα πάρει επιπλέον τις ψήφους των Νο 205, 206 και 207 για να μην καταλήξουν στη θάλασσα και η πρότασή του θα γίνει αποδεκτή με 104 ψήφους. Συνεπώς η επόμενη ομάδα είναι τα Νο 205, 206, 207 και 208.
Επεκτείνοντας αυτή τη λογική η επόμενη ομάδα είναι τα Νο 209-216, μετά τα Νο 217-232, στη συνέχεια τα Νο 233-264, τα Νο 265-328 και τα Νο 329-456. Από τον πειρατή Νο 457 και μετά όλες οι προτάσεις καταψηφίζονται από τους προηγούμενους και δεν καταφέρνουν μέχρι και το Νο 500 να σχηματίσουν ομάδα ικανή να τους δώσει πλειοψηφία.
Οπότε η απάντηση του γρίφου στην πιο ενδιαφέρουσα παραλλαγή του είναι πως οι πειρατές Νο 500 έως 457 πετάγονται στη θάλασσα, ενώ ο πειρατής Νο 456 προτείνει να πάρουν από ένα νόμισμα οι πειρατές Νο 2, 4, 6, …, 200 (ή οι 1, 3, 5, …, 199) και κανένα νόμισμα όλοι οι υπόλοιποι και η πρότασή του γίνεται αποδεκτή από τους 100 που θα πάρουν νόμισμα συν του πειρατές με τα Νο 329 έως 456.

civil είπε...

Aκριβώς! Εκπληκτικό;

pantsik είπε...

Αυτός ο γρίφος είναι κι εμένα ένας από τους αγαπημένους μου. Με την παραλλαγή που μου επισήμανες φαίνεται πως έχει ακόμα περισσότερο βάθος απ' ότι αρχικά νόμιζα. Στους 500 γίνεται αποδεκτή η πρόταση του Νο 456; ποιος θα το φανταζόταν!

Ανώνυμος είπε...

διλαδι ο No 5 δινει χριμα μόνο στους μονούς,ε?

pantsik είπε...

Ναι.

Ανώνυμος είπε...

kai an o No 2 pei ston No 1 na parei ta 70 nomismata,pali den tha ton psifisei?

pantsik είπε...

@Ανώνυμος: Όχι. Διάβασε το Νο 2 της λύσης για να καταλάβεις γιατί.

Ανώνυμος είπε...

ki an pei na parei o No 1 kai ta 100 nomismata,pali den tha ton psifisei?

Ανώνυμος είπε...

ki an misoun ton 203?

pantsik είπε...

@Ανώνυμος: Τότε θα το ψήφιζε. Αλλά σε αυτήν την περίπτωση δεν αλλάζει τίποτα στη λογική των πειρατών.

pantsik είπε...

Αν θυμάμαι γράφω και στις δύο περιπτώσεις τι γίνεται με τον 203.

Ανώνυμος είπε...

exeis dikio

Captain X είπε...

Suggnomi alla na rotiso, anti na katsei na skeftei olo auto, gt dn to xorize sta tria ??? dld ta nomismata itan 100 sosta ?? kai xreiazotan 3is psifous + tin dikia tou,
an elege ton eayto tou(No5) to No 4 kai to No 3 px na pernane apo 33 nomismata o kathenas kai to 1 nomisma pou apemeine na to deinan ston No2, oste kai kala metaksi tous na itan isomirasia. tote sigoura kai xoris risko tha perne tis 3is psifous, dioti o idios tha psifize ton eauto tou kai oi alloi kai oi alloi epeidi itan kai autoi aplistoi tha to dexontousan na ta moirazontousan etsi metaksi tous.

pantsik είπε...

@Captain X: Διότι με τον τρόπο που περιγράφω ο Νο 5 παίρνει 97 νομίσματα ενώ με τον δικό σου τρόπο παίρνει μόνο 33. Αναφέρω στην περιγραφή πως οι πειρατές είναι εξαιρετικά άπληστοι, άρα θα σκεφτούν τον τρόπο που τους αποφέρει τα περισσότερα νομίσματα, όσο πολύπλοκος κι αν είναι.

asofe είπε...

Ο γριφος εχει μια αντιφαση.Ο αρχηγος προτεινε αυτον τον τροπο επειδη θεωρουσε οτι ως αρχηγο τον εριχνε η ιση μοιρασια. Αλλα ως εξαιρετικά άπληστος που σκέφτεται λογικά και γνωρίζει καλά τους αλλους θα επρεπε να φτασει στο συμπερασμα οτι θα αναγκαζοταν να συμβιβαστει με τα 2 νομισματα.

pantsik είπε...

@asofe: Έχεις δίκιο. Ας πούμε πως όταν έκανε την πρόταση δεν είχε αναλύσει τη διαδικασία σκέψης των υπολοίπων και νόμιζε πως απορρίπτοντας τις προτάσεις των προηγούμενων θα κατέληγε με τη μερίδα του λέοντος.

Ανώνυμος είπε...

episis meta tha ton kanane tou alatiou ton 5 epidi edose ligotera apo 10 ston kathe 1 o aplistos
nick

swt είπε...

Πιο αληθοφανές είναι το σενάριο όπου πρώτος κάνει πρόταση ο καπετάνιος και αν η πρότασή του δεν πάρει τουλάχιστον τις μισές ψήφους, τον πετάνε στη θάλασσα ενώ αναλαμβάνει καπετάνιος ο δεύτερος κ.ο.κ.

pantsik είπε...

@swt: Το ερώτημα είναι αν ο αρχηγός πριν προτείνει τη διαδικασία έχει αναλύσει στο μυαλό του το τελικό αποτέλεσμα ή όχι.
Αν δεν το έχει αναλύσει τότε με τον τρόπο που προτείνει στο γρίφο φαίνεται πως ξεσκαρτάρονται ένας-ένας οι πειρατές από τον τελευταίο της ιεραρχίας και μοιράζονται τα χρήματα οι τελευταίοι.
Αν τον έχει αναλύσει τότε πράγματι θα προτείνει να ξεκινήσει η διαδικασία από αυτόν.
Για εμάς όμως που διαβάζουμε το γρίφο για πρώτη φορά και δεν έχουμε αναλύσει ακόμα την κατάσταση, μας φαίνεται πιο φυσιολογική η πρόταση του αρχηγού όπως δίνεται στο γρίφο και πιο αναπάντεχο το τελικό αποτέλεσμα.

Kyriaki Blt είπε...

Υπάρχει σωστότερη λύση.
Όταν μείνουν 4 πειρατές ο τέταρτος προτείνει στον τρίτο 0 νομισματα στον δεύτερο 1νόμισμα και στον πρώτο 0 νομίσματα και κρατάει για αυτόν 99.

pantsik είπε...

@Kyriaki Blt: Ο 4ος θέλει 3 ψήφους για να περάσει η πρότασή του. Μην την πρόταση που κάνεις θα πάρει μόνο τη δική του.