Cet article a été publié il y a 15 ans. Son contenu est sans doute daté, tant sur la forme que sur le fond... Toutefois, cela n’empêche pas d'échanger à son propos. N'hésitez donc pas à vous exprimer en commentaires à la fin de l'article.
Voici une énigme sympathique, pour ce début de semaine :
Un roi donne 100g d’or à chacun de ses dix bijoutiers, et leur demande à chacun de lui faire 10 bagues identiques. Il leur laisse 1 mois. Durant cette période, le roi reçoit une lettre anonyme, l’informant que l’un des bijoutiers tente de l’escroquer : il a gardé 10g d’or pour lui.
Arrivé à la fin de l’échéance, les dix bijoutiers se présentent devant le roi, et lui présentent chacun leurs dix bagues. A l’œil nu, toutes les bagues sont semblables.
Le roi souhaite alors identifier l’escroc. Il dispose pour cela d’une balance à plateau avec un grand nombre de poids. Il souhaite cependant ne faire qu’une seule pesée, qui consiste à poser un (ou plusieurs) objet(s), en une fois sur l’un des plateau, et à établir son poids.
Comment peut-il faire ?
Puisque l’escroc a gardé 10g d’or pour lui, il a donc utilisé 90g pour constituer ses dix bagues : chacune d’elle pèse donc 9g, alors que les bagues des autres bijoutiers pèsent bien 10g chacune.
Pour identifier le coupable en une seule pesée, le roi doit faire comme suit… Au premier bijoutier, il prend une bague, au second il en prend deux, au troisième il en prend trois, et ainsi de suite jusqu’à en prendre 10 au dixième bijoutier. Il dispose d’un total de 55 bagues.
Normalement, le tout doit donc peser 550g (10g par bague). Or, comme il y a un escroc, le tout pèsera moins. La différence entre le poids de ces bagues et le poids théorique (550g) lui indiquera le coupable. Par exemple, si en pesant ses bagues, il obtient 447g. Il n’a qu’à faire l’opération : 550-547=3 pour savoir que le troisième bijoutier est l’escroc.
Nota : Merci à Wafa, qui a posé cette énigme lors de son anniversaire hier soir. J’ai eu l’humble honneur de trouver la réponse en premier.
Il y a un défaut dans ton raisonnement, c’est la première hypothèse : rien ne dit dans l’énoncé que la répartition est équitable.
De plus, l’énoncé est trompeur, quand tu décris « une seule pesée (positionner un ou plusieurs objets sur chaque plateau, en une seule fois) ». En lisant ça, je me disais qu’il pouvait juste mettre ce qu’il voulait sur les plateaux (bagues et poids) une seule fois et juste voir le résultat : équilibré, ou penchant d’un coté ou de l’autre, et non pas effectuer une pesée, qui nécessite de mettre plusieurs fois des poids sur un plateau pour arriver au bon poids.
Et du coup, en sachant juste si on a mis le même poids de chaque coté ou pas, ba c’est impossible à résoudre ^_^
Mmmh… Tu n’as pas tort. Je rectifie en conséquence.
Enfin, tu n’as pas tort pour la seconde partie de ton commentaire. Mais l’énoncé dit que le roi distribue 100g d’or à chaque bijoutier pour faire des bagues identiques. Ca suppose donc une répartition équitable, non ?
Bah en fait si on ne pinaille pas on comprend qu’il s’agit en effet d’une répartition identique. Il s’agit d’une énigme de logique simple, une répartion non identique compliquerait grandement les choses.
Par contre je n’avais pas compris pour ma part qu’il ne pouvait faire qu’une seule pesée pour tout le monde. ^^
Ah ? Tu n’avasi pas compris avec la version initiale, ou avec la présente version corrigée ?
Je ne suis pas d’accord ekho : la consigne du roi est que toutes les bagues soient identiques, avec 100g d’or. Or le fautif ne respectant pas la consigne, il se peut qu’il ne fasse pas non des bagues identiques exactement. Par exemple, il a pu en faire une avec 10g, histoire de montrer celle là si on lui demande un échantillon. Je ne dis pas que cette hypothèse est déraisonnable, je dis juste que sans cette hypothèse, il ne s’agit pas d’une énigme de logique pure, car on n’a pas tout les éléments.
Mais bon, je reconnais que je pinaille pour ça, c’était surtout ma deuxième objection qui m’avait gêné. La nouvelle formulation résoud le problème !
Hu hu ! Je pinaille aussi alors. Mais j’ai bien écris que chaque bijoutier lui présent les 10 bagues, et qu’on ne peut faire aucune différence à l’oeil nu… ^_^
Et moi je te répond que tu peux ne pas distinguer une différence de 1g à l’oeil nu !
Et personnellement, j’avais compris que toutes les bagues (les 100) devaient être identiques, et que malgré la différence de poids de certaines, on ne pouvait voir la différence à l’oeil nu.
Je reconnais, après relecture, qu’il est plus logique de comprendre que chaque bijoutier peut faire un modèle différent des autres bijoutiers, tant que ses 10 bagues sont identiques.
J’ai du voir la version corrigée, et je trouve la réponse super astucieuse.
Voici mon énigme, posée en début d’entretien téléphonique. Il fallait répondre à la fin de l’entretien, et tu n’as pas de temps mort pour réfléchir à l’énigme exclusivement:
Tu disposes de 2 boules résistantes au choc. Tu veux faire des tests de solidité. Tu disposes d’un immeuble de 50 étages.
Pour faire ton test de solidité, tu décides de lancer une boule depuis l’immeuble pour savoir si elle casse ou non.
L’énigme est la suivante : comment feras-tu pour déterminer avec les deux boules (tu n’as donc droit qu’à deux boules cassées) le premier étage où la boule casse, en un minimum d’essai?
Oui, tu as eu la version corrigée, Ji-Pi.
Pour ton énigme, elle t’a été posée durant quel type d’entretien téléphonique ???
Comme réponse, je dirais qu’il faut partir du premier étage et lancer la première boule, puis lancer la seconde du deuxième étage. Si aucune n’est cassée, on réitère jusqu’à ce que l’une d’elles casse. Si X est l’étage déterminé, il aura donc fallu X/2 essais (un essai correspondant au fait de lancer les deux boules depuis deux étages successifs). Mais il y a peut-être plus simple…?
Un ingénieur de Rockwell a passé un entretien téléphonique pour être embauché au Royaume Uni, et on lui a posé l’énigme et il fallait répondre à la fin de l’entretien. Sauf que la personne au bout du fil te pose d’autres questions.
(et en anglais dans le texte …)
Ekho, tu as répondu de la manière la plus simple qu’il soit, et tu n’optimises absolument pas le nombre de coup ^^
(car il faut prendre en compte les probabilités conditionnelles … « si c’était le premier étage, je gagne du premier coup, si c’était au deuxième, au deuxième etc »)
Tu n’utilises d’ailleurs qu’une seule des boules dans ton raisonnement 🙂
Par essai, il veut dire : nombre de fois où une boule est lancée, je dirais. donc avec ta méthode, si X est l’étage, on aura lancé X boules.
Tu lance la première à l’étage 10. Si elle casse, tu as au pire 9 étages à tester avec la deuxième boule.
Si elle résiste, tu la lance à l’étage 20. Si elle casse, le bon étage est entre 11 et 20, que tu teste avec la seconde boule, 1 par 1.
et ainsi de suite, tant que la première boule ne casse pas.
Après, j’ai pris des pas de 10 en 10, mais il devrais être interessant de calculer le pas optimal pour limiter le nombre de tentative en moyenne.
En tout cas, dans la solution d’arnaud, on lance au mieux 1 boule (casse dès le premier étage), au pire 50.
Dans ma solution, on lance au mieux 2 boules (casse à l’étage 10, puis casse à l’étage 1), au pire 14 boules (lancer aux étages 10, 20, 30, 40 et 50 qui casse, puis lancer seconde boule aux étages 41 à 49 sans casse (ou avec casse au 49, ça revient au même)). Et en moyenne, on a 25 essai pour la solution d’arnaud, et 8,4 pour la mienne (en supposant la hauteur de casse équiprobable)
Avec un subdivision de 5 en 5, on va aussi entre 2 essais et 14 essais, mais avec une moyenne de 8,3. Avec 4 on remonte à 8,96 de moyenne, et avec 7 on est à 7,86 de moyenne.
Bref, les calculs, c’est sûr que j’aurais pas pu les faire pendant un entretien téléphonique, mais il est clair que j’aurais proposé cette méthode.
Ben, il convient de définir ce qu’est un « essai ». Pour moi, c’était le fait de lancer les deux boules et de les récupérer (ou pas). Si un essai, c’est juste lancer une boule, dans ce cas, je n’en utilise qu’une, effectivement.
Dans tous les cas, je n’avais effectivement pas pensé à utiliser la première boule pour réduire l’intervalle. Pas mal ! ^_^
C’est l’idée de Lyr qui est la bonne.
Utiliser le premier essai pour se réduire au maximum le champ des possibles par la suite ^^
Après, il faut sentir le résultat.
Perso, j’aurais dit de diviser en deux les intervalles ou au 2/3 de l’immeuble au premier coup, mais c’est du feeling, et le calcul de tête pendant l’entretien relève du génie …
Je n’avais pas fait attention à cette 2ème énigme. J’ai la flemme de faire des calculs propres, alors je vous donner une réponse à l’intuition.
Déjà, on ne sait pas si la boule va effectivement casser dans la hauteur de l’immeuble. Sans cette donnée, on ne peut rien optimiser du tout… Je fais donc l’hypothèse que c’est le cas. L’hypothèse de Lyr (la probablité est équi-répartie suivant les étages) est physiquement acceptable, puisque l’énergie de la boule au moment de l’impact est égale à son énergie potentielle, donc proportionnelle à la hauteur à laquelle on la lache. Par contre, cette considération n’a bien sûr de sens que si on sait que la boule va casser quelque part sur la hauteur de l’immeuble !
Ma solution au problème, basée sur l’intuition : comment « découper » l’immeuble avec la première boule ? Il y a 2 cas pires : découper à chaque étage (solution d’Arnaud ;o) on utilise que la 1ère boule), découper tous les n étages avec n=hauteur de l’immeuble (ce qui revient à ne pas découper… on n’utilise que la 2ème boule). Intuitivement, je dirais qu’il faut que le nombre d’essais max avec la 1ère boule soit à peu près le même que le nombre d’essais max avec la 2ème. Ca revient à regarder la racine carrée du nombre d’étages, à quelques subtilités près parce que le problème est discret (comment gérer les arrondis ? au dessus ? au dessous ?). Ce serait beaucoup plus simple si on pouvait lancer depuis n’importe quelle hauteur, sans se soucies d’étage.
En l’occurence, 50=7*7+1. Je ferais les essais tous les 7 étages avec la première boule.
A confirmer par le calcul…
NB : ça se généralise si on a davantage de boules 😉 Si j’ai droit à 3 boules, je regarde la racine cubique, etc.
L’histoire de la racine carrée me semble bonne, puisque par mes test, j’étais arrivé à la conclusion de 7. Mais il y a effectivement des facteurs qui rentrent en compte lorsque la subdivision n’est pas un facteur premier du nombre d’étage.
Par contre, pour le coup comme quoi ça se généralise avec n balles grace à une racine nième, je suis dubitatif. Plus tu as de balles, plus tu va prendre des intervalles grand. Et au delà d’un certain nombre de balle, tu stagnes sur la solution idéal de la dichotomie.
La racine te donne le nombre d’intervalles, pas le nombre d’étage par intervalle (le cas « 2 balles » est un cas particulier où on trouve autant (enfin si on est proche d’un carré parfait) d’étages par intervalles que d’intervalles). Plus n est grand, plus la racine n-ième va être petite, et comme 1 n’est pas un nombre d’intervalles acceptable (revient à utiliser une balle de moins, comme on l’a vu), on tend vers 2 😉
Prenons un cas simple : j’ai 3 balles, l’immeuble fait 64=4*4*4 étages.
1ère balle : 4 intervalles, donc tous les 16 étages
2ème balle : 4 intervalles aussi, donc tous les 4 étages
3ème balle : tous les étage, bien sûr.
Si tu avais eu 2 balles, tu aurais fait 8 intervalles de 8 étages.
Par contre, avec 6 balles (64=2^6), tu tombes bien sur une dichotomie.
Vous êtes tous cinglés ! 😀
Ok , si ça indique le nombre d’interval, je suis 100% d’accord (d’un autre coté, c’est la vérité, je pourrais difficilement ne pas être d’accord).
Par contre, comme tu le dis, c’est une intuition, il faudrait encore le prouver. Soit réussir à exprimer le nombre moyen d’essai nécessaire en fonction de la hauteur du batiment et du nombre de subdivision et trouver le minimum.
Mais pire que ça, il est possible que la solution idéale ne passe pas forcement par des intervales réguliers.
Par exemple, peut être a t’on de meilleurs résultats en lançant la première balle au 1/3 de la hauteur, puis si ça casse pas, à 1/3 de ce qui reste, et ainsi de suite. Que penses tu d’une telle hypothèse ?
Pas évident, la démonstration, à mon avis !
C’est pas idiot, parce que le problème n’est pas vraiment symétrique. Le fait de savoir que ça ne casse pas au n-ème étage te donne une information sur tous les étages plus bas, mais aucune sur les étages plus haut.
Par contre, une fois la solution idéale trouvée avec 2 balles, la généralisation à n balles se fait assez simplement, par récurrence (en fait une fois qu’on a isolé le bon intervalle avec la 1ère balle, ça revient à regarder un immeuble plus petit avec n-1 balles…)
Après, pour démontrer, c’est sûr que c’est pas simple Déjà parce que le fait que ce soit discret pose des soucis d’effets de bords pénibles (peut-être regarder avec un cas « continu » d’abord : on suppose qu’on peut lacher la balle depuis n’importe quelle hauteur), ensuite parce que le problème n’est pas si simple à écrire mathématiquement…
…complètement marteaux !
Tu te crois de retour en Prépa, ekho ?
Presque, oui. Ma collègue vous prend définitivement pour des dingues ! 😀
Ben moi je ne fait que confirmer que j’étais, et demeurerai, nul en calcul probabiliste… ;-D Revenons aux bagues, c’était beaucoup plus à ma portée !
Petit lapsus.
« Aux blagues » et pas aux bagues 😀
Tu as un mariage en tête? 😉
Ji-Pi : Ou alors, c’est rapport au titre de l’article ! 😀
Et voila, on est des dingues car on aime les maths… C’est de la ségrégation !! 😉
Moi je dis que les dingues, ce sont qui aiment le foot ! (rien à voir, 3615 myLife, mais hier il devait y avoir un match je suppose, il pleuvait légèrement, et il y avait une foule de gens rassemblé à un bar, tellement que certains étaient dehors, dans le froid et la pluie, presque à 90° de l’écran et pendant les 90minutes du match… Et me dire que je suis dingue parce que je réfléchis 30seconde sur un problème, bien au chaud devant mon écran…)
Sympa l’énigme 🙂
J’aimerais bien vous donner quelques énigmes mais comment fait-on pour faire un article? 😀
@Ekho : ah oui, tiens, je n’avais pas relu le nom de l’article :p
@Lyr : plus que le foot, c’est souvent le fait d’avoir une occasion pour se rassembler autour d’un verre qui prime.
Ok, on peut aussi voir ses copains devant son écran de télé chez soi au chaud avec des bières achetés au Auchan d’à coté sans pour autant regarder du foot 🙂
Pour en revenir au sujet de l’article, et à la question de Yufei, çà pourrait être sympa d’avoir un petit espace dédié aux énigmes, j’en ai quelques unes en stock aussi (je suis pas une lumière, mais bon, j’ai toujours aimé réfléchir à des trucs « inutiles » ^^ )
Je me souviens d’une discussion à Bordeaux avec Ekho et Lyr (et peut-être Elderme, je ne sais plus). Un classique je crois:
» Un homme meurt et arrive devant un panneau sur lequel est écrit : ‘si vous êtes arrivés ici, c’est que vous n’avez ni commis de péchés qui vous feraient aller en enfer, ni n’avez fait de bonnes actions remarquables qui vous auraient ouvert les portes du paradis. Avancez, et vous verrez deux portes, chacun gardé par un garde. Vous avez le droit de poser une question à un des gardes, une seule et unique question, et à un seul garde. Dès lors qu’il vous aura répondu, vous devrez choisir l’une des deux portes. La première va tout droit en enfer, et la deuxième au paradis
PS: Un des gardes dit toujours la vérité, et l’autre ment toujours’
Comment peut faire le héros de cette histoire pour aller à coup sûr au paradis? »
@Jpeg : celle là est bien trop connue ! Tout le monde connait la solution ! Il suffit de prendre la deuxième porte, elle va au paradis !
Sinon pour le foot, c’était pas pour se retrouver autour d’un verre qu’ils étaient là !! Il y avait une telle foule qu’ils étaient entassés, debout, débordant du bar jusqu’à au moins 2 mètres (et je n’exagère pas), dans le froid, et la pluie légère… Vu la foule, il était hors de question de prendre un verre, et encore moins de s’assoir autour. Et il y avait deux trois nana qui avaient l’air de se faire chier, surement là parceque leur copain les y avait trainée…
@ Yufei et Ji-Pi : pourquoi ne pas simplement les mettre ici en commentaire, comme l’a déjà fait Ji-Pi, d’ailleurs.
Effectivement, cette dernière énigme est trop connue, donc trop facile. A l’époque ou je rédigeai une nouvelle, je l’y avais intégrée.
Pour le foot, je pense que c’est avant tout pour l’ambiance, ce coté survolté, allié à une passion (ici, le foot), même si ils ne peuvent pas vraiment en profiter. Ca peut aussi se retrouver ans les longues files au cinéma, pour un filmm qui sera encore à l’affiche dans trois semaines… 🙂
Je ne suis pas d’accord avec votre raisonnement.
« Trop connu, donc trop facile »
En quoi est-ce une énigme si on connaît déjà la réponse? Ce serait « mieux » ou plus correct, ou je sais trop quoi (qui parle de logique ici? :p) de voir les choses comme ça à mon sens.
Parce que si quelqu’un ne la connaît pas, il doit chercher la solution, comme toutes les énigmes, et la réponse n’est pas si évidente, de prime abord.
Si tu rajoutes d
suite du commentaire, j’ai eu un ptit souci d’internet ce matin :p
Si tu rajoutes dans l’énigme que le mort n’a que 5 minutes pour réfléchir (donc celui à qui on pose la question aussi), c’est encore moins évident ^^
Je me rends compte que mon commentaire plus haut est assez obscur !
(bizarrement, à 7h44… quelle idée de poster un commentaire aussi !)
Ce que je voulais dire, c’est que si tu connais la réponse à l’énigme, ce n’est plus une énigme pour toi.
Je l’ai postée pour ceux qui ne la connaissent pas encore (et j’avais prévenu que c’était du très gros classique)
Tsss, si même toi, JP, tu ne comprend plus l’humour !
Évidement que c’est une énigme ardue, que je n’ai pas trouvé la première fois qu’on me la présenté, et dont j’ai découvert par hasard la solution dans un livre. Et donc maintenant je peux crâner en disant qu’elle est super facile ! (il suffit de prendre la seconde porte, comme dit dans l’énoncé, elle mène au Paradis !! Même pas besoin de poser de question !)
Si, si j’avais compris qu’il y avait de l’humour dans ce que tu disais (mode mauvaise foi off)
Nan, j’ai pas vu le second degré, c’est vrai 😀
Effectivement, il faut prendre la deuxième porte… mais laquelle est-ce? 🙂
A droite ou à gauche? En Chine ils indiqueraient à droite la première et à gauche la deuxième 😉 . Ici, ce serait l’inverse
Pour les quelques uns qui ne connaîtraient pas l’énigme, s’il en reste, mais qui ne veulent pas d’emblée la solution, voici le cheminement, en 3 points (le troisième donne quasiment la solution, donc n’allez pas jusqu’au bout si vous voulez pas être spoilés) : puisqu’on ne sait pas lequel des deux gardes ment, il faut trouver une question à laquelle les deux gardes donnent la même réponse.
Pour cela, il faut que dans la formulation de la question, on réussisse à obtenir l’opinion des deux gardes…
L’idéal étant que ces opinions soient « chaînées », en série, de sorte que la position du mensonge dans la chaîne n’importe plus (dans une multiplication de plusieurs entiers positifs, si l’on inverse le signe d’un des termes, quel que soit le terme choisi on obtiendra comme résultat un négatif).
Pour ma part, je donnerais un autre indice sur cette énigme… A première vue, on a deux infos à trouver : qui ment ? Ou est la porte ? Mais on a une seule question… Il semble évident qu’on ne pourra pas avoir ces deux infos avec une seule question (enfin, une seule réponse). Donc, en réalité, une seule question nous intéresse : quelle est la porte ? En pratique, on ne saura donc pas qui ment…
D’ailleurs, le pauvre homme n’en n’à que faire de savoir qui ment, puisque lui, tout ce qu’il veut, c’est rejoindre le paradis (ou alors, il est masochiste …)
Pour Ekho
Pourrai je avoir la solution a la devinnette
Merci d’avance
@ Halima Mushtaq:
Salutations !
La réponse est à la fin de l’article : il suffit de passer la souris sur les points d’interrogation pour la faire apparaître.
Dans le doute, en voici un copier/coller :