Grille discrète : pourquoi un générateur minimal peut être immense ?

Intervenant 10:00

Bienvenue à toutes et à tous dans le podcast du magazine Tangente.

Intervenant 20:04

Bonjour Sam !

Intervenant 10:05

Aujourd'hui, on plonge d'emblée dans un univers plat, mais un univers où toutes les règles de la géométrie, enfin celles qu'on a apprises à l'école avec une règle et un compas,

Intervenant 20:15

Ouais, la géométrie bien sage, quoi.

Intervenant 10:17

Voilà, exactement. Eh bien, toutes ces règles s'effondrent totalement. C'est un monde où l'idée même qu'un plan possède deux dimensions devient un concept glissant, voire presque trompeur.

Intervenant 20:29

C'est clair. Et du coup, pour visualiser ce monde un peu paradoxal, il faut vraiment abandonner notre traditionnelle feuille de papier vierge, tu sais, celle sur laquelle le crayon glisse de manière super fluide.

Intervenant 10:39

Ouais, on oublie le papier millimétré classique.

Intervenant 20:41

C'est ça. L'article de Cécile Ouvrier-Buffet, sur lequel on s'appuie aujourd'hui, nous propose un décor très différent. C'est ce qu'on appelle en mathématiques le plan discret.

Intervenant 10:52

D'accord. Alors, il faut planter le décor visuel pour quiconque nous écoute. Imaginons une grille à mailles carrées, mais totalement infinie. Un peu comme dans un de ces vieux jeux vidéo d'arcade super pixelisés.

Intervenant 21:04

Ah ouais, genre avec le ciel bleu en escalier ?

Intervenant 11:06

Voilà, ouais. Avec un petit dinosaure vert qui ne peut qu'avancer par à coups, tu vois, de case en case, et des pièces dorées qui flottent en l'air. Et au milieu de cette grille sans fin, on place un point de départ. Juste un simple point rouge.

Intervenant 21:19

Ok, je visualise bien le point

Intervenant 11:21

rouge. La question de départ, elle semble hyper enfantine. À partir de ce point rouge, quelle case de la grille est-ce qu'on peut atteindre si on respecte un ensemble très précis de déplacements ?

Intervenant 21:31

Ok, décortiquons tout ça. Comment est-ce qu'on se déplace concrètement sur cette grille ? Alors on peut se représenter ces déplacements comme des vecteurs ou tout simplement des flèches, pour faire simple. Des

Intervenant 11:42

flèches, ok.

Intervenant 21:43

Ouais, on pourrait avoir une première flèche qui dicte la règle suivante, genre avance de deux cases vers la droite et monte d'une case. D'accord,

Intervenant 11:50

le mouvement du cavalier aux échecs un peu.

Intervenant 21:53

Un peu, oui. Et puis une deuxième flèche qui impose avance d'une case vers la droite et descend de deux cases. La règle fondamentale de cet univers, et en fait c'est de là que va naître tout le

Intervenant 12:04

chaos,

Intervenant 22:05

c'est qu'on a le droit de combiner ces flèches autant de fois qu'on le

Intervenant 12:09

souhaite,

Intervenant 22:10

mais uniquement avec des coefficients entiers et positifs.

Intervenant 12:15

Alors des coefficients entiers, je visualise bien, on ne peut pas faire un demi-saut de dinosaure ou un quart de pas ?

Intervenant 22:21

Non, c'est interdit.

Intervenant 12:22

On saute d'un croisement de la grille à un autre, pile poil. Mais le côté positif, c'est ça le grand piège de ce système, n'est-ce pas ?

Intervenant 22:29

C'est le cœur du problème. Une combinaison linéaire entière positive, ça veut tout simplement dire qu'il n'y a absolument aucune touche retour en arrière.

Intervenant 12:38

Ah ouais, on ne peut pas annuler son coup.

Intervenant 22:40

Exactement. Si tu possèdes une flèche qui pointe vers le haut et la droite, tu peux l'utiliser 5 fois, 10 fois, 100 fois, mais on ne peut pas l'utiliser moins une fois pour revenir sur ses pas.

Intervenant 12:52

