(续)
以下只要证明:各个d如此相㈩的总和的P进制形式中至少有一位不等于零,即可。
按照抓枚的规则,可知d1~dn至少有一个至多有K个非零,其余都是零。故必存在一个最大的非零的d。
因为影子数的P进制形式中各位只可能是1、0两种情况,故d的P进制形式中各位只可能是1㈠0 =1、1㈠1 =0、0㈠0 =0、0㈠1 =P-1,即只可能是以下三种:
1、0、P-1
而且,因为每堆抓后只可减小不可增加,以及影子数的保序性,所以各个d的P进制最高非零位只可能是1㈠0,不可能是0㈠1,故必为1。
设最大的非零的d的最高非零位是第t位,则其他各个d的最高位或是第t位或低于第t位,那么,所有的各个d中,其第t位或为0,或为1。
设第t位为1的d有m个,则必然1<m≤K<P 。
于是相加的总和中,第t位应等于m。因1<m <P,不存在进位问题,所以第t位≠ 0。
证毕。
(待续)
以下只要证明:各个d如此相㈩的总和的P进制形式中至少有一位不等于零,即可。
按照抓枚的规则,可知d1~dn至少有一个至多有K个非零,其余都是零。故必存在一个最大的非零的d。
因为影子数的P进制形式中各位只可能是1、0两种情况,故d的P进制形式中各位只可能是1㈠0 =1、1㈠1 =0、0㈠0 =0、0㈠1 =P-1,即只可能是以下三种:
1、0、P-1
而且,因为每堆抓后只可减小不可增加,以及影子数的保序性,所以各个d的P进制最高非零位只可能是1㈠0,不可能是0㈠1,故必为1。
设最大的非零的d的最高非零位是第t位,则其他各个d的最高位或是第t位或低于第t位,那么,所有的各个d中,其第t位或为0,或为1。
设第t位为1的d有m个,则必然1<m≤K<P 。
于是相加的总和中,第t位应等于m。因1<m <P,不存在进位问题,所以第t位≠ 0。
证毕。
(待续)