THMMY.gr

ΠΡΟΒΛΗΜΑ: Τέσσερις άκαρδοι και εγωιστές ληστές έχουν κλέψει 1000 φλουριά και θέλουν να τα μοιράσουν. Το πρωτόκολο που θα χρησιμοποιήσουν προέρχεται από τις αρχαίες ληστρικές παραδόσεις και είναι το εξής:

1) Ο αρχαιότερος ληστής (δηλ. ο ληστής Λ1) προτείνει μια κατανομή των φλουριών και οι τέσσερις ληστές ψηφιζουν.
2) Αν η πρόταση συγκεντρώσει το 50% των ψήφων ή παραπάνω η κατανομή γίνεται σύμφωνα με την πρόταση.
3) Αν η πρόταση συγκεντρώσει κάτω από 50% των ψήφων, ο Λ1 εκτελείται, αρχαιότερος ληστής είναι τώρα ο Λ2 και η διαδικασία επναλαμβάνεται.

ΕΡΩΤΗΜΑ: Τι πρόταση πρέπει να καταθέσει ο Λ1 ώστε να μεγιστοποιήσει το κέρδος του?

ΔΙΕΥΚΡΙΝΙΣΕΙΣ ΚΑΙ ΥΠΟΔΕΙΞΕΙΣ:
1) Αν ο Λ1 εκτελεστεί, προφανώς έχει κέρδος 0.
2) Ζητούμε το μέγιστο ΒΕΒΑΙΟ κέρδος, ή αν θέλετε το μέγιστο ελάχιστο (max min) βέβαιο κέρδος.
3) ΣΗΜΑΝΤΙΚΟ: Είπαμε ότι οι ληστές είναι εγωιστές και άκαρδοι. Άρα ο καθένας θα ενεργήσει ώστε να μεγιστοποιήσει το δικό του κέρδος.
4) Σκεφτείτε ΕΠΑΓΩΓΙΚΑ

ΔΙΑΔΙΚΑΣΤΙΚΑ
Στείλτε μου με personal message την απάντηση σας. Θα περιμένω 3-4 μέρες και μετά θα κάνω ένα post που θα συγκεντρώνει τις απαντήσεις που έλαβα.

ΑΛΛΕΣ ΠΑΡΑΤΗΡΗΣΕΙΣ
1) Το πρόβλημα είναι αρκετά ανοιχτό. Π.χ. μπορείτε να σκεφτείτε τις περιπτώσεις  2, 3, 4, 5 ληστών και, φυσικά, τελικά να καταλήξετε στους Ν ληστές. Πρέπει να πω ότι ξέρω τουλάχιστον μια λύση, η οποία όμως δεν με ικανοποιεί απόλυτα.
2) Οποιαδήποτε ομοιότητα με συνελεύσεις Τμημάτων  , Συλλόγων κτλ είναι τυχαία  ;)

Actually οι λύσεις είναι στα επόμενα μηνύματα, απλά ήθελα να πω ότι θα τα δημοσιεύσω με την σειρά που τα έλαβα και στο τέλος θα βάλω και ένα δικό μου μήνυμα με απορίες / επκτάσεις.

Θ

« Sent to: thanasiskehagias on: March 30, 2006, 15:50:57 PM »

Κ. Κεχαγιά αν και το γρίφο που θέσατε τον ξέρω λίγο διαφορετικά δε δυσκολεύτηκα ιδιαίτερα να βρω την απάντηση. Έστω Λ1, Λ2, Λ3, Λ4 οι ληστές (Λ1 ο αρχαιότερος, Λ4 ο νεότερος) Η πρόταση του Λ1 ληστή θα είναι: Να πάρει αυτός 999 και να δώσει στον Λ3 1 φλουρί, ο νεότερος 0 και ο Λ2 επίσης 0. Θα πάρει την ψήφο του και αυτή του Λ3 και θα επικρατήση η πρόταση του. Ελπίζω να το εξήγησα κατανοητά.
===================================
(και όταν του ζήτησα να το εξηγήσει, έστειλε την εξής συνέχεια)
===================================

«  Sent to: thanasiskehagias  on: March 30, 2006, 21:12:56 PM »

