Table des Matières¶

1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012

1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012¶

1.1 Épreuve de modélisation, option informatique¶

Ce notebook Jupyter, utilisant OCaml (via le kernel IOcaml), est une correction non officielle d'un texte de modélisation pour l'option informatique de l'agrégation externe de mathématiques.

Il s'agit du texte public2012-D3.

Cette tentative de correction partielle a été rédigée par Lilian Besson (sur GitHub ?, sur Bitbucket ?), et est open-source.

Une autre version, en Python 3, est disponible (aussi sur GitHub).

Feedbacks?¶

Vous avez trouvé un bug ? → Signalez-le moi svp !, merci d'avance.

Vous avez une question ? → Posez la svp !

1.2 Proposition d'implémentation, en OCaml ¶

1.2.1 Pour l'option informatique (D) de l'agrégation de mathématiques (en France).¶

Attention : ce document ne prétend pas être LA correction du texte, mais un exemple de solution.

Initialisation du générateur de nombres aléatoires et d'une fonction généralisée d'affichage.

In [1]:

Random.self_init ();;
let print = Format.printf;;

Out[1]:

- : unit = ()

Out[1]:

val print : ('a, Format.formatter, unit) format -> 'a = <fun>

C'est un très bon réflexe d'utiliser print = Format.printf ainsi défini, elle permet d'afficher facilement du texte contenant des paramètres. Pour plus de détails, voir la documentation de Printf.printf et des explications sur Format.

Il suffit de retenir que printf s'utilise comme ça :

In [2]:

print "Chaine de caractere\n";;

Out[2]:

- : unit = ()

In [3]:

print "Chaine avec variables : il faut retenir %%i, %%f, %%s et %%c...\n" ;;
print "\n - %%i pour un entier : %i, " 1 ;;
print "\n - %%f pour un flottant : %f, " 3.1415 ;;
print "\n - %%s pour une string : %s, " "OK?" ;;
print "\n - %%c pour un caractère : %c\n" 'c' ;;

Chaine de caractere
Chaine avec variables : il faut retenir %i, %f, %s et %c...

 - %i pour un entier : 1, 
 - %f pour un flottant : 3.141500, 
 - %s pour une string : OK?, 
 - %c pour un caractère : c

Out[3]:

- : unit = ()

Out[3]:

- : unit = ()

Out[3]:

- : unit = ()

Out[3]:

- : unit = ()

Out[3]:

- : unit = ()

1.3 Jeux de Nim¶

1.3.1 Représentation des configurations¶

Pas besoin d'un type de données trop complexe :

In [4]:

type nim = int array;;

Out[4]:

type nim = int array

On va d'abord écrire une fonction toute simple qui affiche une configuration, en mode texte.

In [5]:

let print_nim =
  Array.iteri (fun case total -> begin
    print "\n%i: " case;
    for j = 1 to total do
      print "! ";
    done;
  end);;

Out[5]:

val print_nim : int array -> unit = <fun>

On peut définir et afficher deux exemples de configuration d'un jeu de Nim, venant de la figure 1.

In [6]:

let a = [| 1; 3; 5 |] ;;
print "\n Configuration (a) de la Figure 1 :";
print_nim a;;

 Configuration (a) de la Figure 1 :
0: ! 
1: ! ! ! 
2: ! ! ! ! !

Out[6]:

val a : int array = [|1; 3; 5|]

Out[6]:

- : unit = ()

In [7]:

let b = [| 1; 3; 2 |] ;;
print "\n Configuration (b) de la Figure 1 :";
print_nim b;;

 Configuration (b) de la Figure 1 :
0: ! 
1: ! ! ! 
2: ! !

Out[7]:

val b : int array = [|1; 3; 2|]

Out[7]:

- : unit = ()

1.3.2 Fonction de Sprague-Grundy pour le jeu de Nim¶

Elle est donnée par le corollaire 1. en page 6/7 du texte. On a besoin du xor ("ou exclusif", cf cette page) bit à bit, obtenu en OCaml avec l'opérateur lxor :

$$ \gamma(\mathrm{Nim}(x_1, \dots, x_k)) := \bigoplus_{i=1}^{k} x_i = x_1 \oplus \dots \oplus x_k. $$

Petit rappel sur cette fonction xor :

Entrée		Entrée	Sortie
False	$\oplus$	False	= False
False	$\oplus$	True	= True
True	$\oplus$	False	= True
True	$\oplus$	True	= False

On peut la définir avec l'opérateur infixe :

In [8]:

let somme_nim = ( lxor ) ;;

Out[8]:

val somme_nim : int -> int -> int = <fun>

Ou bien plus simplement :

In [9]:

let somme_nim x y = x lxor y ;;

Out[9]:

val somme_nim : int -> int -> int = <fun>

Quelques exemples, juste pour vérifier.

D'abord, les valeurs pour les deux entiers 0 et 1 :

In [10]:

somme_nim 0 0;; (** = 0 *)
somme_nim 0 1;; (** = 1 *)
somme_nim 1 0;; (** = 1 *)
somme_nim 1 1;; (** = 0 *)

Out[10]:

- : int = 0

Out[10]:

- : int = 1

Out[10]:

- : int = 1

Out[10]:

- : int = 0

Ensuite, d'autres valeurs, juste pour tester :

In [39]:

somme_nim 3 5;;  (** 3 xor 5  =  011_2 xor 101_2  = 111_2  = 6  *)
somme_nim 5 9;;  (** 5 xor 9  = 0101_2 xor 1001_2 = 1100_2 = 12 *)
somme_nim 12 1;; (** 12 xor 1 = 1100_2 xor 0001_2 = 1101_2 = 13 *)
somme_nim 12 2;; (** 12 xor 2 = 1100_2 xor 0010_2 = 1110_2 = 14 *)

Out[39]:

- : int = 6

Out[39]:

- : int = 12

Out[39]:

- : int = 13

Out[39]:

- : int = 14

D'après le corollaire 1., il suffit d'appliquer un xor bit à bit à chaque valeur du tableau pour calculer $\gamma$.

En OCaml, on peut faire ça avec une boucle, une fonction récursive, ou plus concisement avec Array.fold_left.

In [12]:

Array.fold_left ;;

Out[12]:

- : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a = <fun>

Rappel : fold_left prend une fonction f(x,y) et x0 calcule f( ... f( f( x0, a[0] ), a[1] ), a[n-1] ). Ici, pour f = somme_nim, il faut donner x0 = 0 pour que le premier calcul f(0, a[0]) = a[0].

In [13]:

let gamma = Array.fold_left somme_nim 0;;

Out[13]:

val gamma : int array -> int = <fun>

In [14]:

print "\nGamma(a) = %i" (gamma(a));;
print "\nGamma(b) = %i" (gamma(b));;

Gamma(a) = 7
Gamma(b) = 0

Out[14]:

- : unit = ()

Out[14]:

- : unit = ()

1.3.3 Déterminer un coup à jouer selon une stratégie gagnante (s'il y en a une)¶

On suit l'algorithme proposé par le texte, qui utilise la fonction $\gamma$ sur la configuration pour savoir s'il y a une stratégie ou non (d'après la proposition 5.), et ensuite si elle existe on doit trouver un coup qui ammene $\gamma$ à 0.

On a d'abord besoin d'une exception pour signaler s'il n'y a pas de stratégie gagnante.

In [15]:

exception Pas_de_Strat_Gagnante;;

Out[15]:

exception Pas_de_Strat_Gagnante

1.3.3.1 Stratégie optimale¶

L'algorithme va être assez naïf, depuis une configuration actuelle $c$ :

si $\gamma(c)$ est $0$, on échoue (Pas_de_Strat_Gagnante),
sinon, on explore toutes les configurations $c'$ atteignables en un coup depuis $c$, et on choisis la première qui amène à $\gamma(c') = 0$.

In [40]:

let next ?(id=0) config =
  let g = gamma config in
  (** La prop. 5 donne directement : si g(s_0) = 0 alors échec. *)
  if g = 0 then raise Pas_de_Strat_Gagnante;
  (** Sinon, on calcul les gamma des fils, et on pointe vers le fils avec un gamma nul. *)
  print "\n\nIl y a une stratégie gagnante :\n";
  (** En pratique, on aurait pas besoin de calculer chaque fils,
      comme on sait que g != 0, et on doit obtenir g' = 0,
      on peut s'arreter au premier coup qui donne g' = 0.
  *)
  let config' = Array.copy config in
  let colonne = ref 0 and
      nb      = ref 1 in
  (** Il suffit d'explorer toutes les configurations accessibles depuis l'état actuel : *)
  for   j = 0 to (Array.length config') - 1 do
    for i = 1 to config'.(j) do
      config'.(j) <- config'.(j) - i;  (** On essaie d'appliquer ce coup. *)
      if (gamma config') = 0 then begin
          (** On a trouvé un coup gagnant, on le stocke. *)
          colonne := j;
          nb := i;
      end;
      config'.(j) <- config'.(j) + i;  (** On annule ce coup. *)
    done;
  done;
  (**  On applique le coup retenu, dernier coup à donner gamma(c') = 0. *)
  print "\nLe joueur courant (numéro %i) doit enlever %i allumette à la %i-ième rangée." id !nb !colonne;
  config'.(!colonne) <- config.(!colonne) - !nb; (** On retire nb allumette sur cette colonne. *)
  (* assert ((gamma config') = 0); (** Si on veut vérifier *)  *)
  config'
;;

Out[40]:

val next : ?id:int -> int array -> int array = <fun>

Note : cette fonction utilise la notation ?(id=0) dans sa définition pour définir un argument optionnel avec valeur par défaut. La fonction next peut être appelée de deux façons :

next a : sans spécifier id, qui vaudra donc 0,

next ~id:1 a : en spécifiant id=1, qui vaut ici 1.

Cette astuce n'est pas requise, et c'est un peu de la "frime", inutile de la retenir et de se forcer à s'en servir. Néanmoins, ça peut être utile dans certaines situations.

On peut tester cette fonction sur nos deux configuration a et b :

In [41]:

try
  print_nim (next ~id:0 a);
with _ -> print "\n\nBlocage durant la simulation 1 (sur a).";;


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 3 allumette à la 2-ième rangée.
0: ! 
1: ! ! ! 
2: ! !

Out[41]:

- : unit = ()

In [42]:

try
  print_nim (next ~id:1 b);
with _ -> print "\n\nBlocage durant la simulation 2 (sur b).";;


Blocage durant la simulation 2 (sur b).

Out[42]:

- : unit = ()

1.3.4. Une stratégie "stupide" : complètement aléatoire¶

On a d'abord besoin de deux fonctions utilitaires :

array_filter, pour filtrer un tableau (comme List.filter mais pour un array). On fait ça simplement en transformant le tableau en liste, on filtre la liste, puis la liste en tableau. Attention, la taille du tableau n'est pas préservée.
et choose pour choisir un élément aléatoire (uniforme) dans un tableau. En Python, on aurait random.choice. On fait ça simplement en tirant un entier i aléatoire uniformément parmi 0, ..., n-1 pour n = Array.length a, puis en renvoyant a.(i).

(Et oui, la libraire standard de OCaml est assez limitée)...

In [19]:

let array_filter pred a =
  Array.of_list (List.filter pred (Array.to_list a));;

let choose a
  = a.(Random.int (Array.length a));;

Out[19]:

val array_filter : ('a -> bool) -> 'a array -> 'a array = <fun>

Out[19]:

val choose : 'a array -> 'a = <fun>

Dans le but de comparer cette fonction next, qui implémente une stratégie optimale, on implémente aussi une stratégie complétement aléatoire ("Dummy player").

La stratégie aléatoire fonctionne en trois étapes :

trouve les rangées qui ont encore des allumettes (en calculant leurs indices, via array_filter, dans le tableau indices),
choisi une rangée aléatoirement i (uniformément),
enlève un nombre aléatoire (uniforme) d'allumette entre 1 et xi, pour xi le nombre d'allumette dans la rangée i (i.e., xi = config.(i)).

In [20]:

(** Un adversaire stupide qui joue aléatoirement. *)
let random ?(id=1) config =
  print "\nLe joueur courant (numéro %i) joue aléatoirement.\n" id;
  let indices = array_filter ( fun i -> (config.(i) > 0) ) (Array.init (Array.length config) (fun i -> i)) in
  let i = choose indices in
  print "Le joueur (%i) choisi de regarder la %i-ième rangée.\n" id i;
  let nbAEnlever = 1 + Random.int config.(i) in
  print "Le joueur (%i) choisi d'enlever %i allumettes parmi les %i disponibles.\n" id nbAEnlever config.(i);
  let config' = Array.copy config in
  config'.(i) <- config.(i) - nbAEnlever;
  config';
;;

Out[20]:

val random : ?id:int -> int array -> int array = <fun>

1.4 Deux exemples, manuellement¶

1.4.1 Premier exemple¶

On peut ainsi faire un exemple de début de partie entre deux joueurs "stupides" :

In [43]:

let a0 = a ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = random ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = random ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)

0: ! 
1: ! ! ! 
2: ! ! ! ! ! 
Le joueur courant (numéro 0) joue aléatoirement.
Le joueur (0) choisi de regarder la 2-ième rangée.
Le joueur (0) choisi d'enlever 1 allumettes parmi les 5 disponibles.

0: ! 
1: ! ! ! 
2: ! ! ! ! 
Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 2-ième rangée.
Le joueur (1) choisi d'enlever 2 allumettes parmi les 4 disponibles.

0: ! 
1: ! ! ! 
2: ! ! 
Le joueur courant (numéro 0) joue aléatoirement.
Le joueur (0) choisi de regarder la 0-ième rangée.
Le joueur (0) choisi d'enlever 1 allumettes parmi les 1 disponibles.

0: 
1: ! ! ! 
2: ! !

Out[43]:

val a0 : int array = [|1; 3; 5|]

Out[43]:

- : unit = ()

Out[43]:

val a1 : int array = [|1; 3; 4|]

Out[43]:

- : unit = ()

Out[43]:

val a2 : int array = [|1; 3; 2|]

Out[43]:

- : unit = ()

Out[43]:

val a3 : int array = [|0; 3; 2|]

Out[43]:

- : unit = ()

1.4.2 Second exemple¶

On peut aussi faire le même exemple de début de partie entre un joueur "optimal" et un joueur "stupide" :

In [44]:

let c = [| 2; 3; 2 |] ;;
let a0 = c ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = next ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = next ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)

0: ! ! 
1: ! ! ! 
2: ! ! 

Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.
0: ! ! 
1: ! ! ! 
2: ! 
Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 0-ième rangée.
Le joueur (1) choisi d'enlever 1 allumettes parmi les 2 disponibles.

0: ! 
1: ! ! ! 
2: ! 

Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 3 allumette à la 1-ième rangée.
0: ! 
1: 
2: !

Out[44]:

val c : int array = [|2; 3; 2|]

Out[44]:

val a0 : int array = [|2; 3; 2|]

Out[44]:

- : unit = ()

Out[44]:

val a1 : int array = [|2; 3; 1|]

Out[44]:

- : unit = ()

Out[44]:

val a2 : int array = [|1; 3; 1|]

Out[44]:

- : unit = ()

Out[44]:

val a3 : int array = [|1; 0; 1|]

Out[44]:

- : unit = ()

1.5 Un bonus : simulation du jeu¶

Maintenant qu'on dispose d'un joueur stupide et d'un joueur optimal, on peut rapidement coder une petite fonction qui les fera s'affronter (même si c'est un peu cruel envers le pauvre joueur "stupide" purement aléatoire !).

In [23]:

exception Perdu of int;;

Out[23]:

exception Perdu of int

1.5.1 Simulation de plusieurs étapes¶

La fonction kpas va jouer la partie, en partant de la configuration donnée, en commençant par le joueur id et pour un certain nombre de coups joués (nbPas). Si on ne donne pas ce nombre de coups, le nombre total d'allumette est utilisé (sachant qu'une partie se termine souvent par une exception Pas_de_Strat_Gagnante lorsque le joueur optimal ne peut plus gagner).

In [45]:

let kpas config id nbPas =
  let id = ref id in
  let config' = ref (Array.copy config) in
  for i = 1 to nbPas do
    print "\nTour numéro %i." i;
    print_nim !config';
    print "\n";
    if (Array.fold_left ( + ) 0 !config') = 0 then raise (Perdu !id);
    begin
      if !id = 0 then (** Le joueur 0 joue bien. *)
        config' := next   ~id:(!id) !config'
      else (** Mais le joueur 1 joue aléatoirement. *)
        config' := random ~id:(!id) !config'
    end;
    id := 1 - !id; (** Juste pour alterner entre 0 et 1 : 0 -> 1, 1 -> 0 *)
  done;
  !config';
;;

Out[45]:

val kpas : int array -> int -> int -> int array = <fun>

On peut finalement implementer une jolie fonction qui simule en partant du joueur 0 (comme le vrai jeu de Nim) et interprète l'exception renvoyée pour afficher l'issue du jeu :

In [46]:

let simulation config =
  (** On compte le nombre total d'allumettes. *)
  let n = Array.fold_left (fun i j -> i + j + 1) 0 config in
  (** Puis on lance le joueur 0 avec au plus [n] pas. *)
  kpas config 0 n;
;;

(** Dernière fonction, [nim], qui lance [simulation] et rattrape les exceptions. *)
let nim a =
  let resultat =
    (* try ignore (simulation a) with *)
    try ignore(simulation a); None with
      | Perdu i -> (Some i)
      | Pas_de_Strat_Gagnante -> None
  in
  begin
    match resultat with
    | None -> print "Blocage à cause de la stratégie optimisée.\n\n"
    | Some i -> print "\n ==> Le joueur %i a perdu !\n\n" i
  end;
  resultat
;;

Out[46]:

val simulation : int array -> int array = <fun>

Out[46]:

val nim : int array -> int option = <fun>

1.5.2 Exemple :¶

In [47]:

nim a;;

Tour numéro 1.
0: ! 
1: ! ! ! 
2: ! ! ! ! ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 3 allumette à la 2-ième rangée.
Tour numéro 2.
0: ! 
1: ! ! ! 
2: ! ! 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 2-ième rangée.
Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.

Tour numéro 3.
0: ! 
1: ! ! ! 
2: 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.
Tour numéro 4.
0: ! 
1: ! 
2: 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 1-ième rangée.
Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.

Tour numéro 5.
0: ! 
1: 
2: 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 1 allumette à la 0-ième rangée.
Tour numéro 6.
0: 
1: 
2: 

 ==> Le joueur 1 a perdu !

Out[47]:

- : int option = Some 1

In [48]:

nim b;;

Tour numéro 1.
0: ! 
1: ! ! ! 
2: ! ! 
Blocage à cause de la stratégie optimisée.

Out[48]:

- : int option = None

Pas très utile jusqu'ici...

In [49]:

nim c;;

Tour numéro 1.
0: ! ! 
1: ! ! ! 
2: ! ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.
Tour numéro 2.
0: ! ! 
1: ! ! ! 
2: ! 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 0-ième rangée.
Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.

Tour numéro 3.
0: 
1: ! ! ! 
2: ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.
Tour numéro 4.
0: 
1: ! 
2: ! 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 1-ième rangée.
Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.

Tour numéro 5.
0: 
1: 
2: ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.
Tour numéro 6.
0: 
1: 
2: 

 ==> Le joueur 1 a perdu !

Out[49]:

- : int option = Some 1

1.5.3 Générer des configurations aléatoires¶

On peut écrire une fonction qui génére une configuration aléatoire, et ensuite lancer notre simulation nim() dessus, pour voir ce que ça donne sur une configuration plus grande.

La fonction randomstart(k, p) va générer une configuration aléatoire :

avec un nombre de lignes uniforme dans {1, ..., k},
et un nombre d'allumettes uniforme dans {1, ..., p} pour chaque ligne.

In [29]:

let randomstart k p () = Array.init (1 + Random.int k) (fun i -> 1 + Random.int p);;

Out[29]:

val randomstart : int -> int -> unit -> int array = <fun>

Par exemple :

In [30]:

let c = randomstart 5 8 ();;
print_nim c;;

0: ! ! ! ! ! 
1: ! ! 
2: ! ! ! ! ! ! 
3: ! !

Out[30]:

val c : int array = [|5; 2; 6; 2|]

Out[30]:

- : unit = ()

Le joueur optimal (d'indice `0`) gagne toujours¶

In [31]:

let c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c;;
nim c;;

Configuration random c :
0: ! ! 
1: ! ! ! ! ! ! 
Tour numéro 1.
0: ! ! 
1: ! ! ! ! ! ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 4 allumette à la 1-ième rangée.
Tour numéro 2.
0: ! ! 
1: ! ! 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 0-ième rangée.
Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.

Tour numéro 3.
0: 
1: ! ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.
Tour numéro 4.
0: 
1: 

 ==> Le joueur 1 a perdu !

Out[31]:

val c : int array = [|2; 6|]

Out[31]:

- : unit = ()

Out[31]:

- : unit = ()

Out[31]:

- : int option = Some 1

Le joueur stupide peut-il quand-même gagner ?¶

In [37]:

c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c ;;
nim c ;;

Configuration random c :
0: ! ! 
1: ! ! ! ! ! ! 
Tour numéro 1.
0: ! ! 
1: ! ! ! ! ! ! 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 4 allumette à la 1-ième rangée.
Tour numéro 2.
0: ! ! 
1: ! ! 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 1-ième rangée.
Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.

Tour numéro 3.
0: ! ! 
1: 


Il y a une stratégie gagnante :

Le joueur courant (numéro 0) doit enlever 1 allumette à la 0-ième rangée.
Tour numéro 4.
0: ! 
1: 

Le joueur courant (numéro 1) joue aléatoirement.
Le joueur (1) choisi de regarder la 0-ième rangée.
Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.

Tour numéro 5.
0: 
1: 

 ==> Le joueur 0 a perdu !

Out[37]:

- : bool = false

Out[37]:

- : unit = ()

Out[37]:

- : unit = ()

Out[37]:

- : int option = Some 0

C'est effectivement possible que le joueur 0 (celui qui commence) perde, même en suivant sa stratégie gagnante. Si le joueur aléatoire 1 a de la chance...

1.5 Conclusion¶

C'est tout ce que j'avais eu le temps d'implémenter durant les 4h de préparation (c'est un des textes que j'avais préparé en juin 2014, dans les "vraies" conditions en oraux blanc, à l'ENS Cachan, et le code initial était en OCaml mais je n'ai rien changé à part l'écriture du notebook Jupyter).

Quelques remarques :

durant l'épreuve de modélisation, vous êtes libres de faire ce que vous voulez, la seule partie requise est dans le paragraphe Exercice de programmation (ici, il s'agissait d'implémenter une fonction similaire à optimal() (cf. plus haut).
les quelques développements supplémentaires traites ci-dessus (stratégie stupide, configuration aléatoire, simulation de jeu), ne sont qu'une suggestion de ce qui pouvait être fait sur ce texte,
d'autres suggestions sont possibles, si vous avez des idées, envoyez-moi vos notebooks !.

Edit : j'avais une erreur dans mon calcul de next, corrigée le 11/01/17.

1.6 Attention :¶

Les 35/40 minutes de passage au tableau ne doivent PAS être uniquement consacrée à la présentation de vos expériences sur l'ordinateur !

Il faut aussi :

faire une introduction générale (citer des mots clés),
présenter le plan de votre présentation,
introduire les notations, les objectifs et les résultats donnés par le texte,
prouver ou exposer des développements theoriques personnels (à choisir parmi la liste proposée, mais pas seulement),
etc.

C'est tout pour aujourd'hui les amis ! Allez voir d'autres notebooks si vous voulez.

Table des Matières¶

1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012¶

1.1 Épreuve de modélisation, option informatique¶

Feedbacks?¶

1.2 Proposition d'implémentation, en OCaml¶

1.2.1 Pour l'option informatique (D) de l'agrégation de mathématiques (en France).¶

1.3 Jeux de Nim¶

1.3.1 Représentation des configurations¶

1.3.2 Fonction de Sprague-Grundy pour le jeu de Nim¶

1.3.3 Déterminer un coup à jouer selon une stratégie gagnante (s'il y en a une)¶

1.3.3.1 Stratégie optimale¶

1.3.4. Une stratégie "stupide" : complètement aléatoire¶

1.4 Deux exemples, manuellement¶

1.4.1 Premier exemple¶

1.4.2 Second exemple¶

1.5 Un bonus : simulation du jeu¶

1.5.1 Simulation de plusieurs étapes¶

1.5.2 Exemple :¶

1.5.3 Générer des configurations aléatoires¶

Le joueur optimal (d'indice 0) gagne toujours¶

Le joueur stupide peut-il quand-même gagner ?¶

1.5 Conclusion¶

1.6 Attention :¶

1.2 Proposition d'implémentation, en OCaml ¶

Le joueur optimal (d'indice `0`) gagne toujours¶