[关闭]
@cms42 2021-02-06T05:45:44.000000Z 字数 1628 阅读 586

猴子摘桃问题

问题符号化描述如下:

(约定以下全部讨论在值域内进行)
定义一函数 ,其中,显然这一函数并非对于所有都在域内有意义,函数有意义的充要条件是。
定义记号 表示对于进行次变换,即:


设对于某一确定,所有使在域内有意义的的集合为,其中最小的为。
给出、,求。

据说结论为,但我找了一圈似乎没有特别好的证明,遂尝试自行说明。这是萌新的第一次证明,多有不足之处,还请大佬批评指教。更简单的方法应该还有,希望能抛砖引玉。

T1.1 ,当且仅当

T1.2 若,则

T1.3 在T1.2约定的条件下,不存在且

T1.1正确性显然。T1.2利用数学归纳法说明如下:

时,结论正确性显然;

假设结论对于成立,对于,由于,由T1.1得,而

,由于,由归纳假设得,即,由T1.1得,归纳假设成立。

T1.3可利用反证法和数学归纳法说明:假设这样的存在,则

,

设,由函数性质可知。又由于,有。则由T1.1、T1.2可知存在满足,由归纳假设得,这与相矛盾。故假设不正确,不存在。

D1.1 将在进制下的表示中从右向左第位设为。即,,且对于任意正整数有。

在D1.1定义下,T1.2、T1.3可等价表述为:对于,的充要条件是对于有,或称在进制下它们的后位相等。

T1.4 ,或等价表述为:在进制下有位,末位为,其余各位为

不妨用归纳法说明。显然。
对于k,由于,显然,则有归纳假设我们有末位为,第至位均等于。设第位为,更高位为(显然当且仅当此时为最小值),由定义和进制下基本运算定义知,即原数去除末位减去去除末位后右移一位的值,则第位值为或(退位时)。由知,由归纳假设得第位应为,即:

或

解第一个方程得,舍去;解第二个方程得,即第位取值为,归纳假设成立。

则根据T1.4,所求的答案即

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注