Το σκεπτικό μου είναι το εξής:
1) Αν μείνει μόνο ένας ληστής θα ζητήσει τα 1000 φλουριά και δίνει λογαριασμό σε κανέναν!
2) Αν μείνουν δύο ληστές, ο νεότερος (Λ4) και ο αμέσως επόμενος (Λ3), τότε την πρόταση την κάνει ο Λ3. Θα ζητήσει και τα 1000 φλουριά και με τη δική του ψήφο (ο Λ4 ψηφίζει αρνητικά φυσικά), συγκεντρώνει το απαιτούμενο 50% (1 ψήφος σε σύνολο 2).
3) Αν μείνουν τρεις λειστές, ο Λ4, Λ3, Λ2, την πρόταση την κάνει ο Λ2. Σκέφτεται ότι θέλει τουλάχιστον 2 ψήφους. Η μία είναι η δικιά του. Για να πάρει άλλη μία θετική ψήφο πρέπει να δώσει σε έναν τουλάχιστον από τους Λ4 και Λ3 κάτι παραπάνω (και αυτό θα είναι το ελάχιστο φυσικά) από ότι θα έπαιρναν από τη μοιρασιά στην περίπτωση 2. Αυτός φυσικά είναι ο Λ4 και του προτείνει 1 φλουρί και αυτός το δέχεται γιατί ξέρει ότι αν δεν συμφωνήσει και μείνουν 2 ληστές, θα πάρει 0 φλουριά. Έτσι ο Λ2 παίρνει 999 και δίνει 1 στον Λ4. Ο Λ3 (δεν παίρνει τίποτα) ψηφίζει φυσικά αρνητικά, αλλά η πρόταση του Λ2 περνάει με 66%.
4) Αν είναι λοιπόν και οι τέσσερις ληστές, την πρόταση την κάνει ο αρχαιότερος, ο Λ1. Σκέφτεται ότι θέλει τουλάχιστον 2 ψήφους. Η μία είναι η δική του. Πρέπει να προτείνει τουλάχιστον ένα φλουρί παραπάνω σε κάποιον σε σχέση με αυτά που θα έπαιρνε αν έμεναν 3 ληστές. Αυτός είναι ο Λ3. Του δίνει 1 φλουρί και αυτός δέχεται γιατί ξέρει ότι αν καταψηφίσει την πρόταση αυτή και μείνουν 3 ληστές δε θα πάρει κανένα φλουρί (δείτε την παραπάνω περίπτωση). Στους άλλους 2 δε δίνει τίποτα. Η ψήφος του περνάει με 50%.

«  Sent to: thanasiskehagias  on: March 30, 2006, 23:06:49 PM »
   
Έστω Ν ο αριθμός των ληστών
Ο Λ1 θέλει να ελαχιστοποιήσει το κόστος  και να μεγιστοποιήσει το κέρδος.
Ο Λ1 ελαχιστοποιεί το κόστος αν εξασφαλίσει τη σωματική του ακεραιότητα.Αυτό επιτυγχάνεται αν πάρει με το μέρος του(με την κατανομή που θα προτίνει)τουλάχιστον το 50% των ληστών(μαζι και ο Λ1).Δηλαδή:
Α)Αν Ν αρτιος να παρει με το μέρος του τους Ν/2 ληστές
Β)Αν Ν περιττος          >>           >>           (Ν+1)/2 ληστές
Άρα αρκεί με την κατανομή που θα προτίνει να ικανοποιούνται μόνο αυτοί.Αμέσως συμπεραίνουμε ότι η κατανομή θα αφορά μόνο αυτό το 50% και ως αποτέλεσμα το κέρδος του Λ1 μεγαλώνει.
Επειδή οι ληστές είναι εγωιστές και θέλουν να μεγιστοποιήσουν κι αυτόι το κέρδος τους ο μόνος τρόπος για να έχει ΒΕΒΑΙΟ το 50% και άνω των ψήφων ο Λ1 είναι να μοιράσει επι ίσοις όροις τα φλουριά.Δηλαδή:
Α)(αριθμός φλουριών)/(Ν/2) αν Ν άρτιο
Β)(αριθμός φλουριών)/((Ν+1)/2) αν Ν περιττό
Με οποιαδήποτε άλλη κατανομή ή ο Λ1 θα "χάνει" ή το 50% των ληστών  θα δυσαρεστηθεί και ίσως(άρα χάνεται το ΒΕΒΑΙΟ) να μην ψηφίσει την κατανομή.

Άρα τελικά η κατανομή που θα πρέπει να προτίνει ο Λ1 ώστε να έχει το μέγιστο κέρδος και το ελάχιστο κόστος( να μην τον σκοτώσουν) ειναι:
Α)(αριθμός φλουριών)/(Ν/2) αν Ν άρτιο
Β)(αριθμός φλουριών)/((Ν+1)/2) αν Ν περιττό

υγ1.:Ποιους θα επιλέξει ο Λ1 για να μοιραστεί τα φλουριά είναι αδιάφορο.Αρκεί να εξασφαλιζει το 50%.Σίγουρα όμως τον συμφέρει να μη φτιάχει συμμορίες με περιττό αριθμό ληστών

Αν οι ληστές ήταν δύο, ο αρχαιότερος θα πρότεινε να πάρει όλα τα λεφτά, θα ψήφιζε τον εαυτό του και θα τα έπαιρνε:

Ν=2: Β 1000 Α 0

Όταν οι ληστές είναι τρεις, ο αρχαιότερος χρειάζεται άλλη μία ψήφο. Για να την πάρει, πρέπει να προσφέρει στον Α περισσότερα από όσα θα πάρει αν ο Γ εκτελεστεί. Του δίνει λοιπόν το μικρότερο δυνατό ποσό (υποθέτω ότι τα φλουριά δεν έχουν υποδιαιρέσεις):

