问题引入
小学生林朝夕和党爱民备战奥数夏令营,做练习题时遇到以下问题:
问题:工人为你工作七天的总报酬是一根金条,你每天晚上必须为工人结一次账,不能赊账也不能多付,请问金条最少切割多少次才能实现。
聪明的林朝夕同学快速给出了答案:两次,策略如下:将金条按照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_0,a_1,...a_k a0,a1,...ak, a i ∈ N ∗ a n d 1 ≤ a i ≤ n a_i\in N* and\quad 1\le a_i \le n ai∈N∗and1≤ai≤n,且 ∑ 0 k a i = n \sum_0^k a_i=n ∑0kai=n, 若对任意在区间[1,n]之间的正整数 m m m都存在 x 0 ≤ i ≤ k ∈ { 0 , 1 } x_{0\le i \le k} \in \{0, 1\} x0≤i≤k∈{0,1},s.t. m = ∑ 0 k x i a i m =\sum_0^k x_ia_i m=∑0kxiai,则成该分隔为一种k阶可行分隔。
可行分割存在以下性质:
性质1:若 a 0 , a 1 , . . . a k a_0,a_1,...a_k a0,a1,...ak是n的一种k阶可行分割,当 1 ≤ a k + 1 ≤ n + 1 1\le a_{k+1} \le n+1 1≤ak+1≤n+1时, n + a k + 1 n+a_{k+1} n+ak+1存在k+1阶可行分割,且 a 0 , a 1 , . . . a k , a k + 1 a_0,a_1,...a_k,a_{k+1} a0,a1,...ak,ak+1为其一种k+1阶可行分割。
性质2:若 a 0 , a 1 , . . . a k a_0,a_1,...a_k a0,a1,...ak是n的一种k阶可行分割,当 a k + 1 > n + 1 a_{k+1} \gt n+1 ak+1>n+1时, n + a k + 1 n+a_{k+1} n+ak+1 不存在k+1阶可行分割。
证明:
当 a k + 1 > n + 1 a_{k+1} \gt n+1 ak+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+1xiaix0≤i≤k+1∈{0,1}的形式( ∑ 0 k x i a i ≤ n a n d a k + 1 > n + 1 \sum_0^k x_ia_i \le n \quad and\quad a_{k+1} \gt n+1 ∑0kxiai≤nandak+1>n+1),故性质2得证。
当 1 ≤ a k + 1 ≤ n + 1 1\le a_{k+1} \le n+1 1≤ak+1≤n+1时,由于 a 0 , a 1 , . . . a k a_0,a_1,...a_k a0,a1,...ak是n的一种k阶可行分割,
当 m ≤ n m \le n m≤n时,存在 x 0 ≤ i ≤ k ∈ { 0 , 1 } x_{0\le i \le k} \in \{0, 1\} x0≤i≤k∈{0,1},s.t. m = ∑ 0 k x i a i m =\sum_0^k x_ia_i m=∑0kxiai
当 n < m ≤ n + a k + 1 n\lt m \le n+a_{k+1} n<m≤n+ak+1时, m − a k + 1 ≤ n + a k + 1 − a k + 1 = n m-a_{k+1} \le n+a_{k+1}-a_{k+1}=n m−ak+1≤n+ak+1−ak+1=n且 m − a k + 1 ≥ n + 1 − a k + 1 ≥ 0 m-a_{k+1} \ge n+1-a_{k+1}\ge 0 m−ak+1≥n+1−ak+1≥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 = ∑ 0 k x i a i m-a_{k+1} =\sum_0^k x_ia_i m−ak+1=∑0kxiai,即 m = a k + 1 + ∑ 0 k x i a i m =a_{k+1}+\sum_0^k x_ia_i m=ak+1+∑0kxiai,故性质1得证明。
思考:如何在所有的可行分割当中找出分割次数最少的分割呢,很自然的我们可以想到就是让分割后的每一份 a i a_i ai尽可能更大,根据性质1和性质2,分割后的 a i a_i ai最大不能超过 ∑ 0 i − 1 a t + 1 \sum_0^{i-1} a_t+1 ∑0i−1at+1,因此将 a i = ∑ 0 i − 1 a t + 1 a_i=\sum_0^{i-1} a_t+1 ai=∑0i−1at+1作为临界值,这就变成递推数列的问题了,通过计算可以得出:当 a i = 2 i i ∈ 0 , 1 , . . . , k − 1 a n d a k = n − 2 k + 1 a_i=2^i \quad i\in{0,1,...,k-1}\quad and\quad a_k=n-2^k+1 ai=2ii∈0,1,...,k−1andak=n−2k+1时,分割达到最优。
更进一步
回看以上过程,由于每个 x i x_i xi都是在{0,1}之间取值,直觉告诉我们这个问题也许能与二进制扯上关系,实际上, 1 , 2 , 2 2 , . . . 2 k 1,2,2^2,...2^{k} 1,2,22,...2k本身可以看成是整数空间{1…2^{k+1}-1}中的一组线性无关且完备的基,且当 x i x_i xi在{0,1}之间取值时,该整数空间不可能存在更低阶的基,否则将这些值按从小到大排列时,一定存在后一个值比前一个值两倍加1还大的情况,那么根据上面关于性质1和性质2的证明,前一个值得2倍加1就无法用这组值线性表示,因此就不能构成一组基。
这样的话,该问题就转化成一个求二进制的问题,当十进制整数表示成二进制是有多少位,那么其最小分割次数就是相应的位数减一。