L’énigme des moines

Posted on 21 décembre 2011 by Valvino

En ces temps de fêtes, je vous propose une énigme pour briller lors des repas de famille. Je propose même une variante plus subtile si vous estimez que votre belle-mère fait preuve d’un esprit logique à tout épreuve (ou pas).

Premier énoncé

Dans un monastère perdu, il y a N moines (par exemple N = 100). Ces braves religieux ont deux règles absolues :

il est interdit de communiquer entre eux de quelque manière que ce soit : il est impossible pour eux d’échanger la moindre information à leurs congénères par la parole, les gestes, l’attitude, …
il est interdit de regarder son propre visage, que ce soit dans un miroir ou dans une flaque d’eau, etc.

Un beau jour le diable débarque à la cantine où tous les moines sont réunis et déclare (tous les moines l’entendent) :

J’ai marqué sur le front d’au moins un moine un symbole satanique.

Les moines qui savent à coup sûr qu’ils sont marqués du sceau de l’infamie se suicident à minuit. On suppose également que les moines sont parfaitement logiques et intelligents, c’est-à-dire que s’il y a un moyen infaillible de savoir s’ils sont marqués, ils le découvrent dans la journée et se suicident le soir.

La question est : si le diable a marqué disons n moines (par exemple n = 30, les moines ignorent ce nombre), que se passe-t-il?

Deuxième énoncé (plus subtil)

La situation est exactement la même sauf que le diable marque n moines (les moines ignorent ce nombre) sans se faire voir ni rien dire à personne et s’en va.

Un beau jour (le nombre de jour n’importe pas cela peut être 3 jours ou 10 ans après), une femme débarque à la cantine où tous les moines sont réunis et déclare (tous les moines l’entendent) :

Il y a au moins un moine ici avec une marque satanique sur le front.

La question est : que se passe-t-il?

Indices et solution du premier énoncé

Indice : regarder ce qui se passe si n = 1, puis n = 2, etc.

Solution : si n = 1, le moine marqué voit qu’aucun de ses collègues n’a de marque, il sait donc que c’est lui qui a la marque (le diable a dit qu’il y a au moins une marque), donc se suicide dès le premier soir. Si n = 2, les deux moines marqués voient un seul autre moine marqué, donc ne peuvent rien conclure et ne font rien le premier soir. De même les autres moines ne font rien. Mais le deuxième jour, les deux voient que l’autre marqué ne s’est pas suicidé, ils en concluent que eux aussi ont la marque (sinon l’autre se serait suicidé, on serait dans le cas précédent n = 1) et se suicident. En refaisant le même raisonnement, on voit que pour n = 3 les moines marqués vont voir deux autres marqués et vont attendre le troisième jour pour voir si on est dans le cas précédent n = 2, ils voient alors que non et en concluent qu’ils doivent se suicider.

Finalement en réitérant le raisonnement (ie en faisant un raisonnement par récurrence, mais vous allez larguer votre belle-mère avec ce terme, si jamais elle avait suivi jusque là), tous les n moines marqués vont tous se suicider le soir du n-ième jour.

Indice et solution du second énoncé

S’il y a un seul moine marqué c’est exactement comme la situation précédente, le moine marqué va voir qu’il ne voit aucun marqué, il va donc se suicider le soir de la visite de la femme. Avant il n’avait aucun moyen de savoir qu’il était le seul marqué.

S’il y a deux moines marqués ou plus, c’est un peu plus subtil parce qu’on se dit que dès que le diable a fait son oeuvre, les moines voient au moins un marqué et sont au courant de l’existence des marques. On a donc envie de dire que les n moines vont se suicider le n-ième jour après la visite du diable, et non le n-ième jour après la visite de la femme.

La question fondamentale est : qu’apporte réellement comme information la femme (et le diable dans le premier énoncé)?

En fait c’est un peu sur le mode de « je sais qu’il sait que je sais… ». En effet, s’il y a deux moines marqués, dès la visite du diable ils vont tous les deux savoir qu’il y a un seul autre moine marqué. Mais ils ne peuvent savoir comment interpréter que l’autre ne s’est pas suicidé le premier soir après la visite du diable. Est-ce parce qu’il a vu une autre marque, ou parce qu’il est le seul marqué et qu’il ignore qu’il y a des moines marqués?