Ν=3: Γ 999 Β 0 Α 1

Για τέσσερις ληστές, ο αρχαιότερος θα προτιμήσει τη φτηνότερη ψήφο, αυτή του Β:

Ν=4: Δ 999 Γ 0 Β 1 Α 0

Ο πέμπτος ληστής θα εξαγοράσει την ψήφο αυτών που στην αμέσως προηγούμενη περίπτωση δε θα έπαιρναν τίποτα (αφού χρειάζεται δύο ψήφους εκτός της δικής του):

Ν=5: Ε 998 Δ 0 Γ 1 Β 0 Α 1

Επαγωγικά, ο καθένας θα εξαγοράζει πάντα με το μικρότερο δυνατό ποσό (1 φλουρί;) τις ψήφους αυτών που στην αμέσως προηγούμενη περίπτωση δε θα έπαιρναν τίποτα, οι οποίες τελικά είναι και ακριβώς όσες του χρειάζονται ([ν/2], αφού λογικά η κάθε μοιρασιά πάει μονά-ζυγά αντίστροφα από την προηγούμενη) και δε θα δίνει τίποτα στους υπόλοιπους. Δηλ.

Νιοστός 999-[(ν+1)/2] Επόμενος 0 Μεθεπόμενος 1 κλπ.

Αν οι ληστές είναι 2001, ο αρχαιότερος δεν έχει καμία πιθανότητα να βγάλει κέρδος.

«  Sent to: thanasiskehagias  on: Today at 15:26:59 »

Η προτεινόμενη κατανομή είναι:

Λ1 999
Λ2 0
Λ3 1
Λ4 0

Μπορούμε να λύσουμε το γρίφο εύκολα ξεκινώντας από πίσω προς τα μπρος.


Αν έχουμε 1 ληστή τον Λ4 το μέγιστο βέβαιο κέρδος είναι να πάρει όλα τα λεφτά αυτός.

Αν έχουμε 2 ληστές το μέγιστο κέρδος του Λ3 είναι να πάρει αυτός όλα τα λεφτά γιατί όποια πρόταση και να κάνει θα περάσει αφού θα έχει τη ψήφο του που αποτελεί το 50%

Αν έχουμε 3 ληστές τον Λ2,Λ3,Λ4 το μέγιστο βέβαιο κέρδος για τον Λ2 είναι

Λ2 999
Λ3 0
Λ4 1

Ο Λ4 θα αναγκαστεί να ψηφίσει θετικά διότι σε διαφορετική περίπτωση σκοτώνεται ο Λ2 και μεταβαίνουμε στην περίπτωση όπου έχουμε 2 ληστές και ο Λ4 δε παίρνει τίποτα.

Ομοίως όταν έχουμε 4 ληστές η βέλτιστη πρόταση για τον Λ1 είναι:

Λ1 999
Λ2 0
Λ3 1
Λ4 0

γενικά η κατανομές είναι

                                   
                               998
                         999 0
                   999 0    1
          1000  0    1     0
1000   0       1     0    1

Οπότε μπορούμε να υπολογίσουμε και το κέρδος του πρώτου ληστή το οποίο είναι
Κ=δ((Ν-1)/2) όπου Ν το πλήθος των ληστών, δ η ελάχιστη νομισματική μονάδα και με / συμβολίζουμε το πηλίκο της ευκλείδειας διαίρεσης.

Οπως βλέπετε 3 από τους 4 δίνουν την ίδια λύση, η οποία και είναι σωστή σύμφωνα με την εκφώνηση, γιατί ο κάθε ληστής (και ιδιαίτερα οι νεότεροι) θα παίξουν για να πάρουν το ένα σίγουρο φλουρί (μεγιστοποιούν το ελάχιστο βέβαιο κέρδος¨max min).

Η μήπως όχι?

Εν πάση περιπτώσει, υπάρχει κάτι που εμένα δεν με ικανοποιεί στην παραπάνω λύση. Έστειλα στον dimvam το παρακάτω μήνυμα:

====================================
(thanasiskehagias)
Ας μείνουμε στην περίπτωση 3 ληστών. Επίσης δεχόμαστε --έπρεπε ίσως να το πω ξεκάθαρα-- ότι δεν παίζουν υποδιαιρέσεις φλουριών κτλ.)

Το αδύνατο σημείο (κατά την γνώμη μου) είναι το εξής. Αν ο Λ3 απειλήσει τον Λ1 ότι θα τον καταψηφίσει, ο Λ1 έχει κίνητρο να του δώσει περισσότερα από 1, γιατί αν δεν το κάνει, και ο Λ3 καταψηφίσει, τα χάνει όλα (και πεθαίνει, αλλά αυτό μπορούμε να το αγνοήσουμε).

