Recouvrir les sommets de l’hypercube
------------------------------------
Quand on raisonne sur les coordonnées, la géométrie plane (avec abscisse et ordonnée) et la géométrie dans l’espace (avec abscisse, ordonnée et cote) se généralisent facilement à la géométrie à n dimensions. En deux dimensions, les points dont les coordonnées ne sont que des 0 et des 1 forment un carré. Dans l’espace, les sommets, notés 000, 100, 110, 010, 001, 101, 111 et 011, forment un cube. Dans l’espace à n dimensions, on obtient un hypercube, qu’on notera H*n. On peut aussi considérer des hyperplans, qui sont alors tout simplement les ensembles de points décrits par des équations de la forme a*1 x1 + a2 x2 + … +*an xn = b*.
Le cadre étant fixé, un petit jeu occupe les matheux depuis un moment : recouvrir des ensembles de points avec un minimum d’hyperplans, et en particulier des ensembles constitués de certains sommets de l’hypercube. En 1993, l’Israélien Noga Alon et le Hongrois Zoltán Füredi ont démontré que recouvrir tous les sommets de l’hypercube sauf l’origine (celui dont toutes les coordonnées sont nulles, parfois noté 0*n ) nécessite exactement n hyperplans. On peut en effet choisir tous les hyperplans d’équation xi* = 1. La difficulté est de comprendre pourquoi cela n’est pas possible avec moins d’hyperplans.
