如何求解傅里葉17線難題？

01-11

作為後來聞名遐邇的法國數學家兼物理學家傅立葉（1768-1830），出身歐塞爾平民家庭，據說不到10歲時他就成了孤兒，後來是當地的教會收養了他，在這之後，傅里葉才顯露出了超常的數學天賦。
數學史料記載，傅立葉在14歲就讀完了法國著名數學家艾蒂安·貝澤特（étienne Bézout，也有譯成裴蜀的，比如裴蜀定理。）的數學專著。長大後，他經常與歐塞爾的數學教授通信交流數學。
傅立葉19歲那年，他向教授請教了這樣一個問題，大意是：如何在一個平面上畫17條直線，在不容許有三線共點的前提下，使得這些線條能有101個交點。

在ACM 訓練題庫中，有一道叫做《Fourier Lines》是這樣對這個問題進行描述的：How to draw 17 lines on a plane to make exactly 101 crossings, where each crossing belongs to exactly two lines.crossing belongs to exactly two lines ?
對傅立葉的傳記感興趣的朋友可以關注以下鏈接：
1.傅立葉詳細生平：Fourier biography
2.傅立葉簡介：The last major piece of the anatomic puzzle was put into place after
microscopic examination of the cochlea

七夕節補註：
怎樣畫一個好看的圖，四線譜！！！
用這種模型來處理傅立葉問題，其數學描述便是：
在平面上的N條線若被分為四類線簇即N=a+b+c+d，其中斜率分別0，+∞，1和-1的線簇中包含直線條數為a，b，c和d，求證是否能有X個交點的四線譜存在？比如圖表示的就是當N=10，X=35的四線譜。

感覺可以嘗試構造一下。

首先繪製兩兩相交的17條直線（任意三線不共點）。容易知道共有17C2=136個交點。由於需要101個交點，三線又不能共點，那麼只能通過平行來消去交點。

隨後我們總可以調整一些直線的方向，使它們相互平行，並且三三不共點。每一組有n條線的平行線，消去了nC2個交點。我們的目的是消去136-101=35個交點。這個問題轉化為了找到一些ni，滿足Σni&<=17，ΣniC2=35，ni&>=2。

直接求解是比較麻煩的，所幸數字不大，我們可以一一列舉kC2的值來湊。

2 1

3 3

4 6

5 10

6 15

7 21

8 28

9 36（9以及之後的都不要了）

接下來的事情就好辦了。

比如我們湊28+6+1=35

8+4+2=14&<17

那麼取三個不同方向，分別放置8、4、2條平行線；再找三個與上述三方向不同的三個方向，放置三條線，注意不要三線共點即可。

湊法有：

最大數為28：

28 6 1 （14）

28 3 3 1（16）

最大數為21：

21 10 3 1 （17）

最大數為15以下的湊法Σni似乎均大於17，不考慮。（如果有其他我漏了的解請務必告訴我謝謝。）

對於更加一般的情況（比如99交點怎麼湊？75個呢？能不能遍歷0到136？），我們可能需要解決更一般的情況，即求解滿足Σni&<=N，ΣniC2=M的{ni}。對於這種情況直接求解似乎很難，比較方便的就是通過如上所述類似於計數法的思路去湊解。那麼能不能湊出來呢？這就又轉化為另一個更一般的問題：

給定一個無窮正整數列{ai}，能否把任意一個正整數K表示為ai的某種線性組合。

對於ai=iC2，「某種線性組合」要求下標i之和小於等於某個數M，這就是本題的推廣；

對於ai=r^(i-1)，「某種線性組合」要求線性組合的係數取0～r-1的整數，這就是r進位計數法；

對於一個給定的ai集合，「某種線性組合」要求線性組合的係數取正負1或者0，這就是某類給定一些砝碼，稱取未知物品重量的問題；

對於ai=第i個素數；「某種線性組合」要求只能取兩項之和，這個問題似乎很難……

總之感覺進入了什麼不得了的地方……趕緊撤( ′ ▽ ` )?

最後以一段做題目時突然想到的奇怪古文作為結尾吧。

「彼節者有間，而刀刃者無厚；以無厚入有間，恢恢乎其於游刃必有餘地矣。」

先附上一張解的圖

看到這張圖應該就差不多懂我的構造方法了吧，將17條直線分成四組（已用四種顏色標註），同組直線相互平行，不同組直線兩兩不平行。這樣四組直線分別為7+5+3+2，交出的點數為7*5+7*3+7*2+5*3+5*2+3*2=101。

當然這不是這道題的唯一解，可以把17分成如下幾組：

6+5+5+1
7+5+3+2
8+3+3+2+1
8+4+2+1+1

寫個程序爆搜一下就能把這些解跑出來，代碼寫的太丑就不貼上來了。。

簡化一下，其實這道題就是在求解：求一 $n$ ，以及 $a_{1}$ , $a_{1},a_{2},...,a_{n}$ ，使得 $sum_{i=1}^{n}{a_{i} } =17$ 且 $sum_{i=1}^{17}{sum_{j=i+1}^{17}{a_{i} a_{j} } } =101$ 。（不知道求和符號有沒有用對，意思就是 $a$ 數組和為17，兩兩相乘和為101）

更一般的，對於任意的直線數 $E$ 以及交點數 $V$ ，同上就是求一 $n$ ，以及 $a_{1}$ , $a_{1},a_{2},...,a_{n}$ ，使得 $sum_{i=1}^{n}{a_{i} } =E$ 且 $sum_{i=1}^{E}{sum_{j=i+1}^{E}{a_{i} a_{j} } } =V$ 。