主题
Search

No-Three-in-a-Line-Problem

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

对于 2<=n<=32，可以选择 2n 个格点，其中 x,y in [1,n]，使得没有三点共线（其中“直线”指的是平面上的任何直线——不仅仅是水平或垂直线）。对于 n=1, 2, ...，不同解的数量（不包括反射和旋转）为 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769)。对于较大的 n，据推测最多只能选择 (c+epsilon)n 个格点，且没有三点 共线，其中

c=1/3pisqrt(3)
(1)
approx 1.813799...
(2)

(OEIS A093602；Guy，私人通讯，2004年10月22日)，更正了 Guy 和 Kelly (1968) 以及 Guy (1994, p. 242) 的发现，他们发现 c=(2pi^2/3)^(1/3) approx 1.87。

52x52 No-three-in-a-line

已知的最大解是对于 n=52，由 Flammenkamp 发现并在上文展示。Flammenkamp 给出了数千个对于 n<52 的解。

另请参阅

整格， N-簇， 井字棋

使用 Wolfram|Alpha 探索

参考文献

Adena, M. A.; Holton, D. A.; 和 Kelly, P. A. "Some Thoughts on the No-Three-In-Line Problem." 收录于 组合数学：1977年8月16-27日在堪培拉举行的国际组合理论会议论文集，pp. 6-17, 1974。Flammenkamp, A. "Progress in the No-Three-In-Line Problem." 组合理论杂志A辑 60, 305-311, 1992。Flammenkamp, A. "Progress in the No-Three-In-Line Problem. II." 组合理论杂志A辑 81, 108-113, 1998。Flammenkamp, A. "The No-Three-in-Line Problem." http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html。Gardner, M. 彭罗斯瓷砖与活板门密码...以及矩阵博士的回归，再版 纽约：W. H. Freeman, p. 69, 1989。Guy, R. K. "Unsolved Combinatorial Problems." 收录于 组合数学及其应用：1969年7月7-10日在牛津大学数学研究所举行的会议论文集 (Ed. D. J. A. Welsh). 纽约：Academic Press, pp. 121-127, 1971。Guy, R. K. "The No-Three-in-a-Line Problem." §F4 收录于 数论中未解决的问题，第二版 纽约：Springer-Verlag, pp. 240-244, 1994。Guy, R. K. 和 Kelly, P. A. "The No-Three-in-Line-Problem." 加拿大数学公报 11, 527-531, 1968。Guy, R. K. 和 Kelly, P. A. "The No-Three-Line Problem." 研究论文 33, 卡尔加里大学数学系，卡尔加里，艾伯塔省，1968年1月。Pegg, E. Jr. "Math Games: Chessboard Tasks." 2005年4月11日。 http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html。Sloane, N. J. A. 序列 A000769/M3252 和 A093602，收录于“整数数列在线大全”。

在 Wolfram|Alpha 中被引用

No-Three-in-a-Line-Problem

请引用为

Weisstein, Eric W. "No-Three-in-a-Line-Problem." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/No-Three-in-a-Line-Problem.html

主题分类