10 pirates possèdent un trésor constitué de 100 pièces d'or. Ils se mettent d'accord sur une procédure pour se partager le trésor : le pirate le plus fort va proposer une répartition du butin. Puis, tous les pirates vivants vont voter si oui ou non ils sont d'accord avec cette répartition. Si plus de la moitié (strictement) des pirates est d'accord, le partage se fait suivant cette répartition. Sinon, le pirate qui l'a proposée est tué et on passe au prochain pirate le plus fort, qui fait à son tour une proposition. Et ainsi de suite jusqu'à ce qu'une répartition soit acceptée.
Quelle sera la répartition des pièces d'or ?
Précisions utiles : - Les pirates sont aussi de savants logiciens ! - Chaque pirate veut obtenir le plus de pièces d'or possible - Chaque pirate tient à sa propre vie mais n'hésitera pas à faire tuer un autre pirate s'il est sûr qu'il aura au moins autant de pièces que si ce pirate reste en vie - Si un pirate a le choix de donner une pièce à 2 pirates, il la donnera au pirate le plus faible
Pour résoudre cette énigme, il faut raisonner "à rebours" : il faut se demander combien de pièces d'or chaque pirate peut espérer si tous les pirates avant lui sont tués.
Le dernier pirate, le numéro 10, s'attribuera la totalité des pièces d'or s'il est le seul survivant, puisqu'il est le seul à voter. La répartition sera : numéro de pirates : 10 nombre de pièces : 100
S'il reste les pirates 9 et 10, le pirate 9 est condammé quelque soit sa proposition de répartition. Etant donné qu'ils ne sont que 2 à voter et qu'il faut la majorité absolue pour qu'une proposition soit acceptée, le pirate 10 votera toujours contre le 9. Il pourra ainsi tuer un pirate plus fort que lui et s'attribuer toutes les pièces d'or. Le pirate numéro 9 n'aura rien et sera tué si jamais il ne reste plus que 2 pirates. La répartition sera : numéro de pirates : 9 - 10 nombre de pièces : tué 100
S'il reste 3 pirates, que proposera le pirate n°8 pour maximiser son nombre de pièces ? Si le pirate n°8 est tué, le pirate n°9 sera éliminé au prochain coup. Donc le pirate 9 votera pour la répartition proposée par n°8 afin de préserver sa vie, et ce quelle que soit cette répartition, même s'il n'a aucune pièce. Le pirate n°10 votera lui systématiquement contre la proposition : si le pirate n°8 est éliminé, il sait qu'il gagnera les 100 pièces et restera le seul pirate, et aucune proposition ne lui est plus avantageuse. Le pirate n°8 peut donc proposer de s'accaparer toutes les pièces : lui et le pirate n°9 voteront pour, ce qui lui apporte la majorité absolue avec 2 votes pour et 1 vote contre, la proposition est acceptée. La répartition sera : numéro de pirates : 8 - 9 - 10 nombre de pièces : 100 - 0 - 0
S'il reste 4 pirates, le pirate n°7 doit faire une proposition qui sera acceptée par lui et par au moins 2 autres pirates pour l'emporter. Si sa proposition est rejetée, les pirates n°9 et n°10 n'auront aucune pièce. Il suffit donc au pirate n°7 de leur attribuer une pièce chacun dans sa répartition et il s'assurera ainsi leur vote. Il ne donne en revanche rien au pirate n°8 qui votera de toute façon contre lui puisqu'il espère l'éliminer et récolter les 100 pièces au tour suivant. La répartition sera : numéro de pirates : 7 - 8 - 9 - 10 nombre de pièces : 98 - 0 - 1 - 1
Il suffit de répéter le raisonnement jusqu'au pirate n°1 pour trouver la répartition. A chaque étape, on procède comme suit, en notant i le pirate qui fait la proposition de répartition. Il faut d'abord trouver le nombre de pirates que i doit convaincre pour s'assurer la majorité absolue. Notons ce nombre n. i pourra convaincre ces n pirates de voter pour lui - soit en leur attribuant plus de pièces que ce qu'ils auront si i est tué. Plus précisément il leur proposera 1 pièce en plus que ce qu'ils auront à la prochaine répartition, afin de maximiser son propre nombre de pièces - soit en leur "sauvant la vie" pour ceux qui seraient tués lors des tours suivants si jamais la proposition de i était refusée (comme c'est le cas pour le pirate n°9 quand c'est n°8 qui propose une répartition). A ceux-là, i n'a pas besoin de leur attribuer une pièce. Pour déterminer à quels pirates i va donner des pièces, il faut trouver les n pirates qui ont le moins de pièces, pour dépenser le moins de pièces possibles pour les autres pirates et donc en garder le maximum pour i. Si jamais, pour sélectionner les n pirates, on a le choix entre plusieurs pirates ayant le même nombre de pièces, on gardera les pirates les plus faibles (car un pirate donnera de préférence une pièce à un pirate faible s'il a le choix entre 2 pirates) A chacun des n pirates ainsi sélectionnés, on attribue une pièce de plus que ce que la répartition suivante leur aurait attribué. On ne donne rien aux autres.
En appliquant ce raisonnement aux étapes suivantes, on aboutit à ces répartitions :
S'il reste 5 pirates (2 pirates à convaincre) : numéro de pirates : 6 - 7 - 8 - 9 - 10 nombre de pièces : 98 - 0 - 1 - 0 - 2
S'il reste 6 pirates (3 pirates à convaincre) : numéro de pirates : 5 - 6 - 7 - 8 - 9 - 10 nombre de pièces : 96 - 0 - 1 - 2 - 1 - 0
S'il reste 7 pirates (3 pirates à convaincre) : numéro de pirates : 4 - 5 - 6 - 7 - 8 - 9 - 10 nombre de pièces : 96 - 0 - 1 - 0 - 0 - 2 - 1
S'il reste 8 pirates (4 pirates à convaincre) : numéro de pirates : 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 nombre de pièces : 95 - 0 - 1 - 0 - 1 - 1 - 0 - 2
Le premier pirate peut récolter 94 pièces d'or en proposant cette répartition !
Vous pouvez essayer de chercher quelle aurait été la répartition s'il n'y avait eu besoin que de la moitié des votes pour adopter une répartition. Bon courage !
Aucun commentaire:
Enregistrer un commentaire