Αν δούμε το πρόβλημα έτσι, γίνεται πολύ λιγότερο ξεκάθαρο (ίσως για να λυθεί χρειάζονται και άλλες, σαφώς διατυπωμένες, παραδοχές για την συμπεριφορά των ληστών) αλλά και πιο ενδιαφέρον. Πολύ πιθανό να λύνεται με μεθόδους της θεωρίας παιγνίων (game theory). Δεν ξέρω αλλά με ενδιαφέρει.

Άρα μια κατεύθυνση περαιτέρω μελέτης είναι σε σχέση με "εκβιαστικές" κινήσεις.
====================================

και αυτός απάντησε
====================================
(dimvam)

Έτσι το πρόβλημα γίνεται πολύ πιο σύνθετο. Πάντως στη συγκεκριμένη περίπτωση που αναφέρατε, δεν θα είχε νόημα γιατί αν τελικά δεν ισχύσει η πρόταση του Λ3 και μείνουν 2 ληστές, ο Λ1 δε θα πάρει κανένα φλουρί, ενώ στην εκφώνηση του γρίφου, λέγεται ότι: Άρα ο καθένας θα ενεργήσει ώστε να μεγιστοποιήσει το δικό του κέρδος.. Έτσι αν ο Λ3 δεν υποκύψει στον εκβιασμό, ο Λ1 δε θα πάρει τίποτα. Το σίγουρο είναι ότι ο γρίφος γίνεται πιο πολύπλοκος και δε λύνεται με τα δεδομένα που δίνονται.
====================================

Εσείς τι πιστεύετε?  Προφανώς η λύση του Panos προσπαθεί να καλύψει της έννοιες της δικαιοσύνης αλλά και του εκβιασμού.

Μια που η "βασική" λύση του γρίφου δόθηκε, αν έχετε περαιτέρω σχόλια, θα έλεγα πλέον να τα δημοσιεύσετε κατευθείαν (αντί να μου στείλετε PM)

Θ

Πριν από λίγο διαπίστωσα την ύπαρξη του γρίφου και με ενδιαφέρον είδα τις απόψεις των συναδέλφων.

Με τα δεδομένα που υπήρξαν δόθηκε μία ικανοποιητική λύση. Αφού όμως ζητάμε και άλλες παραμέτρους, ο σημαντικότερος από όλους είναι η ανομοιομορφία που υπάρχει στους ληστές λόγω του παράγοντα άνθρωπος, πρόβλημα που δεν λύνεται με μαθηματικά:
Και εξηγώ:
Ο Αρχιληστής έχει να επιλέξει μεταξύ μεγιστου δυνατού κέρδους και θανάτου, τι θα επικρατήσει; η απληστία ή η επιβίωση;
Το να κερδίσει με το ελάχιστο δυνατό ποσό τους νεότερους σε ιεραρχία είναι λογικό όσο και επικίνδυνο γιατί αν μπλέξει με διαπλοκή μπορούν εύκολα να χαθούν κάποιοι ψήφοι (ο δευτερος μπορει να τους υποσχεθει μεγαλύτερο ποσό).
Από την άλλη οι μόνοι που έχουν ελπίδες να καθορίσουν την μοιρασιά είναι οι 2-3 επόμενοι στην ιεραρχία όμως και αυτοί θα αντιμετωπίσουν το ίδιο διλημμα με τον αρχιληστή όταν έρθει η σειρά τους, οπότε μπορούν να ικανοποιηθούν με κάποιο ποσό.
Γενικά θεωρώ οτι ο Αρχιληστης οφείλει να κατανείμει τα κέρδη με ένα σεβαστό ποσό για αυτόν και τα υπόλοιπα σε όλους τους άλλους με βάση την ιεραρχία τους.
Σκοπός είναι να μην παίζει στο 50% που πολύ εύκολα γίνεται 49.9%

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

Αν βγάλουμε αυτό το κομματάκι από την εκφώνηση, το πρόβλημα δεν έχει πια νόημα.

Με τη λύση που έδωσα πιο πολύ προσπάθησα να εξασφαλήσω το ΒΕΒΑΙΟ που λέτε στη 2η υπόδειξη.Μιας και μπαίνει η παράμετρος "άκαρδοι και εγωιστές" δεν νομίζω ότι εξασφαλίζεται το ΒΕΒΑΙΟ με την άλλη λύση!Κανείς δεν συνυπολόγισε το κόστος.Δεν προσπαθούμε να μεγιστοποιήσουμε μόνο το κέρδος αλλά να ελαχιστοποιήσουμε και
το κόστος και το κόστος για τον Λ1 είναι η ζωή του.Πιστεύω κακώς λέτε στην εκφώνηση ότι αν σκοτώσουν τον Λ1 το κέρδος του είναι μηδέν.Το κέρδος του θα ήταν 0 ακόμα και αν δεν έπερνε αυτός τίποτα αλλά εξασφάλιζε τη ζωή του.Με λίγα λόγια  πρέπει να ξεχωρίσουμε το κέρδος από το κόστος.Το κόστος είναι και αυτό που πρώτα πρέπει να εξασφαλιστεί σε μια παρέα απο άκαρδους(εκβιαστές) ληστές γιατι τι να τα κάνεις στο κάτω κάτω τα λεφτά αν δεν έχεις την υγειά σου...   :)

