\Annee{2002}
\Titre{Bataille navale lin\'eaire}
\Auteur{Fr\'ed\'eric \textsc{Le Roux}}
\AutresAuteurs{}


\Date{2002/07/15}
\Niveau{\DEUGi}
\NiveauxSecondaires{\DEUGii}
\AnglePedagogique{\Ludique}
\AnglesSecondaires{}

\Theme{\AlgLin}
\ThemesSecondaires{}
\Objectif{
Dans cette activit\'e, on utilise un jeu de type ``bataille navale''
 pour amener les \'etudiants \`a se poser des
questions sur la g\'eom\'etrie des sous-espaces vectoriels, et plus
 particuli\`erement sur la dimension.
\paragraph{R\'ealisation pratique}
Notons d'abord que contrairement \`a ce qu'on peut penser au premier
abord, le jeu ne n\'ecessite pas beaucoup de calculs, puisqu'on peut
r\'epondre \`a la plupart des questions \`a l'aide d'arguments de
dimension~: \'evidemment, l'un des buts de l'exercice est d'inciter les
\'etudiants \`a utiliser ces raisonnements.

On sugg\`ere de grouper les \'etudiants par quatre, et de les faire jouer
deux contre deux (et \'eventuellement plus tard quatre contre
quatre). Par rapport \`a un affrontement ``un contre un'', ces
configuration ont l'avantage de favoriser la confrontation des id\'ees~:
le fait de ne pas \^etre d'accord sur le coup \`a jouer devrait obliger
les \'etudiants \`a justifier leurs propositions, donc \`a jouer plus
rationnellement, voire \`a chercher une bonne strat\'egie. Et aussi, ceci
diminue la fr\'equence des erreurs...

Il vaut probablement mieux commencer par jouer dans $\bbR^3$, o\`u
l'intuition aide beaucoup. Mais il serait dommage de ne pas jouer
aussi dans $\bbR^4$, o\`u l'\'etudiant doit justement remplacer son
intuition d\'efaillante par les raisonnements sur la dimension.

On peut pr\'eciser les r\`egles au fur et \`a mesure des parties ; on
sugg\`ere les r\`egles additionnelles suivantes~:
\begin{itemize}
\item un joueur qui d\'etecte une erreur dans la r\'eponse de son
adversaire \`a l'une de ses questions gagne la partie (y compris si la d\'etection intervient
longtemps apr\`es l'erreur)~;
\item le joueur qui se trompe en annonçant la dimension perd la partie~;
\item un joueur est autoris\'e \`a modifier son sous-espace
vectoriel secret en cours de partie (y compris apr\`es que l'autre ait
propos\'e une dimension) \`a condition toutefois que son nouveau
sous-espace secret reste compatible avec ses r\'eponses pr\'ec\'edentes. L'int\'er\^et de
cette r\`egle est d'obliger le joueur qui pr\'etend avoir trouv\'e \`a \^etre
s\^ur de lui (et donc \`a chercher \`a d\'emontrer que la dimension est ce
qu'il pense). On pourrait aussi demander explicitement au gagnant, \`a
la fin de la partie,
de fournir  une preuve que la dimension est ce qu'il affirme (mais
ceci risque de rendre l'activit\'e plus scolaire et moins ludique, ce
qui est dommage).
\end{itemize}


\paragraph{Complexit\'e algorithmique}
 Apr\`es un
peu de pratique, on peut sugg\'erer aux \'etudiants de chercher un
algorithme, par exemple en leur demandant comment on pourrait
programmer un ordinateur pour qu'il trouve la r\'eponse en temps fini
dans tous les cas. Ceci est probablement assez difficile en DEUG, sans parler
de la recherche d'une strat\'egie optimale~: on peut ainsi transformer
le jeu en un exercice de niveau licence... Voici des \'el\'ements de
r\'eponses (en note de bas de page pour ne pas contrarier le lecteur
qui voudrait y r\'efl\'echir tout seul !).
\footnote{
\textbf{Quelques remarques sur la complexit\'e} Pour un
champ de bataille $E$ de dimension $n$, quel est le nombre de coups
n\'ecessaires pour r\'epondre dans tous les cas~?
Voici une strat\'egie qui marche toujours en moins de $n$ coups. 

On choisit une base $B=\{e_1,..,e_n\}$. On regarde les parties $F$
contenues dans $B$ 
telles que $\mathrm{vect}(F) \cap E_1 =\{0\}$ (o\`u $E_1$ est l'espace
inconnu).
On note $\cal F$ l'ensemble de ces parties.
\begin{enonce1*}{Lemme}
 Une partie maximale dans $\cal F$ est de dimension $n-\mathrm{dim}(E_1)$.
\end{enonce1*}

Donc on cherche une partie maximale.
L'algorithme est le suivant.
On pose la question ``$F=\mathrm{Vect}(e_1)$~?''
Si la r\'eponse est ``\`a l'eau'', on prend $F_1=\{e_1\}$~;
si c'est ``touch\'e'', on prend $F_1=\emptyset$.
Puis on continue~: \`a l'etape $i$, on pose la question ``$F=vect(F_{i-1}\cup
\{e_i\})$~?'', et
on prend $F_{i}=F$ si ``\`a l'eau'', $F_{i}=F_{i-1}$ si ``touch\'e''.
Le $n$-i\`eme ensemble $F_n$ est maximal~: en effet, le $i$-i\`eme
ensemble $F_i$ est maximal 
pour l'ajout d'un des $i$ premiers vecteurs
(\emph{i. e.} si on rajoute un des $i$ premiers vecteurs \`a $F_i$, on
touche $E_1$). 

Remarquons aussi la diff\'erence entre le ``presque s\^ur'' et le
``s\^ur''~: si on fait une dichotomie sur la dimension (en proposant
d'abord un espace de dimension $n/2$, \emph{etc.}), on va trouver la
dimension en temps $\log(n)$ pour presque tout sous-espace~; la
complexit\'e presque sure est en $\log(n)$, alors
que c'est beaucoup moins \'evident pour la complexit\'e ``au pire''.
\begin{enonce1*}{Question}
 Y a-t-il un algorithme meilleur que celui propos\'e au-dessus~? Autrement
dit, quelle est la complexit\'e au pire~? 
\end{enonce1*}
}

Ce jeu est inspir\'e d'une bataille navale g\'eom\'etrique (non lin\'eaire)
 propos\'ee par Nicolas Bouleau dans le texte
de sa conf\'erence au colloque EM2000 sur l'enseignement des maths, 
\emph{Y a-t-il lieu d'envisager des math\'ematiques post-modernes ?}
(\href{http\deuxpoints//em2000.imag.fr/Actes/}{http\deuxpoints//em2000.imag.fr/Actes/}).
Citons le texte d'origine, qui peut inspirer d'autres exercices~:

``... Chaque \'el\`eve d'un binôme d\'efinit une figure g\'eom\'etrique (par
exemple constitu\'ee d'un cercle et de deux droites) dans un syst\`eme de coordonn\'ees.
Pour deviner la figure de son adversaire, il tire des droites et non
des points. Si \`a son
tour de jouer, il propose ainsi la droite $y = 2x + 1$, son adversaire lui indique tous
les points d'intersection de sa figure avec $y = 2x + 1$, etc. Il y a de multiples
variantes suivant les figures cach\'ees et les objets qu'on tire, la d\'eduction et la
combinatoire ne sont pas absentes de ce jeu qui peut s'organiser en tournoi comme
les \'echecs.''
}

\begin{exo}
La bataille navale lin\'eaire est un jeu qui se joue \`a deux joueurs,
dans lequel chacun doit d\'ecouvrir la dimension d'un sous-espace
vectoriel cach\'e par l'autre.

Expliquons les r\`egles en d\'etail. On
d\'ecide d'abord du champ de bataille~: il s'agit d'un espace vectoriel
$E$ de dimension finie (par exemple $\bbR^3$ ou $\bbR^4$).
Chaque joueur choisit en secret un sous-espace vectoriel de
$E$ (on notera $E_1$ et $E_2$ ces deux sous-espaces).
Commence alors la phase de jeu proprement dite~: le premier joueur
sugg\`ere un sous-espace vectoriel $F$ de $E$~; le second lui r\'epond
\begin{itemize}
\item ``touch\'e'' si le sous-espace propos\'e a une intersection non triviale avec
le sous-espace cach\'e (autrement dit, si $F \cap E_2$ n'est pas r\'eduit \`a $\{0\}$)~;
\item ``dans l'eau'' sinon.
\end{itemize}
C'est alors au tour du second de faire une proposition, et le jeu
continue ainsi jusqu'\`a ce que l'un des deux joueurs trouve la \textbf{dimension} du
sous-espace choisi par l'autre. 

On pr\'ecise que chaque joueur est libre de choisir son sous-espace
secret et les sous-espaces qu'il propose de la mani\`ere qui lui
convient (par exemple, \`a l'aide d'un syst\`eme d'\'equations cart\'esiennes
ou bien d'une base).
\end{exo}


