{"id":150,"date":"2011-07-25T12:31:57","date_gmt":"2011-07-25T10:31:57","guid":{"rendered":"http:\/\/antoine.wojdyla.free.fr\/?p=150"},"modified":"2014-05-05T08:47:48","modified_gmt":"2014-05-05T06:47:48","slug":"deux-enigmes","status":"publish","type":"post","link":"http:\/\/antoine.wojdyla.fr\/blog\/2011\/07\/25\/deux-enigmes\/","title":{"rendered":"Trois enigmes"},"content":{"rendered":"<p>Voici trois \u00e9nigmes, qui m&#8217;ont \u00e9t\u00e9 propos\u00e9es par Guillaume L. et Silvan T. :<strong> <\/strong><\/p><strong>1. La strat\u00e9gie de la table.<\/strong><\/p>Deux concurrents ont face \u00e0 eux une table parfaitement ronde, et une machine qui leur permet de frapper des pi\u00e8ces de la taille qu&#8217;ils souhaitent.<br \/>\nChacun \u00e0 son tour a le droit de poser une pi\u00e8ce su la table, le but du jeu \u00e9tant d&#8217;\u00eatre le dernier \u00e0 poser une pi\u00e8ce. Les joueurs ont le choix de commencer ou de laisser la main.<br \/>\nIl y a-t-il une strat\u00e9gie optimale pour gagner?<!--more--><\/p>\n<ul>\n<li>solution<br \/>\n<em>La table est ronde. Elle est donc pourvue d&#8217;une sym\u00e9trie centrale. Si un joueur joue en premier, il peut placer une pi\u00e8ce au centre de la table, quelle que soit sa taille: il s&#8217;agit du seul point o\u00f9 l&#8217;on ne pourra pas faire jouer de sym\u00e9trie.<br \/>\nLe second joueur posera ensuite une pi\u00e8ce \u00e0 n&#8217;importe quel endroit.<br \/>\nLa sym\u00e9trie de la table assure au premier joueur de pouvoir toujours placer une pi\u00e8ce \u00e0 l&#8217;exact oppos\u00e9 de la pi\u00e8ce qui vient d&#8217;\u00eatre pos\u00e9e, et ce \u00e0 chaque coup.<br \/>\nCela lui assure la victoire<br \/>\n<\/em><\/li>\n<\/ul><p><strong>2. Les chapeaux chinois<\/strong><\/p>Un despote un peu pervers veut tuer cent personnes; mais afin de les faire souffrir une ultime fois leur cerveau avant qu&#8217;ils ne meurent, il leur propose le jeu morbide suivant:<br \/>\n&#8220;vous serez align\u00e9s sur le flanc d&#8217;une colline, chaque personne ne pouvant regarder que les personnes se situant en dessous d&#8217;eau (par rapport au sommet). Vous aurez tous un chapeau, dont la couleur sera tir\u00e9e au sort parmi sept, et que vous ne pourrez voir. Je viendrai vous voir un par un, et vous devrez dire un mot, un seul. Si ce mot correspond \u00e0 la couleur de votre chapeau, vous serez \u00e9pargn\u00e9s. Vous aurez une demi heure pour vous mettre d&#8217;accord sur mon ordre de passage lorsque je viendrais vous voir&#8221;.<br \/>\nQuelle est la strat\u00e9gie peux-t-on proposer pour \u00e9pargner un maximum de personnes?<\/p>\n<ul>\n<li>solution :<em><br \/>\nSi chaque personne donne soit la couleur de la personne que la suit soit la sienne (qu&#8217;il connait gr\u00e2ce au sacrifice de la personne pr\u00e9c\u00e9dente), il y a 50% de morts.<\/em><em><br \/>\nSi maintenant les chinois conviennent d&#8217;un code couleur (bleu = 0, vert = 1, etc&#8230;), et qu&#8217;ils font la somme modulo 7 des couleurs des chapeaux qui les suivent, et que la personne au sommet de la colline se sacrifie en donnant le r\u00e9sultat de la somme de tous les chapeaux, la personne suivante pourra d\u00e9duire sa propre couleur en calculant la diff\u00e9rence des sommes modul\u00e9es qu&#8217;il a d\u00e9termin\u00e9 et celle qui lui a \u00e9t\u00e9 annonc\u00e9e. L&#8217;information se propage.<\/em><\/li>\n<\/ul><p><strong>3. Le jeu des poids<\/strong> (Ce probl\u00e8me est issu d&#8217;un entretien chez JPMorgan)<\/p>On poss\u00e8de une balance, huit objets de m\u00eame masse, et un objet un peu plus lourd.<br \/>\nQuel est le nombre minimum de pes\u00e9e n\u00e9cessaire pour d\u00e9terminer quel est l&#8217;objet le plus lourd?<\/p>\n<ul>\n<li>solution<br \/>\n<em>Si on proc\u00e8de par dichotomie classique , on a au minimum besoin de 4 pes\u00e9es.<\/em><br \/>\n<em>R\u00e9fl\u00e9chissons sous un autre angle : quel est le nombre maximal de poids que je peux discriminer avec une seule pes\u00e9e? la r\u00e9ponse est trois : deux sur la balance, un \u00e0 cot\u00e9.<\/em><br \/>\n<em>En suivant ce raisonnement, et en proc\u00e9dant par ensembles de trois,\u00a0 on peut proposer une solution en seulement deux mesures : on constitue trois tas de trois objets, puis l&#8217;on met un tas\u00a0 bras de la balance, un autre sur le second bras et le dernier de cot\u00e9. On peut ainsi d\u00e9terminer quel tas de trois objets est le plus lourd, et on proc\u00e8de de la m\u00eame mani\u00e8re sur ce tas pour d\u00e9terminer quel est l&#8217;objet &#8220;vilain petit canard&#8221;<br \/>\n<\/em><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Voici trois \u00e9nigmes, qui m&#8217;ont \u00e9t\u00e9 propos\u00e9es par Guillaume L. et Silvan T. : 1. La strat\u00e9gie de la table.Deux concurrents ont face \u00e0 eux une table parfaitement ronde, et une machine qui leur permet de frapper des pi\u00e8ces de la taille qu&#8217;ils souhaitent. Chacun \u00e0 son tour a le droit de poser une pi\u00e8ce [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,6],"tags":[],"class_list":["post-150","post","type-post","status-publish","format-standard","hentry","category-francais","category-mood"],"_links":{"self":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/comments?post=150"}],"version-history":[{"count":12,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/150\/revisions"}],"predecessor-version":[{"id":310,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/150\/revisions\/310"}],"wp:attachment":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/media?parent=150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/categories?post=150"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/tags?post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}