Jeu de Berlekamp : peut-on éteindre encore plus d’ampoules ?

Intervenant 10:00

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

Intervenant 20:04

C'est un vrai plaisir d'être là pour cette nouvelle discussion.

Intervenant 10:07

Et quelle discussion ? Aujourd'hui, on se lance dans une exploration, comment dire, un peu diabolique. On va plonger dans le fameux problème de Berlekamp.

Intervenant 20:16

Ah oui, un classique. C'est un sujet qui est absolument fascinant.

Intervenant 10:19

Carrément. Alors, notre mission du jour, avec les sources qu'on a sous les yeux, c'est de comprendre comment une situation qui ressemble à un simple petit jeu de société, un vrai casse-tête quoi, va nous propulser directement dans l'univers de la modélisation mathématique la plus pure.

Intervenant 20:35

Tout à fait. Et ce qui est génial avec ce problème, c'est qu'il met vraiment en lumière la défaite totale de l'intuition humaine face à la complexité. On va voir comment une abstraction, une simple idée de distance mathématique, vient carrément sauver la mise.

Intervenant 10:48

Exactement, parce qu'on a tendance à croire que face à un puzzle physique, il suffit d'être un peu astucieux, d'avoir de la

Intervenant 20:56

patience. Spoiler, l'astuce, ça ne suffit pas ici. Il faut complètement changer notre façon de percevoir la réalité.

Intervenant 11:04

Alors, pour bien comprendre cette fameuse solution mathématique qui va nous retourner le cerveau plus tard, il faut poser le décor, visualiser l'arène de ce duel.

Intervenant 21:13

Je te laisse présenter le champ de bataille.

Intervenant 11:16

Ça marche. Alors, le terrain de jeu, c'est une grille carrée, une grille mathématique de dimensions n par n. Et sur chaque case, on a une petite ampoule classique.

Intervenant 21:26

Oui, très basique. Elle n'a que deux états, allumée ou éteinte.

Intervenant 11:30

Voilà, et sur ce champ de bataille lumineux, on a deux adversaires virtuels qui s'affrontent, mais en décalé. On va les appeler Alice et Bob.

Intervenant 21:39

Les grands habitués des exemples mathématiques.

Intervenant 11:41

Exactement, toujours eux. Alice est la conceptrice, elle joue en premier en cachette et c'est elle qui configure le plateau de départ. Elle choisit quelles ampoules sont allumées et où elles sont.

Intervenant 21:52

Et ensuite, c'est au tour de Bob. Et lui, son but, c'est tout l'inverse d'Alice. Il veut absolument minimiser le nombre d'ampoules allumées à la fin de la partie. S'il est un tout, c'est le jackpot.

Intervenant 12:02

D'accord, mais il a quoi comme outil pour faire ça ?

Intervenant 22:05

C'est là que ça devient vicieux. Il a des interrupteurs, mais pas n'importe lesquels. Il a un interrupteur au bout de chaque ligne et un autre au bout de chaque colonne.

Intervenant 12:12

Donc pour une grille de taille N, ça lui fait deux N interrupteurs en tout, c'est ça ?

Intervenant 22:17

C'est ça. Et la subtilité, la vraie mécanique diabolique du jeu, c'est que quand Bob appuie sur l'interrupteur d'une ligne, ça cible pas juste une ampoule. Ça inverse instantanément l'état de la totalité des ampoules de cette ligne.

Intervenant 12:29

Ah ouais, attends, je t'arrête tout de suite pour être sûr de bien piger. Si Bob, disons qu'il a une ligne avec deux ampoules allumées et une éteinte. S'il touche à l'interrupteur, les deux allumées s'éteignent, mais celle qui était éteinte, paf elle s'allume.

Intervenant 22:45

Exactement, c'est automatique. Il peut jamais isoler son action sur une seule case.

Intervenant 12:50

Mais du coup, c'est un peu comme un Rubik's Cube lumineux ce truc. Dès qu'on essaye de faire le ménage sur une ligne, on risque de rallumer des trucs qu'on avait galéré à éteindre sur les colonnes qui croisent.

Intervenant 22:59

C'est une super analogie, c'est tout à fait ça. Chaque action a des dommages collatéraux. Et la règle, c'est que Bob a le droit de cliquer sur ses interrupteurs autant de fois qu'il veut, dans l'ordre qu'il veut.

Intervenant 13:09

Jusqu'à ce qu'il en ait marre quoi.

Intervenant 23:11

Voilà. Le jeu s'arrête quand il décide qu'il ne peut pas faire mieux.

Intervenant 13:14

Le conflit d'intérêts est ouf. Bob rêve de tout éteindre. Mais Alice, qui a un esprit complètement machiavélique, elle veut préparer une grille de départ tellement tordue que même si Bob passe des années à tester des combinaisons, il restera bloqué avec des ampoules allumées.

Intervenant 23:30

Elle cherche le pire scénario possible pour Bob. Et pour réaliser à quel point le cerveau humain bug complètement face à ça, les sources proposent un petit cas pratique d'échauffement. Une grille toute petite, du 3 par 3. 9 cases au

Intervenant 13:43

total, c'est

Intervenant 23:44

tout petit. C'est minuscule. Alice prépare son coup. Elle laisse 6 ampoules allumées sur les 9 éparpillées sur la grille. Et Bob arrive.

Intervenant 13:52

J'imagine bien la scène. Il regarde ses six ampoules. Il commence à transpirer un peu. Disons qu'il attaque par le centre. Il clique sur la ligne du milieu.

Intervenant 24:00

Paf ! Les trois ampoules du milieu s'inversent. Il analyse. Ensuite, il tente la ligne du bas.

Intervenant 14:06

Clique, nouvelle inversion. On sent que là, il y va un peu au pif, non ? Il n'a pas de vision à long terme.

Intervenant 24:12

Totalement à l'aveugle, ensuite il attaque la colonne de droite. Clique, toute la verticale change. À ce stade, la grille ressemble plus du tout à ce qu'Alice avait préparé.

Intervenant 14:22

Il hésite un peu et, allez, il reclique sur la ligne du milieu. Et là, surprise !