Πραγματικά θα ήταν ενδοιαφέρον να το δει κάνεις και με θεωρία παιγνίων αλλά η παράμετρος "εκβιασμός" θα το έκανε εξαιρετικά πολύπλοκο και δεν ξέρω αν θα εμφάνιζε το παίγνιο ισορροπία Nash

Μα βρε Πάνο, δεν υπάρχει ρίσκο για τη ζωή του πρώτου ληστή με τη λύση που δώσαμε. Εκτός αν οι υπόλοιποι ληστές είναι βλάκες (η βλακεία είναι απρόβλεπτη).

OK, λάθος μου που είπα ότι αν η πρόταση απορριφθεί ο ληστής εκτελείται. Πείτε ότι βγαίνει στην σύνταξη ή κάτι άλλο που έχει 0 κόστος -- έτσι το μόνο του "κόστος" είναι ότι έχασε τα φλουριά. Αλλάζει κάτι? Αν ναι, τι?

Θ

Ναι υπάρχειρίσκο αφού οι ληστές είναι "άκαρδοι και εγωιστές",και τονίζεται κιόλας με υπόδειξη ότι πρέπει να ληφθει υπόψη αυτό.Αν του λέγανε δηλαδή του  Λ1:"προτιμώ να σου κόψω το λαιμό παρά να ΄πάρω το 1 φλουρί που μου δίνεισ"(όντας άκαρδος) τι θα έκανε ο Λ1?Με λίγα λόγια η λύση αυτή, κατα τη γνώμη μου πάντα,θα ήταν σωστή αν έλεγε στην εκφώνηση ότι κάθε ληστής θέλει απλά να μεγιστοποιήσει το κέρδος του.Εγώ "κολλάω"στο "άκαρδοι"!!

Αν τώρα το μόνο κόστος για το Λ1 ήταν να χάσει τα φλουριά τότε αλλάζει το πράμα.Τότε φεύγουμε απο τα όρια του γρίφου και πάμε σε επίπεδο διαπραγματεύσεων,"τόσα σου δίνω" "όχι θέλω τόσα" "πάρτα γιατί θα πάω σε άλλον" κτλ
Ελληνικά πράγματα δηλαδή...
Ίσως τότε να λύνόταν με PLA μαθαίνοντας στον Λ1 τις διαπραγματευτικές στρατηγικές των άλλων ληστών(ψιλά γράμματα και ξεφεύγουμε...)

Πάντως άμα φύγει το άκαρδοι και η συγκεκριμένη υπόδειξη συμφωνώ απόλυτα με τη λυση σας!

Τώρα είδα το γρίφο. Έχει πολύ ενδιαφέρον.

Για το σχόλιο που κάνατε έχω να πω το εξής:

Ξεκινάμε από την περίπτωση που είναι 3 ληστές. Ο Λ3 απειλεί το Λ1 ότι θα τον καταψηφίσει αν του δώσει μόνο ένα φλουρί. Ο Λ1 προτείνει να δώσει ένα φλουρί. Τότε ο Λ3 τι κάνει; Ξέρει ότι αν καταψηφίσει δε θα πάρει τίποτα, αλλιώς παίρνει ένα φλουρί, οπότε σίγουρα ψηφίζει υπέρ. Μέχρι εδώ συμφωνώ με τη Nessa.
Τα πράγματα θα άλλαζαν αν ο ληστής Λ3 έδινε μια δεσμευτική απόφαση που δεν μπορούσε να την αλλάξει στη συνέχεια του τύπου "Αν μου δώσει τουλάχιστον n φλουριά είμαι υπέρ, αλλιώς είμαι κατά". Τότε ο Λ1 θα ήξερε ότι αν δεν του δώσει τα n φλουριά, αυτός θα τα χάσει όλα (ή θα πεθάνει).  Επομένως θα προτιμούσε να του δώσει τα n φλουριά και αυτός να κρατήσει τα 1000-n. Με αυτό το σκεπτικό ο Λ3 θα μπορούσε να ζητήσει μέχρι 999 φλουριά. Όμως δεν πρέπει να ξεχνάμε ότι αν μπορεί να κάνει και ο Λ2 μια πρόταση που το δεσμεύει, τότε θα μπορούσε να ζητήσει να πάρει m<n φλουριά για να ψηφίσει αυτός υπέρ της πρότασης του Λ1. Επομένως, σε κάθε περίπτωση αυτός που θα ζητούσε από το Λ1 τα λιγότερα (δεσμευόμενος από συμφωνία που δεν μπορεί να αρνηθεί) θα τα έπαιρνε. Άρα, αναγκαστικά, για να μην τα χάσουν όλα και ο Λ2 και ο Λ3 θα ζητήσουν από 1 φλουρί. Τότε ο Λ3 θα δώσει το φλουρί σε αυτόν που συμπάθησε περισσότερο (αφού ο ίδιος θα πάρει έτσι κι αλλιώς 999). Θα ήταν ακόμη πιο πολύπλοκο αν ο Λ2 μπορούσε να δεσμευτεί για την πρόταση που θα έκανε όταν θα ερχόταν η σειρά του.

