※ 引述《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