Subluminal

Voici trois énigmes, qui m’ont été proposées par Guillaume L. et Silvan T. :

1. La stratégie de la table.

Deux concurrents ont face à eux une table parfaitement ronde, et une machine qui leur permet de frapper des pièces de la taille qu’ils souhaitent.
Chacun à son tour a le droit de poser une pièce su la table, le but du jeu étant d’être le dernier à poser une pièce. Les joueurs ont le choix de commencer ou de laisser la main.
Il y a-t-il une stratégie optimale pour gagner?

• solution
  La table est ronde. Elle est donc pourvue d’une symétrie centrale. Si un joueur joue en premier, il peut placer une pièce au centre de la table, quelle que soit sa taille: il s’agit du seul point où l’on ne pourra pas faire jouer de symétrie.
  Le second joueur posera ensuite une pièce à n’importe quel endroit.
  La symétrie de la table assure au premier joueur de pouvoir toujours placer une pièce à l’exact opposé de la pièce qui vient d’être posée, et ce à chaque coup.
  Cela lui assure la victoire
  

2. Les chapeaux chinois

Un despote un peu pervers veut tuer cent personnes; mais afin de les faire souffrir une ultime fois leur cerveau avant qu’ils ne meurent, il leur propose le jeu morbide suivant:
“vous serez alignés sur le flanc d’une colline, chaque personne ne pouvant regarder que les personnes se situant en dessous d’eau (par rapport au sommet). Vous aurez tous un chapeau, dont la couleur sera tirée 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 à la couleur de votre chapeau, vous serez épargnés. Vous aurez une demi heure pour vous mettre d’accord sur mon ordre de passage lorsque je viendrais vous voir”.
Quelle est la stratégie peux-t-on proposer pour épargner un maximum de personnes?

• solution :
  Si chaque personne donne soit la couleur de la personne que la suit soit la sienne (qu’il connait grâce au sacrifice de la personne précédente), il y a 50% de morts.
  Si maintenant les chinois conviennent d’un code couleur (bleu = 0, vert = 1, etc…), et qu’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ésultat de la somme de tous les chapeaux, la personne suivante pourra déduire sa propre couleur en calculant la différence des sommes modulées qu’il a déterminé et celle qui lui a été annoncée. L’information se propage.

3. Le jeu des poids (Ce problème est issu d’un entretien chez JPMorgan)

On possède une balance, huit objets de même masse, et un objet un peu plus lourd.
Quel est le nombre minimum de pesée nécessaire pour déterminer quel est l’objet le plus lourd?

• solution
  Si on procède par dichotomie classique , on a au minimum besoin de 4 pesées.
  Réfléchissons sous un autre angle : quel est le nombre maximal de poids que je peux discriminer avec une seule pesée? la réponse est trois : deux sur la balance, un à coté.
  En suivant ce raisonnement, et en procédant par ensembles de trois,  on peut proposer une solution en seulement deux mesures : on constitue trois tas de trois objets, puis l’on met un tas  bras de la balance, un autre sur le second bras et le dernier de coté. On peut ainsi déterminer quel tas de trois objets est le plus lourd, et on procède de la même manière sur ce tas pour déterminer quel est l’objet “vilain petit canard”