Des progrès réalisés dans le problème de non-collinéarité de trois points

par Ed Pegg
Article original
Après des décennies sans progrès réalisés dans le problème de non-collinéarité de trois points, en septembre 2025, Thomas Prellberg a trouvé de « nouvelles solutions pour n = 47, 49, 51, 53, 54, 55, 56 et n = 58 ». En janvier, une « solution pour n = 59 et n = 60 ». Toute une série de nouvelles solutions a suivi, avec, en mars 2026, avec, en mars 2026, une solution pour n = 68.
En 1917, Henry Dudeney a demandé quel était le nombre maximal de points que l’on pouvait sélectionner dans une grille
n
×
n
de sorte qu’aucun groupe de trois points ne soit aligné. Il est évident qu’on ne peut pas sélectionner plus de deux points dans une même ligne ou une même colonne, donc le nombre maximal de points est
2n
. Si l’on définit une solution comme une grille
n
×
n
comportant une sélection maximale de
2n
points sans que trois points ne soient colinéaires, une grille 52×52 avec 104 points sélectionnés est la plus grande solution connue (en 2023).
Voici du code provenant de ma démonstration, problème de non-collinéarité de trois points.
In[]:=
known=
;​​ascii="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$%&@?!()[]<>{}=*+|-/~^_:;,.";​​replace=Thread[Characters[ascii]Range[90]];​​nothree[dat_]:=ArrayPlot[Transpose[Normal[SparseArray[#1&/@Flatten[MapIndexed[Transpose[{#1,{#2[[1]],#2[[1]]}}]&,​​Partition[Drop[Characters[dat],1]/.replace,2]],1]]]],MeshTrue,PixelConstrained->6]
Un exemple d’élément provenant des données « connues » est « :13062415240635 ». Après le premier caractère, la première ligne comporte des points aux positions 1 et 3. La deuxième ligne comporte des points aux positions 0 et 6. Et ainsi de suite.
In[]:=
nothree[":13062415240635"]
Out[]=
Le titre est emprunté à un article d’Achim Flammenkamp (J. Combin. Theory Ser. A, 60 (1992)). Il a poursuivi avec un article II (de même titre) en 1998, qui donnait une solution d’ordre 52, démontrée ci-dessous. Pendant des décennies, ce fut la fin du problème. C’est devenu un problème tristement célèbre sans aucun progrès.
In[]:=
nothree[Last[known]]
Out[]=
Le premier caractère est une classe de symétrie : « . : / - o c x + * ». Que signifient ces caractères ? Nous pouvons rechercher des représentants dans les données.
Out[]=
.
:
/
-
o
Out[]=
.
:
/
x
Out[]=
.
:
/
o
x
Out[]=
:
/
c
x
Après des décennies sans progrès réalisés, en septembre 2025, Thomas Prellberg a trouvé « de nouvelles solutions pour n=47,49,51,53,54,55,56 et n=58 ». En janvier, une « solution pour n=59 et n=60 ». Toute une série de nouvelles solutions a suivi, avec, en mars 2026, avec, en mars 2026, une solution pour n = 68.
Out[]=
Nous pouvons vérifier la solution à l’aide de droites extraordinaires. Une droite ordinaire est une droite contenant deux points. Une droite extraordinaire en contient 3 ou plus. Un problème différent minimise le nombre de droites ordinaires dans une configuration de points. Tout ensemble 2D de n points contient au moins 6 n/13 droites ordinaires. Le problème de non-collinéarité de trois points maximise le nombre de droites ordinaires. L’ensemble de points ci-dessus est rassemblé dans p68.
In[]:=
ResourceFunction["FindExtraordinaryLines"][p68]
Out[]=
{}
Et il n y a aucune droite extraordinaire. Mais si nous ajoutons un point, nous en obtenons quelques-unes.
In[]:=
ResourceFunction["FindExtraordinaryLines"][Append[p68,{17,17}]]
Out[]=
{{1,17,137},{3,69,137},{14,43,137},{27,32,137},{33,34,137},{35,37,137},{49,134,137},{61,76,137},{73,87,137}}
Même si nous sortons de la grille, nous avons tendance à trouver des lignes de 3.
In[]:=
ResourceFunction["FindExtraordinaryLines"][Append[p68,{74,75}]]
Out[]=
{{4,80,137},{99,115,137},{125,129,137}}
In[]:=
ResourceFunction["FindExtraordinaryLines"][Append[p68,{74,76}]]
Out[]=
{{19,105,137},{22,64,137},{112,136,137},{122,124,137}}
Hier, Thomas Prellberg a dénombré les 118057 solutions pour n=20. C’est un sujet qui fait beaucoup parler de lui en ce moment. Pour en savoir plus à ce sujet, consultez Mathworld : No-Three-in-a-Line-Problem, Wikipédia : No-three-in-line problem et Universität Bielefeld : The No-Three-in-Line Problem.
L’énumération semble être exponentielle jusqu’à présent.
In[]:=
ListLogPlot[{Table[0.236(1.876)^n,{n,1,20}],{0,1,1,4,5,11,22,57,51,156,158,566,499,1366,3978,5900,7094,19204,32577,118057}},Joined->{True,False}]
Out[]=
Pour les curieux, voici toutes les solutions d’ordre 8 :
Toutes les solutions d’ordre 9 :
Toutes les solutions d’ordre 10 :

CITER CE NOTEBOOK