Finalement, il faut vraiment attendre la visite de la femme pour commencer le cycle, et les n moines vont se suicider le soir du n-ième jour après la visite de la femme (même raisonnement que pour le premier énoncé).

En fait, la femme (et le diable dans le premier énoncé) apporte plus que la connaissance de l’existence de moines marqués. Elle apporte aussi le fait que les autres sont au courant de l’existence de ces marques.

Amusez-vous à la raconter, et dites-moi ce que vous en pensez dans les commentaires. Bonnes fêtes!

Modéliser le trafic routier : introduction aux lois de conservation hyperboliques (1)

Posted on 10 août 2011 by Valvino

Il est assez facile de créer des modèles qui simulent le trafic routier. Bien que trop simpliste, et donc irréaliste, ces modèles constituent une bonne introduction à la théorie des lois de conservations hyperboliques.

L’équation de base

On va supposer que la route est une ligne droite sans début ni fin (pas très réaliste donc). Il n’y a qu’une seule voie : les voitures ne peuvent pas se doubler; si une voiture est bloquée elle bloque les voitures derrière elle. On modélise donc la route par la droite des réels $\mathbf R$ .

On note $v(t,x)$ la vitesse des voitures à l’instant $t$ au point $x$ et $\rho(t,x)$ la densité de voitures.

Le principe physique utilisé ici est simple : la variation du nombre de véhicule entre deux points $x_1$ et $x_2$ en un instant $t$ est égale à la différence des flux de voitures en $x_1$ (ce qui rentre) et $x_2$ (ce qui sort).

Le nombre de véhicule entre $x_1$ et $x_2$ à l’instant $t$ est égal à

$\displaystyle \int_{x_1}^{x_2} \rho(t,x) \mathrm dx$

donc sa variation est

$\displaystyle\partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx.$

Le flux étant par définition $v(t,x)\times \rho(t,x)$ on obtient d’après le principe physique

$\displaystyle\partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx = v(t,x_1)\rho(t,x_1)-v(t,x_2)\rho(t,x_2)$ .

Or par une formule d’intégration par parties on a

$\displaystyle v(t,x_1)\rho(t,x_1)-v(t,x_2)\rho(t,x_2) =-\int_{x_1}^{x_2} \partial_x [ v(t,x)\rho(t,x)] \mathrm dx$

d’où

$\displaystyle \partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx=-\int_{x_1}^{x_2} \partial_x [ v(t,x)\rho(t,x)] \mathrm dx$ .

Comme $x_1$ et $x_2$ ne dépendent pas du temps on a par les régles de dérivation des intégrales

$\displaystyle \partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx = \int_{x_1}^{x_2} \partial_t \rho(t,x) \mathrm dx$ .

Finalement on obtient

$\displaystyle \int_{x_1}^{x_2} [\partial_t \rho(t,x)+\partial_x(v(t,x)\rho(t,x))]\mathrm dx=0$ .

Comme le choix des points $x_1$ et $x_2$ est arbitraire on en déduit que ce qu’il y a sous l’intégrale est nul. On obtient donc l’équation

$\boxed{\partial_t \rho(t,x)+\partial_x(v(t,x)\rho(t,x)) =0}$ .

Choix du flux

L’équation ci-dessus a deux inconnues. Il faut donc rajouter une autre équation si on veut arriver à la résoudre. Le plus simple est de considérer que la vitesse est une fonction décroissante de la densité (plus il y a de voitures moins on peut rouler vite).

Par exemple, on peut considérer que lorsque la densité est presque nulle les voitures roulent à une vitesse maximale $v_{max}$ (typiquement 130 à l’heure) et que pour une certaine densité $\rho_{max}$ les voitures sont à l’arrêt (embouteillage).

Un candidat serait donc la fonction affine

$v(t,x)=v_{max}\left(1-\frac{\rho(t,x)}{\rho_{max}}\right)$

et on obtient l’équation aux dérivées partielles suivante :

