Bài toán mở, Tổ hợp và Toán rời rạc, Hình học, nêu năm 1917

Bài toán không có ba điểm thẳng hàng trên lưới

Còn mở

Với mỗi số nguyên $n \ge 2$ , xác định số lượng điểm nút tối đa $f(n)$ có thể chọn ra từ lưới $n \times n$ gồm $\{1, 2, \dots, n\}^2$ sao cho không có ba điểm được chọn nào cùng nằm trên một đường thẳng có hệ số góc bất kỳ, và đặc biệt xác định xem $f(n) = 2n$ với mọi $n$ hay $\lim_{n \to \infty} f(n)/n < 2$ .

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, tỷ số tiệm cận $\lim_{n \to \infty} f(n)/n$ vẫn chưa được biết, nằm kẹp giữa cận dưới đại số $\frac{3}{2} = 1.5$ năm 1975 của Hall–Jackson–Sudbery–Wild và cận trên tầm thường $2$ theo nguyên lý Dirichlet. Các tìm kiếm bằng máy tính (của Flammenkamp, Prellberg, Heule và những người khác) đã tìm ra cấu hình $2n$ điểm không có ba điểm thẳng hàng cho mọi $n \le 74$ , nhưng số nghiệm $2n$ điểm đối xứng giảm dần khi $n$ lớn, củng cố thực nghiệm cho dự đoán heuristic Guy–Kelly $f(n) \sim \frac{\pi}{\sqrt{3}} n \approx 1.8138n$ .

Kết quả tốt nhất đã biết

Với mọi $n \ge 2$ , $(\frac{3}{2} - o(1))n \le f(n) \le 2n$ (Hall, Jackson, Sudbery và Wild, 1975).
Đẳng thức chính xác $f(n) = 2n$ đúng với mọi $2 \le n \le 74$ nhờ các cấu hình tường minh tìm được bằng máy tính.

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Đường cong đại số trên trường hữu hạn $\mathbb{F}_p$ (Erdős, Hall–Jackson–Sudbery–Wild)	Sử dụng định lý Bézout trên $\mathbb{F}_p$ — rằng một đường thẳng cắt một đường conic bất khả quy như $y \equiv x^2 \pmod p$ hay $xy \equiv k \pmod p$ tại tối đa $2$ điểm theo modulo $p$ , do đó tối đa $2$ điểm trong $\mathbb{Z}^2$ — để dựng $(3/2 - o(1))n$ điểm.	Các đường cong bậc $d \ge 3$ trên $\mathbb{F}_p$ có thể cắt một đường thẳng tại từ $3$ điểm trở lên, còn việc ghép nhiều đường conic dịch chuyển sẽ làm phát sinh các bộ ba điểm thẳng hàng xuyên qua các ô khác nhau khi mật độ vượt quá $3n/2$ .

Câu hỏi còn mở

Có tồn tại số nguyên $n \ge 2$ nào mà $f(n) < 2n$ hay không?
Giới hạn $\lim_{n \to \infty} f(n)/n$ có tồn tại hay không, và liệu nó có nhỏ hơn ngặt $2$ (chẳng hạn bằng $\pi/\sqrt{3} \approx 1.8138$ ) hay không?

Tài liệu tham khảo

Klaus Friedrich Roth (with an appendix by Paul Erdős) (1951). On a problem of formal logic · DOI:10.1112/jlms/s1-26.3.198
Richard K. Guy, Patrick A. Kelly (1968). The no-three-in-line problem · DOI:10.4153/CMB-1968-062-3
R. R. Hall, T. H. Jackson, A. Sudbery, K. Wild (1975). Some advances in the no-three-in-line problem · DOI:10.1016/0097-3165(75)90043-6