Du coup, t'es condamné à aller de l'avant, toujours dans la direction dictée par le vecteur.

Intervenant 22:56

C'est ça. Et cette restriction de marche arrière, c'est vraiment ce qui transforme la navigation sur le plan en un casse-tête infernal.

Intervenant 13:03

C'est un peu la tragédie du fou sur un échiquier, en fait.

Intervenant 23:06

Comment ça ?

Intervenant 13:07

Bah, le fou, il se déplace en diagonale et quoi qu'il fasse, il est mathématiquement condamné à rater la moitié du plateau. S'il démarre sur une case blanche...

Intervenant 23:16

Ah oui, il n'atteindrait jamais une case noire.

Intervenant 13:18

Jamais. Même après un million de déplacements. On laisse d'immenses ondes d'ombre.

Intervenant 23:22

C'est une super analogie. Le fou d'échecs illustre parfaitement ce phénomène d'inaccessibilité. Avec notre petit dinosaure et ses flèches sur la grille infinie, il se passe exactement la même chose.

Intervenant 13:33

Il reste coincé sur sa couleur, en quelque

Intervenant 23:35

sorte. Avec certains ensembles de déplacement, on va générer un grand cône de position possible à partir du point rouge. Mais tout le reste du monde autour reste vierge. Et le plus troublant, c'est qu'à l'intérieur même de ce cône qu'on a l'impression d'explorer, on laisse ce que les mathématiciens nomment des trous.

Intervenant 13:52

Des

Intervenant 23:52

trous. Des points inatteignables, mais qui sont entourés de tous côtés par des points qu'on a pourtant réussi à toucher.

Intervenant 13:59

C'est fou ça ! Donc, pour gagner à ce jeu, c'est-à-dire pour pouvoir colorier toute la grille sans exception avec notre point rouge, l'article mentionne qu'il faut réussir à réunir deux propriétés bien spécifiques.

Intervenant 24:10

Oui, il faut en effet que notre ensemble de déplacements possède la propriété de densité et la propriété de proximité.

Intervenant 14:17

Alors, on y va doucement. La densité, c'est quoi ?

Intervenant 24:20

La densité, c'est la capacité globale d'un ensemble de flèches à atteindre les points d'un secteur extrêmement large du plan. En gros, sans laisser de secteur infini complètement vide derrière lui.

Intervenant 14:31

Ok, on balaye large. Et la proximité, j'imagine que c'est ce qui gère nos fameux trous dont tu parlais ?

Intervenant 24:36

C'est exactement ça. La proximité, ça impose une limite stricte à la taille de ses trous. Mathématiquement parlant, si on choisit un point quelconque de la grille, même un point inatteignable, la distance entre ce point impossible et un point qu'on peut atteindre, elle doit toujours être bornée.

Intervenant 14:53

Donc on ne s'éloignait jamais trop du chemin.

Intervenant 24:55

Voilà. En d'autres termes, peu importe où on zoome sur cette grille infimie, on ne doit jamais être très loin d'une case qu'on a réussi à fouler. Sans densité et sans proximité, le plan reste une passoire géante.

Intervenant 15:08

Mais attends, je vois une solution super évidente à ce problème de passoire. Ah bon ? Laquelle ?

Intervenant 25:13

Bah, si on rate des cases, ne suffit-il pas d'ajouter des flèches supplémentaires dans notre arsenal ? Je veux dire, on rajoute une flèche plein nord, une plein sud, une à l'est, une à l'ouest, et pourquoi pas quelques grandes diagonales pour être sûr. Ah, la méthode forte !

Intervenant 15:29

Exactement. Si on inonde la grille avec, je sais pas, une vingtaine d'options de mouvements différents, on finira bien par reboucher tous les trous, non ?

Intervenant 25:37

Ce qui est fascinant ici, c'est que cette solution de facilité esquive la véritable beauté du problème. L'objectif des mathématiciens, ce n'est pas du tout d'écraser la grille sous un déluge de flèches. Ah, ils

Intervenant 15:47

aiment se compliquer la vie,

Intervenant 25:50

quoi. Un peu. Non, la vraie quête, c'est l'économie de moyens.