Πάμε να δούμε τώρα την περίπτωση που δεν υπάρχει δυνατότητα να δεσμευτούν οι ληστές για το τι θα ψηφίσουν, δηλαδή αποφασίζουν τι θα ψηφίσουν αφού γίνει η πρόταση από το Λ1. Όπως είπα και παραπάνω όταν είναι 3 ληστές ο Λ3 δεν μπορεί να κάνει κανέναν εκβιασμό. Όταν είναι περισσότεροι οι ληστές, εκβιασμός θα μπορούσε να γίνει αν ένας ληστής ξέρει ότι καταψηφίζοντας το Λ1, ο Λ2 θα του δώσει τουλάχιστον 1 φλουρί, άρα δε θα έχανε τίποτα αν απειλούσε να καταψηφίσει το Λ1 που του δίνει μόνο ένα φλουρί. Επίσης, "εκβιασμός" ή μάλλον... συμφωνία που συμφέρει το Λ1 θα μπορούσε να γίνει, αν κάποιος ληστής ήξερε ότι ούτε στη μοιρασιά του Λ1 ούτε στου Λ2 θα έπαιρνε φλουριά και μπορούσε να προτείνει στο Λ1 κάτι που θα τους συνέφερε και τους δύο. Όμως, όπως βλέπουμε από την πορεία της κατανομής καθώς ο αριθμός των ληστών αυξάνονται, κάθε φορά που αυξάνεται κατά ένα ο αριθμός των ληστών, αυτοί που έπαιρναν 0 φλουριά καταλήγουν να παίρνουν 1, και αυτοί που έπαιρναν ένα καθώς και αυτός που έκανε τη μοιρασιά καταλήγουν να παίρνουν 0. (βλ. κατανομή στη λύση του BoboMastoras). Άρα δεν μπορεί να γίνει μια συμφωνία κάποιου είδους από τα παραπάνω.

Πάμε τώρα στο πιο ωραίο...
Η μόνη δυνατότητα που μένει για εκβιασμό, είναι να συνεννοηθούν δύο ληστές που είναι αρκετά νέοι ώστε να έχουν τουλάχιστον 3-4 πιο παλιούς από αυτούς. Η συμφωνία θα μπορούσε να έχει την εξής μορφή: Ζητάνε και οι δύο απο τον αρχαιότερο να κρατήσει για τον εαυτό του 1 φλουρί, να δώσει στους άλλους που θέλει να εξαγοράσει την ψήφο τους από ένα φλουρί και να μοιράσει τα υπόλοιπα φλουριά σε αυτούς τους δύο. Έστω ότι ο Λ10 και ο Λ11 το ζητάν αυτό από το Λ1. Αν ο Λ1 προτείνει αυτό που δώσαν στη λύση τα 3 παιδιά, δηλαδή από ένα φλουρί σε αυτούς που στην επόμενη μοιρασιά δεν παίρνουν τίποτα και κανένα φλουρί στους υπόλοιπους, τότε ο Λ11 παίρνει ένα φλουρί και ο Λ10 κανένα. Ο Λ10 σίγουρα καταψηφίζει. Ο Λ11 αν υπερψηφίσει παίρνει ένα φλουρί. Αν καταψηφίσει τότε κάνει πρόταση ο Λ2 και οι ίδιοι Λ10 και Λ11 ζητούν το ίδιο πράγμα, δηλαδή να μοιραστούν τα περισσότερα φλουριά σε αυτούς. Ο Λ2 βλέπει ότι κινδυνεύει να πάθει αυτό που έπαθε ο Λ1, οπότε μπορεί να υποκύψει στον εκβιασμό. Οι Λ10 και Λ11 δείχνουν αποφασισμένοι, αφού έχουν ακόμα χρόνο να σταματήσουν τους εκβιασμούς. Ο εκάστοτε αρχιληστής δεν έχει περιθώριο να κάνει συμφωνία με κανέναν για μια μελλοντική μοιρασιά, αφού δε θα έχει τη δυνατότητα να ψηφίσει ξανά. Αν οι άλλοι ληστές δεν είναι συνεννοημένοι, τότε οι Λ10 και Λ11 θα κερδίσουν τον εκβιασμό. Όμως, δεν πρέπει να ξεχνάμε ότι οι ληστές είναι άκαρδοι και εγωιστές και μπορεί να προδώσουν ο ένας τον άλλο. Αν το δούμε επαγωγικά προκύπτει κάτι παράξενο.

