. (a) You wish to color each of the integers 0, 1, 2, . . . , n red or blue, in such a way that
both colors are used, and
integers that differ by 7 or 11 have the same color.
Can you do this for all n? If not, what is the largest value of n for which it is possible?
Prove your answer.
(b) How does the answer in (a) change if we replace the numbers 7 and 11 with arbitrary
integers m and k? If you can’t gure out the solution for the most general case, try it for
some special cases—e.g., for a xed value of k or for some speci c relationship between
m and k. Include your most interesting/general proofs in your solution.
2. (a) 将0, 1, 2, …, n个数字用红色或蓝色涂色,要求:
# 两种颜色均用上;
# 差值为7或者11的数为同一颜色;
是否可以将全部的n做出?如果不可以,n的最大值是多少?并证明
(b) 如果用m和k代替7和11,(a)的答案是什么?如果不可得出一般结论,试着用特例解决。例如固定一个k值,或者用特定的m和k的关系。总结你的结论并证明。
谢谢
现在还没有得到最后结果,希望各位继续帮忙!!
一般情况下,
m、k互质时,n的最大值是 m+k-2。
m、k不互质时,n可以是无穷。(这一步容易得出,关键是上一步)
好像也可以用图论的方法来考虑。
证明 显然0属于S,由差值为7或者11的数为同一颜色,则7,7*2,7*3,…, 11,11*2,11*3,…均属于S,即对任意非负整数t,s,7t,11s≥0属于S,同样的理由,如果7t,11s属于S,则7t+11,7t+11*2,7t+11*3,…,7t-11,7t-11*2,7t-11*3,…, 11s+7,11s+7*2,11s+7*3,…,11s-7,11s-7*2,11s-7*3,…,也均属于S,从而对任意整数,7t+11s≥0属于S.
命题2将所有非负整数用红色或蓝色涂色,要求差值为7或者11的数为同一颜色,则只能涂一种颜色。
证明 由于1=11*2-7*3,从而对任意自然数(包括零)k,k=11*2k-7*3k,故k属于S,即任意自然数均与0同色,即如果对全体自然数(包括零)涂色,只能是同一颜色,不存在两种颜色的涂色。
如果将S看成一个袋子,0首先放在袋子中,如果有一个数x,它与袋子中的某个数差为7或差11,则将数x也放在袋子中,也即论证了数x也属于S,下面给出1属于S 的论证(产生)过程:
0属于S ,则0+11=11属于S,11-7=4属于S,4+11=15属于S,15-7=8属于S,8-7=1属于S,将上述过程简记为0-11-4-15-8-1
上面序列从0开始,且序列中任何相邻两数字的差或是7或是11。
下面再给出2,3,4,5,6属于S 的论证过程:
0-11-4-15-8-1-12-5-16-9-2
0-11-4-15-8-1-12-5-16-9-2-13-6-17-10-3
0-11-4
0-11-4-15-8-1-12-5
0-11-4-15-8-1-12-5-16-9-2-13-6
从上可看出上述这些序列的出现的最大整数是16(在产生2,3,6的过程中),如果缺少16及大于16的数,将不会产生出2,因为2只能由9或13产生,9除由2产生(不能再回到2)外不能由小于16的数产生,13除由2产生外只能由6产生,而6又只能由13产生,这又回到了13,故得结论:缺少16及大于16的数,将不会产生出2。
如果允许出现的最大数是16,是否能产生出所有非负整数呢?答案是肯定的。
因为任何非负整数均可由表示为一个7的倍数加上0-6的数,既然0-6属于S,加上若干个7所得结果必然也属于S。这样得下面命题3.
命题3将0, 1, 2, …, n个数字用红色或蓝色涂色,要求差值为7或者11的数为同一颜色,两种颜色均要用上,则n的最大值是15。
证明 由上面可知。如果n<16, 2不属于S,故n<16可涂两种颜色。即两种颜色均要用上,如果n≥16,由上面分析可知,所有非负整数均属于S,则n的最大值只能是15。
命题4将0, 1, 2, …, n个数字用红色或蓝色涂色,要求差值为k或者m的数为同一颜色,两种颜色均要用上,如果k,m最大公约数d=(k,m)>1,则对任意的n,均可涂一种颜色。
证明 设与 0同色的数构成的集合记为S,类似于命题1的证明,S={kt+ms≥0,其中t,s为整数},由于d=(k,m),故对任意S中的数x,d均整除x,于是1不属于S,否则1属于S,则d均整除1,这与d>1矛盾。由1不属于S,故1可以不与0同色。
命题5将0, 1, 2, …, n个数字用红色或蓝色涂色,要求差值为k或者m的数为同一颜色,如果k,m互素,n≥k+m-1时,则只能涂一种颜色。即两种颜色均要用上, 则n的最大值是k+m-2。
证明 设与 0同色的数构成的集合记为S,由k,m互素,则存在正整数x,y有k*x-m*y=1或m*x-k*y=1,,显然0属于S,由于k*x-m*y=1或m*x-k*y=1,故可以构造出产生1的过程,如果是k*x-m*y=1,则0-k-2k-…-k*x-(k*x-m)-(k*x-2m)-…-( k*x-m*y)=1,如果是
m*x-k*y=1,则0-m-mk-…-m*x-(m*x-k)-(m*x-2k)-…-( k*m-k*y)=1.
下面证明在这过程中出现的数均可以小于等于k+m-1,如果在这个过程(产生序列)中首次出现了大于等于k+m的数x,那么在出现x之前,一定是x-k或x-m,由x≥k+m,得x-k≥m或x-m≥k,此时可用x-k-m代替x-k或x-k,从而使产生序列中的所有数小于等于k+m-1。故n≥k+m-1时,则只能涂一种颜色,也即两种颜色均要用上的涂色, 则n的最大值是k+m-2。
如果n无限的话(n大于7和11的最小公倍数就很好证明),任何能够写成1+7k+11m的数和1的颜色都要相同;
如果n有限,任何能够写成1+7k+11m的数(需要参照扩展的欧几里得算法)和1的颜色都要相同。
所以a很容易证明,7和11互质,所以n无限的话只能有一种颜色
b将7和11换成m,k,证明还是很容易。
假设k>m
则下面球必须和1颜色相同:1+m,1+k,1+k-m,1+2k-m,1+2k-2m……当1+ak-am>1+m时,下一个数写1+ak-am-m,即尽量往小减。当序列包含了1到m的所有数时说明该序列加上1+am已经包含了1到n的所有数,那么这个序列中最大的数减1就是所求的n。显然每加一个k会多一个小于等于m的数,再加一次k,所有数没有重复而且最大值小于等于m+k。最后那个数没必要加,则共有m+k-1个数,这样再减1就是n的最大值了。所以有m+k-2.
(1,2),(2,3),...,(49,50)
任意取出26个数,必有两数同在一组,这同组的两个数之差为1,故互质.
首先证明下面命题:
命题1,将与0同色的数构成的集合记为S,则S={7t+11s≥0,其中t,s为整数}
证明 显然0属于S,由差值为7或者11的数为同一颜色,则7,7*2,7*3,…, 11,11*2,11*3,…均属于S,即对任意非负整数t,s,7t+11s≥0属于S,同样的理由,如果7t,11s属于S,则7t-11,7t-11*2,7t-11*3,…, 11s-7,11s-7*2,11s-7*3,…,也均属于S,从而对任意整数,7t+11s≥0属于S.
由于1=11*2-7*3,从而对任意自然数(包括零)k,k=11*2k-7*3k,故k属于S,即任意自然数均与0同色,即如果对全体自然数(包括零)涂色,只能是同一颜色,不存在两种颜色的涂色。
将0,1,2,…,22涂色,1必与0同色。
反证法 1与0不同色,则8,15也必与0不同色,故22也必与0不同色,但是11与0同色,故22也必与0同色,矛盾。
将0,1,2,…,22涂色,则所有的数必与0同色。
由2=2*7-11-1,6=7-1可知2,6均与1同色,上面已证1必与0同色,故2,6均与0同色,由3=2*7-11,故知3必与0同色,由4=7-3,5=7-2,可知4与3,5与2同色,故1-6的数均与0同色。由于任何非负整数均可表示为7的倍数加上1-6的数,故所有的数均与0同色。
将0,1,2,…,21涂色,可取两种不同的颜色。
记[k]={0≤7t+11s≤21, 其中t,s为非负整数},将0,1,2,…,21分为如下7类:
[0]={0,7,11,14,18,21},
[1]={1,8,12,15,19},
[2]={2,9,13,16,20},
[3]={3,10,14,17,21},
[4]={4,11,15,18},
[5]={5,12,16,19},
[6]={6,13,17,20},
显然[0]-[6]覆盖集合{0,1,2,…,21},[0][3][4]同色,[1][2][5][6]同色
故21是n的最大值,即n>21不能对0,1,2,…,n涂两种颜色。
命题2,设m,k互素,k<m, 差值为m或者k的数着同一颜色,x0是同余式k*x=1(mod m)的最小正整数解,n=k*x0,则将0,1,2, …,n个数字涂色,1必取与0相同的颜色.
证明 设S={0≤k*x+m*y≤n,其中x,y为整数},与命题1证明类似,与0同色的数构成的集合S,0属于S ,故k*x也属于S,x0是同余式k*x=1(mod m)的解,故存在y0有k*x0=m*y0+1,m*y0<k*x0,故m*y0属于S,故1属于S。
同理y0是同余式m*y=1(mod k)的最小正整数解,n=m*y0,则将0,1,2, …,n个数字涂色,1必取与0相同的颜色.
命题3,在命题2的条件下,n=min(k*x0,my0)+(k+1)/2时,则0-n中的任意自然数均与0同色,即对0-n自然数不存在两种颜色的涂色。
证明由命题2可知1必取与0相同的颜色.又由k*x0=m*y0+1,得k*x0+1=m*y0+2,左边的数与1同色(也与0同色),右边m*y0与0同色,故2与0同色,同理k*x0+2=m*y0+3可知,3也与0同色,依次类推(k+1)/2也与0同色,(k+1)/2+1=k-(k-1)/2, (k+1)/2+2=k-(k-3)/2,…,可推知1,2,…,k-1均于0同色,从而证明了所有自然数均与0同色。
x0是同余式k*x=1(mod m)的最小正整数解, y0是同余式m*y=1(mod k)的最小正整数解,由命题2可知,最大值不会小于n=min(k*x0,my0)-1,由命题3可知,最大值不会大于于min(k*x0,my0)+(k+1)/2,我再进一步考虑。