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