本帖最后由 hbghlyj 于 2019-7-25 22:12 编辑
回复 3# hbghlyj
(12)先证明若最后留下的数全等于k，k只能取任何形如$2^t≥n$(t为正整数)的正整数:对于任何非负整数p≥q,p+q+p-q=2p,因此总和不减少,k≥$\frac{n+1}2$≥2.若p+q与p-q能被奇数d(≥3)整除,则p+q+
p-q=2p,p+q-p-q=2q也被d整除,从而p,q都被d整除,因此若k能被d(≥3)整除,则一开始1,2,3…,n都能被奇数d(≥3)整除,这是不可能的.故k只可能为$2^t$(t为正整数),且每次操作后,黑板上的最大数不减小,所以$k=2^t≥n$.
再证明对于各种情况，只有甲操作时将所有数变为k的最小操作数u不小于对于各种情况，只有乙操作时将所有2的幂去除的最小操作数的最大值v。
注意到$(2^a,2^a)→(0,2^{a+1})$以及$(0,2^c)→(2^c,2^c)$,所以,不难得到:如果黑板上写的数全是2的幂(包括零次幂),它们的指数都不超过$b_0$,并且其中至少有2个相等的小于$2^{b_0}$的数,那么经过有限步操作之后,必可使所有的数都变成$2^{b_0}$.
因此,我们只需对n≥3用归纳法来证明下列结论成立:由数组1,2…,n出发,经过有限步操作,可使所有n个数都变成2的方幂,其指数都不超过$b_0$,并且其中至少有2个相等的小于$2^{b_0}$的数,这里$b_0$为满足$2^{b_0}≥n$的任意正整数.
因为(1,3)→(2,4),故知n=3,4时结论成立.又因(3,5)→(2,8),(2,6)→(4,8),(1,3,5,7)→(6,2,8,8)→(8,4,8,8),故知n=5,6,7,8时结论也成立,设结论对3≤n≤m-1
(m≥9)的所有正整数n结论成立,再证明对n=m结论也成立,设$m=2^{b-1}+r$,其中b≥4,1≤r≤$2^{b_0-1}$.若r=$2^{b-1}$,即m=$2^b$,则对(1,2…,m-1)应用归纳假设,便知结论成立.
下设1<r≤$2^{b-1}$.这时我们依次对数对(p,q)=$(2^{b-1}-i,2{b-1}+i)$(i=1,2…,r)进行操作,于是得到的n个数可分为3类:
(1)1,2,3,...,$2^{b-1}-r-1$(黑板上未经操作过的数,若$r=2^{b-1}-1$时,这部分数不存在).
(2)2,4,6,…,2r(这些数由差|p-ql得到).
(3)$2^{b-1},2^b.….2^b$(这些数由和p+q及$2^{b-1}$得到).
若$2^{b-1}-r-1≤2$,则$2r≤2$,则$2^{b-1}≤r+3≤4$这与b≥4矛盾:故(1)(2)两组中至少有一组中的数的个数不少于3.若(1)(2)两组中数的个数都不小于3,由归纳假设知结论成立.若(1)(2)两组中数的个数不小于3，则对该组使用归纳假设，而其余两部分则已全是2的方面，从而结论也成立
....未完待续 |
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
发表于 2019-7-25 18:11
|