初中竞赛题选讲 第一百六十九题解答

银行发行了一种硬币,一面是 H,另一面是 T.培神 有 枚这样的硬币，并把它们从左到右排成一行. 他重复进行以下操作: 如果存在有硬币 H 面朝上, 培神可以挑选连续的若干枚硬币(至少一枚)将它们] 翻面.如果所有硬币都 T面朝上，则终止操作.例如, 当 n=3 时，培神可能进行如下操作:

也可以按如下步骤操作:

对每一种初始排列 C,设  是培神最少需要进行 的操作次数,例如  对任意给定的 自然数 n,求 m(C)的最大可能值.

解:首先我们归纳证明, 对枚硬币, m(C)不超过
(i)显然,时,结论成立.
(ii)若对时,结论成立, 考虑的情况:
先用不超过步将前枚硬币全部翻成朝上, 此时最后两枚硬币无论是, 都可以用不超过一步翻成
由(i)(ii)知, 该结论对任意正整数都成立.

下面我们给出构造:
若枚硬币中从左往后起第奇数枚为, 第偶数枚为, 则至少需要操作次
证明如下: 定义数列如下:
若左起第枚硬币面朝上, 则,否则
特别地,
定义数列
于是,每次操作至多能改变两个的值
而若枚硬币中从左往后起第奇数枚为, 第偶数枚为时,
当所有硬币都是朝上时,
于是我们从前一种状态到后一种状态至少需要操作次

综上,求 m(C)的最大可能值为.