Enigmes

Quand on pose une énigme mathématique, à moitié formalisée, on finit toujours par avoir une réponse type: "on enlève le bandeau qu'on a sur les yeux", "on casse la gueule au bourreau", etc. D'où l'idée de formaliser vraiment, sous forme d'un exercice de programmation... (qui a dit "maniaque" ?)

Un groupe de n prisonniers se trouve en mauvaise posture. Ils vont être mis en file indienne, chaque prisonnier voyant seulement les prisonniers devant lui. Puis on leur mettra sur la tête un chapeau bleu, blanc ou rouge, qu'ils ne peuvent voir. Un bourreau procède alors comme suit: en partant du dernier prisonnier il demande "Quelle est la couleur de ton chapeau ?", et le prisonnier n'a le droit qu'à une réponse, qui doit être une couleur. A la fin, les prisonniers qui ont deviné la couleur de leur chapeau sont épargnés, les autres exécutés. Les prisonniers peuvent se concerter avant l'épreuve sur la stratégie à adopter. Quelle est la meilleure stratégie ?

Voici maintenant l'énoncé complètement formalisé. Un prisonnier est représenté par une fonction qui prend deux listes de couleurs (celles qu'il voit devant lui, celles qui ont été prononcées comme réponses derrière lui), et renvoie une couleur (sa réponse). Dans la liste des réponses précédentes, la réponse du dernier de la file est la dernière de la liste. Trouver une fonction prisonniers qui à un entier n associe une liste de n fonctions/prisonniers telle que le nombre de morts calculé par (execution (prisonniers n)) soit le plus petit possible dans le pire cas. La fonction d'exécution est la suivante:

type couleur = Bleu | Blanc | Rouge
type prisonnier = couleur list -> couleur list -> couleur

let random_couleur () =
  let n = Random.int 3 in
    if n = 0 then Bleu else if n = 1 then Blanc else Rouge

let execution (prisonniers : prisonnier list) =
  let prisonniers =
    List.map (fun p -> p, random_couleur ()) prisonniers
  in
  let rec morts avant = function
    | (p,c)::l ->
        let reponse = p (List.map snd l) avant in
          (if reponse = c then 0 else 1) +
          (morts (reponse::avant) l)
    | [] -> 0
  in
    morts [] prisonniers

Amusez-vous bien, et postez vos réponses dans le langage de votre choix...

Edit: une autre énigme beaucoup plus étonnante, que Florent et Julien m'ont racontée. Vous avez devant vous sur une table 7 pièces côté pile et 19 pièces côté face. Mais vos yeux sont bandés (et vous portez des moufles) de sorte que vous ne pouvez savoir l'état d'une pièce. Tout ce que vous pouvez faire c'est en retourner certaines, autant que vous voulez, et les déplacer. Il vous faut les séparer en deux groupes qui contiennent le même nombre de pièces côté pile.

La solution sera une fonction qui prend le nombre de piles et le nombre de faces (je vous aide bien en généralisant) et qui renvoie deux tableaux de taille piles+faces: le premier indique les indices des pièces choisies, le second indique les pièces qu'il faut retourner. La fonction sera passée à la fonction de test suivantes:

(** Perfect Fisher-Yates shuffle
  * (http://www.nist.gov/dads/HTML/fisherYatesShuffle.html). *)
let randomize a =
  let permute i j =
    let tmp = a.(i) in
      a.(i) <- a.(j);
      a.(j) <- tmp
  in
  let l = Array.length a in
    if l>=2 then
      for i=0 to l-2 do
        permute i (i + Random.int (l-i))
      done

let test nb_piles nb_faces joueur =
  let choix,retourne = joueur nb_piles nb_faces in
  let n = nb_piles + nb_faces in
  let a = Array.init n (fun i -> i<nb_piles) in
  (* Nombre de piles à gauche - nombre de piles à droite *)
  let d = ref 0 in
    randomize a ;
    for i = 0 to n-1 do
      if retourne.(i) then a.(i) <- not a.(i) ;
      d := (if choix.(i) then (+) else (-)) !d (if a.(i) then 1 else 0)
    done ;
    !d = 0

A suivre: les solutions commentées...