※ 引述《hiei81 (寶貝。永遠)》之銘言：
: 據說是ARML的問題...
大驚...
: Let S = {f(k) | f(1)=i,f(2)=j,f(n+2)=f(n+1)+f(n) for all n belongs to N}
: i,j
: i<j, i,j belongs to N
: Could N be partitioned by infinite S ?
: i,j
: 即存在無限個S，彼此之間交集為空集合，聯集為所有自然數
: Ex: S = {2,5,7,12,19,...}
: 2,5
好玩的題目
剛才想到了一個解法
和以前某年IMO某題的解法幾乎一樣
(IMO1993-5)是否存在一個 N->N 的嚴格遞增函數使
f(1)=2 and f(f(n))=f(n)+n for all integers n
這題通常的解法是用高斯函數構造(http://www.kalva.demon.co.uk/imo/imo93.html)
另一個大致如下(Note:下面寫的是前面那題的證明,前面那題成立則這題顯然成立)
注意若a<b<c<d<a+c則S 和S 不相交
a,c b,d
首先取S ,接下來以3-5,5-8,8-13,13-21,...為一個區間做以下操作
1,2
在每個區間中,設這個區間被另外n-1個數列分成n區塊
將每個區塊中的第i個空位和下一個區間中的對應區塊的第i個空位設為一個數列
如此便可取遍所有正整數
至於不會重複的原因by induction可得
(induce the statement:兩個數列在區間中的距離遞增)
XD我又寫了一個很簡略的證明...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.32.78.42