<HTML> <HEAD> <TITLE>Juin 2002 solution</TITLE> </HEAD> <BODY bgcolor="#ffffff">  <table width="100%"> <tr> <td width="15%">&nbsp;</td> <td width="75%">  <center> <font size="+3" color="#0000cc">Solution au probl&egrave;me de juin 2002</font> </center>  <font size="+1">  <P> Les sept nains prennent leur petit d&eacute;jeuner, et Blanche Neige leur a vers&eacute;  du lait. Avant de boire, les nains se livrent au rituel suivant: Le premier  nain verse un sixi&egrave;me de son lait dans le verre de chacun de ses fr&egrave;res  (ce qui le laisse avec rien du tout). Puis le deuxi&egrave;me nain fait la m&ecirc;me  chose, et ainsi de suite. Ce processus se poursuit autour de la table,  jusqu'&agrave; ce que le septi&egrave;me nain aie distribu&eacute; son lait de la m&ecirc;me fa&ccedil;on  (il s'agit de Simplet). A la fin, chaque nain a dans son verre exactement  la m&ecirc;me quantit&eacute; de lait qu'il avait au d&eacute;part. Si Blanche Neige leur avait  vers&eacute; 42 onces de lait en tout, quelle quantit&eacute; de lait chaque nain a-t-il re&ccedil;u? Le probl&egrave;me a-t-il une seule solution, ou existe-t-il plusieurs solutions?  </P>  <P> Ce probl&egrave;me est tir&eacute; du test d'application au <a href="http://www.mathcamp.org">camp math&eacute;matique  Etats-Unis-Canada 2002.</a>  </P>  <P> Seulement six nains nous ont envoy&eacute; des solutions, soit   John Campbell (Edmonton, Alberta), Normand Lalibert&eacute; (Kitchener, Ontario),  Juan Mir Pieras (Espagne), Penny Nom (R&eacute;gina), Alexander Potapenko (Russie),  et Gordon Robinson (Victoria, Colombie Britannique); chacun se m&eacute;rite un verre  de lait. Tous sont d'accord pour dire que les nains ont re&ccedil;u respectivement  <dir> 12, 10, 8, 6, 4, 2 et 0  </dir> onces de lait. Vous pouvez v&eacute;rifier que cette  suite arithm&eacute;tique a les propri&eacute;t&eacute;s d&eacute;sir&eacute;es: Lorsque le premier nain  donne 2 onces de son lait &agrave; chacun de ses fr&egrave;res, l'effet est le m&ecirc;me  que si chacun des nains avait pass&eacute; son verre au suivant; donc la  distribution ne change pas. Robinson, Mir et Potapenko nous indiquent  la g&eacute;n&eacute;ralisation: Si n verres contiennent respectivement k(n-1), k(n-2),  k(n-3), ..., k et 0 onces de lait et on effectue le m&ecirc;me processus, alors  chaque verre se retrouve avec la m&ecirc;me quantit&eacute; qu'il avait au d&eacute;part.  Notre probl&egrave;me correspond au cas n = 7 et k = 2; notons que k est d&eacute;termin&eacute;  par la quantit&eacute; totale de lait, soit 42 onces. </P>  <P> Maintenant, cette solution est-elle unique?  Il est assez clair que le septi&egrave;me nain (Simplet) ne re&ccedil;oit rien au d&eacute;part (puisqu'il termine le processus en vidant son verre), mais il n'est pas aussi clair que la distribution du lait dans les autres verres doit n&eacute;cessairement suivre une progression arithm&eacute;tique 12, 10, 8, ... Les explications qui &eacute;claircissent ce point se regroupent en trois cat&eacute;gorie: </P>  <b>Solution 1 (Potapenko, Robinson)</b>  <P> Notons s<sub>i</sub> la quantit&eacute; de lait que le i-i&egrave;me nain a re&ccedil;u au d&eacute;part,  et r<sub>i</sub> la quantit&eacute; de lait qu'il a re&ccedil;u des autres nains avant de vider son verre. Le i-i&egrave;me nain a s<sub>i</sub> + r<sub>i</sub> onces dans son verre avant de vider en donnant (s<sub>i</sub> + r<sub>i</sub>)/6 onces &agrave; chacun de ses fr&egrave;res.  On a donc:  <dir> <IMG SRC="june02sol.1.gif" HEIGHT=30 WIDTH=122>. </dir>   En effet, avant de vider son verre, le (i+1)-i&egrave;me nain re&ccedil;oit autant de lait que le i-i&egrave;me en a re&ccedil;u, plus ce que lui donne celui-ci. </P>  <P> Or, s<sub>i</sub> est aussi la quantit&eacute; de lait qui se retrouve dans le verre du i-i&egrave;me nain lorsque le processus se termine, c'est &agrave; dire la quantit&eacute; qu'il re&ccedil;oit des autres nains apr&egrave;s avoir vid&eacute; son verre. On a donc:   <dir> <IMG SRC="june02sol.2.gif" HEIGHT=30 WIDTH=146> </dir>   En effet, apr&egrave;s avoir vid&eacute; son verre le i-&egrave;me nain recevra (s<sub>i+1</sub> + r<sub>i+1</sub>)/6 onces de lait du (i+1)-i&egrave;me nain, en plus de la quantit&eacute; que celui-ci recevra apr&egrave;s avoir &agrave; son tour vid&eacute;  son verre. </P>  <P> Ces deux syst&egrave;mes d'&eacute;quations (12 &eacute;quations en tout) permettent de d&eacute;terminer les valeurs relatives de s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, ...: On sait que r<sub>1</sub> = 0. Supposons s<sub>1</sub> = 6. Alors l'&eacute;quation (1) donne r<sub>2</sub> = 1. Connaissant s<sub>1</sub> et r<sub>2</sub>, l'&eacute;quation (2) permet alors de trouver s<sub>2</sub> = 5. Puis, connaissant s<sub>2</sub> et r<sub>2</sub>, l'&eacute;quation (1) permet de trouver r<sub>3</sub> = 2, et ainsi de suite. Les valeurs s<sub>i</sub> ainsi obtenues sont 6, 5, 4, 3, 2, 1 et 0. Mais puisque 6 + 5 + 4 + 3 + 2 + 1 + 0 = 21, il faut tout multiplier  par 2 pour obtenir 42 onces de lait en tout. Ceci nous donne la distribution 12, 10, 8, ... qu'on a indiqu&eacute; au d&eacute;part comme unique solution au probl&egrave;me. </P>   <b>Solution 2 (Campbell, Mir)</b>  <P> On peut formuler les instructions alg&eacute;briquement en termes des variables  s<sub>i</sub> de la solution pr&eacute;c&eacute;dente. Soit S, le vecteur colonne dont les entr&eacute;es sont s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>7</sub> dans l'ordre. Alors le premier stage du rituel correspond &agrave; la multiplication de S par la matrice <BR><BR>   <center> <IMG SRC="june02sol.3.gif" HEIGHT=131 WIDTH=174> </center>	 <BR> De m&ecirc;me, les stages successifs correspondent &agrave; la multiplication par des matrices B, C, D, E, F, G, o&ugrave; la i-i&egrave;me matrice a des 1 sur la diagonale sauf en i-i&egrave;me position, des 1/6 dans la i-i&egrave;me  colonne sauf en i-i&egrave;me position, et des 0 partout ailleurs. Notons P = GFEDCBA, la matrice qui repr&eacute;sente le processus au complet. Le probl&egrave;me se r&eacute;duit alors &agrave; d&eacute;montrer que l'ensemble solution du syst&egrave;me d'&eacute;quations PS = S a dimension 1. </P>  <P> Il existe un r&eacute;sultat profond en alg&egrave;bre lin&eacute;aire, le th&eacute;or&egrave;me de Perron-Frobenius, qui permet de d&eacute;montrer facilement le r&eacute;sultat souhait&eacute;. Cependant, comme il s'agit d'un th&egrave;me avanc&eacute; en alg&egrave;bre lin&eacute;aire, on laisse tomber cette approche. Cependant, l'exp&eacute;rience suivante qui est &agrave; la port&eacute;e de nos lecteurs qui ont acc&egrave;s &agrave; un chiffrier, indique la puissance du th&eacute;or&egrave;me de Perron-Frobenius. Il nous a &eacute;t&eacute; sugg&eacute;r&eacute; par Robinson: Distribuons les 42 onces de lait arbitrairement entre les lutins, puis r&eacute;p&eacute;tons le processus o&ugrave; chaque nain r&eacute;partit son lait entre ses fr&egrave;res, pas seulement pour un cycle complet des 7 nains, mais pour plusieurs cycles. Alg&eacute;briquement, ceci correspond &agrave; multiplier plusieurs fois le vecteur S par la matrice P. En fait, quelque soit la distribution originale des 42 onces, la distribution  finale convergera rapidement vers la suite 12, 10, 8, 6, 4, 2, 0. </P>  <b>Solution 3 (Penny Nom)</b>  <P> Si on abandonne provisoirement la condition s<sub>1</sub> + s<sub>2</sub> + ... + s<sub>7</sub> = 42, l'ensemble des vecteurs (s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>7</sub>) qui satisfont aux conditions de notre probl&egrave;me est un espace vectoriel, soit un ensemble clos sous les sommes, diff&eacute;rences et multiplications par un scalaire. Ceci est une cons&eacute;quence de l'approche matricielle de la solution 2 (pour ceux que cette approche rebute, on donne ci-bas une d&eacute;monstration physique, en rempla&ccedil;ant le lait par de l'huile et de l'eau). On utilise aussi le fait que les valeurs s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>7</sub> sont toutes  positives ou nulles. </P>  <P> On sait donc qu'avec s<sub>1</sub> = 12, s<sub>2</sub> = 10, ..., s<sub>7</sub> = 0, les nains peuvent se livrer &agrave; leur rituel matinal et terminer avec la m&ecirc;me  quantit&eacute; de lait qu'ils avaient au d&eacute;part. Supposons donc que s<sub>1</sub> = x<sub>1</sub>, s<sub>2</sub> = x<sub>2</sub>, ... , s<sub>7</sub> = x<sub>7</sub> est une autre solution avec la m&ecirc;me propri&eacute;t&eacute;. On a alors x<sub>7</sub> = 0, et en multipliant par une constante appropri&eacute;e, on peut supposer que x<sub>1</sub> &lt;= 12, x<sub>2</sub> &lt;= 10, x<sub>3</sub> &lt;= 8, x<sub>4</sub> &lt;= 6, x<sub>5</sub> &lt;= 4 et x<sub>6</sub> &lt;= 2, et qu'au moins une de ces contraintes est satisfaite avec &eacute;galit&eacute;. Par soustraction, on obtient alors la nouvelle solution s<sub>1</sub> = 12 - x<sub>1</sub>, s<sub>2</sub> = 10 - x<sub>2</sub>, ..., s<sub>6</sub> = 2 - x<sub>6</sub> et s<sub>7</sub> = 0. Ici, on a s<sub>i</sub> = 0 pour au moins un des termes s<sub>i</sub> autre que s<sub>7</sub>. Mais si un des lutins autre que Simplet se retrouve avec un verre vide apr&egrave;s que Simplet aie vid&eacute; son verre, c'est que Simplet lui-m&ecirc;me n'avait rien re&ccedil;u des autres lutins, donc tous les verres &eacute;taient vides  au d&eacute;part. Ainsi, s<sub>1</sub> = 12 - x<sub>1</sub> = 0, donc x<sub>1</sub> = 12, s<sub>2</sub> = 10 - x<sub>2</sub> = 0 donc x<sub>2</sub> = 0, et ainsi de suite. Pour une quantit&eacute; totale de 42 onces de lait, la solution s<sub>1</sub> = 12, s<sub>2</sub> = 10, ..., s<sub>7</sub> = 0 est bien unique. </P>  <P> On termine en d&eacute;montrant que si le rituel des lutins pr&eacute;serve les quantit&eacute;s originales s<sub>1</sub> = 12, s<sub>2</sub> = 10, ..., s<sub>7</sub> = 0 et aussi les quantit&eacute;s  s<sub>1</sub> = x<sub>1</sub>, s<sub>2</sub> = x<sub>2</sub>, ... , s<sub>7</sub> = x<sub>7</sub> alors le rituel pr&eacute;servera les quantit&eacute;s s<sub>1</sub> = 12 - x<sub>1</sub>, s<sub>2</sub> = 10 - x<sub>2</sub>, ..., s<sub>6</sub> = 2 - x<sub>6</sub> et s<sub>7</sub> = 0 sans avoir recours au notions d'&eacute;quations lin&eacute;aires et d'espaces vectoriels. Pour ce faire on remplace le lait par de l'eau et de l'huile: Le premier lutin re&ccedil;oit x<sub>1</sub> onces d'eau et 12 - x<sub>1</sub> onces d'huile, le deuxi&egrave;me x<sub>2</sub> onces d'eau et 12 - x<sub>2</sub> onces d'huile, et ainsi de suite. L'eau et l'huile ne se m&eacute;langent pas, donc chaque lutin doit prendre soin de bien brasser son verre avant d'en partager le contenu entre ses fr&egrave;res. A la fin du rituel, chaque lutin a la m&ecirc;me quantit&eacute; totale de liquide qu'il avait au d&eacute;part, comme si c'&eacute;tait du lait.  Si on laisse reposer le liquide un moment, alors l'eau et l'huile se s&eacute;parent, et les lutins retrouvent respectivement x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>7</sub> onces d'eau dans leurs verres, comme au d&eacute;part.  Ainsi, les quantit&eacute;s respectives d'huile dans chaque verre, soit 12 - x<sub>1</sub>, 10 - x<sub>2</sub>, ...,  2 - x<sub>6</sub>, et 0 onces, sont &eacute;galement les m&ecirc;mes qu'au d&eacute;part. </P>  </font>  <font size="+1"> <p> <center><a href="./">Probl&egrave;mes et solutions pr&eacute;c&eacute;dents</a> <br>&nbsp;<br> <center><a href="../../../findex.html">Centrale des Maths</a> </p> </font>  </td> <td width="10%">&nbsp;</td> </tr> </table>  </body> </html> 
