Re: [讨论] 被问倒了XD

楼主: darkseer   2004-09-23 16:34:57
※ 引述《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我又写了一个很简略的证明...

Links booklink

Contact Us: admin [ a t ] ucptt.com