Choux romanesco, Vache qui rit et intégrales curvilignes

12 janvier 2014

[#] Ordre et désordre

Un dernier verre, peut-être ? Venez, ma mie, je vous invite pour un dernier chocolat chaud. Installez-vous sur le canapé, je reviens dans un instant. Ne faites pas attention à cette pile de papiers sur la table et faites comme si les affaires qui traînent par terre, c'est normal. Ignorez également la vaisselle entassée dans l'évier, toute comme cette casserole dans lequel il reste un fond de... euh... ce que j'ai mangé la semaine dernière. Comment ça, cet appartement est mal rangé ? Absolument pas ! D'ailleurs, le désordre total ne peut pas exister ! Ce n'est pas moi qui dit ça, c'est la théorie de Ramsey... Et n'allez pas croire que je me cache derrière les maths... Eh, revenez, je n'ai pas terminé le chocolat chaud !...

La théorie de Ramsey est la suivante : dans une structure contenant beaucoup d'éléments, on finit toujours par retrouver une propriété donnée. La question qui se pose alors, c'est la valeur numérique de ce "beaucoup", qui, pour certain exemple, peut être démesurément grand. On résume plus souvent la théorie de Ramsey par "le désordre total n'existe pas".

Le principe de base de la théorie de Ramsey est le principe des pigeons (alias principe des tiroirs de Dirichlet). Par exemple, à partir de combien de personnes peut-on être sûr d'en trouver deux possédant le même signe du zodiaque ? Puisqu'avec 12 personnes, on peut avoir le zodiaque au complet, la propriété "au moins deux personnes possèdent le même signe astrologique" devient vraie à partir de 13.

Théorème de Ramsey
Le problème central en théorie de Ramsey (et, de façon plus générale, en combinatoire) est celui du théorème de Ramsey. On présente souvent ce théorème par le célèbre problème des six amis.

Vous invitez un groupe d'amis pour une occasion quelconque (soirée foot à la télé, soirée puzzle ...). Parmi ces invités, certains se sont déjà rencontrés auparavent, d'autres se rencontrent pour la première fois. Mais à partir de combien d'invités peut-on être sûr qu'il y ait
- soit trois invités qui se connaissent deux à deux
- soit trois invités qui ne se connaissent pas deux à deux.
Ce nombre, on le notera R(3).

K5

Graphe de la situation.
Deux invités sont reliés par une arête bleue si ils se connaissent, en rouge sinon.
Pour 5 invités, il n'existe pas forcément de trio qui se connaissent ou qui ne se connaissent pas
Ce contre-exemple prouve R(3) ≥ 6.

La réponse est 6, et je peux le prouver ! On suppose que 6 invités sont là, et que David en fait partie (il y a toujours un David dans les invités). Parmi les 5 autres invités, soit il y en a 3 qui le connaissent, soit 3 ne le connaissent pas (par le principe des tiroirs). Sans pertes de généralité, on peut supposer que ces trois invités connaissent David, et qu'ils s'appellent respectivement Karen, Natalie et Billy. Deux possibilités alors : soit ces trois invités ne se connaissent pas (et on a notre trio gagnant), soit il y en a au moins deux qui se connaissent, et ils forment avec David le trio gagnant. CQFD.

Ce problème se reformule dans la théorie des graphes : si les arêtes d'un graphe complet d'ordre 6 sont colorés à l'aide deux couleurs, alors il existe un triangle unicolore.

Friends_strangers_graph

On peut lister l'ensemble des graphes bicolores complets à 6 noeuds.
Ils admettent tous un sous-graphe complet unicolore.

Mais le problème se généralise : combien faut-il réunir d'invités pour être sûr que, parmi eux, il existe un groupe de k invités se connaissant mutuellement, ou ne se connaissant pas du tout ? Ce que nous dit le théorème de Ramsey, c'est que ce nombre existe toujours. Ce que ne nous dit pas le théorème, c'est sa valeur exacte.

Pour k = 4, on peut montrer R(4) = 18, en raisonnant de façon similaire (en trouvant un graphe contre-exemple à 17 sommets, puis en montrant que cela marche bien dès que n=18).
Pour k = 5, les choses se compliquent. Tout ce que l'on sait dire aujourd'hui, c'est que R(5) est strictement compris entre 42 et 50.
Pour k = 6, cela empire : on ne sait pour l'instant dire qu'une seule chose, c'est que le nombre R(6) est quelque part entre 102 et 165...

A ce sujet, Erdõs a imaginé ce qu'il se passerait si une armée d'aliens belliqueux nous déclarait la guerre, à moins qu'on leur fournisse la valeur de R(5). Dans un tel cas, on pourrait mettre à profit l'ensemble des ordinateurs et des mathématiciens de la planète pour calculer ce nombre. Cependant, si ils nous réclamaient R(6), les ordinateurs et mathématiciens disponibles seraient plutôt réquisitionnés pour mettre au point une stratégie permettant de mettre hors d'état de nuire ces extraterrestres...

Le problème de la fin heureuse
Dès qu'un problème cherche le nombre minimal d'objets à réunir pour qu'une propriété soit vérifiée, on peut l'inclure dans la théorie de Ramsey. Un autre problème représentatif est le problème du Happy ending (parce que, à la fin, ils se marièrent et eurent beaucoup1 d'enfants). Ce théorème nous annonce que :

Etant donné (au moins) 5 points du plan (jamais alignés ni confondus),
il y existe toujours quatre points formant les sommets d'un quadrilatère convexe.

Un quadrilatère (ou n'importe quelle figure géométrique) est convexe quand il ne possède aucun creux. Par exemple, le quadrilatère rouge en dessous n'est pas convexe.

HappyEnding

A gauche : un exemple où 4 points ne forment pas un quadrilatère convexe.
A droite, plusieurs dispositions de 5 points. Dans tous les cas, il existe toujours (au moins) un quadrilatère convexe. L'enveloppe convexe des groupes de 5 points est représentée en jaune.

Pour démontrer ce fait, il suffit d'envisager tous les cas possibles, selon l'enveloppe convexe des 5 points (l'enveloppe convexe, c'est le polygone que l'on obtient quand on place un élastique autour de l'ensemble de ses points. Par essence, une enveloppe convexe est convexe).
- si l'enveloppe convexe est un pentagone, il suffit d'en retirer un point pour retrouver le quadrilatère tant cherché.
- si l'enveloppe convexe est un quadrilatère, inutile d'aller chercher plus loin
- si c'est un triangle, alors les deux points à l'intérieur forment un quadrilatère convexe avec au moins l'un des côté (avec le côté qui ne coupe pas la droite formée par les points intérieurs). CQFD.

Cette histoire de quadrilatère convexe est le problème original du happy ending, découvert et démontré en 1933 par Esther Klein. Elle demande alors a ses collègues si l'un d'eux a une idée pour généraliser la question : étant donné un grand nombre de points, y existe-t-il toujours un pentagone/hexagone/n-gone convexe. George Szekeres revient une semaine plus tard avec sa réponse : oui !

Théorème de Erdös-Szekeres : Étant donné un ensemble suffisamment grand de points du plan (jamais alignés ni confondus), il y existe toujours N points formant les sommets d'un polygone convexe.

HappyEnding5
9 points suffisent pour y trouver un pentagone convexe

Si Erdös a accolé son nom a celui de Szekeres, c'est qu'il a pas mal étudié la question lui aussi. C'est d'ailleurs Erdos qui a surnommé ce théorème "happy ending" en 1937, puisque c'est celui-ci qui a mené Esther Klein et George Szekeres à se marier en 1937 !

On peut être un peu plus précis sur la valeur de "suffisamment grand" :
- si on cherche les triangles convexes, 3 points suffisent (puisqu'on les suppose ni alignés, ni confondus)
- si on cherche les quadrilatères convexes, 5 points suffisent.
- si on cherche les pentagones convexes, il faut au moins 9 points.
- si on cherche des hexagones convexes, c'est 17 points qu'il est suffisant d'avoir. Ceci n'a été démontré qu'en 2006 (Szekeres, Peters)
- pour les polygones plus grand, rien n'est encore sûr. On sait qu'il faut au moins 1+2N-2 points pour y trouver à coup sûr un N-gone convexe, on conjecture que cette borne est optimale.

Le problème du polygone vide
Le théorème de Erdös-Szekeres serait encore plus élégant si, en plus d'être convexe, le polygone pouvait être vide (aucun point à l'intérieur). Pour 5 points, pour peu que l'on modifie légèrement la démonstration, on peut montrer qu'il existe toujours un quadrilatère convexe vide. Pour 9 points, il n'existe pas forcément de pentagone convexe vide, mais il suffit de 10 points pour rendre cette assertion vraie. Mais existe-t-il toujours un hexagone convexe vide dans un ensemble assez grand de points ?

La réponse est oui, mais il a fallu attendre 2007 pour en être sûr. Le nombre exact de points suffisant n'est pas connu exactement, mais on sait quand même qu'avec 463 points, on est sûr d'avoir un hexagone convexe vide.

HexagoneCache

463 points au hasard. Il y existe forcément (au moins) un hexagone convexe vide
Avec moins de 463 points, rien n'est sûr...

Je prèfère ne pas trop évoquer le cas de l'heptagone convexe vide, puisqu'il contredit la théorie de Ramsey : même avec un nombre arbitrairement grand de points, on ne peut pas être sûr d'y trouver d'heptagone convexe vide...

Le nombre de Graham
Un dernière exemple de problème de la théorie de Ramsey, le problème de Graham :

Considérons un hypercube de dimension n où chaque arête et diagonale est coloré en rouge ou en bleu.
Y existe-t-il toujours un plan unicolore défini par 4 sommets coplanaires ?
Si non, à partir de quelle dimension n est-ce toujours vraie ?

Exemple, avec n = 3. On a donc un cube (on ne peut plus classique, en 3D), on colore en rouge/bleu ses 28 arêtes et diagonales. Parfois, on peut y trouver un plan unicolore :

GrahamCube

Et parfois, non :

GrahamCube2
Impossible de trouver un plan unicolore passant par 4 points dans ce cube

A partir de quelle dimension peut-on être sûr d'en trouver ? Les spécialistes conjecturent qu'il suffit de chercher dans un hypercube de dimension 13. Mais entre ce que l'on conjecture et ce qu'on l'on arrive à démontrer il y a un gouffre, ce problème en est le plus gros exemple. Ce que Graham est parvenu à démontrer, c'est que la dimension recherchée est un nombre grand. Très grand. Ce nombre est tellement grand que je ne peux l'écrire sur ce blog. Je ne peux même pas écrire le nombre de chiffres qui le compose, pas plus que le nombre de chiffres qui compose son nombre de chiffresCe nombre est tellement grand que si je l'utilise dans une blague de "ta mère", on pourrait penser que j'exagère un peu. A l'heure d'aujourd'hui, cette borne supérieure reste la pire qui existe de toute l'histoire des démonstrations mathématiques. Et pourtant, grace à cette démonstration, on peut quand même dire qu'il est vrai que la propriété de Graham est vraie en grandes dimensions...

Ce nombre N*, c'est le 64e terme de la suite
u1 = 4
u2 = 3 ↑ 3
u3 = 3  3 3
... où n désigne la flèche (itérée n fois) de Knuth (voir ce vieil article)

Certaines personnes ont du mal à penser en dimension 3, la plupart des gens sont incapable de penser en dimension 4. Il ne me semble pas que quiconque sur Terre soit capable de réfléchir en dimension N*. 


Sources :
Une démonstration du calcul de R(4)
, et plein d'autres articles intéressants sur cut-the-knot
Colorie-moi le ciel, qui parle aussi du théorème de Ramsey infini
Le désordre total n'existe pas..., Pour la Science N°376 - fevrier 2009

Images :
Friends strangers graph


1 : Encore une fois, la théorie de Ramsey ne nous donne pas la valeur exacte de ce "beaucoup".


05 janvier 2014

[#] 2013+1 (Cette nouvelle année est-elle intéressante ? Episode 05)

Nous venons de changer d'année, et, comme en chaque nouvelle année, je ne peux pas résister à l'envie de passer en revue les différentes propriétés (in)intéressantes du nombre de l'année.

Pour savoir si un nombre est intéressant, l'instrument de mesure officiel est l'OEIS, l'encyclopédie en ligne des suites entières. Plus un nombre apparaît sur l'OEIS, plus il est intéressant. A titre d'exemple, 2011 possédait 378 propriétés et était, ce ce fait, un nombre particulièrement intéressant (il faut dire que c'était un nombre premier, une vertu qui se fait de plus en plus rare chez les nombres). Les années 2012 et 2013 possèdent respectivement 121 propriétés et 96 propriétés, ce qui font d'elles des années bien moins intéressantes.

Et 2014, dans tout ça ? Eh bien... Comment dire ?... Il va falloir faire avec... C'est la crise pour tout le monde, hein ?...

2014 possède seulement 76 propriétés !

Ce n'est pas encore cette année que la courbe des propriétés va s'inverser. Mais j'ai cru comprendre que le changement, c'est l'année prochaine. Voyons tout de même ce que le nombre 2014 a à nous offrir.

Excursions de Motzkin [A057585]
Le n-ième nombre de Motzkin (noté Mn), c'est le nombre de façons de placer des cordes non concourantes sur un cercle, entre n points [A001006].

Par exemple, M4 = 9 : il y a 9 façons de dessiner des cordes qui ne se croisent pas entre 4 points d'un cercle :

Motzkin

En cherchant à la main, on peut voir que M1 = 1, M2 = 2, M3 = 4 et que M4 = 9.

Pour calculer les nombre suivants, il faut réfléchir de manière un peu plus récursive. Supposons que l'on vient de calculer Mn, et cherchons Mn+1. Combien y a-t-il de façons de placer des cordes entre ces n+1 points ?
Déjà, il y en a au moins Mn (il suffit d'ignorer ce n+1-ième point que l'on vient d'ajouter.
Maintenant, prenons en compte ce nouveau point, et reliant-le à l'un des autres points, disons qu'il s'agit du k-ième (n choix possibles). Cette corde sépare le cercle en deux morceaux, l'un comptant k-1 points (donc Mk-1 façons d'y placer des cordes), l'autre en comptant en comptant n-k (et donc, Mn-k placements de cordes possibles). Cette séparation offre donc Mk-1×Mn-k façons de placer les cordes.

Schema_Motzkin
La corde [n+1;k] sépare le cercle en deux zones, l'une comptant k-1 points, l'autre n-k.
Il y a donc Mk-1×Mn-k placements comptant cette corde.

Si on fait le compte, il y a Mn placements qui ne prennent pas en compte le n+1 points, et, pour chaque point k entre le 1er et le n-ième, il y a  Mk-1×Mn-k placements comprenant la corde [n+1 ; k]. Donc :

FormuleMotzkin

A l'aide de cette formule, on peut calculer que M5 = 21, M6 = 51, M7 = 127, M8 = 323, M9 = 835 et que M10 = 2188. Non, 2014 n'est pas un nombre de Motzkin (mais on y arrive...)

Mais il existe d'autres façons d'intérpréter les nombres de Motzkin, en particulier, celle des chemins de Motzkin : un chemin qui peut monter, descendre ou aller tout droit, et qui revient à sa hauteur de départ. Le nombre de chemins de Motzkin de longueur n est donné par Mn. Ainsi, il existe 9 chemins de Motzkin de longueur 4 :

CheminMotzkin
9 chemins de Motzkin de longueur 4, autant que de cercles de Motzkin.

On peut obtenir un chemin de Motzkin à partir d'un cercle cordé en le parcourant dans l'ordre de ses points. Un début de corde se traduira par un chemin montant, une fin de corde se traduit par un chemin descendant.

Chemin_8
Exemple de placements de corde sur un cercle à 8 points, et son chemin de Motzkin de longueur 8 correspondant.

La question primordiale qui se pose alors : quid de l'aire sous les chemins de Motzkin ? Pour n=4, on peut compter que A4 = 16. Mais pour n plus grand ? On peut montrer (la démonstration en question a été coupée au montage de cet article) que l'aire totale An sous les chemins de longueur n est donnée par la formule :

FormuleMotzkin2

On peut calculer que A5 = 56, A6 = 190, A7 = 624 et A8 = 2014.

Bref : l'aire totale sous les 323 chemins de Motkin est 2014 ! (Tout ça pour ça...) Et c'est a peu près la seule propriété qui vaut la peine d'être développée parmi tout ce que l'OEIS a à nous proposer.

Mais 2014 a de nombreuses autres propriétés intéressantes :

  • 2014 correspond à la somme de 12 nombres triangulaires (nombres de la forme T(N)=1+2+3+...+N), en commençant par le 12e : 2014 = T(12) + T(13) + ... + T(23). [A119034
  • 2014 est de la forme n(n+15) : 2014 = 38×(38+15). [A132760]
  • Ma préférée : 2014 = 133 - 132 - 131 - 130.[A083074]
  • 5 × 22014-1 est un nombre premier. [A001770]
  • 2014 peut-être écrit comme la somme de plusieurs carrés impairs distincts de 89 façons différentes, c'est plus que pour n'importe quel nombre plus petit. [A167702]
  • Il y a 2014 4-uplets (a,b,c,d), où 1 ≤ a,b,c,d ≤ 7, tels que ab+cd ≤ 49. [A212150]
  • Les 2014e nombre dodécahédral peut s'écrire comme la somme de deux nombres dodécahédraux. C'est plutôt rare ! [A053017]
  • Le numérateur du 4028e (=2*2014) nombre de Bernoulli est divisible par 233. J'ai du mal à comprendre pourquoi cette liste existe... [A092228]
  • Et c'est à peu près tout...

Du côté des propriétés qui trainent sur Twitter aux alentours du premier janvier, on a :

  • 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 + 2 = 2014 (@mikko)
  • (10 + 9 ) × ((8×7) + 6 - 5 - 4) × (3 - 2 + 1 + 0) = 2014 (@alexbello)

Bref : bonne année 2014 !

Et la santé !

01 décembre 2013

[#] Calendrier de l'avent

Et pourquoi pas un calendrier de l'avent, en attendant petit papa Noël ? A la manière des Shots of science, un nouvel instantané mathématique sera ajouté tous les jours dans cet article, histoire de frimer à la machine à café  (pour peu que vous ayez des collègues compréhensifs...)

Posté par El Jj à 00:01 - Commentaires [7]
Tags : ,

24 novembre 2013

[#] Bézout futé

Le théorème de Bézout n'est pas qu'un théorème d'arithmétique vu en Terminale, c'est aussi un des principaux résultats de la géométrie algébrique. Ce qui est chouette avec ce résultat, c'est qu'il est manifestement faux au premier abord, mais qu'il devient particulièrement satisfaisant quand on s'y penche un peu. Je ne vais pas le creuser dans cet article, simplement déblayer le terrain. En quelques mots, il dit que :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection.

Une courbe algébrique, c'est une courbe dont l'équation est un polynôme (que l'on peut écrire sous la forme P(x,y)=0, comme par exemple 3x36y6+4x²y-1=0). Le degré de la courbe, c'est le degré du polynôme. Globalement, les courbes algébriques, c'est ce qui se fait de plus joli en matière de courbes.

A titre d'exemple, les courbes algébriques de degré 1 sont les droites (ax + by + c = 0), celles de degré 2 sont les coniques (paraboles, hyperboles, ellipses...). Plus on grimpe en dégré, plus les courbes sont compliquées à appréhender.

Vous avez échappé à des cubiques de tous horizons, faute de place.

Quelques exemples de courbes algébriques de degré 1 et 2.

Ainsi, d'après le théorème de Bézout, deux droites (degré 1) se coupent toujours en un (=1×1) seul point, deux coniques (degré 2) se coupent toujours en 4 (=2×2) points, une droite (degré 1) coupe toujours une cubique (degré 3) en exactement 3 (=1×3) points...

Jusqu ici, tout va bien (Sophia Aram)

A gauche, l'intersection d'un cercle (degré 2) et d'une cubique de Humbert (degré 3) donne 6 points d'intersection
A droite, l'intersection de deux cubiques (de degré 3) donne 9 points d'intersection

Mais ça, c'est ce qu'il se passe dans un monde parfait. Les contre-exemples sont malheureusement légion :

En général, on se contente d un seul contre-exemple. Quand on en a besoin de quatre, c est que l on cherche à compenser quelque chose.

Quatre contre-exemples au théorème de Bézout.

Et pourtant, dans chaque cas, le nombre de points annoncé est bien le bon. Il y a cependant de nombreuses subtilités...

Sauf que... la multiplicité
Dans certains cas, un même point d'intersection comptera plusieurs fois (on parle de la multiplicité de ce point d'intersection). C'est injuste, mais il faut faire avec. Cette situation peut arriver sous plusieurs formes différentes.

Déjà, il y a les courbes qui s'auto-intersectent. C'est par exemple le cas de la cubique x3 - 3x² + y² = 0 (représentée dans le premier contre-exemple), dont la courbe forme une boucle. Au point (0,0), la courbe s'auto-coupe, ce point là sera donc compté deux fois s'il intervient dans une intersection.

On pourrait surement faire une version algébrique du Scrabble, dans lequel les points compteraient double...

Le point (0,0) appartient à la fois à l'arc vert et à l'arc jaune, il sera donc compté deux fois, ce qui donne bien trois points d'intersection.
Remarquons que si on déplace un peu la droite bleue, on retrouve trois vrais points d'intersection.

Lorsque les courbes se touchent sans se croiser, on tombe aussi sur des points comptés double (voire pire). En particulier, c'est ce qui se passe lorsque l'on compte le nombre de point d'intersection entre une courbe et l'une de ses tangentes. 

Ca serait un scrabble où, au lieu de jouer des lettres, on jourait des polynômes !... Non, ça semble définitivement être une mauvaise idée.

La droite bleue est tangente à la courbe rouge au point (2,2), ce point d'intersection comptera double.
En déplaçant un peu la droite, on peut faire apparaître ces deux points.

Le théorème de Bézout est en fait:

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection, comptés avec leur multiplicité.

Sauf que... les nombres complexes
Le problème de la représentation graphique des courbes algébriques, c'est qu'elles ne sont que la partie émergée de l'iceberg. Rien n'oblige les courbes à se croiser dans le plan réel, les points d'intersection peuvent parfaitement être complexes. Et cette situation arrive bien trop souvent pour être négligée.

On peut reprendre l'exemple des points d'intersection de la parabole d'équation y-x²=0 et de l'ellipse d'équation x²+2y²-y-2=0. Les points (-1;1) et (1;1) sont solutions, mais les points (i;-1) et (-i;-1) aussi (vérifiez par le calcul si vous ne me croyez pas !). On a bien les quatre points attendus.

DesCourbesComplexes

En comptant les points à coordonnées complexes, on a bien 4 points d'intersection.

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan complexe ℂ² , comptés avec leur multiplicité.

Sauf que... les points à l'infini
Où se coupent deux droites parallèles ? Eh bien, elles se croisent... à l'infini ! Pour le voir, il suffit de pencher un peu la caméra pour regarder ce qu'il se passe au loin. En faisant cela, on fait apparaître la ligne d'horizon, où se rencontrent toutes les droites parallèles.

Là où toutes les droites se croisent...

A gauche : deux droites parallèles, vu de dessus
A droite : deux droites parallèles, vu de biais

Ces deux droites, courbes algébriques de degré 1, possèdent donc bien un unique point d'intersection, mais il est "à l'infini". Ce point d'intersection n'est pas dans le plan, mais dans le plan projectif, où l'on a ajouté tous les points à l'infini (chaque point à l'infini correspond à une direction de droite).

De la même façon, on peut voir que la droite et la parabole du premier exemple possèdent bien deux points d'intersection, dont un à l'infini :

Après 3 heures de réflexion, j ai enfin réussi à dessiner ce f$#$* plan projectif !

En penchant la caméra, la parabole devient une ellipse, faisant apparaître un deuxième point d'intersection à l'infini. On peut en fait démontrer que n'importe quelle conique est une ellipse, pourvu qu'on la regarde sous le bon angle.

C'est aussi ce qui arrive lorsque deux courbes sont asymptotes l'une à l'autre : elle se croisent sur la ligne de l'infini (et en plus, le point d'intersection sera de multiplicité 2 ou plus).

Le théorème de Bézout est en fait :

Deux courbes algébriques de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Sauf que... des composantes communes
Un dernier point à vérifier pour que le théorème fonctionne parfaitement : il ne faut pas que les courbes aient des composantes communes.

Par exemple, prenons les courbes (de degré 2) d'équation x² - 1 = 0 et xy-x-y+1=0. Selon Bézout, ces courbes devraient avoir 4 points en commun. En réalité, ces courbes ont une infinité de points d'intersection :

Non, ces courbes ne sont pas vraiment intéressantes.
Les deux courbes ont une composante commune, la droite verticale d'équation x=1, qui correspond donc à une infinité de points en commun.

Le problème, c'est que les courbes en question peuvent être écrites comme la réunion de courbes de degré plus petit (des composantes irréductibles). La première est la réunion des droites d'équation x-1=0 et x+1=0, la deuxième est la réunion des droites d'équation x-1=0 et y-1=0. Les deux courbes ont une même composante commune (x-1=0), et le théorème de Bézout n'est pas prévu pour ça.

Le théorème de Bézout est en fait :

Deux courbes algébriques sans composantes communes de degré n et p ont exactement n×p points d'intersection dans le plan projectif complexe P2(ℂ) , comptés avec leur multiplicité.

Maintenant, on peut appliquer le théorème, et jouer au jeu pratiqué dans le cercle très fermé des géomètres algébristes : "où sont passés les points d'intersection manquant ?!".

Par exemple, combien de points d'intersection possèdent ce quadrifolim (en bleu), de degré 6, et ce trifolium (en rouge), de degré 4 ?

Oui, j ai piqué cette image sur wikipédia. Mais on a rarement de si joli points de multiplicité 14.

A première vue, on compte 5 points d'intersection, mais il y en a en fait 24 :
4 points réels, de multiplicité 1
1 point réel, de multiplicité 14
2 points complexes à l'infini (les deux à la fois !), de multiplicité 3

(Et joyeux anniversaire à ce blog, qui vient de fêter ses 7 ans !)


A lire également :
Bézout et les intersections de courbes algébriques, sur BibNum, analyse de Liliane Alfonsi du texte original de Bézout.

13 octobre 2013

[#] Indivisibles

Tout bon agenda de lycéen comporte une page regroupant les formules d'aires et de volumes des figures usuelles. Certaines formules coulent de sens (aire d'un carré, d'un rectangle), d'autres sont évidentes si on prend deux secondes pour y réfléchir (aire d'un triangle, d'un parallélogramme). Et il y a les autres, qui semblent sortir de nulle part : pourquoi l'aire d'un disque de rayon r est πr² ? Et pourquoi le volume d'une sphère est de  4/3 π r3 ?

Ces formules ont été découvertes assez vite, mais au fil de l'histoire, ce sont les démonstrations qui ont évolué. Dans l'antiquité, Euclide et Archimède ont utilisé la méthode d'exhaustion pour prouver l'équivalent de ces formules : l'aire d'un disque ne peut pas être plus grande que πr², elle ne peut pas être plus petite non plus, elle lui est donc égale.
Cette méthode d'exhaustion fait appel aux limites, autrement dit, à l'infini. La notion d'infini étant taboue à l'époque, les calcul d'aires étaient plutôt limités.

Aujourd'hui, pour calculer l'aire ou le volume d'une figure, on utilise l'intégration, qui fait appel à des sommes infinies d'objets infiniment petit. Depuis que l'on sait dompter l'infini, ce genre de calculs ne fait plus peur à qui que ce soit.
Entre temps, il y a eu le XVIIe siècle. A l'époque, l'infini n'était toujours pas parfaitement assimilé, mais plus personne n'avait peur de le manipuler, quitte à faire pleurer n'importe quel mathématicien moderne. C'est à cette période que John Wallis invente le symbole ∞ et que Leibniz et Newton inventent/découvrent le calcul infinitésimal moderne.

Juste avant ces progrès, il y a eu Cavalieri et Roberval, qui ont mis au point une méthode redoutable pour calculer des aires et produire de nouvelles formules. La seule ombre, c'est que cette méthode miracle ne fonctionne pas dans toutes les situations, sans que l'on ne sache exactement pourquoi. Aujourd'hui, on le sait : l'infini doit être manipulé avec précaution pour éviter les paradoxes. Il n'empêche, leur méthode fonctionne !

Robin l'avait évoqué dans cet excellent épisode de Podcast Science sur l'infiniment petit, j'ai voulu creuser un peu. La méthode des indivisibles de Cavalieri, ancêtre du calcul intégral, comment ça marche ?

Le principe de Cavalieri
L'idée de base est de considérer une surface comme l'empilement d'un nombre indéfini de lignes, toutes parallèles. Si deux surfaces sont composées de lignes deux à deux de même longueur, alors les surfaces auront la même aire.

MemeAire

Ces deux triangles sont formés d'un empilement de segments, deux à deux de même longueur. Les deux triangles ont donc la même aire.
Ceci permet de montrer que n'importe quel triangle est équivalent à un triangle rectangle, et donc, d'aire ½ b×h.

Avec cette méthode, pour montrer que deux surfaces ont la même aire, il suffit de montrer que les segments transversaux ont deux à deux la même longueur. La méthode fonctionne également pour le calcul de volumes, comme empilement d'un nombre indéfini de plans.

Ces lignes, on les appelle les "indivisibles". Le gros soucis, c'est que l'on ne comprend pas vraiment leur nature : ce ne sont pas des segments, ce ne sont pas des rectangles, c'est probablement quelque chose entre les deux.

Quadrature de la cycloïde
Le premier morceau de bravoure de cette théorie naissante a été celui de la quadrature de la cycloïde
, la courbe qui correspond à la trajectoire d'un point sur le bord d'un disque qui roule :

Cycloid_f

Fait particulièrement intéressant : l'aire située sous cette courbe correspond à trois fois l'aire du disque qui l'a générée. Ça, c'est Galilée qui l'a découvert, après avoir construit et pesé des cycloïdes en métal. Il a cependant refusé de croire que ce résultat était correct, et a conclu à une erreur de mesure (1599). Le premier calcul de cette aire est dû à Roberval, grâce à la méthode de Cavalieri (qui était un étudiant de Galilée).

Pour cela, nous avons besoin :
- du cercle générateur, en vert, d'aire Adisqueπ
- de la cycloïde, en bleue
- de sa courbe "compagnon", en rouge, définie à partir du cercle générateur de la façon suivante : pour un point A du cercle, on construit le point M à la même hauteur de A, et dont l'abscisse 0N est égale à la longueur de l'arc de cercle 0A.

Cycloide1

Disque générateur en vert (de rayon r, donc de circonférence 2πr)
Cycloïde en bleu. Après déplacement du disque, le point 0 se retrouve en position 0'.
Courbe compagnon en rouge. Par construction, la longueur 0N est égale à la longueur de l'arc violet 0A.

On peut alors montrer que :
- les portions situées entre la cycloïde et sa courbe compagnon ont chacun l'aire d'un demi disque.
- l'aire sous la courbe compagnon est égale au double de celle du disque.
Finalement, l'aire sous la cycloïde est égale à l'aire de trois disques.

* Aentre les courbes = ½ Adisque
On utilise ici la méthode de Cavalieri. Les segments du demi-disque sont de même longueur que ceux de l'entre-deux courbes, les aires sont donc égales.

 

AHegaleEMLes segments à hauteur égale sont de même longueur. D'après la méthode de Cavalieri, les deux aires hachurées sont égales.

Sur le schéma ci-dessus, on prend un point A sur le cercle C, et on considère les points H, E et M à hauteur de A sur, respectivement, le diamètre vertical du cercle C, sur la cycloïde et sur la courbe compagnon. Il s'agit de montrer que AH = EM. Pour cela, on considère le point L, intersection du cercle C et de EM (lui aussi, à hauteur de A). Lorsqu'on fait tourner le cercle C pour qu'il aille en position C', puisque les arcs 0L=0A=0N, L est envoyé sur N, et donc, 0 est envoyé sur E (car 0L=EN). Donc le point E appartient au cercle C'. Le cercle C' peut alors être vu comme le translaté de C, de même pour les segments AH et EM : ils sont donc identiques.

* Acompagnon = 2 Adisque
On se place dans le rectangle (0,0),(πr,0),(πr,2r),(0,2r), d'aire b×h = πr×2r = 2πr².

BallonDeRugbyLa courbe compagnon est symétrique !

Il suffit alors de remarquer que la courbe compagnon est symétrique par rapport au centre de ce rectangle (pour s'en convaincre, on peut tracer une deuxième cycloïde), elle le coupe donc en deux parts égales. Donc l'aire sous cette demie courbe compagnon est πr², qui est l'aire du disque.

Bref : l'aire de la cycloïde, c'est trois fois l'aire du disque. Yeah !

 

Quadrature du cercle
La méthode de Cavalieri fonctionne aussi lorsque les lignes ne sont pas des segments. Il faut évidemment prendre encore plus de pincettes, mais cela donne une méthode assez intuitive permettant de calculer l'aire du disque.

Aire_disquePour calculer l'aire d'un cercle de rayon r, on considère tous les cercles concentriques de rayons k ≤ r. Chacun de ces cercles a une circonférence égale à 2πk. On redresse alors tous ces cercles : on obtient un triangle isocèle de base b = 2πr (la circonférence du disque initial), et de hauteur h = r (le rayon du disque initial).

L'aire de ce triangle est alors de b × h ÷ 2 = 2πr × r ÷ 2 = πr². Yeah !

La quadrature ratée du triangle
Parlons tout de même de ce qui fâche : la méthode de Cavalieri ne fonctionne pas dans tous les cas. Ce n'est pas parce que les lignes sont deux à deux de même longueur que les aires seront égales. On sent bien, sur l'exemple ci-dessous, qu'il y a "plus" de lignes dans le premier triangle que dans le deuxième...

Paradoxe_CavalieriLes deux segments oranges sont de même longueur, les deux rectangles devraient avoir la même aire...

Quadrature du rouleau de PQ
En s'inspirant du calcul de l'aire du disque par la méthode de Cavalieri, on peut en déduire une excellente méthode permettant de calculer le nombre de feuilles de papier toilette dans un rouleau. La principale différence d'avec la méthode de Cavalieri, c'est que les feuilles de papier toilette ne sont pas infiniment fine (et heureusement).

Quadrature_du_PQ

Il suffit finalement de se rendre compte que, en redressant chacune des feuilles du rouleau, on obtient un paquet de feuilles, rectangulaire. En notant R (resp. r) le rayon du rouleau plein (resp. vide), l'aire latérale du rouleau est π(R²-r²). En notant L la longueur d'une feuille, N le nombre de feuilles dans un rouleau et e son épaisseur, on trouve que l'aire du paquet est LNe.

D'après Cavalieri, les deux aires sont égales, donc le nombre N de feuilles dans un rouleau de papier toilette est donné par...

Nb_Feuilles_PQ

Ce qui, pour R = 4.5 cm, r = 2 cm, L = 12.5 cm et e = 0.015 cm, nous donne environ 270 feuilles. Yeah !


Sources :
Cycloids and Paths : Tout sur la cycloïde
Méthode des indivisibles, sur Wikipedia

Images :
Cycloid

Posté par El Jj à 10:00 - Commentaires [11]
Tags : , ,


07 octobre 2013

[#] De l'humour mathématique

Une nouvelle chaîne, initiée par Eric de Rock 'n' science vient de voir le jour sur le c@fé des sciences : blague à caractère scientifique. L'objectif est de mettre en avant ce que la science a fait de meilleur en terme de vannes vaseuses et jeux de mots approximatifs. Je ne pouvais pas passer à côté de cette occasion pour poster mes blagues mathématiques préférées. Celle que j'ai choisi de mettre en valeur, je l'ai découverte il y a quelques mois, et, chose rare, je l'ai retenue ! 

matrix_transform

The best joke ever
Je préfère prévenir : le public succeptible de comprendre cette blague est très restreint. Du coup, je ne suis plus à un snobisme près, et je vais faire l'affront de la publier en anglais... La voici :

A comathematician is a device for turning cotheorems into ffee.

Ce qui, en français, donne :

Un comathématicien est une machine à transformer les cothéorèmes en fé.

(Du coup, on perd le jeu de mot...) 

La meilleur blague jamais : explication
Ce bon mot fait en fait référence à une citation du mathématicien honrois Alfréd Rényi (et non, comme on le voit souvent, de Paul Erdõs, avec qui il a cosigné de nombreux papiers) :

Un mathématicien est une machine à transformer le café en théorèmes.

Autrement dit, un mathématicien n'a besoin que de café pour produire des théorèmes. La citation contiendrait également un jeu de mot en allemand, sans doute volontaire de la part de Rényi : "Satz" signifie à la fois "théorème" ("Lehrsatz") et "marc de café" ("Kaffeesatz").

En anglais, "café" se traduit par "coffee", qui contient le préfixe co- si cher aux mathématicien (cosinus, cotangente...). Ce préfixe intervient surtout quand on parle d'homologie, une technique intervenant dans divers domaines (algèbre, topologie...) et dans lequel on étudie le comportement d'une opération entre des espaces de dimensions décroissantes (l'homologie) ou croissantes (la cohomologie). Généralement, quand il existe une homologie dans un sens, on a une cohomologie dans l'autre sens (son dual). Finesse de vocabulaire des matheux : pour passer de l'homologie à la cohomologie, il suffit généralement d'ajouter ou d'enlever le préfixe co-. 

Avec le vocabulaire de l'homologie, la citation de Rényi devient :

Mathematician : coffee → theorems

Quand on passe en cohomologie, on change de sens et on enlève/ajoute co-, ce qui donne la blague en question :

Comathematician : cotheorems → ffee.

CQFE (ce qu'il fallait expliquer)

Degré d'une blague mathématique
On peut définir récursivement le degré d'une blague mathématique de la façon suivante :

  • Une blague est de degré 0 lorsqu'elle n'a rien de mathématique.
  • Une blague est de degré n+1 lorsqu'elle peut être obtenu à partir d'une blague de degré n en lui ajoutant une notion mathématique.

Quelques exemples :

  • "Qu'est ce qu'un canif ? Un p'tit fien" est une blague de degré 0, puisque, même en cherchant bien, il n'y a rien de mathématique là-dedans.
  • "Quelle est l'anagramme de Banach-Tarski ? Banach-Tarski Banach-Tarski" est une blague de degré 1, puisqu'elle fait référence au théorème de Banach-Tarski, qui démontre que l'on peut découper et réassembler un objet de manière à former deux copies identiques de cet objet.
  • "Il existe 10 sortes de personnes : celles qui connaissent le ternaire, celles qui ne le connaissent pas et celles qui pensent que c'est du binaire" est de degré 2, puisqu'elle s'appuie sur la blague suivante, de degré 1 : "Il existe 10 sortes de personnes : celles qui connaissent le binaire et les autres".
    Notons que cette blague peut servir à construire une blague de degré arbitrairement long, en considérant d'autres bases de numérations - une blague de degré 42 ressemble à "Il existe 10 sortes de personnes, celles qui connaissent la base 41, celles qui ne le connaissant pas, celles qui pensent que c'est de la base 40, celles qui pensent que c'est de la base 39, ..., celles qui pensent que c'est du binaire". Les blagues en question perdent cependant très vite de leur force comique.

La blague du comathématicien est à mon sens le seul exemple vraiment valable de blague de degré 3. En effet, elle s'appuie sur la citation de Rényi, qui est de degré 2 (puisqu'elle mêle réflexion sur le métier de mathématicien et jeu de mot hilarant en allemand).

Le papier introduisant cette notion de degré d'une blague (Pourquoi est-il si diffcile de calculer le degré d’une blague mathématique ?) donne un autre exemple de blague de degré 3, mais je dois admettre qu'elle ne m'a pas vraiment convaincu.

Pour terminer, une autre bonne blague à raconter demain matin à la machine à café :

Trois logiciens entrent dans un bar. Le barman leur demande : "un café pour chacun ?"
Le premier logicien répond : "Je ne sais pas".
Le deuxième répond alors : "Je ne sais pas".
Le dernier conclut : "Oui".

(Et j'attends vos meilleures blagues dans les commentaires. Attention : toute blague à base de jeu de mot sur l'intégration ou la dérivation de fonctions exponentielles, logarithme ou trigonométriques est prohibée.)


Sources :
Dimitri Karpov, Minos Libbouet, Roland Triedich, Pourquoi est-il si difficile de calculer le degré d’une blague mathématique ?,
Bruno Winckler, Recueil de blagues mathematiques : Plus de 100 pages d'humour mathématique, à lire absolument !
Image :
Xkcd, Matrix Transform

Posté par El Jj à 21:00 - Commentaires [30]
Tags :

22 septembre 2013

[#] Cliquez plus pour gagner plus (de cookies)

Alors que les grands médias se gargarisent des coûts de production et de la violence du dernier GTA, c'est un tout autre jeu qui affole la toile de l'Internet : le génial Cookie Clicker. Créé en quelques heures (!), pour rigoler (!!), par Orteil, (le créateur d'excellents chronophages dont la moitié ont disparu de la surface d'internet [mais le BFGFT survivra !]), ce jeu en javascript (!!!) a connu un succès incroyable, à tel point qu'une société japonaises va commercialiser des figurines de la mamie du jeu !

En fait, Orteil était un voisin de blog quand j'ai débuté le blogging il y a presque 10 ans. Je dois être honnête : c'est terriblement émouvant de voir que, du jour au lendemain, un membre de sa famille numérique a le droit à des félicitations de Notch ou à des reprises japonaises !

CookieClickerArtworkNon, les jeux vidéo ne rendent pas violent, mais ils peuvent donner envie de manger des cookies.

Cookie clicker ?
Le concept de Cookie Clicker est très simple : on clique sur un cookie pour gagner des cookies. Quand on a assez de cookies, on peut les échanger contre des curseurs supplémentaires, des mamies ou des bâtiments divers (fermes à cookies, usines à cookies, laboratoires d'alchimie pour transformer l'or en cookies, portail vers le cookieverse...) pour gagner encore plus de cookies. Cookie sur le gâteau : le jeu est bourré de références à la culture geek sous toutes ses formes. L'objectif du jeu, c'est de gagner des cookies, plein de cookies, trop de cookies !

Commeil n'y a pas d'objectif précis, le mien sera le suivant : posséder un million de cookies !

Les différents "bâtiments" sont les suivants :

  • Le curseur, coûte 15 cookies, rapporte 0.1 cookie par secondes (c/s).
  • La mamie, coûte 100 cookies, rapporte 0.5 c/s..
  • La ferme, coûte 500 cookies, rapporte 2 c/s.
  • L'usine, coûte 3 000 cookies, rapporte 10 c/s.
  • Le vaisseau spatial, coûte 40 000 cookies, rapporte 100 c/s.
  • Le laboratoire d'alchimie, coûte 200 000 cookies, rapporte 400 c/s.
  • Le portail interdimensionnel, coûte 1 666 666 cookies, rapporte 6 666 c/s.
  • La machine à remonter le temps, coûte 123 456 789 cookies, rapporte 98 765 c/s.
  • Le condensateur d'antimatière, coûte 3 999 999 999 cookies, rapporte 999 999 c/s.

Cliquer sur le cookie rapporte un cookie par clic. Avec une cadence raisonnable, on peut estimer qu'ils rapportent 6 cookies par seconde.

Le prix indiqué est le prix du premier bâtiment de chaque type. Après chaque achat, le prix d'un bâtiment supplémentaire est augmenté de 15 %. Ainsi, le premier curseur coûte 15 cookies, le deuxième 17 cookies, le troisième 20 cookies, le n-ième coûte 15×1.15n-1  cookies. Le 200e curseur - qui permet de débloquer un achievement - coûte donc environ 18 000 000 000 000 cookies (suite géométrique powaaa) ! Le nombre de cookies dépensés lors de l'achat du n-ième curseur est alors de 100×(1.15n-1). Fait intéressant : les 5 derniers achats représentent la moitié des cookies dépensés au total.

100 curseursNombre de cookies nécéssaires à l'obtention de 100 curseurs.

Il est aussi possible, pour des sommes astronomiques, d'acheter des upgrades qui permettent d'améliorer de manière dérisoire la productivité de chaque bâtiment. Oublions-les pour le moment.

Je veux une mamie !
Une mamie coûte 100 cookies, un curseur rapporte 0.1 c/s.

  • Avec 1 curseur, il faut donc 1000 secondes pour obtenir la mamie.
  • Avec 2 curseurs, il faut 500 secondes pour obtenir la mamie, auxquelles s'ajoutent les 170 secondes nécessaire à l'obtention du deuxième curseur. Il faut donc 670 secondes pour obtenir la mamie.
  • Avec 3 curseurs, il faut 334 secondes pour obtenir la mamie, mais il faut ajouter 170 secondes pour le 2e curseur, et 100 secondes pour le 3e curseur. Il faut donc 604 secondes.
  • Avec 4 curseurs, il faut 597 secondes ;
  • Avec 5 curseurs, il faut 611 secondes.

Autrement dit, le moyen le plus rapide d'obtenir une mamie (sans cliquer sur le cookie) est de préalablement acheter 4 curseurs. Si on s'autorise à cliquer le cookie, 17 secondes suffiront (mais les warriors n'utilisent pas ces artifices !).

Je veux une ferme !
Une ferme coûte 500 cookies ! Avec 4 curseurs et une mamie, LA production est donc de 0.9 c/s.

  • Si je me contente d'une seule mamie et de 4 curseurs, il faudra 556 secondes.
  • Avec 2 mamies et 4 curseurs (1.4 c/s), la ferme demande 357 secondes. La mamie supplémentaire, qui coûte 115 cookies, réclame 128 secondes. Bilan : il faut 485 secondes.
  • Avec 2 mamies et 5 curseurs (1.5 c/s), la ferme demande 333 secondes, auxquelles s'ajoutent le 5e curseur (26 c à 0.9 c/s : 29 s) et la 2e mamie (115 c à 1 c/s : 115 s). Bilan : 477 secondes.
  • Avec 2 mamies et 6 curseurs (1.6 c/s), la ferme demande 313 secondes. On ajoute le 5e curseur (26 c à 0.9c/s : 29 s), le 6e curseur (30 c à 1 c/s : 30s) et la 2e mamie (115c à 1.1 c/s : 105 s). Bilan : 476 secondes (en comptant les arrondis).
  • Avec 2 mamies et 7 curseurs, la ferme demande 481 secondes.

On peut vérifier que, quelle que soit la façon dont on s'y prend, la ferme demandera plus de temps si on achète préalablement une mamie supplémentaire.

Bref, il faut acheter dans l'ordre :
Curseur × 4, mamie, curseur × 2, mamie puis ferme (ce qui demande au total 1072 secondes).

Le hic, c'est que l'on peut faire mieux, en attendant un peu avant d'acheter sa première mamie... La séquence curseur × 5 , mamie, curseur, mamie, ferme ne demande que 1059 secondes !

C'est contre-intuitif : pour gagner plus, il peut être nécéssaire d'attendre un peu avant de faire son premier gros achat... Suivant l'objectif à long terme que l'on cherche, les stratégies sur le court terme sont différentes.

Je veux un millions de cookies !
Quel est donc le temps minimal pour obtenir un millions de cookies ? Le raisonnement s'arrête ici, je laisse ma place au calcul à la pelleteuse.

En cherchant parmi toutes les stratégies de la forme "acheter des curseurs, puis des mamies, puis des fermes,  etc.", la méthode la plus rapide est la suivante : acheter 6 curseurs, 6 mamies , 6 fermes, 7 usines, 6 vaisseaux et 2 laboratoires. Il faudra alors 4920 secondes, pour une production finale de 1485.6 cookies (soit 1 h et 22 minutes, dont 11 minutes à attendre après le dernier achat). 

En ajoutant ici et là d'autres achats de curseurs, de mamies ou de ferme, on peut diminuer le temps total, mais il me semble inenvisageable de faire mieux que 1h21 sans utiliser d'upgrades, sans manger de cookie doré et sans cliquer comme un taré sur ce cookie. A en croire Youtube, le record actuel est de 6 minutes 39 (mais tout le monde s'accorde pour dire que les cookies dorés, c'est de la triche).

Pour résumer les choses :

  • Suivant l'objectif à long terme que l'on se donne, les objectifs à court terme ne seront pas les mêmes.
  • Trouver la bonne stratégie à long terme demande beaucoup trop de temps de calcul, autrement dit, du temps que l'on perd à ne pas cliquer sur le cookie.
  • Orteil est un génie.

Posté par El Jj à 10:00 - Commentaires [4]
Tags : ,

15 septembre 2013

[#] Faut-il appliquer la théorie des jeux combinatoire pour le jeu du chou-fleur ?

Il y a des questions qui empêchent de dormir (qui suis-je ? où vais-je ? est-ce la fin de la crise ? va-t-elle me rappeller ?), et il y a des questions qui empêchent vraiment de dormir. La question que je pose aujourd'hui fait partie de cette deuxième catégorie, puisque c'est pendant une insomnie qu'elle m'est apparue : peut-on appliquer la théorie des jeux combinatoires pour le jeu du chou-fleur ? Mon état de semi-sommeil m'a alors apporté une réponse inattendue : "oui, et ça ferait un bon article WTF sur le blog, en en attendant un vrai !".

Bref : quelle stratégie adopter pour gagner au jeu du chou-fleur ?

320px-Romanesco_Broccoli_detail_-_(1)Je n'ai pas trouvé d'illustration du jeu du chou-fleur, alors à la place, j'ai mis une jolie photo d'un chou romanesco.

Le jeu du chou-fleur
Pour ceux qui n'ont jamais mis les pieds dans une cour de récréation, il faut savoir que le jeu du chou-fleur est un jeu où deux joueurs avancent tour à tour de la distance exacte d’un pied, le premier en disant "chou" et le suivant "fleur", et ainsi de suite. Le premier à écraser le pied de l’autre a gagné.

Dans ce jeu, seule la distance initiale entre les pieds des deux joueurs déterminera le gagnant du duel. Pour espérer gagner, c'est la distance de départ qu'il faudra négocier au mieux.

Notons d la distance de départ,  lC la longueur des chaussures de Chou (le premier joueur à faire un pas), et lF celle de Fleur.

  • Si d ∈ [0 ; lC[, Chou gagnera en un pas.
  • Si d ∈ [lC ; lC + lF[, Fleur gagnera lors de son premier pas.
  • Si d ∈ [l+ lF ; 2 lC + lF[, Chou gagnera lors de son deuxième pas.

Et ainsi de suite :

  • Si d ∈ [k(l+ lF) ; k(l+ lF) +  lC [, Chou gagnera lors de son (k+1)-ième pas
  • Si d ∈ [k(l+ lF) +  lC ; (k+1)(l+ lF) [, Fleur gagnera lors de son (k+1)-ième pas

Moralité : pour que Chou gagne, il faut que la distance soit dans un intervalle de type [k(lC+lF) ; k(lC+lF) + lC [. Un tel intervalle est de longueur lC. Autrement dit, si la distance est choisie au hasard, celui qui chausse du 42 aura l'avantage sur celui qui chausse du 35.

Ah, ça valait le coup de se creuser la tête pour avoir cette réponse...

Le jeu du chou-pomme
Le jeu du chou-fleur est très bien en l'état, mais souffre d'un gros défaut, à l'image d'une bataille ou d'un Mario Kart Wii : il n'y a pas de stratégie pour gagner, c'est que de la chance.

C'est pourquoi il a fallu inventer une variante : le jeu du chou-pomme. Deux règles s'ajoutent :

  • Les grand "chou" (et les grand "pomme") sont autorisées : la longueur d'un pas peut être aussi grande que possible. Il y a donc deux type de pas, les "chou" et les grand "chou" (et leur équivalent pour Pomme).
  • Interdiction de gagner avec un grand "chou" (ou un grand "pomme") : on ne peut écraser le pied adverse qu'avec un pas de distance minimale.

Là, le jeu devient intéressant, puisqu'il entre dans la catégorie des jeux impartiaux, comme le jeu des bâtonnets de Fort Boyard, le jeu de Nim, le Sprouts, le Chomp ou le quart de singe (on admettra que les joueurs ont des chaussures et des jambes de tailles équivalentes).

Ce qui est intéressant avec un jeu impartial, c'est qu'il existe toujours une stratégie de victoire pour l'un des deux joueurs. Pour trouver cette stratégie, il faut trouver quelles sont les situations gagnantes et les situations perdantes. 

Prenons par exemple le jeu des bâtonnets de Fort Boyard. Vingt bâtonnets sont présentés, chaque joueur prend à son tour 1, 2 ou 3 bâtonnets. Le joueur qui prend le dernier bâtonnet perd. 

  • Si, à mon tour de jeu, il reste 2, 3 ou 4 bâtonnets, j'ai gagné : il me suffit de ne laisser qu'un bâtonnet.
  • Si, à mon tour de jeu, il reste 6, 7 ou 8 bâtonnet, j'ai gagné : il me suffit de ne laisser que 5 bâtonnets. Puisque mon adversaire devra en laisser 2, 3 ou 4, cela revient à la situation précédente.
  • Et ainsi de suite : je gagne si il reste 10, 11, 12 ou 14, 15, 16 ou 18, 19, 20 bâtonnets... Puisqu'il y a 20 bâtonnets au début, je suis sûr de gagner... si je commence à jouer ! Pour ce jeu, les situations gagnantes sont celles où il reste 4n+2, 4n+3 ou 4n+4 bâtonnets.

Dans le cas du chou-pomme, on peut chercher les situations gagnantes de la même façon. Notons l la longueur d'un pas (on supposera que l = l= lF/P), et L la longueur maximale d'un grand pas (que l'on supposera strictement inférieure à 2J, J désignant la longueur d'une jambe (Cette remarque n'a aucune incidence sur la suite)). Chou fera le premier pas.

  • Si d ∈ IFinal = [0 ; l[, Chou gagnera lors de son premier pas.
  • Si d ∈ IP0 = [l ; 2l[, Pomme gagnera lors de son premier pas, puisque Chou ne peut pas gagner sur un grand "chou".
  • Si d ∈ IG0 = [2l ; 2l + L[, Chou gagnera : il lui suffit de faire un grand "chou" de façon à ce que la distance restante soit dans l'intervalle IP0.
  • Si d ∈ IP1 = [2l + L ; 2l + L + l[, Pomme dispose d'une stratégie gagnante. Quelle que soit la longueur du pas de Chou, la distance restera sera dans IG0, qui est une situation gagnante pour celui qui s'y trouve.

Il y a donc les situations gagnantes, de la forme IGk = [k(L+l) + 2l ; k(L+l) + 2l + L[. Le joueur qui s'y trouve peut toujours ramener son adversaire dans une situation perdante de la forme IPk = [k(L+l)+l ; k(L+l) + 2l[.
A nouveau, si la distance initiale est choisie au hasard, elle laisse un très net avantage à Chou !

Chou vs Pomme

Cas où L = 6l. Le bleu représente les position dans lequel il existe une stratégie gagnante, qui consiste à faire un pas pour revenir dans le rouge.
Ici, la distance initiale est d'environ 20 pas : Chou dispose d'une stratégie gagnate !

Il reste à envisager le cas où les deux joueurs n'ont pas des chaussures ni des jambes de la même longueur, mais je crois que j'ai encore du sommeil en retard... 


Images :
Romanesco broccoli detail

Posté par El Jj à 10:00 - Commentaires [1]
Tags : , , ,

08 septembre 2013

[#] Les mathématiques de Futurama [rediffusion]

futurama_bender
[6ACV10 - Le Prisonnier de Benda]

La saison 7 de Futurama, petite sœur des Simpsons créée par Matt Groening et développée par David X. Cohen, vient de se terminer - pour la troisième fois. En nous laissant sur le mariage de Fry et Leela sur fond de voyage dans le temps, Futurama aura marqué les esprits -en tout cas, le mien. La science est un sujet très présent chez les Simpsons, mais c'est encore pire dans Futurama, où les clins d’œil à la physique, à l'informatique ou aux mathématiques sont légions, sans parler des références à la culture pop  ! Il faut dire que, outre David X. Cohen, diplômé en physique de Harvard et en informatique de Berkeley, la série compte dans ses scénaristes Ken Keeler, diplômé en mathématiques appliquées de Harvard et Jeff Westbrook, diplômé en informatique à Princeton...

La série, diffusée de 1999 à 2003 sur la Fox, et entre 2008 et 2013 sur Comedy Central, narre les aventures de Fry, un livreur de pizza très moyen de la fin du XXe siècle, propulsé par erreur en l'an 2999...

 futurama_ref_sciences
Quelques clins d’œils à la physique [2ACV10 - Le clone de Farnsworth], à l'informatique [1ACV03 - Le colocataire] ou à l'électronique [6ACV04 - Proposition infinity]. La géologie [1ACV09 - L'enfer, c'est les autres robots] semble un peu moins appréciée...

Et comme ce blog traite de mathématique, je me suis donné une mission : débusquer toutes les références mathématiques dans Futurama. Et pour une série mainstream, elles sont nombreuses. Très nombreuses !

Nombres taxicab
Quand un nombre apparaît dans Futurama, c'est rarement un nombre choisi par hasard. Le nombre 1729, notamment, apparaît à de très nombreuses reprises :

 futurama_1729
- Bender serait le 1729e robot de M'man [2ACV04 - Conte de Noël]
- Lors d'un épisode, l'équipe visite de nombreux univers parallèles, dont le n°1729 [4ACV15 - Le bon, la boîte et l'ahuri]
- Le Nimbus, vaisseau commandé par Zapp Brannigan, a pour numéro BP-1729 [5ACV05 - Le Monstre au milliard de tentacules]

Ce nombre est très célèbre pour être un nombre taxicab : un nombre qui peut être exprimé comme la somme de deux cubes, de plusieurs façons différentes (en l’occurrence, 2). En effet,

1729 = 13 + 123 = 93 + 103

Ces nombres sont surtout connus pour faire l'objet d'une anecdote impliquant Hardy et Ramanujan. Alors que le premier rendait visite au deuxième, malade, il lui annonça que le numéro de son taxi, 1729, était plutôt ennuyeux, et qu'il espérait que ce n'était pas un mauvais présage. Ramanujan lui dit que non, c'est un nombre tout à fait intéressant : il est exprimable comme la somme de deux cubes de deux façons distinctes !

Et à propos, le 3ème nombre Taxicab (exprimable comme somme de deux cubes de trois façons différentes) est 87539319 :

87539319 = 1673 + 4363 = 2283 + 4233 = 2553 + 4143

futurama_87539etc
Qui, comme par hasard, apparaît -en petit- sur un taxi... [5ACV01 - La grande aventure de Bender]

Il ne faut pas oublier que les numéros de série de Bender et de Flexo (les deux robots tordeurs) sont respectivement 3370318 (=1193 + 1193) et 2716057 (=9523 + (−951)3), tous deux exprimables comme la somme de deux cubes. (Le genre de coïncidence qui font bien rire les deux robots lors de leur première rencontre). [2ACV06 - Le moins pire des deux]

Aucun rapport : à la Central Bureaucracy, il existe une salle appelée Cubicle Room 729. On remarque tout de suite que 729 n'est autre que 93, et pour cause, la salle consiste en un cube 9x9x9 de bureaux en open-space.

futurama_729
[6ACV06 - Inspection mortelle]

Nombres parfaits
Dans le registre des nombres qui ne sont pas là par hasard, il y a 6421.12 :

futurama_dial-a-joke
La facture de téléphone de Fry [5ACV05 - Le Monstre au milliard de tentacules]

Si on fait le calcul, on s'aperçoit que Fry a appelé Dial-a-joke... 8128 fois ! (Soit 254 pages, avec 32 entrées par pages). Un nombre pas du tout aléatoire, puisque c'est un nombre parfait, un nombre égal à la somme de ses diviseurs propres. On note au passage que 8128=254*32 est sa factorisation par un nombre premier de Mersenne. Rien n'est là par hasard.

En parlant de nombres de Mersenne, l'un des robots de la planète Chapek 9, la planète des robots, a pour nom Mr 147573952589676412927 [7ACV09 - Free Will Hunting]. Ce nombre est M67 = 267-1, un nombre de Mersenne non premier. Ce nombre fait référence à une anecdote autour du mathématicien Frank Cole ; en 1903, il propose à l'American Mathematical Society une conférence inédite intitulée "On Factoring Large Numbers", dans laquelle, pendant plus d'une heure, il a conciencieusement et silencieusement calculé que 193 707 721 × 761 838 257 287 = 147 573 952 589 676 412 927

Irrationnels
A en croire la série, plus personne dans le futur n'aura de problèmes avec les nombres irrationnels...

futurama_racine
- √2 News, le rendez-vous information de Linda et Morbo de la chaîne √2 [1ACV08 - Un gros tas d'ordures]
- La célèbre route √66 (en anglais, "square root of 66") parodiant la Route 66 américaine.  [3ACV02 - Parasites perdus]
- La station de police de la √15e avenue [4ACV04 - Astéroïque]
- Les dés de Mars Vegas (qui n'ont rien d'irrationnels, seulement le plaisir de mettre des radicaux) [5ACV13 - Vous prendrez bien un dernier vert ?]

futurama-pi
- De l'huile π-en-1 [3ACV11 - Vol au-dessus d'un nid de robot]
- La πième avenue, qui arrive après la 2e et la 3e [3ACV21 - Les actions du futur]
- Le carton d'un supercollider de la marque πkéa [4ACV04 - Astéroïque]
-
π pour le prix de i, au milieu d'une dizaine d'autres spams sur l'écran d'Amy [5ACV01 - La grande aventure de Bender], unique référence au nombre imaginaire i. 

vlcsnap-2013-09-04-21h40m20s85Le bâtiment des des Rational Archives parodient celui des National Archives, à Washington. L'affiche célèbre le 22 juillet, journée de π approximatif (puisque 22/7 ≃ π)  [7ACV16 - T.: The Terrestrial]

Et pour finir avec les références aux constantes mathématiques classique, le nombre e. Le vaisseau de Planet Express passe au travers de séquences de chiffres semblant aléatoires. Il s'agit en fait des décimales de e. Si si !

futurama_e
[5ACV09 - Prenez garde au seigneur des robots !]

Infinis
L'infini mathématique est aussi source d'inspiration. Sous sa forme analytique, la proposition ∞ parodie la proposition 8 californienne du 2 mars 2008 interdisant le mariage homosexuel.

futurama_infinity
[6ACV04 - Mariages interdits]

Mais surtout, l'infini apparaît dans le nom du cinéma de New New York : le Loew's ℵ0-Plex. A en croire le nom, c'est un multiplexe qui aurait un nombre infini dénombrable de salles (ℵ0 désignant - à peu de choses près - le nombre d'élément de l'ensemble infini des nombres entiers naturels ℕ). Un gag coupé au montage fait dire à Bender que même avec un nombre dénombrable de salles, le ℵ0-Plex n'est pas assez grand pour diffuser tous les films Rocky ayant été tournés.

futurama_aleph0
[2ACV08 - Raging Bender]

Une autre idée de l'infini apparait dans la dernière saison, lorsque Bender marche dans les rues de Chapek 9, la planète natale des robots : la (n+1)e rue parodie les rues numérotées de New York.

La (n+1)e rue[7ACV09 - Free Will Hunting]

Solides de Platon
Un des quatre épisode de la saison 4 met en scène la terrible M'man à la recherche de l'anticristal de matière noir, elle-même possédant déjà son cristal. A l'écran, le cristal (rouge) est en forme d'icosaèdre, et l'anticristal (noir) a celle d'un dodécaèdre, qui sont deux solides de Platon (un polyèdre dont toutes les faces sont un même polygone régulier). Mathématiquement, l'icosaèdre et le dodécaèdre sont duaux : on obtient l'autre en reliant le milieu des faces de l'un.

Dans ce même épisode, une scène montre les 3 autres polyèdres de Platon : le cube, le tétraèdre et l'octaèdre.

polyèdres
[5ACV09 - Prenez garde au seigneur des robots !]

Il faut aussi parler de Madison Cube Garden, parodie du Madison Square Garden, un lieu récurrent de la série dans lequel se déroule les concerts ou les matchs de Blernsball. Sans surprise, il a la forme... d'un cube ! Notons au passage qu'il a été dessiné de façon à ce que la base du plafond de verre ait la forme d'un hexagone régulier.

futurama_cube
[4ACV04 - Astéroïque]

Topologie
L'image scientifique la plus emblématique de la série reste la suivante :

futurama_klein_beer
[3ACV12 - Le mal absolu]

Côte à côte, on peut voir de la liqueur de malt Olde Fortran (bière pour robot, en référence au langage de programmation Fortran), de la bière St Pauli Exclusion Principle Girl (référence croisée entre la bière St Pauli Girl et le principe d'exclusion de Pauli, en physique quantique) et surtout, de la bière de Klein, vendue dans des bouteilles de Klein (une surface mathématique ayant la particularité topologique de n'avoir ni intérieur, ni extérieur).

Dans la rubrique topologie, on peut aussi parler de l'épreuve de tordage des jeux olympiques, où un robot tord une poutre intordable en forme de nœud de trèfle (le nœud - au sens mathématique - le plus simple après le nœud trivial)

futurama_noeud_de_trefle
[4ACV13 - L'homme est une femme formidable]

Dans l'épisode  2-D Blacktop de la septième saison, la série se permet un très grand nombre de blagues autour de la topologie. Tout commence lorsque Farnsworth booste son vaisseau avec un collecteur d'admission 4D (Jeu de mot intraduisible : "collecteur d'admission" se traduit par "intake manifold", manifold étant le nom anglais d'une variété topologique), qui ne serait que l'aile d'un hyperpoulet. Visuellement, c'est un tesseract, la version 4D d'un cube. Le vaisseau est alors capable de faire un Dimensional drift, un dérapage qui passe par la 4eme dimension.

 Jeu de mot pour les amateurs de tuning et de topologie...
[7ACV15 : 2-D Blacktop]

A bord de ce vaisseau, Farnsworth affronte Leela à la course sur un dragstrip de Möbius (en anglais, Möbius dragstrip, jeu de mot entre dragstrip, une piste droite pour les courses de dragster, et Möbius strip), une piste en ligne droite en forme de ruban de Möbius. Le but est de faire deux tours de piste (ce qui, sur un ruban de Mobius, ne correspond en fait qu'à un seul tour).

vlcsnap-2013-09-04-18h17m04s99
[7ACV15 : 2-D Blacktop]

Suite à un accident du Dimensional drift, l'équipe se retrouve plongé dans Flatbush, un monde à deux dimensions. Les personnages rencontrent les Seigneurs de Flatbush, des créatures incapables d'imaginer un monde à 3 dimensions. La série parodie ici Flatland, un monde à deux dimensions de Edwin Abbott Abbott.

vlcsnap-2013-09-04-18h18m46s120Le château des Seigneurs de Flatbush
[7ACV15 : 2-D 
Blacktop]

Lorsqu'ils s'échappent de ce monde à deux dimensions pour retourner dans celui à 3 dimensions, le vaisseau passe par des dimensions intermédiaires (2.1, 2.2, 2.314...), la dimensions que l'on accorde aux fractales. Graphiquement, le vaisseau traverse des fractales dont la dimension est strictement comprise entre 2 et 3.

vlcsnap-2013-09-04-18h12m08s0[7ACV15 : 2-D Blacktop]

Grands théorèmes
On ne peut pas y échapper : la conjecture de Goldbach, l'hypothèse de Riemann ou la conjecture P=NP sont en l'an 3000 devenus de vrais théorèmes...

futurama_goldbach
[5ACV05 - Le Monstre au milliard de tentacules]

Une fois au paradis, Farnsworth et Wernstrom parviennent à démontrer la conjecture de Goldbach (qui dit que tout entier pair peut s'écrire sous la forme de la somme de deux nombres premiers). En détails, on peut lire sur le tableau :

  • GOLDBACH QUODLIBET (écrit en langage alien, signifiant littéralement en latin "n'importe quoi")
  • n2+m < p1+p2 < (n+1)2+2m (une inégalité que l'on peut imaginer faire partie de la démonstration de Goldbach faisant intervenir la conjecture de Legendre (entre deux carrés, on trouve un nombre premier - à ce jour non démontrée) et le postulat de Bertrand (entre un entier et son double, on trouve un nombre premier))
  • 3+5=8 (écrit de manière figurée, un exemple de nombre pair somme de deux premiers)
  • w'+z'→θ
  • η'+η'→2(η+ππ)
  • 31, 314159 (les premiers nombres premiers que l'on peut obtenir en concaténant les décimales de pi)
  • π2(x) = 2c2 x/(ln(x))², x→∞
  • QED ("CQFD")
  • Nombre premier martien : ♂2 = 170141183460469231731687303715884105727 (un exemple de nombre premier de Mersenne 2p-1, où p est également un nombre premier de Mersenne)
  • ETC

Le problème P=NP ("un problème peut-il toujours être résolu rapidement par un algorithme ?") fait une apparition au détour de deux livres dans le placard à balai des locaux de Planet Express.

futurama_PNP
Ne prêtez pas attention au fait que la tête de Fry est greffée sur le corps d'Amy, et regardez en bas à gauche. Un livre indique P, l'autre, NP. [2ACV07 - La tête sur l'épaule]

On peut aussi apercevoir l'hypothèse de Riemann (sous une forme démontrée) lors d'un cours sur les coniques :

futurama_riemann
[6ACV05 - Sciences idiotes]

Futurama parle également du théorème Greenwaldien, disant a²+b²>c² (l'homologue du théorème de Pythagore en géométrie sphérique). Il n'existe pas réellement de théorème Greenwaldien, c'est simplement un clin d’œil des scénaristes à Sarah Greenwald, qui a écrit plusieurs articles sur la science et les maths dans les Simspons et dans Futurama.

L'autre équation du tableau, E=9.87sin(2B)-7.53cos(B)-1.5sin(B), est l'équation du temps, utilisé en astronomie et qui mesure "la différence entre le temps solaire moyen et le temps solaire vrai".

futurama_Greenwaldian
 [5ACV01 - La grande aventure de Bender]

Dans un autre épisode, le professeur Farnsworth invente une machine à dupliquer les objets. Son nom : le duplicateur Banach-Tarski. Ce théorème, qui indique qu'il est possible de découper deux boules en deux boules de même taille, a enfin trouvé une application ! 

vlcsnap-2012-10-10-21h26m36s29
[6ACV16 - Benderama]

Le théorème de Ken Keeler
Dans le dixième épisode de la saison 6, les scénaristes y sont allés encore plus fort : un théorème mathématique du domaine de la théorie des groupes, un vrai de vrai, a été inventé pour l'occasion, et sert de dénouement à l'intrigue !

Le professeur Farnsworth invente une machine permettant d'échanger deux esprits entre deux corps. Ainsi, l'esprit d'Amy se retrouve dans le corps de Farnsworth, et vice-versa. La premier soucis, c'est que si un échange est fait, il est impossible de revenir en arrière (Farnsworth et Amy ne peuvent plus échanger à nouveau leurs esprits). Le deuxième soucis, c'est que très vite, tous les personnages de la série utilisent la machine, et qu'une dizaine d'esprits sont dispersés dans tout autant de corps... Comment s'en sortir ?

futurama_lesmaths
[6ACV10 - Le Prisonnier de Benda]

La solution est énoncée par les deux mathématiciens-basketteurs de la série, Sweet Clyde et Bubblegum Tate : en ajoutant seulement deux personnes, il est possible de remettre à leur place tous les esprits, quel que soit le nombre d'échanges ayant été faits. Et ils le prouvent :

futurama-kenKeeler
Oui. Il s'agit bien de la preuve d'un théorème de la théorie des groupes. Entièrement rédigé. Dans une série du câble. [6ACV10 - The Prisoner of Benda]

Le théorème montre que si le corps et l'esprit de k personnes sont mélangés, il suffit de deux autres personnes et de k+3 échanges (au plus) pour que chacun retrouve sa place initiale.

Avec l'aide des deux corps de Clyde et Tate, les 9 esprits mélangés parviennent à retrouver leur corps d'origine, en 13 échanges (dans le contexte de l'épisode, on peut montrer que le problème était résolu en 9 échanges, sans l'intervention de deux autres personnes).

Tout le reste
Il me reste encore plein d'images à mettre... Ca ne vous gêne pas si je les mets là, en désordre ?...

futurama_11sup4
11 est plus grand que 4. Cette vérité mathématique fait partie de l'ensemble de la connaissance humaine, rassemblée par les cerveaux avant de détruire l'Univers [4ACV10 - Fry : Le pourquoi du comment]

futurama_discret
Bender lance une agence de rencontre : discrète (qui n'attire pas l'attention) et discrète (non continue) [2ACV07 - La tête sur l'épaule]

futurama_iluvX
∀xI♥x : une façon mathématique de dire qu'elle aime tout ce qui existe [5ACV05 - Le Monstre au milliard de tentacules]

futurama_girls
Dans les tréfonds de l'Internet, toutes les perversions ont leur site, notamment, "Girls proving theorems" [2ACV09 - Le mariage de Leela]

futurama_Euclide
De nombreuses célébrités sont caricaturées dans Futurama. Entre autres : Euclide.
[6ACV05 - Sciences idiotes]

futurama_binaire
Le nombre 0101100101 (357, en binaire), écrit en lettre de sang sur le mur, ne fait peur à personne. Le reflet dans le miroir est un peu plus effrayant : 1010011010 signifie 666 en binaire. [2ACV18 - La voiture garoute]
 

vlcsnap-2012-10-10-21h37m50s56Les duplications répétées de Bender dans l'épisode Benderama posent un problème de taille : la masse totale des Bender n'est pas convergente ! [6ACV16 - Benderama]

vlcsnap-2012-10-12-20h31m53s217
Perdu dans le tétraèdre des Bermudes, le Planet Express est pris en chasse par Möbius Dick, la baleine quadridimensionnelle (clin d'oeil croisé à Moby Dick et au ruban de Möbius). Par son évent, celle-ci ne crache pas de l'eau, mais bien de la fumée en forme d'ensemble de Julia. [6ACV15 - Obsession]

vlcsnap_2012_10_29_22h10m27s136
Suite à un overcloacking [6ACV25 - Overclockwise], Bender se met à lire très rapidement l'ensemble de la bibliothèque du Planet Express. Parmi les livres qui apparaissent, on peut citer :
- Calculus
- Advanced Calculus
- The Mathketball Diaries
- Some of the Digits of π


Sources :
Dr. Sarah's Futurama Math: Mathematics in the Year 3000

07 juillet 2013

[#] Une découpe presque parfaite

Le 15 juin dernier, lors de la soirée Radio-Dessinée “Une expérience presque parfaite” organisée par Podcast Science, Robin Jamet a proposé aux auditolectospectateurs une variante du problème du partage équitable de gâteau (que j'avais expliqué dans cet article). 

Couper un gâteau de manière équitable entre gourmands se résout facilement avec le principe du "je coupe, tu choisis" : le premier gourmand coupe le gâteau en deux, le deuxième choisit la part de son choix. Si chacun cherche à maximiser la taille de sa part, celui qui coupe a tout intérêt à faire une découpe équitable.
Mais que se passe-t-il si, au lieu de faire deux parts, celui qui coupe (appelons-le A), décide d'en faire davantage ? Celui qui ne coupe pas (appelons-le B) choisit la part de son choix, puis chacun à leur tour, ils choisissent une part autour de l'ouverture jusqu'à ce qu'il n'y ait plus de gâteau. Existe-t-il une découpe qui permettrait à A d'obtenir à coup sûr plus de gâteau que B ? La question mérite d'être posée !

Ce problème a seulement été étudié par des lycéens dans le cadre de MATh.en.JEANS, donc le sujet reste encore largement ouvert. 

Exemple_decoupe_gateauFig 1: A découpe le gâteau en quatre parts, de tailles respectives 1, 2, 3 et 4.
Fig 2 : B choisit la part de son choix, il prend la part de taille 4
Fig 3 : A a le choix entre les parts 2 et 3, il choisit la part 3
Fig 4 : B a le choix entre la part 1 et 2, il choisit la part 2
Fig 5 : A choisit la dernière part. Au final, A n'obtient que 40 % du gâteau, son découpage n'était donc pas idéal !

N=3 parts
Premier cas de figure : existe-il un découpage en trois parts qui serait profitable à A ? Malheureusement, non !
Appelons P1, P2 et P3 les différentes parts, en admettant que P3 est la plus petite et P1 la plus grande. Dans ce cas, B commencera par prendre P1, puis A prendra P2, puis A prendra P3. La part P2 étant la part intermédiaire, elle ne peut pas être plus grande qu'un demi-gâteau. Avec les parts P3+P1, B obtient donc au moins la moitié du gâteau.

Trois_partsAu mieux (si B cherche à maximiser sa proportion de gâteau), A ne s'en sortira qu'avec la deuxième part P2.

N=2n parts
Autre cas de figure : A propose une découpe comprenant un nombre pair de parts. Dans ce cas, B dispose d'une stratégie lui permettant à coup sûr d'obtenir plus de gâteau que A.

Numérotons les parts du gâteau. Il y a alors deux types de parts : les parts de rang pair et les parts de rang impair. L'une de ces deux familles représente au moins la moitié du gâteau ; c'est cette famille que B choisira. Disons qu'il s'agit de la famille paire.
La stratégie de B est alors la suivante : B choisit n'importe quelle part de rang pair. Quel que soit le choix de A (une part impaire), B pourra toujours choisir une part paire, et ainsi de suite.
Cette stratégie assure à B d'obtenir au moins la moitié du gâteau, mais il est possible qu'une autre stratégie lui permette d'en obtenir encore plus !

Decoupe_gatea_pair
B peut s'arranger pour ne récupérer que les parts rouges (celles de rang pair), qui représentent 57% de ce gâteau.

N=5 parts
Et si A propose un découpage à 5 parts ?... Encore une fois, B disposera toujours d'une stratégie gagnante.

Appelons P1, P2, P3, P4 et P5 les différentes parts, de la plus grande à la plus petite. A l'issue du partage entre les deux joueurs, A aura deux parts, B en aura 3.
Pour qu'une stratégie gagnante existe pour A, il faut qu'au moins deux parts vérifient l'inégalité Pi+Pj > 1/2 (*) (les parts que devra choisir A pour gagner). De plus, aucune des parts ne doit être plus grande que le demi-gâteau (sinon, B la choisit en premier)
Si seuls P1 et P2 vérifient l'inégalité (*), il suffit que B choisisse en premier P1 pour empêcher A de gagner.
Il faut donc que P1, P2 et P3 vérifient deux à deux l'inégalité (*). En particulier, il faut que

P2+P3 > 1/2 (a)

Cependant, il existe pour B une stratégie obligeant A à choisir au moins l'une des parts P4 ou P5 (si P4 et P5 se touchent, B choisit en premier n'importe quelle autre part ; si P4 et P5 ne se touchent pas, B choisit en premier la part entre les deux). Il faut donc que P4 intervienne aussi dans une inégalité (*). Autrement dit, il faut (au moins) que

P1+P4 > 1/2 (b)

Les inégalités (a) et (b) sont incompatibles. En les additionnant, on trouve que P1+P2+P3+P4 > 1, ce qui est impossible. Autrement dit, il n'existe aucune stratégie gagnante pour A !

On peut montrer que la même façon qu'il n'existe pas de stratégie gagnante pour A dans le cas N=7. Pour assurer la victoire, il faut au moins que P2+P3+P4 > 1/2. En étudiant les positions relatives de P1, P2, P6 et P7, on aboutit à chaque fois à une inégalité incompatible avec la précédente.

Bref, pour que A puisse à coup sûr obtenir plus de gâteau que B, il faut un découpage comprenant au moins 9 parts...

N=15 parts
Tout espoir n'est pas perdu pour A, car il existe bien des découpages gagnants. Pour l'instant, le seul découpage découvert compte 15 parts, et ressemble à ceci :

Gros_gateauLe découpage stratégique pour A :
1, 4, 1, 7, 1, 1, 7, 1, 10, 1, 1, 10, 1, 13, 1

Ce découpage de gâteau est constitué de trois portions qui suivent le même schéma : 1 - P1 - 1 - P2 - 1, où P1 et P2 sont les seules parts réellement intéressantes. Les trois portions ne sont pas équivalentes.

Pour ses deux premiers choix, A prendra ses parts parmi celles de la portion initiée par B (sauf si l'occasion est donnée par B de prendre une grosse part d'une autre partie). Pour son premier choix, A priviligiera la plus grosse part ; en cas d'égalité, il prendra la part du bord de la portion. Pour son 3e, 4e et 5e choix (la totalité de la première portion ayant été choisie), A choisira ses parts dans la plus petite des deux autres portions (les grosse parts de cette portion reviendront alors à B). Finalement, B sera contraint de laisser les deux dernières grosses parts à A. Au final, A aura (au moins) 3 parts des 6 plus grandes parts ; par cette stratégie, elles seront plus grandes que celles de B.

Gros_gateau_exemple

Exemple
Fig 1 : B choisit la plus grosse part "13". Parmi ses deux parts possibles, A doit choisir celle du bord de la portion.
Fig 2 : B a deux possibilités : choisir une part "1" de la petite portion (et céder les parts "4" et "7" à A), ou choisir la part "1" du milieu de la grande portion. Ce deuxième choix est plus stratégique pour B. Ensuite, A choisit la part "10", puis B choisit la dernière part de la portion.
Fig 3 : A a deux possibilités : choisir une part de la petite portion ou de la moyenne portion. En prenant celle de la petite portion, il laisse à B les grandes parts de cette petite portion, mais récupères celles de la moyenne portion (Fig 4)
Fig 4 : A récupère donc 31/60 du gâteau, contre 29/60 pour B. 

Variantes
De nombreuses questions restent encore ouvertes : existe-t-il un découpage stratégique à 9 parts ? à 11 parts ? à 17 parts ? De plus, il est certain qu'il existe un bon découpage avec toutes les parts différentes (il suffit de modifier légèrement la taille des parts de l'exemple au dessus), mais existe-t-il un découpage où les 15 parts sont respectivement de taille 1, 2, ..., 15 ?

On peut aussi penser à la variante avec une barre pâtissière où A coupe la barre puis, chacun à leur tour en commençant par B, les deux gourmands choisissent l'une des parts à l'extrémité. Si le nombre de parts est pair, B dispose d'une stratégie gagnante (il peut faire en sorte que A ne récupère que les parts de rang pair ou celles de rang impair). Si le nombre de parts est impair, A dispose d'un découpage gagnant (par exemple, un découpage en 3 parts où celle du milieu est sensiblement plus grande que les deux autres).

Barre_patissièreUn partage de barre pâtissière sensiblement avantageux pour A, deuxième à choisir !

Une dernière variante, toujours avec une barre pâtissière : B choisit la part de son choix, puis, à leur tour, les gourmands prennent une part autour de l'ouverture (il peut n'y avoir qu'une seule part disponible).
Pour un nombre pair de part, B a une stratégie gagnante, toujours la même. Les cas impairs sont un peu moins évident, mais on peut montrer sans trop de difficultés que A n'a pas de stratégie gagnante pour N=1, 3, 5 ou 7 parts (en raisonnant sur des inégalités, comme pour le cas du gâteau).
Existe-t-il un découpage gagnant pour 11 parts ou plus ? La question reste ouverte ! Ami lecteur, ces questions sont pour vous !

Posté par El Jj à 10:00 - Commentaires [5]
Tags : , ,


  1  2  3  4  5    Fin »
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.