\input upsnum.tex
%=============================================================================================
%Corrig\'e de ECOLE DE L'AIR 99, MP, \'epreuve 2 (Matrice d'adjacence d'un graphe=
%Le corrig\'e d\'ebute ligne 115
%Remarques et relev\'es d'erreurs \`a JC Dufait, e-mail: cjcbtm.dufait@wanadoo.fr
%======================================================================================
%
%*****Macros de pr\'esentation*******************
%*****Mise en page
\vsize   =   24 true cm
\hsize   =   17 true cm
\hoffset=-1.1 true cm
\voffset=-2.2 true cm % \`a adapter pour l'imprimante 
\overfullrule=0mm
\hfuzz=5mm
\leftskip = 1cm % dimension marge gauche
\parindent = 0mm % pas d'indentation en d\'ebut de paragraphe
%*****Fontes
\font\Bf=cmbx10 scaled\magstep1
\font\BF=cmbx10 scaled\magstep2
%*****Haut et bas de page
%\def\makeheadline{
%\ifnum\pageno=1
%\null\vskip 2mm\null
%\else
%\line{\rm \titre\hfil\folio/\nbretotal}
%\vskip 2mm\hrule\vskip5mm\fi}
%\def\makefootline{}
%*****Num\'erotation
\dimendef\grandrecul=100%\grandrecul=30pt
\dimendef\petitrecul=101%\petitrecul=14pt
\def\num#1{\sv\sv\setbox1\hbox to \grandrecul{\bf#1\delimI\hfil}
\leavevmode\llap{\box1}}%-----num\'ero de question 
%*****Fin
\def\finetoiles{\centerline{*\hphantom{*}*\hphantom{*}*}\centerline{*\hphantom{*}*}\centerline{*}}
%*****Cadres
%-----cadre simple
\def\encadre#1{
\leavevmode             % mode horizontal
\hbox{\vrule            % trait vertical gauche
\vtop{\vbox{\hrule      % trait horizontal haut
\kern 5pt               % cale verticale
\hbox{\kern 5pt         % cale horizontale
#1\kern 5pt             % texte + cale horizontale
}}\kern 5pt             % cale verticale
\hrule                  % trait horizontal bas
}\vrule}}               % trait vertical droit
%----- cadre pour le titre 
\def\cadrelong#1{%
{\SV                    % va a la ligne
\leftskip=3mm           % pas de marge gauche
\hrule                  % trait horizontal sup\'erieur
\dimen0=\hsize\advance\dimen0 by 7mm %
\hbox to \dimen0{\vrule  % trait vertical gauche
\hfil                   % centrage horizontal
\vrule height 16pt depth 8pt width 0pt     % cale de hauteur
\BF #1%                  % texte en gras
\hfil                   % centrage horizontal
\vrule                  % trait vertical droit
}\hrule                 % trait horizontal inf\'erieur
\sv}}                   % petit espace
%*****Op\'erateurs math\'ematiques*********************
%*****Nouvelles definitions
\let\oldsum=\sum                         % modifie la d\'efinition de \sum
\def\sum{\oldsum\limits}                 % pour placer correctement les bornes
\def\frac#1#2{{\textstyle#1\over\textstyle#2}} % fraction
\def\fracs#1#2{{\scriptstyle#1\over\scriptstyle#2}} %  petite fraction
%*****Ensembles de nombres
\def\Z{{\bf Z}}
\def\C{{\bf C}}
\def\R{{\bf R}}
\def\N{{\bf N}}
%*****Calculs en cascade
\def\cascade#1{                            
\leavevmode\vtop{\halign{$##$\hfil&${}##{}$\hfil&$##$\hfil\cr #1}}\par}
%*****Limites d'intervalles d'entiers:
\def\[{[\![}
\def\]{]\!]}
%*****Operateurs algebriques
\def\rg{\mathop{\rm rg}\nolimits}
\def\im{\mathop{\rm Im}\nolimits}
\let\oldker=\ker
\def\ker{\mathop{\rm Ker}\nolimits}
\def\vect{\mathop{\rm Vect}\nolimits}
\def\sp{\mathop{\rm Sp}\nolimits}
\def\tr{\mathop{\rm Tr}\nolimits}
%*****Matrices
%matrice avec []
\def\cmatrix#1{\left[\matrix{#1}\right]}
%petites matrices
\def\petitematrix#1{\vcenter{\normalbaselineskip=8pt
\ialign{\hfil$\scriptstyle{##}$\hfil&&\hfil$\;\;\scriptstyle{##}$\hfil\crcr #1\crcr}}}
\def\petitepmatrix#1{\left(                            
\vcenter{\normalbaselineskip=8pt
\ialign{\hfil$\scriptstyle{##}\mathstrut$\hfil&&\hfil$\;\;\scriptstyle{##}$\hfil\crcr #1\crcr}}\right)}
\def\petitecmatrix#1{\left[                            
\vcenter{\normalbaselineskip=8pt
\ialign{\hfil$\scriptstyle{##}$\hfil&&\hfil$\;\;\scriptstyle{##}$\hfil\crcr #1\crcr}}\right]}
\def\petitematrixbis#1{                            
\vcenter{\normalbaselineskip=0pt
\ialign{\hfil$\scriptstyle{##}$\hfil&&\hfil$\;\;\scriptstyle{##}$\hfil\crcr #1\crcr}}
}
%*****Raccourcis
\let\un=\underline
\let\h=\hbox
\let\s=\smallskip
\def\sv{\vskip 4mm plus 2mm minus 2mm}   
\def\SV{\vskip 12mm plus 6mm minus 6mm} 
%%%%%%%%%%%%%%%%%%%% Macros sp\'ecifiques %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\grandrecul=30pt
\def\delimI{.}
\def\titre{Ecole de l'Air 1999, concours MP, Math\'ematiques 2.}
\def\nbretotal{3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SV 
\cadrelong{\BF \titre }
\centerline{\sl (\nbretotal\  pages )}
\SV

\num 1%
$\diamond$ Il y a $n\times d\ $ "bouts de rue". Or chaque rue a exactement $2$
bouts donc $\un{\h{le nombres de rues est }\frac{nd}{2}}$~.\s
$\diamond$ En particulier, $nd$ est pair et $\un{\h{un au moins des
nombres }n\h{ et }d\h{ est pair}}$~.

\num 2%
Soit $k$ le nombre de lampes. Chaque lampe \'eclaire le carrefour o\`u elle
est situ\'ee ainsi que les $d$ adjacents donc $d+1$ carrefours. Il y a donc
au plus $k\times(d+1)$ carrefours \'eclair\'es (certains pouvant l'\^etre par
plusieurs lampes). Comme chaque carrefour est \'eclair\'e, on a $n\le
k(d+1)$ donc $\frac{n}{d+1}  \le k$ et donc $\un{k\ge \left[
\frac{n}{d+1}\right]}$~.

\num 3%
Posons $L'=M.L$, on a, pour $i\in\[1,n\]$,
$L'_i=\sum_{j=1}^{n}M_{i,j}={\rm Card}\,\bigl\{j\bigm|M_{i,j}\ne 0 \bigr\} 
={\rm Card}\,\bigl\{j\bigm|j\h{ reli\'e \`a }i\bigr\}=d$ donc $L'=d.L$.
Donc $\un{d\h{ est valeur propre de }M\h{ et }L\h{ est un vecteur propre
associ\'e}}$~.

\num 4%
On a $\bigl( j\h{ reli\'e \`a }i\bigr) \Leftrightarrow \bigl( i\h{ reli\'e \`a
}j\bigr)$ donc $M_{i,j}=M_{j,i}$ donc $M$ est sym\'etrique r\'eelle donc
$\un{M\h{ a toutes ses}}$ $\un{\h{valeurs propres r\'eelles}}$~.

\num 5%
$\diamond$ Posons $X'=MX$ et $X''=(M+I)X$. On a, pour $i\in\[1,n\]$,
$$x'_i=\sum_{j=1}^{n}M_{i,j}x_j={\rm Card}\,\bigl\{j\ne i\bigm|M_{i,j}=1
\h{ et }x_j=1 \bigr\} 
={\rm Card}\,\bigl\{j\ne i\bigm|j\h{ reli\'e \`a }i\h{ et }j\h{ \'eclair\'e}\bigr\}$$
et $x''_i=x'_i+x_i=x'_i+\cases{1& si $i$ \'eclair\'e,\cr 0& sinon.\cr}$.\par
Donc $x''_i={\rm Card}\,\bigl\{j\bigm| j\h{ \'eclaire }i \bigr\} $ et donc
$\bigl( x''_i\ge 1\bigr) \Longleftrightarrow \bigl( i\h{ est
\'eclair\'e}\bigr)$.\s
Donc $\un{X\h{ est une solution au probl\`eme si et seulement si
}(M+I)X\h{ a toutes ses composantes }\ge 1}$~.\sv

$\diamond$ $\,^t\!L(M+I)X=\,^t\!LMX+\,^t\!LX=\,^t\!L\,^t\!MX+\,^t\!LX=
\,^t\!(ML)X+\,^t\!LX=\,^t\!(dL)X+\,^t\!LX=(d+1)\,^t\!LX$ et
$\,^t\!LX=\sum_{i=1}^{n}x_i= 
{\rm Card}\,\bigl\{i\bigm|x_i=1
 \bigr\}=k$ o\`u $k$ est le nombre de lampes install\'ees. De plus,
$\,^t\!L(M+I)X=\sum_{i=1}^{n}x''_i$ donc, si $X$ repr\'esente une
solution, on a $\,^t\!L(M+I)X\ge n$ donc $(d+1)k\ge n$ et donc
$\un{k\ge \frac{n}{d+1}}$~.\sv

$\diamond$ Si, de plus, $X$ a exactement $\frac{n}{d+1}$ composantes \'egales
\`a $1$, alors $\,^t\!LX=\frac{n}{d+1}$ donc $\,^t\!L(M+I)X=n$ soit
$\sum_{i=1}^{n}x''_i=n$ ou encore $\sum_{i=1}^{n}(x''_i-1)=0$ avec
$\forall i\in\[1,n\],\ x''_i\ge 1$. On obtient donc $\forall i\in\[1,n\],\
x''_i=1$ soit $X''=(M+I)X=L$. En \'ecrivant $X=X_1+X_2$ avec $X_1\in\R.L$ et $X_2
\in(\R.L)^\bot$, on obtient $L=(M+I)X_1+(M+I)X_2=(d+1)X_1+(M+I)X_2$ avec $(d+1)X_1\in\R.L$
et $(M+I)X_2\in(\R.L)^\bot$ car, gr\^ace \`a la sym\'etrie de $M$,
 $\,^t\!L(M+I)X_2=\,^t\!\bigl( (M+I)L\bigr)X_2=(d+1)\,^t\!LX_2=0$. Donc,
par unicit\'e de l'\'ecriture dans la somme directe
$\R^n=\R.L\oplus(\R.L)^\bot$, on a $(d+1)X_1=L$ et $(M+I)X_2=\vec 0$
soit $MX_2=-X_2$. De plus, si on avait $X_2=\vec 0$ on aurait $X\in\R.L$
donc $X$ aurait $0$ ou $n$ composantes non nulles ce qui n'est pas le
cas. Donc $X_2$ est un vecteur propre pour la valeur propre $-1$.\s
On a donc : $\un{\h{si }X,\h{ solution, a exactement }\frac{n}{d+1}
\h{ composantes \'egales \`a }1\h{ alors }-1\in\sp(M)}$~.

\num 6%
Soit $k'$ le nombre de lampes. Le nombre de rues \'eclair\'ees est $k'\times
d$ et le nombre total de rues est $\frac{nd}{2}$. Il faut donc
$k'd\ge \frac{nd}{2}$  soit $k'\ge \frac{n}{2}$ et donc $\un{k\ge \left[
\frac{n}{2}\right]}$~.

\num 7%
$\diamond$ On a~:
\cascade{\,^tYMY&=\sum_{(i,j)} M_{i,j}y_iy_j=  
{\rm Card}\,\bigl\{(i,j)\in\[1,n\]^2 \bigm|M_{i,j}=1\h{ et }y_i=1
\h{ et }y_j=1 \bigr\}\cr
&={\rm Card}\,\bigl\{(i,j)\in\[1,n\]^2 \bigm|\h{ la rue }(i,j)\h{ existe
et n'est pas \'eclair\'ee}\bigr\}\cr} 
donc on a bien $\un{\,^tYMY=0\Longleftrightarrow\bigl( Y \h{
repr\'esente une solution} \bigr)}$~.\sv

$\diamond$ On a $Y_1=\frac{\langle L,Y\rangle }{\langle L,L\rangle}\,L=
\frac{\,^t\!LY }{\,^t\!LL}\,L=\frac{p}{n}\,L$ donc
$\,^tY_1Y_1=\frac{p^2}{n^2}\,^t\!LL$ soit $\un{\,^t
Y_1Y_1=\frac{p^2}{n}}$~. Puis, le th\'eor\`eme de Pythagore donne 
$\,^t YY=\,^t Y_1Y_1+\,^t Y_2Y_2$ donc $\,^t
Y_2Y_2=p-\frac{p^2}{n}$ donc $\un{\,^t Y_2Y_2=\frac{p(n-p)}{n}}$~.\sv

$\diamond$ $\,^tYMY=\,^t\bigl[ Y_1+Y_2\bigr] \bigl[d Y_1+MY_2\bigr]=d 
\,^t Y_1Y_1+\,^t Y_2MY_2=d\,\frac{p^2}{n}+\,^t Y_2MY_2$.\par
Or $M$ \'etant sym\'etrique r\'eelle est diagonalisable dans une base
orthonorm\'ee et si $\bigl( E_1,\ldots,E_n\bigr)$ est une base
orthonorm\'ee de diagonalisation de $M$, $E_i$ \'etant associ\'e \`a la valeur
propre $\lambda _i$, on a, pour $Z=\sum_{i=1}^{n}z_iE_i$,
$$\,^tZMZ=\sum_{i=1}^{n}\lambda _i\,z_i^2\ge   \mu\,\sum_{i=1}^{n}z_i^2=
\mu\, \,^tZZ~.$$
En appliquant \`a $Y_2$, on obtient $\un{\,^tYMY\ge d\,\frac{p^2}{n}+\mu\,
\frac{p(n-p)}{n}}$~.\sv

$\diamond$ Si $Y$ repr\'esente une solution, on a donc
$0\ge d\,\frac{p^2}{n}+\mu\,\frac{p(n-p)}{n}$ soit $0\ge dp+\mu(n-p)$
donc $(d-\mu)p\le -\mu n$. Or $0=\tr (M)=\sum_{i=1}^{n}\lambda _i\ge
n\mu$ donc $\mu\le 0<d$ et donc, en divisant par $d-\mu>0$,\quad
$\un{p\le \frac{-\mu n}{d-\mu}}$~.

\num 8%
$\diamond$ Soit $P$ la matrice de permutation associ\'ee \`a 
$\bigl(1,2,3,4,5,6 \bigr)\bigl(7,8,9,10,11,12\bigr)$. Comme $P$ et $M$
commmutent, $M$ laisse stable les sous-espaces propres de $P$. Cherchons
donc les valeurs propres et les sous-espaces propres de $P$.
$$PX=\lambda \,X\Longleftrightarrow\left\{\petitematrix{\mathstrut x_2&=&\lambda
\,x_1\cr x_3&=&\lambda\,x_2\cr&\vdots&\cr x_1&=&\lambda\,x_6\cr
x_8&=&\lambda\,x_7\cr x_9&=&\lambda\,x_8\cr&\vdots&\cr
x_7&=&\lambda\,x_{12}\mathstrut \cr}\right.\Longleftrightarrow
\left\{\petitematrix{\mathstrut x_2&=&\lambda
\,x_1\cr x_3&=&\lambda^2\,x_1\cr&\vdots&\cr x_6&=&\lambda^5\,x_1\cr
x_1&=&\lambda^6\,x_1\cr
x_8&=&\lambda\,x_7\cr x_9&=&\lambda^2\,x_7\cr&\vdots&\cr
x_{12}&=&\lambda^5\,x_7\cr x_7&=&\lambda^6\,x_7\mathstrut\cr }\right.$$
donc $\sp(P)=\bigl\{ \omega \mid \omega^6=1\bigr\}$ et $E_\omega =
\vect\left( \left[\petitematrix{\strut 1\cr \omega\cr \vdots\cr
\omega^5\cr 0\cr 0\cr \vdots\cr 0\strut \cr} \right],  \left[
\petitematrix{\strut 0\cr 0\cr \vdots\cr 0\cr 1\cr \omega\cr \vdots\cr
\omega^5\strut \cr }
\right]\right) = \vect(e_\omega , e'_\omega)$.\s
Et on a $M\,e_\omega=\left[
\petitematrix{\strut\omega^2+\omega^4\cr \vdots\cr 1\cr \vdots\strut\cr}\right]
=(\omega^2+\omega^4)
\,e_\omega+e'_\omega$ et $M\,e'_\omega=\left[
\petitematrix{\strut 1\cr \vdots\cr \omega+\omega^5\cr \vdots\strut\cr}\right]=
e_\omega+(\omega+\omega^5)\,e'_\omega$ (il suffit de calculer les composantes
d'indice $1$ et $7$ puisque $M\,e_\omega\in \vect(e_\omega ,
e'_\omega)$). Et sur la base $\Bigl((e_\omega , e'_\omega)
\Bigr)_{\omega\in{\bf U}_6}$, l'endomorphisme associ\'e \`a $M$ dans la base
canonique de $\R^{12}$ a pour matrice une matrice une matrice diagonale
par blocs ayant comme blocs diagonaux les $6$ matrices
$N_\omega=\cmatrix{\omega^2+\omega^4&1\cr 1&\omega+\omega^5\cr}$.\s
Donc on a $P_M=\prod_{\omega\in{\bf U}_6}P_{N_\omega }$ et donc 
$\un{\sp(M)=\bigcup\limits_{\omega\in{\bf U}_6}\sp(N_\omega)\h{ o\`u }
N_\omega=\cmatrix{\omega^2+\omega^4&1\cr 1&\omega+\omega^5\cr}}$~.\sv

$\diamond$ On a $\omega^4=\omega^{-2}=\overline{\omega^2}$ et
$\omega^5=\overline{\omega}$. De plus $\omega={\rm e}^{i\theta }$ avec
$\theta\in\bigl\{k\,\fracs{\pi}{3}\mid k\in\[0,5\] \bigr\}$ et donc
$\omega^2+\omega^4=2\,\cos(2\theta)$ et $\omega+\omega^5=2\,\cos
\theta$.\par
On a donc, avec cette notation, $P_{N_\omega}=X^2-2\,\bigl(\cos(2\theta)+\cos
\theta \bigr)\,X+4\cos(2\theta)\cos\theta-1$ de discriminant r\'eduit $\Delta
'=\bigl(\cos(2\theta)+\cos\theta \bigr)^2-4\cos(2\theta)\cos\theta+1=
\bigl(\cos(2\theta)-\cos\theta \bigr)^2+1$.\par Donc $\sp(N_\omega)=\bigl\{
\cos(2\theta)+\cos\theta+\sqrt{\bigl(\cos(2\theta)-\cos\theta \bigr)^2+1},
\cos(2\theta)+\cos\theta-\sqrt{\bigl(\cos(2\theta)-\cos\theta
\bigr)^2+1}\bigr\}$.\par Par parit\'e du cosinus, on a $\sp(N_\omega)=
\sp(N_{\overline{\omega}})$ car $\overline{\omega}={\rm e}^{-i\theta }$ et $
\sp(N_1)=\bigl\{3,1\bigr\}$, $\sp(N_{{\rm e}^{i\pi/3}})=
\sp(N_{{\rm e}^{5i\pi/3}})=\bigl\{\sqrt{2},-
\sqrt{2}\bigr\}$, $\sp(N_{{\rm e}^{2i\pi/3}})=\sp(N_{{\rm e}^{4i\pi/3}})=\bigl\{0,-2\bigr\}$, $\sp(N_{-1})  
=\bigl\{\sqrt{5},-\sqrt{5}\bigr\}$.\s
Finalement $\un{\sp(M)=\Bigl\{-\sqrt{5},\;-2,\;-\sqrt{2},\;0,\;1,\;\sqrt{2},\;
\sqrt{5},3
\Bigr\},\quad -2,0,\pm\sqrt{2}\ \h{ \'etant valeurs propres doubles}}$~.\sv\sv

$\diamond$ En particulier $-1$ n'est pas valeur propre de $M$ et donc, d'apr\`es ({\bf
5}), $X$ a strictement plus que $\frac{n}{d+1}=\frac{12}{4}=3$
composantes non nulles.
Donc \underbar{3 lampes ne suffisent pas \`a r\'esoudre le premier probl\`eme}~.\sv

$\diamond$ $\un{\h{Une solution est:\quad une lampe en}\quad
\encadre{1}\ ,\ \encadre{2}\ ,\ \encadre{9}\ ,\ \encadre{11}}$~~.\s
En effet, la lampe en $1$ \'eclaire 1, 3, 5, 7; celle en 2  \'eclaire 2, 4, 6, 8;
celle en 9  \'eclaire 9, 10 et, enfin, celle en 11  \'eclaire 11 et 12.\sv\sv
  
$\diamond$ Avec les notations du ({\bf 7}), on a, ici, $p\le
\frac{\sqrt{5}\times 12}{3+\sqrt{5}}\simeq 5,125$ donc $p\le 5$ et donc
le nombre de lampes v\'erifie $k'=n-p\ge 12-5=7$.
Ainsi, \underbar{il faut au moins 7 lampes pour r\'esoudre le second
probl\`eme}~.\sv
Montrons qu'\underbar{il n'y pas a de solution avec seulement 7 lampes}~.\s
Supposons qu'il existe une telle solution. Consid\'erons les 3 rues
$(1,3)$, $(3,5)$, $(5,1)$~: pour les \'eclairer il faut, d'apr\`es ({\bf
6}), au moins $2=\left[ \frac 32\right] $ lampes sur les sommets 1, 3, 5. 
Notons $k_1\ge 2$ le nombre de lampes sur ces $3$
sommets. De m\^eme, il faut $k_2\ge 2$ lampes sur les sommets 2, 4, 6 et
$k_3\ge 3$ lampes sur les six sommets de 7 \`a 12. On a donc
$7=k_1+k_2+k_3$ donc $(k_1-2)+(k_2-2)+(k_3-3)=0$ et donc $k_1=k_2=2$ et
$k_3=3$.\par
On a donc exactement 2 lampes sur les sommets 1, 3, 5, par exemple en 1
et en 3. Alors, pour que la rue $(5,11)$ soit \'eclair\'ee, il faut une
lampe en $11$. Mais pour que les $3$ lampes plac\'ees sur les sommets 
7 \`a 12 \'eclairent les 6 c\^ot\'es de l'hexagone, il ne faut pas que deux
lampes soient dans la m\^eme rue. Ceci donne comme emplacement des lampes
les sommets 9 et 7. Et alors, pour \'eclairer $(2,8)$ , il faut
une lampe en 2, pour $(4,10)$, une lampe en 4 et pour $(6,12)$, une lampe en
6 ce qui donne $k_2=3$ en contradiction avec $k_2=2$.\sv

$\un{\h{Une solution en 8 lampes est:\quad une lampe en}\quad
\encadre{1}\ ,\ \encadre{3}\ ,\ \encadre{11}\ ,\ \encadre{9}
\ ,\ \encadre{7}\ ,\ \encadre{2}\ ,\ \encadre{4}\ ,\ \encadre{6}}$~~.\s
En effet, la lampe en 1 \'eclaire les rues $(1,3)$, $(1,5)$, $(1,7)$; celle en
3 \'eclaire $(3,5)$, $(3,9)$; celle en 11 \'eclaire $(11,5)$, $(11,12)$, $(11,10)$;
celle en 9 \'eclaire $(9,8)$, $(9,10)$; celle en 7 \'eclaire $(7,8)$, $(7,12)$
; celle en 2 \'eclaire $(2,4)$, $(2,6)$, $(2,8)$; celle en 4
\'eclaire $(4,6)$, $(4,10)$ et, enfin, celle en 6 \'eclaire $(6,12)$. 

\sv\sv\sv
\finetoiles

\bye

