高校问答卢本伟在哪直播房间号:在100×100的方格表里每个方格中填一个整数，要求相邻两整数之差不大于20，求证至少有3个方格中的数相同。
来源：百度文库 编辑：高校问答 时间：2024/04/29 15:49:21
在100×100的方格表里每个方格中填一个整数，要求相邻两整数之差不大于20，求证至少有3个方格中的数相同。
1.设最小的数在第m行，n列，值为x
用a[i,j]表示第i行，j列的数
考虑到对称性，不妨设n,m<=5
下面考虑最大数的最大值，考虑到距离越远的两数，绝对值之差的最大值最大
因为|a[n,m]-a[n,m+1]|<=20，|a[n,m+1]-a[n,m+2]|<=20，...|a[n,9]-a[n,10]|<=20，
|a[n,10]-a[n+1,10]|<=20，|a[n+1,10]-a[n+2,10]|<=20，...|a[9,10]-a[10,10]|<=20，
所以|a[n,m]-a[10,10]|<=|a[n,m]-a[n,m+1|+a[n,m+1]-a[n,m+2]...+a[n,9]-a[n,10]+a[n,10]-a[n+1,10]+...|a[9,10]-a[10,10]|<=20*(10-m+10-n)=4000-20(m+n)<4000
所以最大值-最小值<4000
所以至多出现4000个数
10000/4000=2余2000
由鸽巢原理
至少有3个方格中的数相同
晕，
又是奥数……
10000个格子里都填1，，，呵呵．答案没错吧