Enigme : Le butin des pirates [Solution]

Voici donc la solution à notre énigme.

Classons déjà nos 5 pirates par degré de férocité. Le moins sauvage étant P1, allant jusqu’à P5 le plus dangereux.
De façon similaire à l’énigme des yeux, pour la résoudre il convient de partir à l’envers depuis un cas simplifié et de remonter jusqu’à la solution globale. Chaque décision de pirate dépendant de ce que feraient les suivants, il ne serait pas pratique de commencer par le début.

Regardons ce qui se passe s’il ne reste que deux pirates. Le cas extrême où il ne reste qu’un seul pirate est trivial vu qu’il repart avec tout l’or, mais il est surtout impossible à atteindre car avec deux pirates restants, P1 et P2, P2 propose son partage, 100 pour lui et 0 pour P1, P2 vote pour lui-même et avec sa seule voix obtient 50% des votes et la proposition est acceptée.

Rajoutons maintenant le pirate P3. Chacun sait que si la proposition de P3 est refusée, on se retrouve à deux pirates et P1 n’aura rien. P3 sait donc que P1 acceptera toute proposition qui lui rapporterait mieux que rien. P3 a donc à donner 1 pièce à P3 et 99 pour lui-même. De cette façon il s’assure du vote de P1, plus le sien, ce qui lui donne la majorité.

Avec P4 c’est le même raisonnement. P4 sait que P2 n’aura rien si son vote est refusé . Il propose 1 pièce à P2 et 99 pour lui-même. P2 votera pour lui, ce qui fera 50% des voix avec la sienne.

P5 doit agir de la même façon, mais il doit par contre soudoyer deux pirates. Il sait que P1 et P3 n’auront rien si P4 se retrouvait à décider d’un partage. Il lui suffit donc de leur proposer 1 pièce à chacun pour s’assurer de leur vote. Le partage final est donc 98 pour P5, 0 pour P4, 1 pour P3, 0 pour P2 et 1 pour P1.

Passons aux choses sérieuses, avec 500 pirates !
On a toujours 100 pièces d’or à partager. Il est clair que le même motif de partage se retrouve jusqu’à un certain nombre. Avec 10 pirates, on aurait 0-1-0-1-0-1-0-1-0-96. On voit que lorsque le nombre de pirates est pair (n=2k pirates), tous les pirates impairs se retrouvent avec rien, les pirates pairs reçoivent 1 sauf le dernier (celui qui partage) qui reçoit 100-(k-1) pièces d’or. Pour un nombre impair de pirates (n=2k+1), les pirates pairs ne reçoivent rien, les pirates impairs reçoivent une pièce sauf le dernier qui reçoit 100-k pièces d’or.

Cela n’est vrai que jusqu’au 200e pirate. P200 n’offre rien aux pirates impairs de P1 à P199, et une pièce d’or aux pirates pairs de P2 à P198, ce qui lui laisse une seule pièce pour lui-même.

Ensuite ça devient intéressant ! P201 n’a que 100 pièces à partager et ne peut espérer repartir avec une pièce. Mais il a tout de même un intérêt à ne pas être jeter par-dessus bord. Il propose ainsi 1 pièce à chaque pirate impair de P1 à P199 et rien pour lui-même.

Le pirate P202 est forcé d’agir pareil. Il utilise les 100 pièces d’or pour soudoyer 100 pirates. Ces 100 doivent être ceux qui n’auraient rien sous la proposition de P201. On remarque que comme il y a 101 pirates qui n’auraient rien avec P201, la distribution n’est plus unique et on a ainsi 101 façons de répartir 100 pièces d’or parmi eux.
On a donc 101 pirates qui pourraient avoir quelque chose par la proposition de P202, et 101 pirates qui sont sûrs de ne rien avoir.

Le pirate P203 doit obtenir 102 votes pour une majorité (soit 101 pirates + lui-même, et il n’a pas assez d’or pour soudoyer 101 de ses camarades. Donc P203 est condamné à la planche (si on arrive jusqu’à lui). Mais ça ne veut pas dire qu’il ne participe plus au raisonnement.

P204 sait que P203 sera jeté par-dessus bord si les votes arrivaient jusqu’à lui. Il sait donc que P203 votera pour n’importe laquelle de ses proposition juste pour éviter la planche.  Il faut 102 votes à P204 pour obtenir la majorité, il peut compter sur le vote de P203, le sien et de 100 autres pirates qu’il peut soudoyer avec les 100 pièces. Ces 100 pirates sont parmi les 101 pirates qui n’auraient rien par la proposition de P202.

A P205 maintenant. Pas de bol pour lui, il lui faut 103 votes pour survivre, mais il ne peut compter sur ceux de P204 et P203 qui se feront le plaisir de le jeter par-dessus bord (sans rien gagner de plus après !). P205 est donc tué quoi qu’il arrive.

De même pour P206, s’il est sûr d’avoir le vote de P205, ça ne suffit pas.
Pareil pour P207 qui a besoin de 104 votes. Il a déjà le sien, plus ceux de P205 et P206, et de 100 pirates soudoyés. Mais ça ne suffit pas.

Ça change pour P208. Il lui faut également 104 votes, mais il aura P205 P206 et P207 qui voteront pour lui. En ajoutant les 100 pirates à qui il offre une pièce. Il obtient ses 104 votes et survit. Ces 100 pirates soudoyés doivent se trouver parmi ceux qui n’auraient rien sous la proposition de P204 : Les pirates pairs de P2 à P200, P201, P202, P203 et P204.

On commence à voir le motif. Les pirates qui peuvent s’en sortir (toujours en ne se donnant rien et offrant les pièces à 100 pirates) s’alternent avec des suites de plus en plus longues de pirates qui seront jetés par-dessus bord de toute façon, et qui voteront ainsi pour les premiers pour sauver leur peau. Les pirates qui s’en sortiraient sont P201, P202, P204, P208, P216, P232, P264, P328, et P456 (si on arrête à 500), soit les pirates dont le nombre est 200 plus une puissance de 2.
Il reste à répartir les 100 pièces d’or, juste en s’assurant qu’elles seront reçues par des pirates qui les accepteront. La solution n’est pas unique, mais une façon de le faire est que P201 offre à tous les pirates impairs de P1 à P199, que P202 offre à tous les pirates pairs de P2 à P200, que P204 offre à tous les pirates impairs, etc.
Le résultat final est donc, pour 500 pirates : Les 44 premiers pirates sont jetés par-dessus bord. P456 offre une pièce à tous les pirates impairs de P1 à P199, et les autres sont juste contents de sortir vivants de tout ce bordel. Grâce à ce brillant système démocratique, les pirates s’arrangent pour se débarrasser des plus dangereux, et ce sont les plus calmes qui ont une chance d’avoir quelque chose.

Advertisements
Cet article, publié dans Enigme, est tagué , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s