Question

设f：N→N是一个正整数集N的一一映射．
（1）证明存在一个由正整数a，a+d，a+2d组成的等差数列，这里d＞0，使f（a）＜f（a+d）＜f（a+2d）．
（2）一定存在一个等差数列a，a+d，…，a+2003d，这里d＞0，使f（a）＜f（a+d）＜…＜f（a+2003d）吗？

Answer 1

分析：（1）可以采用反证法证明，假设不存在满足要求的等差数列，由于1=f（a）＜f（a+2ⁱ），其中i是非负整数，则必有f（a+2ⁱ）＞f（a+2ⁱ⁺¹）．但f（a+1）是一个确定的正整数，且f：N→N是一个正整数集N的一一映射，从而小于f（a+1）的正整数有有限个即可得到矛盾，即可证明；
（2）构造映射：1→1，||2→2，||4→3，3→4，||8→5，7→6，6→7，5→8，||16→9，15→10，14→11，13→12，12→13，11→14，10→15，9→16，||以象f满足2^n-1＜f≤2ⁿ分成若干档，其中n是非负整数．由抽屉原理知，必定在后三档里存在某一档至少被选择了两个．即可证明不一定存在满足要求的等差数列．

解答：证明：（1）设f（a）=1，考虑a+1，a+2，a+4，a+8，a+16，a+32，，显然其中任意相邻两项与a都构成等差数列，在这些等差数列中，必存在一个满足要求．这是因为：
假设不存在满足要求的等差数列．由于1=f（a）＜f（a+2ⁱ），其中i是非负整数，则必有f（a+2ⁱ）＞f（a+2ⁱ⁺¹）．
即f（a+1）＞f（a+2）＞f（a+4）＞f（a+8）＞f（a+16）＞f（a+32）＞．但f（a+1）是一个确定的正整数，且f：N→N是一个正整数集N的一一映射，从而小于f（a+1）的正整数有有限个，故在f（a+2^j）中必存在某一个f（a+2^k），满足f（a+1）＞＞f（a+2^k-1）且f（a+2^k）＞f（a+1），其中j，K∈N．则f（a）＜f（a+2^k-1）＜f（a+2^k），这时公差d=2^k-1的等差数列a，a+2^k-1，a+2^k满足要求．矛盾！
（2）不一定存在．
构造映射：1→1，||2→2，||4→3，3→4，||8→5，7→6，6→7，5→8，||16→9，15→10，14→11，13→12，12→13，11→14，10→15，9→16，||以象f满足2^n-1＜f≤2ⁿ分成若干档，其中n是非负整数．上述映射中“||”为分档线．
设f（a+2003d）在第i档，而第i档的最大的象是2^i-1．分析各档里象的情况如下：

由于第i-1档里象的个数为2^i-2-2^i-3=2^i-3，又每档里最多只能选择一个，否则将出现f（a+id）＞f（a+（i+1）d），故d＞2^i-4．从而前i-3档里最多只能选择一个．故总共最多只能选择四个．
倘若从中选择五个及五个以上，由抽屉原理知，必定在后三档里存在某一档至少被选择了两个．
因此题设中的映射不一定存在满足要求的等差数列．

点评：本题主要考查了反证法，以及抽屉原理，正确构造映射是证明的关键．