ARML思考賽兩題

提供一個想法參考看看。
依題意，構成矩形的充要條件，即在兩個相異的 x坐標上各存在兩點，其有相同的 y坐標數對，如:(1,4),(1,5)與(2,4),(2,5)。在 L(m,n)中，y坐標數對共有 C(n,2) = n(n-1)/2 個。如果取的點數夠多，將無可避免地在兩個相異的 x坐標上存在相同的 y坐標數對(鴿籠原理)，從而構成矩形。依此思維，以下考慮取到最大的 k值而不構成矩形的"策略"。
考慮兩個相異的 X1 與 X2 坐標上各已取了 a個與 b個點 (0 <= a < b)。現要增加一個"新點"，比較取在 X1 與 X2 坐標上的情形，前者增加的 "y坐標數對"數量較後者少。這是由於 C(n,2) = n(n-1)/2 呈現階差，亦即 C(3,2)-C(2,2) < C(4,2)-C(3,2) < C(5,2)-C(4,2) ...(用代數或巴斯卡三角形皆簡明)，而當 a,b 中存在 0 或 1 時亦然。也就是說，增加新點時，把它取在"已取點最少"的 x坐標上，可使"y坐標數對"增加(消耗)較慢，從而在這個觀點上可容納較多的點。當在此原則下取了 k點，這 k點不構成矩形，而再增加第(k+1)點將使"y坐標數對"數量大於 n(n-1)/2 個時(從而必構成矩形)，即是最大的 k值。
依以上推論，簡言之，依次在不同 x坐標上取 1點，再取第 2點，...，直到"y坐標數對"數量將大於 n(n-1)/2 個時停止，若此時取的 k個點不構成矩形，則即是最大的 k值。(注意: 因為"y坐標數對"並不一定彼此獨立不相關，所以仍必須說明此 k個點不構成矩形)。
第 1 至 6 題皆可用此結論簡明答出。
5. 試求 f(7,7)，並證明你的答案。
解:

C(7,2) = 21，即有 21 個"y坐標數對"可用。依上述原則，最佳策略為: 依序在 7 個相異 x坐標上取 1個點，再取第 2個點，再取第3個點 (共21個點)，此時用了 7*C(3,2) = 21 個"y坐標數對"。以下若再取第22點時，必構成矩形。所以 f(7,7) < 22。下面舉例說明此 21個點是存在的:
x = 1, y = 1,2,3
x = 2, y = 1,4,5
x = 3, y = 1,6,7
x = 4, y = 2,4,6
x = 5, y = 2,5,7
x = 6, y = 3,4,7
x = 7, y = 3,5,6

因此，f(7,7) = 21 。
6. 當 m > = n(n-1)/2 時，試求 f(m,n)，並證明你的答案。
解:

"y坐標數對"有 C(n,2) = n(n-1)/2 個。先依序在 m 個相異 x坐標上取 1個點 (共 m 個點)，接著依序再取第 2個點，當取了 n(n-1)/2 個 "第 2個點"時，n(n-1)/2 個"y坐標數對"就用完了 [此時共取了 m + n(n-1)/2 個點]。由於這個情形下，n(n-1)/2 個"y坐標數對"彼此獨立不相關，所以一定可以把存在的 n(n-1)/2 個具有相同 x坐標的"雙點組"調整為與 n(n-1)/2 個"y坐標數對"成一對一關係，從而不構成矩形。(或者反過來說，當初可依 n(n-1)/2 個相異的"y坐標數對"來選點)。

因此 f(m,n) = m + C(n,2) = m + n(n-1)/2。

到下面的網址看看吧

▶▶http://candy5660601.pixnet.net/blog

到下面的網址看看吧

▶▶http://candy5660601.pixnet.net/blog

參考下面的網址看看

http://phi008780520.pixnet.net/blog

參考下面的網址看看

http://phi008780520.pixnet.net/blog

參考下面的網址看看

http://phi008780520.pixnet.net/blog

參考下面的網址看看

http://phi008780520.pixnet.net/blog

發問者你好：

幫你整理好了，詳細資料在這邊

http://adf.ly/jXLsv

希望其他回答者也認同我意見^^

>這家不錯*****買幾次啦真的一樣
乸呮乨使傖