En détail

Le chercheur d'or

Le chercheur d'or

Un chercheur d'or est arrivé dans une auberge où il était sur le point de rester pendant 31 jours. L'aubergiste a demandé l'argent de l'hébergement à l'avance mais le chercheur d'or ne faisait pas confiance alors il a proposé un accord:

J'ai un lingot d'or de 31 centimètres de long qui a une valeur égale au coût de l'hébergement pendant les 31 jours. Je vais couper le bar en petits morceaux pour que le premier jour je vous donne un pouce du bar en paiement de mon logement et chaque jour qui passe je vous donnerai un autre pouce. A la fin du séjour j'aurai livré les 31 pièces donc j'aurai payé ma dette.

Une façon de couper la barre consiste à la diviser en 31 parties de chaque centimètre de long afin d'en livrer une portion chaque jour. Mais comme c'était une tâche très laborieuse de le couper en autant de morceaux, le chercheur a réussi à le diviser en le plus petit nombre de morceaux qui lui permettrait de rembourser la dette quotidiennement.Par exemple, le premier jour, il pouvait donner à l'aubergiste un centimètre de la barre, un autre centimètre le deuxième jour et le troisième jour pourrait livrer un morceau de trois centimètres et recevoir en retour les deux parties précédentes d'un centimètre.

Quel est le moins de pièces dans lesquelles le moteur de recherche doit diviser sa barre d'or pour satisfaire sa dette?

Solution

Le moteur de recherche peut remplir la transaction en coupant la barre cinq parties de 1 cm, 2 cm, 4 cm, 8 cm et 16 cm de longueur.
Le premier jour, il donne à l'aubergiste la pièce de 1 cm, le lendemain, l'aubergiste la rend et il livre la pièce de 2 cm, le troisième jour, il livre à nouveau la pièce de 1 cm, le quatrième jour, l'aubergiste rend les deux pièces et il donne le morceau de barre 4cm. En livrant et en recevant de cette manière le moteur de recherche peut ajouter un centimètre par jour et ainsi couvrir les 31 jours du mois comme indiqué dans le tableau suivant:

Jours / Pièces 1 2 4 8 16
1 X
2 X
3 X X
4 X
5 X X
6 X X
7 X X X
8 X
9 X X
10 X X
11 X X X
12 X X
13 X X X
14 X X X
15 X X X X
16 X
17 X X
18 X X
19 X X X
20 X X
21 X X X
22 X X X
23 X X X X
24 X X
25 X X X
26 X X X
27 X X X X
28 X X X
29 X X X X
30 X X X X
31 X X X X X