D’une conjecture d’Erdős à un théorème de Tao


Jacques Bair

Le prolifique mathématicien hongrois Paul Erdős (1913–1996) et, dans sa foulée, de nombreux théoriciens des nombres et spécialistes de combinatoire ont étudié le « problème de la discrépance ». En 1932, Erdős a formulé une profonde conjecture. En 2015, Tao l’a démontrée.

Le mot « discrépance » est peu courant en langue française. D’origine latine (discrepantia), il peut signifier, au figuré, « désaccord » ou « discordance ». Le problème mathématique de la discrépance est ardu ; une présentation métaphorique et élémentaire peut cependant en être donnée (voir Tangente 168, 2016). Une approche ludique est également possible. Voyons comment se présente la question mathématique de la discrépance dans ce cadre.

 

Le poseur et le ramasseur

Le jeu qui va nous intéresser est pratiqué par deux joueurs qui, pour des raisons qui apparaîtront clairement par la suite, sont nommés le poseur et le ramasseur. Au départ, le poseur possède des billes toutes semblables, sauf qu’elles sont blanches ou vertes, en nombre illimité pour chacune des deux couleurs. Il effectue une marche en ligne droite au cours de laquelle il va déposer sur le sol une bille après chaque mètre parcouru. Toutefois, il est obligé de « bien choisir » la couleur lors de chaque dépôt, sauf le premier, qui est par convention celui d’une bille blanche.

Le ramasseur va le suivre en partant du même endroit initial puis en ramassant des billes qu’il doit placer sur l’un des deux plateaux d’une balance (les billes blanches sur le plateau de droite et les ... Lire la suite