A 题 决策单调性证明

最小执行次数 可以表示为：

证明： 在 时取到最小值。

解析解

首先，打开 oeis，输入前几项 "0, 2, 3, 6, 8"，得到对应数列 A097383

发现有个解析解

其中 为 的二进制长度，即

这个式子怎么来的不做详细叙述，只讨论一下 取最小值的位置

凸函数

思路： 不是凸函数，但是这个式子看起来和凸函数能搭上关系。为了用上凸函数的性质，思路是找到一个和 极其接近的凸函数，并对二者的差进行讨论。

令 ，容易看出 成立

引理1. 是一个凸函数

证：

令

当 不为 2 的幂次时，那么 ，有

当 为 2 的幂次时，那么 ，即 ，有

因此， 单调不减， 是一个凸函数

引理2. 对于一个凸函数， 满足：

证：

当 时，，即 ，所以 越靠近中间越小。

对 n 进行分类讨论，联系 和

回顾一下 ，也就是 为偶数时 ， 为奇数时

① 为偶数

因为 和 一定是一奇一偶，那么有

因为 和 也一定是一奇一偶，那么有

所以 为偶数时， 在 取到最小值

②

此时 为奇数，那么有

而 ，因此

而根据定义，有

所以有

所以 时， 在 取到最小值

③

这是唯一特殊的情况，分成 , , 三种讨论。

令

，即

那么有

，即

那么有

根据 的定义和之前的推论，有 ，其中

两式相减，有

所以 （换句话说，这时候取中点也就是 不是最优的）

，即

那么有

不可能更优

总结一下，即

所以 时， 在 取到最小值

结论

综上所述，对于 ，

时， 在 取到最小值

时， 在 取到最小值

把对称性考虑上，再合并这两种情况就是