

\begin{enumerate}
\item Si chaque sommet est un couple \coord{i}{j} o\`u $i$ d\'esigne le nombre d'allumettes du premier tas et $j$ celui du second tas, alors le graphe est le suivant :

\begin{center}
\begin{tikzpicture}[xscale=3,yscale=3,>=stealth']
\node (A) at (0,0) {\coord{3}{3}}; \node[red] at (A.south) {A};
\node (B) at (0.5,0.5) {\coord{2}{3}};\node[red] at (B.north) {B};
\node (C) at (.75,-0.5) {\coord{1}{3}};\node[red] at (C.south) {C};
\node (D) at (1,0) {\coord{2}{2}};\node[red] at (D.south) {D};
\node (E) at (2.5,1) {\coord{0}{3}};\node[red] at (E.north) {E};
\node (F) at (2.5,0) {\coord{1}{2}};\node[red] at (F.south) {F};
\node (G) at (3.25,.75) {\coord{0}{2}};\node[red] at (G.north) {G};
\node (H) at (3.25,-1) {\coord{1}{1}};\node[red] at (H.south) {H};
\node (I) at (3.5,0) {\coord{0}{1}};\node[red] at (I.east) {I};
\node (J) at (4,0.5) {\coord{0}{0}};\node[red] at (J.south) {J};
\draw[->] (A) -- (B);
\draw[->] (A) -- (C);
\draw[->] (B) -- (E);
\draw[->] (B) -- (C);
\draw[->] (B) -- (D);
\draw[->] (B) -- (F);
\draw[->] (C) -- (E);
\draw[->] (C) -- (F);
\draw[->] (C) -- (H);
\draw[->] (D) -- (G);
\draw[->] (D) -- (F);
\draw[->] (E) -- (G);
\draw[->] (E) -- (I);
\draw[->] (F) -- (G);
\draw[->] (F) -- (H);
\draw[->] (F) -- (I);
\draw[->] (G) -- (I);
\draw[->] (G) -- (J);
\draw[->] (H) -- (I);
\draw[->] (I) -- (J);
\end{tikzpicture}
\end{center}

\item Pour que le premier joueur gagne, il faut que l'autre joueur jour en dernier, ce qui n\'ecessite un nombre pair de coups. \uline{Il faut donc que la longueur de $c$ soit paire.}

\item La matrice d'adjacence du graphe est la suivante, en convenant de classer les sommets par ordre alphabétique:
\[
\mathcal{A}=
\begin{pmatrix}
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\]

\item \`A l'aide du logiciel Xcas, on cherche la plus petite puissance paire de $\mathcal{A}$ telle que $a_{1,10}\neq 0$. Pour $\mathcal{A}^2$, $a_{1,10}=0$ mais pour $\mathcal{A}^4$, on a $a_{1,10}=10$.

On peut donc dire qu'il y a 10 cha\^ines de longueur 4 qui m\`enent du premier sommet au dernier. Par exemple : $(3;3)\to(1;3)\to(0;3)\to(0;2)\to(0,0)$.
\item Sur le graphe $\mathcal{G}$, on peut observer que si le joueur retire deux allumettes, alors il est assur\'e de gagner.

En effet, la cha\^ine $\coord{3}{3}\to\coord{2}{3}\to\coord{2}{2}\to\coord{1}{2}\to\coord{0}{1}\to\coord{0}{0}$ \`a une longueur impaire, donc ne convient pas. Par contre, toutes les cha\^ines commen\c{c}ant par \linebreak $\coord{3}{3}\to\coord{1}{3}$ ont une longueur paire.
\end{enumerate}
