从1.2.3.4.5..N中,任取57个数,使57个数必有2个数的差是13,问N的最大值是几?

Question

从1.2.3.4.5..N中,任取57个数,使57个数必有2个数的差是13,问N的最大值是几?

Answer 1

在1、2、3、…、n中,我们考虑它们对13的余数,然后按其结果进行分组：
1、2、3、…、13 （把余数是0的,也就是能整除的余数记为13）
在这13组数中：每个数都可以表示成 13m+k的形式,其中k=1、2、…、13,而 m=0、1、2、…我们称k为余数,m为基数.
一、任意两组之间的数,因为余数不相等,所以其差不可能是13的倍数,也就不可能是13
二、在同一组数中,因为余数相等,任意两个数的差肯定是13的倍数.如果同一组中有相邻基数的同余序列,那么它们的差就是13,
要使57个数被分配在13个序列中,同一组数不能取相邻基数的.
57=13*4+5=(8+5)*4+5
要使57个数之间任意两个都不等13,n取最小值时,每组数中被分配的基数差要>=2,在13个序列中,有8个长度为8,5个长度为9,那么n=8*8+5*9=109,所以,要使这57个数必有两个数的差为13,则n的最大值是108
[以上是解法和证明过程,下面是具体的取法]
具体到数的取法上,有两个方面：
A、在1,2,3,...108这组数中,我们可以这么取：
1-13
27-39
53-65
79-91
4组各13个,再加4个 (13*4+4=56)
105,106,107,108
这56个数可以保证两两的差都不等于13,再加进去1-108中其他的数肯定会与前面四组的基相差1,结果差就会是13
这就可以证明,从1-108中取57个肯定会有两个数的差是13
B、
A、在1,2,3,...108这组数中,我们可以这么取：
1-13
27-39
53-65
79-91
4组各13个,再加5个 (13*4+5=57)
105,106,107,108,109
这57个数可以保证两两的差都不等于13
所以要使取得57个数中肯定有两个数的差是13,那么n=108是最大的.