Στη σειρά του Λ9, ο Λ11 δεν έχει κανένα λόγο να ψηφίσει κατά, αφού στη σειρά του Λ10, εφόσον οι επόμενοι ληστές δεν έχουν κάνει συμφωνίες για ομαδικούς εκβιασμούς, ο Λ11 δεν παίρνει τίποτα, σύμφωνα με το μοντέλο που προτείνει η κλασική λύση. Άρα δεν μπορεί να γίνει συμφωνία με το Λ10. Πάμε λίγο πιο πίσω, στη σειρά του Λ8. Ο Λ10 ξέρει ότι αν ο Λ8 καταψηφιστεί, τότε ο Λ11 θα ψηφίσει υπέρ του Λ9, επομένως αυτός (ο Λ10) δεν παίρνει τίποτα. Γι' αυτό ο Λ10 πρέπει να ψηφίσει υπέρ του Λ8. Άρα καμιά συμφωνία δε γίνεται μεταξύ του Λ10 και Λ11. Ο Λ8 στηρίζεται στο γεγονός ότι ο Λ9 δεν έχει λόγο να υποκύψει στον εκβιασμό, αφού έχει σίγουρα μαζί του το Λ11. Αν πάμε ακόμα πιο πίσω, βλέπουμε ότι ο Λ11 πρέπει να ψηφίσει το Λ7 γιατί στη σειρά του Λ8 δεν μπορεί να κάνει συμφωνία με το Λ10 και τα χάνει όλα. Ο κάθε αρχιληστής στηρίζεται στο γεγονός ότι ο επόμενός του δεν έχει λόγο να υποκύψει στον εκβιασμό, αφού δε θα μπορεί να γίνει καμιά συμφωνία μεταξύ Λ10 και Λ11. Επομένως, οι Λ10 και Λ11 δεν έχουν καμιά δύναμη; Φαίνεται πολύ παράδοξο (ειδικά στις 2:30 το βράδυ...), αφού παραπάνω είδαμε διαισθητικά ότι μπορούν να εκβιάσουν και να κερδίσουν και οι δύο παραδειγματίζοντας τους αρχιληστές με το να καταψηφίσουν και οι δύο τον προηγούμενο.

Όσο υπάρχουν πολλοί ληστές μέχρι να φτάσουμε στους Λ10 και Λ11, το να βλέπουν οι αρχιληστές τους προηγούμενούς τους να πεθαίνουν (ή έστω να μην παίρνουν τίποτα), τους κάνει να φοβούνται. Επομένως, οι Λ10 και Λ11 έχουν λόγο να δρουν συντονισμένα. Από την άλλη, ο καθένας από τους Λ10 και Λ11 ξέρει ότι αν ο άλλος τον πουλήσει θα πάρει ο άλλος ένα φλουρί και αυτός τίποτα. Και κάποια στιγμή ο Λ11 ξέρει ότι αν δεν πουλήσει πρώτος τον Λ10, τότε ο Λ10 θα έχει μεγαλύτερο κέρδος, αφού θα πάρει κάπου 900+ φλουριά. Δηλαδή ο Λ11 έχει λόγο να πουλήσει τον Λ10, ο Λ10 το ξέρει, άρα έχει λόγο να πουλήσει το Λ11.
Μακροσκοπικά, λοιπόν, οι δύο ληστές έχουν λόγο να δρουν συντονισμένα, όμως μικροσκοπικά έχουν λόγο να πουλήσει ο ένας τον άλλον.  :???: :???: :-\ :-\
Είναι ήδη αργά για να το ψάξω περισσότερο (αύριο πάλι...). Ίσως είναι κάτι που δε βλέπω. Τώρα απλά θέτω τον προβληματισμό.
(Ουφφ!)

Αλέξης Γελαστόπουλος

Εγώ πιστεύω ότι αυτός που επινόησε το γρίφο δε σκέφτηκε καμία πτυχή από όσα συζητάμε τώρα. Η κλασική λύση του γρίφου, είναι αυτή που δώσαμε. Συμφωνώ με την ανάλυση που κάνατε παραπάνω, απλώς δε νομίζω ότι στέκει σαν λύση αυτού του γρίφου. Το πρόβλημα γίνεται περίπλοκο. Άλλωστε στην εκφώνηση του γρίφου η λέξη "άκαρδοι" ίσως μεταφράζεται (τουλάχιστον όπως το καταλαβαίνω εγώ) ότι κάποιος ληστής δε θα συνεργαστεί με άλλους ληστές.

Αρα μια καλή λύση θα ναι αυτη που θα συμπεριλαμβάνει  - "ξεπερνά" - προβλήματα "πουλήματος" και "συνενοήσεων".

Λοιπόν καταθέτω ένα κάπως τελικό (για μένα, εννοείται) Post.

Η αλήθεια είναι ότι ο γρίφος με τους ληστές (ή διάφορες παραλλγές του) ήταν ψιλογνωστός και η γενικά παραδεκτή λύση είναι η 999-0-1-0. Όπως είπα και στο πρώτο μου post, η λύση αυτή δεν με ικανοποιεί απόλυτα. Μετά από την συζήτηση που έγινε στο forum, έχω καταλάβει καλύτερα και γιατί δεν με ικανοποιεί και αυτό θα προσπαθήσω να εξηγήσω παρακάτω.

