问题引入

小学生林朝夕和党爱民备战奥数夏令营，做练习题时遇到以下问题：
问题：工人为你工作七天的总报酬是一根金条，你每天晚上必须为工人结一次账，不能赊账也不能多付，请问金条最少切割多少次才能实现。
聪明的林朝夕同学快速给出了答案：两次，策略如下：将金条按照1:2:4的比例分成3分，第一天给1，第二天给2收回1，第三天再给1，第四天给4收回1和2，第五天再给1，第6天给2收回1，第七天给1。

思考：如果将本问题中的7天改成n天，其他条件不变呢？

问题描述

问题：工人为你工作n天的总报酬是一根金条，你每天晚上必须为工人结一次账，不能赊账也不能多付，请问金条最少切割多少次才能实现。
分析：假设将金条切割成k份是一种可行切割，对于可行切割的定义如下：
定义：若切割k次以后每一份的占比分别为$a_0,a_1,...a_k$, $a_i\in N\ast and1\le a_i\le n$，且${\sum }_0^k{a}_i=n$, 若对任意在区间[1，n]之间的正整数$m$都存在 x 0 ≤ i ≤ k ∈ { 0 , 1 } x_{0\le i \le k} \in \{0, 1\} x0≤i≤k​∈{0,1}，s.t. $m={\sum }_0^k{x}_i{a}_i$，则成该分隔为一种k阶可行分隔。
可行分割存在以下性质：
性质1：若$a_0,a_1,...a_k$是n的一种k阶可行分割，当$1\le a_{k+1}\le n+1$时，$n+a_{k+1}$存在k+1阶可行分割，且$a_0,a_1,...a_k,a_{k+1}$为其一种k+1阶可行分割。
性质2：若$a_0,a_1,...a_k$是n的一种k阶可行分割，当$a_{k+1}>n+1$时，$n+a_{k+1}$ 不存在k+1阶可行分割。

证明：
当$a_{k+1}>n+1$时, 显然正整数n+1无法表示表示成 ∑ 0 k + 1 x i a i x 0 ≤ i ≤ k + 1 ∈ { 0 , 1 } \sum_0^{k+1} x_ia_i\quad x_{0\le i \le k+1} \in \{0, 1\} ∑0k+1​xi​ai​x0≤i≤k+1​∈{0,1}的形式（${\sum }_0^k{x}_i{a}_i\le nand{a}_{k+1}>n+1$），故性质2得证。
当$1\le a_{k+1}\le n+1$时，由于$a_0,a_1,...a_k$是n的一种k阶可行分割，
当$m\le n$时，存在 x 0 ≤ i ≤ k ∈ { 0 , 1 } x_{0\le i \le k} \in \{0, 1\} x0≤i≤k​∈{0,1}，s.t. $m={\sum }_0^k{x}_i{a}_i$
当$n<m\le n+a_{k+1}$时，$m-a_{k+1}\le n+a_{k+1}-a_{k+1}=n$且$m-a_{k+1}\ge n+1-a_{k+1}\ge 0$，故存在 x 0 ≤ i ≤ k ∈ { 0 , 1 } x_{0\le i \le k} \in \{0, 1\} x0≤i≤k​∈{0,1}，s.t. $m-a_{k+1}={\sum }_0^k{x}_i{a}_i$，即$m=a_{k+1}+{\sum }_0^k{x}_i{a}_i$，故性质1得证明。
思考：如何在所有的可行分割当中找出分割次数最少的分割呢，很自然的我们可以想到就是让分割后的每一份$a_i$尽可能更大，根据性质1和性质2，分割后的$a_i$最大不能超过${\sum }_0^{i-1}{a}_t+1$,因此将$a_i={\sum }_0^{i-1}{a}_t+1$作为临界值，这就变成递推数列的问题了，通过计算可以得出：当$a_i=2^{i}i\in 0,1,...,k-1and{a}_k=n-2^k+1$时，分割达到最优。

更进一步

回看以上过程，由于每个$x_i$都是在{0,1}之间取值，直觉告诉我们这个问题也许能与二进制扯上关系，实际上，$1,2,2^2,...2^k$本身可以看成是整数空间{1…2^{k+1}-1}中的一组线性无关且完备的基，且当$x_i$在{0,1}之间取值时，该整数空间不可能存在更低阶的基，否则将这些值按从小到大排列时，一定存在后一个值比前一个值两倍加1还大的情况，那么根据上面关于性质1和性质2的证明，前一个值得2倍加1就无法用这组值线性表示，因此就不能构成一组基。
这样的话，该问题就转化成一个求二进制的问题，当十进制整数表示成二进制是有多少位，那么其最小分割次数就是相应的位数减一。