$\boxed{\partial_t\rho(t,x)+\partial_x\left[v_{max}\left(1-\frac{\rho(t,x)}{\rho_{max}}\right)\rho(t,x)\right]=0}$ .

On a donc ici un modèle, extrêment simpliste certes, du traffic routier. Pour résoudre correctement ce problème, il faudra spécifier une condition initiale pour $\rho$ en $t=0$ .

Dans le prochain article nous verrons pourquoi le cadre classique des fonctions dérivables ne convient pas ici et comment y remédier.

Simuler l’équation des ondes en dimension 2

Posted on 25 octobre 2010 by Valvino

On peut modéliser la propagation d’une onde dans un milieu homogène, linéaire et isotrope en dimension 2 par l’équation aux dérivées partielles suivante :

$\dfrac{1}{c^2} \dfrac{\partial^2}{\partial t^2} u(t,x,y)=\dfrac{\partial^2}{\partial x^2} u(t,x,y)+\dfrac{\partial^2}{\partial y^2} u(t,x,y)$

où $u(t,x,y)$ représente l’amplitude de l’onde au temps $t$ et au point de coordonnées $(x,y)$ et $c$ la vitesse de propagation de l’onde dans le milieu considéré. Nous allons voir comment simuler une telle équation en utilisant la méthode des différences finies. Dans la suite, on considère $c=1$ , on se donne la condition initiale $u^0(x,y)=u(0,x,y)$ et on suppose que l’onde n’a pas de vitesse initiale :

$\dfrac{\partial }{\partial t} u(0,x,y)=0.$

On fait ces hypothèses pour simplifier l’article, mais la méthode reste valable sans.

Regardons déjà ce qui se passe en dimension 1. Pour une fonction $f$ régulière, la formule de Taylor nous assure que pour un réel $\Delta x>0$ petit on a

$f(x+\Delta x)=f(x)+\Delta x f^\prime (x)+\dfrac{ \Delta x^2}{2} f^{\prime\prime }(x)+\mathcal O(\Delta x^3)$

$f(x-\Delta x)=f(x)-\Delta xf^\prime(x)+\dfrac{\Delta x^2}{2}f^{\prime\prime }(x)+\mathcal{O}(\Delta x^3).$

En additionnant les deux lignes, on a donc

$f(x+\Delta x)+f(x-\Delta x)=2f(x)+\Delta x^2f^{\prime\prime }(x)+\mathcal{O}(\Delta x^3).$

On note $f_i$ la valeur de $f$ au point $i\Delta x$ : $f_i=f(i\Delta x)$ . En négligeant le terme en $\mathcal O(\Delta x^3)$ on a donc

$f^{\prime\prime }_i =\dfrac{f_{i+1}+f_{i-1}-2f_i}{\Delta x^2}.$

On peut faire le même raisonnement avec des fonctions de plusieurs variables. L’équation des ondes s’écrit alors

$\dfrac{u_{i,j}^{n+1}+u_{i,j}^{n-1}-2u_{i,j}^n}{\Delta t^2}=\dfrac{u_{i+1,j}^n+u_{i-1,j}^{n}-2u_{i,j}^n}{\Delta x^2}+\dfrac{u_{i,j+1}^n+u_{i,j-1}^n-2u_{i,j}^n}{\Delta y^2}$

où $\Delta t$ , $\Delta x$ et $\Delta y$ sont des réels positifs petits et où $u_{i,j}^n=u(n\Delta t,i\Delta x,j \Delta y)$ . On peut écrire cette formule de manière différente :

$u_{i,j}^{n+1}=2u_{i,j}^{n}-u_{i,j}^{n-1}+\dfrac{\Delta t^2}{\Delta x^2}(u_{i+1,j}^n+u_{i-1,j}^{n}-2u_{i,j}^n)+\dfrac{\Delta t^2}{\Delta y^2}(u_{i,j+1}^n+u_{i,j-1}^n-2u_{i,j}^n)$

