Solution au problème d'avril 2007

Le problème:
	Deux points d'une sphère sont dit orthogonaux si les segments qui les relient au centre de la sphère sont perpendiculaires. Par exemple, le pôle Nord est orthogonal à tous les points de l'équateur. Quel est le nombre minimal de couleurs requis pour colorier la sphere de telle sorte qu'il n'existe aucune paire de points orthogonaux de la même couleur?

Réponses correctes:
	Nous avons reçu des réponses correctes de Gérard Billion (France), Dan Dima (Roumanie), Philippe Fondanaiche (France), Xavier Hecquet (France), Matthew Lim (États-Unis), John T. Robinson (États-Unis) et K. Sengupta (Inde):

La solution:

C. D. Godsil and J. Zaks. Coloring the sphere. University of Waterloo research report CORR 88-12, 1988

Il est démontré que trois couleurs suffisent pour colorier les points de la sphère dont les trois coordonnées sont rationelles. Merci à Philippe Fondanaiche pour cette information et d'autres références de la page

 http://tph.tuwien.ac.at/~svozil/publ/blatter.htm.

Pour démontrer que quatre couleurs sont nécessaires, il est bon d'appliquer un théorème de de Bruijn, Erdős (A colour problem for infinite graphs and a problem in the theory of relations. Dans: Nederl. Akad. Wetensch. Proc. Ser. A 54, 1951 371–373. (Indag. Math. 13.)), qui dit que si tous les sous-graphes finis d'un graphe sont k-colorables, alors le graphe l'est aussi. Il suffit donc de trouver un ensemble fini de points qui ne peuvent pas être coloriés avec trois couleurs sans que deux points orthogonaux aient la même couleur.

Première partie: Trois couleurs ne suffisent pas.
Nous présentons ici une adaptation de la solution de John T. Robinson. Considérons le graphe G formé des treize vecteurs suivants, où deux vecteurs sont adjacents lorsqu'ils sont orthogonaux. Le graphe G contient trois triangles:
    T₁: (0,0,1), (1,1,0), (1,-1,0)
    T₂: (1,0,0), (0,1,1), (0,-1,1)
    T₃: (0,1,0), (1,0,1), (-1,0,1)
En plus des quatre points de l'ensemble
    I: (1,1,1), (-1,-1,1), (1,-1,1), (-1,1,1).
Les vecteurs de G ne sont pas tous sur même sphère, mais en divisant chaque vecteur par sa norme, on obtient un graphe identique constitué de points sur la sphère unité. On peut donc éviter de s'embarasser de racines en démontrant que G ne peut être colorié avec trois couleurs.

Supposons que G est colorié avec trois couleurs. Alors une des couleurs, disons rouge, est utilisée pour au moins cinq points, dont exactement un point de chaque T_i (autrement ce T_i serait colorié avec trois autre couleurs) et au moins deux points de I.

- Si le point rouge de T₁ est (0,0,1), alors le point rouge de T₂ est (0,1,1) ou (0,-1,1) et le point rouge de T₃ est (1,0,1,) ou (-1,0,1), donc les points rouges de T₂ et T₃ sont adjacents à trois points de I, donc il ne peut y avoir cinq points rouges.

- Donc, le point rouge de T₁ est soit (1,1,0), adjacent aux points (1,-1,1), (-1,1,1) de I, soit (1,-1,0) adjacent aux points (1,1,1), (-1,-1,1) de I. Par conséquent les points rouges de I sont soit (1,-1,1) et (-1,1,1), ou (1,1,1), (-1,-1,1). Dans les deux cas, le seul point de T₂ qui n'est pas adjacent à un point rouge de I est (1,0,0), et le seul point de T₃ qui n'est pas adjacent à un point rouge de I est (0,1,0). Donc les points (1,0,0) et (0,1,0) doivent être rouges, ce qui est impossible puisqu'ils sont adjacents.

Ainsi, il est impossible de colorier G avec trois couleurs.

Deuxième partie: Quatre couleurs suffisent.
Nous reproduisons ici l'argument de Philippe Fondanaiche.
``Je considère le repère orthonormé Oxyz qui coupe la sphère de centre O en six points A, A', B, B', C et C' qui ont respectivement pour coordonnées:
A = (1,0,0) et A' = (-1,0,0) colorié en bleu
B = (0,1,0) et B' = (0,-1,0) colorié en rouge
C = (0,0,1) et C' = (0,0,-1) colorié en vert
Il y a trois grands cercles qui passent par respectivement par les 4 points (B,C,B',C') puis par les 4 points (C,A,C',A'), et enfin par les 4 points (A,B,A',B). Ces trois grands cercles peuvent être coloriés avec les deux couleurs utilisées pour colorier les points par lesquels ils passent. C'est ainsi que les douze arcs de cercle ayant pour extrémités les 6 points A,A',B,B',C et C' sont coloriés de la manière suivante:

AB = rouge, BA' = bleu, A'B' = rouge, B'A = bleu, AC = bleu, CA' = vert, A'C' = bleu, C'A = vert, BC = vert, CB' = rouge, B'C4 = vert, C'B = rouge.

Ces trois grands cercles divisent ainsi la sphère en huit octants identiques entre eux ABC, BA'C, A'B'C, etc.... Si l'on raisonne sur les 4 octants placés au dessus du plan horizontal Oxy, on peut colorier chacun d'eux avec 4 couleurs: bleu, rouge,vert et  jaune. Par exemple l'intérieur de ABC qui est bordé par trois arcs coloriés en bleu, rouge et vert est colorié en jaune tandis que l'octant BA'C qui est bordé par deux arcs verts est colorié en vert à l'exclusion de la bordure A'B qui est en bleu. L'octant A'B'C bordé par deux arcs rouges est colorié en rouge à l'exclusion de la bordure A'B' qui est en vert. Enfin l'octant B'AC bordé par deux arcs bleus est colorié en bleu à l'exclusion de la bordure B'Cqui est en rouge. Les quatre autres octants placés en-dessous du plan horizontal sont alors coloriés de la même couleur que les octants qui leur sont symétriques par rapport au centre O de la sphère.''