Για να γίνουν ξεκάθαρα τα πράγματα, ας πούμε ότι έχουμε 3 ληστές (ο αρχαιότερος είναι ο Λ1, δεύτερος ο Λ2, μετά ο Λ3). Και ακόμη, ας πούμε ότι αν η πρόταση του Λ1 καταψηφιστεί, αυτός δεν εκτελείται, απλά βγαίνει από την μοιρασιά. Τέλος, θα υποθέσω ότι όποια συμφωνία γίνει μεταξύ των ληστών είναι δεσμευτική, δηλαδή ο καθένας θα κάνει ακριβώς αυτό που έχει υποσχεθεί.

Λοιπόν, νομίζω ότι όλοι συμφωνούμε στο εξής: αν ο Λ1 βγει από την μοιρασιά, τότε οι Λ1 και Λ3 παίρνουν 0 φλουριά.  Οπότε σίγουρα οι Λ1 και Λ3 έχουν κίνητρο να καταλήξουν σε κάποια συμφωνία. Ως εδώ όλα είναι όπως τα περιγράφει η "κλασσική" λύση.

Νομίζω ότι αυτό που δεν λαμβάνει υπόψη η κλασσική λύση είναι ότι: όσο κίνητρο έχει ο Λ3 να συμβιβαστεί με τον Λ1, άλλο τόσο έχει και ο Λ1 να συμβ. με τον Λ3. Και αυτό γιατί σε περίπτωση μη συμβιβασμού, κανείς δεν παίρνει τίποτα. Και γι' αυτό η λύση 999-0-1 μου φαίνεται πολύ ετεροβαρής. Νομίζω ότι ο Λ3 θα μπορούσε να απαιτήσει (και ίσως και να πετύχει) την 1-0-999.

Γενικότερα, νομίζω ότι οποιαδήποτε μοιρασιά των 1000 μεταξύ των Λ1 και Λ3 είναι εξίσου "λογική". Με κάποια έννοια η 500-0-500 είναι πιο "δίκαια", αλλά αυτό δεν σημαίνει ότι είναι λογικά αναγκαία.

Υπάρχει και κάτι  ακόμα: Από την στιγμή που οι συμφωνίες είναι δεσμευτικές, τίποτα δεν εμποδίζει είτε τον Λ1 είτε τον Λ3 να έρθει σε συμφωνία με τον Λ2. Π.χ., εάν ο Λ1 παρατηρήσει ότι ο Λ3 έχει μεγάλες απαιτήσεις, μπορεί να στραφεί στον Λ2 και να πει "κύττα, αν με υποστηρίξεις, θα προτείνω 990-10-0. Μη με κοντράρεις, γιατί τότε θα προτείνω 1-0-999 και δεν θα πάρεις τίποτε". Τέλος, όχι μόνο ο Λ1 αλλά και ο Λ3 μπορεί να διαπραγματευτεί με τον Λ2, αν η πιθανή μεταξύ τους συμφωνία είναι δεσμευτική (δηλ. αν μπορεί να είναι σίγουρος ότι ο Λ2 δεν θα υπαναχωρήσει μόλις ξεφορτωθούν τον Λ1).

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

Επειδή μόλις διάβασα αυτό το topic θα ήθελα να κάνω μια παρατήρηση.
Έστω ότι έχουμε 4 ληστές όπως αρχικά ειπώθηκε.
Στη λύση 999 - 0 - 1 - 0 υπάρχει νομίζω bug.
Αν ο καθένας σκέφτεται πως να μεγιστοποιήσει το κέρδος του, ο Λ3 θα επιδιώξει να μείνουν 2 ληστές στο τέλος ώστε να πάρει 1000. Άρα δεν εξαγοράζεται. (Ένας ληστής θα ρίσκαρε να μην πάρει τίποτα αν επρόκειτω να τα πάρει όλα). Η εύκολη ψήφος για τον Λ1 είναι ο Λ4 ο οποίος με βάση την ανάλυση που προηγήθηκε θα πάρει στην καλύτερη 1 (δηλαδή χαμένος απο χέρι). Εγώ λέω στην καλύτερη 500. (Αν μείνουν 3 ληστές ο Λ2 αποκλείεται να του προσφέρει πάνω από τα μισά λόγω ιεραρχίας και ο Λ4 το ξέρει αυτό). Άρα το μόνο που χρειάζεται είναι ο Λ1 να υπερβεί τον εγωισμό του και να δώσει 501 στον Λ4 ώστε να τον εξαγοράσει με βεβαιότητα και να πάρει κι αυτός 499. - Η θέση του Λ1 είναι πολύ επισφαλής αφού ξέρει ότι όλοι θα προσπαθήσουν να τον βγάλουν από τη μέση άρα θα είναι οκ με κάτι λιγότερο από τα μισά.

Με λίγα λόγια προτείνω: 499 - 0 - 0 - 501

Μπορεί να γράφω και βλακείες οπότε ακούω σχόλια.!