ce qui permet ainsi de calculer les valeurs approchées de $u^{n+1}$ en fonction des valeurs de $u^n$ et $u^{n-1}$ . Il suffit donc d’écrire une boucle dans votre logiciel de calcul numérique favori (pour moi Matlab, sinon en gratuit il y a Scilab) pour calculer les solutions approchées. Il reste cependant deux problèmes. On se donne la condition de départ $u^0$ . On ne peut calculer $u^1$ par la formule précédente, car il nous faut les expressions des deux termes $u^0$ et $u^{-1}$ que l’on a pas! Heureusement Taylor nous vient encore une fois en aide, on a

$u^1_{i,j}=u^0_{i,j}+\Delta t \dfrac{\partial}{\partial t} u^0_{i,j}+\dfrac{\Delta t^2}{2}\dfrac{\partial^2}{\partial t^2} u^0_{i,j}+\mathcal{O}(\Delta t^3)$ .

La vitesse initiale est nulle, donc le terme d’ordre 1 est nul. De plus, on a

$\dfrac{\partial^2}{\partial t^2} u^0_{i,j}=\dfrac{\partial^2}{\partial x^2} u^0_{i,j}+\dfrac{\partial^2}{\partial y^2} u^0_{i,j}$

par l’équation des ondes. En refaisant encore une fois les approximations par Taylor, on trouve que

$u_{i,j}^1=u_{i,j}^0+\dfrac{\Delta t^2}{2\Delta x^2}(u_{i+1,j}^0+u_{i-1,j}^{0}-2u_{i,j}^0)+\dfrac{\Delta t^2}{2\Delta y^2}(u_{i,j+1}^0+u_{i,j-1}^0-2u_{i,j}^0).$

Le second problème est que l’ordinateur ne peut effectuer les calculs que sur un nombre fini de données. Il faut donc borner $i$ et $j$ . Cela pose un problème pour calculer la valeur de $u$ aux bords du domaine. Si on prend $-N \leq j \leq N$ , pour calculer $u^n_{N,j}$ il faudrait connaitre $u^{n-1}_{N+1,j}$ , ce que l’on ne connait pas. On se donne alors les valeurs sur le bord du domaine de calcul. On peut par exemple donner une valeur nulle aux bords, ce qui donnera une onde réfléchie sur les bords. On peut également développer des méthodes pour que les bords soient absorbants, bien qu’il subsiste toujours des réflexions parasites. Ici, j’ai évité le problème en arrêtant la simulation quand la première onde touche les bords.

Voilà ce que donne cette méthode implémentée sous Matlab. Ca ressemble pas si mal que ça à une mare dans laquelle on aurait jeté une pierre, non?

Vidéo de l’équation des ondes en dimension 2

Remarque : la vidéo chez moi est en rouge sous Windows Media Player et en bleu sous VLC, je n’ai aucune idée de la raison… Avez-vous une idée?

L’équation de transport unidimensionnelle

Posted on 3 octobre 2010 by Valvino

On appelle équation aux dérivées partielles une équation qui lie les dérivées partielles d’une ou plusieurs fonctions. Elles sont énormément utilisées en physique, dans des domaines aussi variées que la mécanique des fluides (équation de Navier-Stokes), l’électromagnétisme (équations de Maxwell), la thermodynamique (équation de la chaleur), la mécanique quantique (équation de Schrödinger), etc… On les trouve également dans des domaines comme la météorologie, la synthèse d’image ou l’économie (équation de Black-Scholes).

On va étudier l’exemple le plus simple d’équation aux dérivées partielles : l’équation de transport unidimensionnelle. Elle s’écrit sous la forme

$\displaystyle \frac{\partial}{\partial x} u(x,y)+c \frac{\partial}{\partial y} u(x,y)=0$

où $u(x,y)$ est la fonction inconnue des deux variables $x$ et $y$ et où $c \neq 0$ est une constante. Comme pour les équations différentielles ordinaires, il faut ajouter une condition initiale :

$u(0,y)=u_0(y)$

où $u_0$ est une fonction donnée de la variable $y$ que l’on suppose assez régulière, par exemple dérivable à dérivée continue.

Résolution

On suppose que $u$ est une solution régulière de notre problème, c’est-à-dire que $u$ admet des dérivées partielles selon $x$ et selon $y$ et que ses dérivées partielles sont continues.

