【討論】一個看不出數學的數學題

[曾阿牛 10]

從1到200中 挑選出n個(不同的)正整數

如果 希望 就算任意挑選 在這被挑選到的n個數字中

存在有五個數字 a, b, c, d, e 滿足 a-b = b-c = c-d = d-e 的話

這 n 至少要多大 才能保證存在那樣的五個數字?

__________________________________________________

以下做一點討論...

n 不會是 6 因為任意挑6個數字 無法滿足題目要求

譬如挑 11, 14, 17, 20, 24, 28. 這6個數字中 不存在五個數字 滿足等差式

如果 n 是 200 從 1到200中 挑選出200個數字出來

則 7, 8, 9, 10, 11 一定會被挑到 而且 11-10 = 10-9 = 9-8 = 8-7

所以 n 是 200 的話 滿足要求 但顯然 200不是最小的

n 是 199 的話 也滿足題目要求 那 n 究竟能多小 但又不能小到不滿足要求

[Lin彧 10]

這　我也只是推測　依照題目看來，至少要１９６個數（４個沒被選到）

不管這四個漏在哪，一定都會有一組是等差數

（因為他是要確保１００％有，故１９６我推測應該是最小了）

Ａ－Ｂ＝Ｂ－Ｃ＝Ｃ－Ｄ＝Ｄ－Ｅ

這應該就是等差吧!!!

[貓喵 10]

剛剛發錯見解...

等等更改= =

[夢境的行旅 10]

很難啊。由其是嚴格要說明上界在哪裡更是困難。

本題該不會跟拉姆西(齊)數有關吧？link:wiki

看一個簡單的例子：1 到 10 要讓沒有連續三個數成等差

1 2 3 4 5 6 7 8 9 10

我只要把3 4 7 8 劃掉就可以了

1 2 3 4 5 6 7 8 9 10

反過來，只要取7個數就可以保證一定有三項成等差。數量相對算是少的。

[夢境的行旅 10]

至於十五個數，不讓任何四個數成等差數列的辦法。我甚至很難驗證這樣是不是最少的方法。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

槓掉4 5 6 、10 11 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

沒辦法，難道要像n-Queen問題一樣驗證嗎？

[曾阿牛 10]

1 到 10 要讓沒有連續三個數成等差

1 2 3 4 5 6 7 8 9 10

我只要把3 4 7 8 劃掉就可以了

呃... 不是唷　　把3 4 7 8 劃掉 即挑選 1, 2, 5, 6, 9, 10

這六數中 有三數 1, 5, 9 ( 或 2, 6, 10 ) 形成等差唷

[夢境的行旅 10]

重來一次，畫成這個略顯笨重的圖。是1~10中所有構成三項等差的數組。

用「劃掉」的方法怎麼找都是5個數，例如刪掉2 3 5 7 8，才能讓其中不留下一個3項等差數列。

有沒有人能提供新的想法啊？我覺得我走到一條很艱難的路了。

[曾阿牛 10]

好吧　給個新想法　這是在一本教"鴿籠原理"的書中 提到的問題

書裡舉了幾個問題　說是"鴿籠原理可以解決像是這樣的問題"　這問題是其中之一

但沒有給真正的做法　如果想多了解鴿籠原理的話　這裡有個不錯的介紹文章鴿籠原理

但　我的老師說過　鴿籠原理　本身的敘述很簡單　但應用起來可以非常的詭異 非常的難

難在　你不知道誰當鴿子　誰當籠子

[夢境的行旅 10]

裡面介紹到所有定理都牽涉到n個「不相交的子集」，但在這題的情況似乎會形成「籠子」的各種數列a b c d e是互相交錯的。

[黃昏Dacapo 10]

今天早上起床躺在床上似乎想到怎麼解

到學校完整的算一算就出來了

得到的答案應該是97

我是先討論公差

如果要讓公差為1的五個數不存在的話

毎隔4個就要挖一次洞

xooooxooooxooooxoooo...(x=空洞)

接著就會發現公差=2或3或4的也都不存在，一定會挑到空洞

然後就可以推導公差=5k+1,5k+2,5k+3,5k+4都不可能

所以剩下5k

緊接著把oooo看成一小坨O

這樣總共有40坨

依照剛剛的方法再排成

XOOOOXOOOOXOOOO....

再把OOOO看成一大坨xd

就可以排成

:|xdxdxdxd:|xdxd

剩下6個xd

總數=6*4*4=96

因此，只要再隨便塞一個回去就一定會有等差數列了(總覺這一步才像鴿籠原理)

故得97

不知道這樣對不對呢?

[曾阿牛 10]

個人認為 您的想法是對的 但要修正一個小地方

從您的最後一步來看

『把OOOO看成一大坨xd　就可以排成　:|xdxdxdxd:|xdxd　剩下6個xd』

當　有八個xdxdxdxdxdxdxdxd 的時候　不需要挖掉兩個　只要挖去第五個xd即可滿足所求

所以呢　將您的方法　改成ooooxoooox.... 重頭做一次　變成

毎隔4個挖一次　則挖掉 40

挖掉8小坨　則挖掉 4x8=32

挖掉1大坨　則挖掉 4x4x1=16

故　剩下　200-40-32-16=112　再塞一個回去　即是113個

感謝　黃昏Dacapo　提供想法