果樹問題猜想與構造

來自專欄遇見數學36 人贊了文章

外行看熱鬧，內行看門道。為了保證文章的嚴謹性內附許多證明，如果對於數學證明感到不適，可以只看方法。如果對於方法也感到不適，可以只看圖片和結論。如果對於文章有疑問或是質疑歡迎在評論區指出，小編會給予回復，感謝大家的支持。

先從一個小學問題談起

有10個小朋友，每一排有4個人，一共有5排，問10個小朋友應該怎麼站？

人數比較少，算是簡單題。

那就問一個中學題：

有16個點，每條線上有且僅有4個點，問最多能夠組成多少條線？

12條線，這是小編能夠想到最多的了。可是......

答案竟然是15，好，還有這種操作我知道這遊戲怎麼玩了。趕緊進入正題。

problem boss：有p個點，每條直線的點的個數有且僅為n，直線的條數為m。問最多有多少條直線？

這個問題早在1821年被 J.Jackson 在《Rational Amusement to Winter Evening》書中提出。原文如下:

Fain would I pant a grove in rows.

我欣然願意將果園種成幾排

But how must I its form compose,

但我怎麼將果樹

With three trees in each row,

擺成每排3個

To have as man rows as trees.

能使行和樹一樣多

Now, tell me, artists, if you please:

現在，藝術家請告訴我：

This all I want to know

這是我全部想知道的

當n=3的時候，該問題被成為了orchard-planting problem（wikipedias Orchard-planting problem）。在近200年的時間中，一個看似簡單問題卻引來了無數的卓越的數學家的思考，至今未能找到問題的答案，也未能給出一個明確的通項公式，更不能給出一個漂亮的構造。在這裡這篇文章給給出幾個構造的方式。（構造引用Cultivating New Solutions for the Orchard-Planting Problem）

先看一看數學家對於這個問題的進展在The On-Line Encyclopedia of Integer Sequences? (OEIS?) 中 A003035 - OEIS 所列出的已知的數，在網站中該數列被評為nonn（自然數）,nice（精彩）,hard（極難）。到1974年，Burr , Grunbaum and Sloane 給出了答案最準確的上界和下界。

列表如下

可以看出要完成整個的問題的路還有很長呀

先從最簡單的開始討論

下面在解決p>7的情況

構造方法1 湊配法

對於給定的點數p，讓q= ?(p-1)/2?；選擇{-q,-q+1,…,q}的一個三元子集使得元素的和為0（modp）。下圖給出了p=8到p=14的所有子集。

下面解釋上圖的作用，將每一個點標個號，把3個點和為0的數放在一條線上。效果如下圖。

發現條數還不夠，其實缺了4 + 6 + 7 = 17。膜17餘0的數還沒有考慮到，所以將這些點調整一下放在一條線上，結果如下圖

點評：這種方法看技術和運氣，但具有一定的美感。

構造方法2 向量法

在三角形中建立質心坐標系http://mathworld.wolfram.com/Orchard-PlantingProblem.html.

定理：在質心為O的三角形ABC中選取一點P

需證

證明：

所以在可以把三角形內的一個點變為三維坐標

然後將坐標化簡，如頂點為（1,0,0）（0,1,0）和（0,0,1）將（1/3,1/3,1/3）化為（1,1,1） 將（1/6,1/2,1/3）化為（1,3,2）分數化為最簡正整數。

這個工具的神奇之處是可以用向量來代表直線，如直線為（a,b,c）則直線上任意一點（A,B,C）有aA+bB+cC等於0。雖然小編在幾何觀點下無法理解這個方程，但是感覺很厲害。

下面只需要把過三角形的所有直線求出來，這樣直接求直線的交點就可以。

下面是網友的圖片展示環節（ http://community.wolfram.com/groups/-/m/t/947771 ）

數不過來了，不過挺漂亮的……

方法三 三次函數方程法

在三次函數y=x3中，{-7，-6，…，7}中加起來等於0的數正好在一條直線上。

比如{2，3，-5}是一個和為0的集合。那麼這三個點的坐標為，（2,8）、（3、27）、（5、125）可以看出來這三個點在一條直線上。你不信你算。

聽起來挺厲害的，其實你要是稍微會一點一元三次函數韋達定理其實就是秒證的…….

下面就可以來去構造方程求解

其中{-4,-3,-2,-1,0,1,2,3,4}皆為三次函數上的點，其中任意的三元和為0子集代表一條直線。

在中心對稱中，點7可以有直線16,25,34上交點求出。

解出的解為

到現在15點產生25條線，但是15點最少產生31條線，那麼還剩下六條線分別為{-7，-6，-2}，{-7，-5，-3}，{-6，-5，-4}，{2,6,7}，{3,5,7}，{4,5,6}

把這些點帶入用行列式等於0去解方程得到

發現每一項湊巧有一項–e + e2 + f – e f + f2 – e f2 + f3 = 0。那麼把e=φ（黃金分割比）f=-1代入設(a,b)=(1,1),(c,d)=(1,-1)得到這樣的圖像

是不是有點丑，反正abcd是可以改的那麼不妨就換幾個數好了。

好看多了吧15點 31線 每條線3個點

最後wolfram作者成功把9~28點的構造全部完成

在那篇作者的艱辛工作後得到了無數的答案，雖然離最終的結果還很遠，但是這種堅持不懈的精神與對於審美追求值得每一個人學習。希望這篇文章能夠激發讀者的思考，期待讀者能夠為這個問題找到答案。

推薦閱讀：