On va montrer que $u$ est constante le long de certaines droites, appelées caractéristiques. Pour $y_0$ un réel, posons $D(x)=cx+y_0$ la droite de pente $c$ qui passe par $y_0$ .

On a par les règles de dérivation des fonctions composées :

$\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=\frac{\partial}{\partial x} u(x,D(x))+D'(x) \frac{\partial}{\partial y}u(x,D(x)).$

Or $D'(x)=c$ , on a donc

$\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=\frac{\partial}{\partial x} u(x,D(x))+c \frac{\partial}{\partial y}u(x,D(x))$

et comme $u$ est solution de l’équation de transport, on a

$\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=0$

ce qui montre que $u$ est constante le long de toutes les caractéristiques. On a donc pour tout réel $x$

$u(x,D(x))=u(0,D(0))=u(0,y_0)$

ce qui s’écrit

$u(x,cx+y_0)=u_0(y_0).$

Soient $x$ et $y$ deux réels. Pour connaître la valeur de $u(x,y)$ , il suffit de connaitre la valeur de $u_0$ au point où la caractéristique passant par $(x,y)$ coupe l’axe des ordonnées car $u$ est constante le long de cette caractéristique. On cherche donc le réel $y_0$ tel que la caractéristique passant par $(0,y_0)$ de pente $c$ passe aussi par le point $(x,y)$ . Il faut donc que $D(x)=cx+y_0$ , c’est-à-dire $y_0=y-cx$ . Finalement, on obtient

$\boxed{u(x,y)=u_0(y-cx).}$

C’est la formule de Duhamel. Réciproquement, il est facile de vérifier que si on définit $u$ par la formule de Duhamel, alors $u$ admet des dérivées partielles continues et que

$\begin{cases} \displaystyle\frac{\partial}{\partial x} u(x,y)+c \frac{\partial}{\partial y} u(x,y)=0 \\u(0,y)=u_0(y).\end{cases}$ .

On a donc montré que $u$ définie par la formule de Duhamel est l’unique solution de l’équation de transport.

Médailles Fields 2010 : cocorico!

Posted on 19 août 2010 by Valvino

Ca vient tout juste de tomber : il y a deux français parmi les quatre médailles Fields de 2010. Rappelons que les médailles Fields sont une récompense pour des travaux en mathématique. Sa notoriété est équivalente à un prix Nobel (il n’y a pas de prix Nobel en mathématiques…). On les donne tous les quatre ans. Voici les lauréats de cette année :

Elon Lindenstrauss (Israël) pour ses travaux sur la rigidité des mesures en théorie ergodique et ses applications en théorie des nombres.
Stanislav Smirnov (Russie) pour sa démonstration de l’invariance conforme de la percolation et le modèle d’Ising plan en physique statistique.
Ngô Bảo Châu (né au Vietnam, naturalisé français) pour sa démonstration du lemme fondamental en théorie des formes automorphes grâce à l’introduction de nouvelles méthodes de géométrie algébrique.
Cédric Villani (France) pour ses démonstrations sur l’amortissement de Landau non-linéaire et la convergence vers l’équilibre de l’équation de Boltzmann.

Notons plusieurs choses intéressantes :

la super forme des mathématiques françaises (11 médailles sur 52 en tout ce qui fait la deuxième nation), comme quoi la recherche en France marche pas si mal que ça si on lui en donne les moyens. De plus, l’université Paris-Sud 11 est encore à l’honneur car Ngô Bảo Châu y travaille. On commence à marcher sur les médaillés Fields à Orsay ^^
il y a encore des probabilité (en 2006 la première médaille Fields qui récompensait des travaux en probabilité a été remise au français Wendelin Werner, encore un gars d’Orsay);
sur quatre médailles, deux portent sur des branches des mathématiques « dures », mais deux autres ont des travaux en lien avec la physique.

Rendez-vous dans quatre ans pour la prochaine fournée, avec on l’espère d’autres français (et des prix Clay aussi). Pour plus d’infos, c’est par ici.

Kilomaths.com

Un autre blog de maths…

Author Archives: Valvino