Question

高中奥数题

正整数可以分为两个互不相交的正整数子集:
｛f(1),f(2),f(3)...f(n)...｝;｛g(1),g(2),g(3)...g(n)...｝
其中f(1)<f(2)<f(3)<...<f(n)<...
g(1)<g(2)<g(3)<...<g(n)<...
且 g(n)=f(f(n))+1 (n>=1)
求:f(240)
要求完整过程.

Answer 1

因为正整数可以分为两个互不相交的正整数子集:
且g(n)=f(f(n))+1,故：g(1)=f(f(1))+1＞1
故：f(1)最小,故：f(1)＝1
故：g(1)＝2
故：f(2)、g(2)均大于等于3
又：g(n)=f(f(n))+1,故：g(2)=f(f(2))+1＞f(3) ＞f(2)
故：f(2)＝3,f(3)＝4
故：g(2)=f(f(2))+1＝f(3)＋1＝5
又：g(3)=f(f(3))+1＝f(4)＋1＞f(4)
故：f(4)＝6,g(3)＝7
又：g(4)=f(f(4))+1＝f(6)＋1＞f(6) ＞ f(5)
故：f(5)＝8,f(6)＝9,g(4)＝10
又：g(5)=f(f(5))+1＝f(8)＋1＞f(8)＞f(7)
故：f(7)＝11,f(8)＝12,g(5)＝13
又：g(6)=f(f(6))+1＝f(9)＋1＞f(9)
故：f(9)＝14,g(6)＝15
又：g(7) ＝f(f(7))+1＝f(11)＋1＞f(11)＞f(10)
故：f(10)＝16,f(11)＝17,g(7)＝18
又：g(8) ＝f(f(8))+1＝f(12)＋1＞f(12)
故：f(12)＝19,g(8)＝20
又：g(9) ＝f(f(9))+1＝f(14)＋1＞f(14)＞f(13)
故：f(13)＝21,f(14)＝22,g(9)＝23
又：g(10) ＝f(f(10))+1＝f(16)＋1＞f(16)＞f(115)
故：f(15)＝24,f(16)＝25,g(10)＝16
我们看看f(n)的规律：
f(1)＝1,f(2)＝3,f(3)＝4,f(4)＝6,f(5)＝8,f(6)＝9,f(7)＝11,f(8)＝12,f(9)＝14,f(10)＝16,f(11)＝17,f(12)＝19,f(13)＝21,f(14)＝22,…
（1、3、4、6,8,9,11,12）、（14,16,17,19,21,22,24,25）、…(378,…..,389)
故：f(240)=f(8)+13×(240/8-1)=12+13×(30-1)=389

Answer 2

f(n+1)=f(n)+1，如果 n 没有在之前的 f(x) 中出现过；
f(n+1)=f(n)+2，如果 n 在之前的 f(x) 中出现过（即：存在 x 使得 f(x)=n）。
这是因为如果没有出现过，那么 f(n)+1 一定不在 g 的范围里，所以在 f 的范围里；反之如果出现过，则存在 x0 使得 f(x0)=n，那么 g(x0)=f(n)+1，被跳过，因此只能取 f(n)+2。（容易证明 g 不存在相邻的两数，所以一定是 f(n)+2）。
然后写个程序计算，发现答案是 388……
具体结果如下：（8个分一组是因为楼主答案发现的“规律”是8个一组。其实那个规律到第三组就不成立了……）