突然刚想到一个问题

我还小

假设一个国家所有人都有身份证号，身份证号是由m位数字组成，每一位上的数字是0到n-1上的任意一个数，假设这个国家任意两个人的身份证号不存在高于k个数字位上的数字相同，
问题1，这个国家最多有多少人？
问题2，已知两人的省份证号，对这个国家的最多人数有影响吗？若有影响，两人的身份证号满足什么条件时该国人口的最大值最小。

褒千秋

任意两个人的身份证号不相同的话，应该要求k≤m-1
k=m-1时每个身份证号都可以使用，最多可以使用n^m个不同号码，而且由于出现了所有的号码，不管已知两个人的号码怎样都不会影响可使用号码的数量上限
但k≤m-2时应该都会有影响，而且都很复杂…问题1相当于求出已知图的最大独立集，问题2相当于在已知含某两个顶点(某子图)的条件下求最大独立集
特殊情况k=0时问题1最多有n个人，问题2不知道

我还小

谢谢，虽然说了和没说一样，另外，如果m=n，k=2，任意一人身份证号要求不能出现重复的数字，在这个情况下答案也是显然的。

褒千秋

n=2时如果任意两个身份证号至少有m-k=2r+1位不同，那号码总数N≤2^m/(C(m, 0)+C(m, 1)+…+C(m, r))  (一个上界)
这是课上刚刚学的编码理论的二进制hamming不等式，两个等长的二进制序列之间具有不同字符的数位总数，定义成hamming距离
与某个字符串a的hamming距离不超过r的全体二进制数叫作a的r邻域，可以证明总长为m的一个二进制字符串r邻域中一共有C(m, 0)+C(m, 1)+…+C(m, r)个不同字符，并且其中任意两个字符串的hamming距离不超过2r+1
所以如果一共有N个身份证号而且N*(C(m, 0)+C(m, 1)+…+C(m, r))>2^m，那一定有两个身份证号落在同一个号码的r邻域内，它们之间至少有m-(2r+1)个位置上数码相同

褒千秋

我觉得应该也可以推广到n≥3的情况，如果m-k=2r+1，则号码总数N≤n^m/[C(m, 0)+(n-1)*C(m, 1)+(n-1)²*C(m, 2)+…+(n-1)^r*C(m, r)]

我还小

解法来源于这位哥们的回复