注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

校内iq测试一题  

2010-02-26 12:07:14|  分类: 数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

有16名学生参加一次数学竞赛。考题全是选择题,每题有四个选项。考完后发现任何两名学生的答案至多有一道题相同。问:这次竞赛最多有多少道选择题?
答案是5。
解答:
为了清楚,画个表格:
image 
则问题也就是说要用A,B,C,D填入各格,使任意两行至多有一个对应位点相同,问n最大为几。
首先显然n=1,2,3都容易构造出来,所以n>=3
构造过程中将发现:
引理:每列恰有4个A,4个B,4个C。
证明:假设第i列某个字母不为4个,则或者其本身多于4个,或者因其本身少于4个而导致另一字母多于4个。总之,将导致某个字母多于4个。不妨设字母A为k>=5个,那么考虑第j列(j≠i)相对应的k行,由于k>=5,故由抽屉原理知其中至少有两行L1,L2字母相同。于是L1,L2两行有两个对应位点(列i和列j)字母相同,与题设矛盾。
下面证明n最大值不会超过5:
假设不然,而有六道题。
考虑人P,由引理知第i题与P答案相同者恰有3个,设为Pi1,Pi2,Pi3。
则有(*):若i≠j,则{Pi1,Pi2,Pi3}∩{Pj1,Pj2,Pj3}=Φ。
原因是:若{Pi1,Pi2,Pi3}∩{Pj1,Pj2,Pj3}≠Φ,不妨设Pi1=Pj1(设都=Q),则说明人Q第i题及第j题均与P答案相同,与至多有一题相同矛盾,所以(*)成立。
所以有{P11,P12,P13},{P21,P22,P23},{P31,P32,P33},{P41,P42,P43}, {P51,P52,P53},{P61,P62,P63}两两互不相交。这一共是6*3=18个人,再加上P,一共19个人。这与共有16人参加考试矛盾。
所以说六道题不行。当然,同理可知多于六道也都不行。
现在,要证明n最大值就是5,只差构造一实例,实例如下:
(n=5的解:)
A A A A A
A B B B B
A C C C C
A D D D D
B A B C D
B B A D C
B C D A B
B D C B A
C A C D B
C B D C A
C C A B D
C D B A C
D A D B C
D B C A D
D C B D A
D D A C B
下面是计算上面局面所用到的程序:
(如果从穷举各种组合的角度考虑,算法是指数级的,根本无法实现,所以不能完全蛮算,必须考虑用一些数学性质来减少计算量。下面程序用前面的引理缩小搜索范围,另外加入剪枝,能较快地遍历完搜索空间):

#include<iostream.h>
#define X -1//未填充
#define A 0
#define B 1
#define C 2
#define D 3
const int ncol=5;
int nSame(int mat[16][ncol],int I,int J){//计算mat的第I,J两行相同位点个数
    int _nSame=0;
    for(int i=0;i<=ncol-1;i++){
        if(!(mat[I][i]==X||mat[J][i]==X)&&mat[I][i]==mat[J][i])_nSame++;
    }
    return _nSame;
}
void finn(int mat[16][ncol],int I,int J,bool avail[ncol],bool&gotit){//函数f的递归核
    if(I%4==0){
        avail[A]=true;
        avail[B]=true;
        avail[C]=true;
        avail[D]=true;
    }
    if(I>15){//转下一列
        I=0;J++;
    }
    if(J>ncol-1){//出口
        gotit=true;
        return;
    }
    //暂存avail
    bool _avail[4]={avail[0],avail[1],avail[2],avail[3]};
    //尝试各种填法
    for(int k=A;k<=D;k++){//遍历avail
        if(avail[k]==true){//如果k可用       
            //用k填充mat[I][J]
            //但在填充前要先判断这种填法是不是行
            bool isOk=true;
            //找到本列前面各J元素为k的行
            for(int i=I-1;i>=0;i--){
                if(mat[i][J]==k){
                    //判断这两行是否相容
                    if(nSame(mat,i,I)>=1){//如果有2个以上对应位点,不相容
                                          //注意,由于mat[I][J]还没填,所以用>=1而不是>=2
                        isOk=false;
                    }
                }
            }//得到isOk
            if(isOk){//行则填充
                mat[I][J]=k;
                avail[k]=false;
                finn(mat,I+1,J,avail,gotit);
                if(gotit)return;
                //复原avail
                avail[0]=_avail[0];
                avail[1]=_avail[1];
                avail[2]=_avail[2];
                avail[3]=_avail[3];
                //恢复mat
                mat[I][J]=X;
            }
        }
    }
}
bool f(int mat[16][ncol]){//计算一个解,返回是否得到解
    int I=0;
    int J=2;
    bool avail[4]={true,true,true,true};
    bool gotit=false;
    finn(mat,I,J,avail,gotit);
    return gotit;
}
void print(int mat[16][ncol],int m,int n){//打印结果
    for(int i=0;i<=m-1;i++){
        for(int j=0;j<=n-1;j++){
            switch(mat[i][j]){
            case A:
                cout<<"A";
                break;
            case B:
                cout<<"B";
                break;
            case C:
                cout<<"C";
                break;
            case D:
                cout<<"D";
                break;
            case X:
                cout<<"X";
                break;
            }
            cout<<" ";
        }
        cout<<endl;
    }
}
main(){
    int mat[16][ncol];
    //---初始化---
    for(int i=0;i<=15;i++){
        for(int j=0;j<=ncol-1;j++){
            mat[i][j]=X;
        }
    }
    //前两列是固定的
    mat[0][0]=A;mat[0][1]=A;
    mat[1][0]=A;mat[1][1]=B;
    mat[2][0]=A;mat[2][1]=C;
    mat[3][0]=A;mat[3][1]=D;
    mat[4][0]=B;mat[4][1]=A;
    mat[5][0]=B;mat[5][1]=B;
    mat[6][0]=B;mat[6][1]=C;
    mat[7][0]=B;mat[7][1]=D;
    mat[8][0]=C;mat[8][1]=A;
    mat[9][0]=C;mat[9][1]=B;
    mat[10][0]=C;mat[10][1]=C;
    mat[11][0]=C;mat[11][1]=D;
    mat[12][0]=D;mat[12][1]=A;
    mat[13][0]=D;mat[13][1]=B;
    mat[14][0]=D;mat[14][1]=C;
    mat[15][0]=D;mat[15][1]=D;
    //---初始化完毕---
    bool gotit=f(mat);//求解
    if(gotit){
        //输出解
        print(mat,16,ncol);
    }else{
        cout<<"无解!"<<endl;
    }
}

程序的运行结果就是前面“n=5的解”。
若将第7行的ncol=5改为6,则将得到无解的结论,也相当于证明了n的最大值为5。
----
进一步研究:

设人数为m,题数为n。
设第i题选择A,B,C,D的人数分别为ai,bi,ci,di,(ai+bi+ci+di=m)。
则有∑(C(ai,2)+C(bi,2)+C(ci,2)+C(di,2))<=C(m,2),其中求和是从i=1到n。
证明:C(ai,2)+C(bi,2)+C(ci,2)+C(di,2)意思是第i列中取两个相同字母的方法数。C(m,2)的意思是一列m个字母中取两个字母的最多方法数。所以如果左边和式超过了右边,就必定有两列重叠了,不满足要求,所以必须满足 左边<=右边。
下面用这个不等式再来证明一下m=15时的那个结果:
由前面的引理知,对所有的i有ai=bi=ci=di=4。所以不等式变为:
∑(C(4,2)+C(4,2)+C(4,2)+C(4,2))=n*24<=C(16,2)=120.
解得n<=5。
进一步考虑此不等式,得到一个求解此类问题的一般思路:
由于∑(C(ai,2)+C(bi,2)+C(ci,2)+C(di,2))<=C(m,2)是恒成立的,所以要想使n最大,就得使得各项 (C(ai,2)+C(bi,2)+C(ci,2)+C(di,2))最小,由于各项是相互独立的,所以它们同时取到最小。于是上问题就是:
已知a+b+c+d=m,求C(a,2)+C(b,2)+C(c,2)+C(d,2)的最小值。
这个最小值v求出来以后,就有n<=C(m,2) / v。
实事上可以证明:当a,b,c,d尽量接近时达到最小值。
下面利用此不等式解决其它m值的情况:(假设题目其它条件不变)
m>16的情况:

如果人数超过16,要想保证任两人至多一题答案相同,则题数只能是1。
证明:假设人数为m>16,则根据抽屉原理,第1列必存在某字母个数>=5。不妨设A的个数为k>=5。假设存在第二列,则考虑第二列中相对应的k行,由于k>=5,故由抽屉原理知其中至少两行L1,L2字母相同,于是L1,L2两行有两个对应位点(列1和列2)字母相同,与题设矛盾。
m<5的情况:
显然此时n可取无限大。
m=5的情况:
当m=5时不等式成为:
∑(C(ai,2)+C(bi,2)+C(ci,2)+C(di,2))<=C(5,2)=10
由于C(ai,2)+C(bi,2)+C(ci,2)+C(di,2)>=1,所以上式左边>=n,而它又<=10,所以得到n<=10。
另一方面,容易手工构造出m=5且n=10的例子:
AAAABBBBBB
ABBBAAACCC
BACCACCAAD
CCADCADADA
DDDADDADAA
m=6的情况:

∑(C(ai,2)+C(bi,2)+C(ci,2)+C(di,2))<=C(m,2)
所有ai+bi+ci+di=m
中令
m=6,,所有ai=2,bi=2,ci=1,di=1,则可得n<=7.5,即n最大为7。
但是否能取到7则需举出实例,于是考虑用程序计算出m=6且n=7的解。
但直接计算是不可能的,因为计算量过大,所以要想办法减少一些计算量:
1,每列第一个字母取A。
2,第一列取AABBCD。
以上削减是基于下面事实:
(1),对局面的任何一列的ABCD作置换不影响局面的成立与否。
(2),如果m=6且n=7的局面存在,则必有一列其a=2,b=2,c=1,d=1。
原因是:对于m=6的情况,a=2,b=2,c=1,d=1是使C(a,2)+C(b,2)+C(c,2)+C(d,2)最小的一组数字,稍大一些就是 a=3,b=1,c=1,d=1。所以如果任何一列都不是
a=2,b=2,c=1,d=1,则C(a,2)+C(b,2)+C(c,2)+C(d,2)最小为3,此时求得n至大为5,与n=7矛盾。所以必有一列 a=2,b=2,c=1,d=1。
由于各列顺序无所谓,故可取第一列为a=2,b=2,c=1,d=1,即第一列取为AABBCD。
运用了1,2两条削减之后计算量就小多了,然后由程序可得:
A A A A A A A
A B B B B B B
B A B C C C C
B B A D D D D
C C C A B C D
D C D B A D C
所以m=6时n最大为7。
下面就是这个计算m=6且n=7局面的程序:

#include<iostream.h>
#define X -1//未填充
#define A 0
#define B 1
#define C 2
#define D 3
const int ncol=7;
const int nln=6;
int nSame(int mat[nln][ncol],int I,int J){//计算mat的第I,J两行相同位点个数
    int _nSame=0;
    for(int i=0;i<=ncol-1;i++){
        if(!(mat[I][i]==X||mat[J][i]==X)&&mat[I][i]==mat[J][i])_nSame++;
    }
    return _nSame;
}
void finn(int mat[nln][ncol],int I,int J,bool&gotit){//函数f的递归核
    if(I>nln-1){//转下一列
        I=0;J++;
        mat[I][J]=A;
        finn(mat,I+1,J,gotit);
        if(gotit)return;
        //恢复mat
        mat[I][J]=X;
        return;
    }
    if(J>ncol-1){//出口
        gotit=true;
        return;
    }
    //尝试各种填法
    for(int k=A;k<=D;k++){
        //用k填充mat[I][J]
        //但在填充前要先判断这种填法是不是行
        bool isOk=true;
        //找到本列前面各J元素为k的行
        for(int i=I-1;i>=0;i--){
            if(mat[i][J]==k){
                //判断这两行是否相容
                if(nSame(mat,i,I)>=1){//如果有2个以上对应位点,不相容
                    //注意,由于mat[I][J]还没填,所以用>=1而不是>=2
                    isOk=false;
                }
            }
        }//得到isOk
        if(isOk){//行则填充
            mat[I][J]=k;
            finn(mat,I+1,J,gotit);
            if(gotit)return;
            //恢复mat
            mat[I][J]=X;
        }
    }
}
bool f(int mat[nln][ncol]){//计算一个解,返回是否得到解
    int I=0;
    int J=1;
    bool gotit=false;
    mat[I][J]=A;
    finn(mat,I,J,gotit);
    return gotit;
}
void print(int mat[nln][ncol],int m,int n){//打印结果
    for(int i=0;i<=m-1;i++){
        for(int j=0;j<=n-1;j++){
            switch(mat[i][j]){
            case A:
                cout<<"A";
                break;
            case B:
                cout<<"B";
                break;
            case C:
                cout<<"C";
                break;
            case D:
                cout<<"D";
                break;
            case X:
                cout<<"X";
                break;
            }
            cout<<" ";
        }
        cout<<endl;
    }
}
main(){
    int mat[nln][ncol];
    //---初始化---
    for(int i=0;i<=nln-1;i++){
        for(int j=0;j<=ncol-1;j++){
            mat[i][j]=X;
        }
    }
    mat[0][0]=A;
    mat[1][0]=A;
    mat[2][0]=B;
    mat[3][0]=B;
    mat[4][0]=C;
    mat[5][0]=D;
    //---初始化完毕---
    bool gotit=f(mat);//求解
    if(gotit){
        //输出解
        print(mat,nln,ncol);
    }else{
        cout<<"无解!"<<endl;
    }
}

m=7的情况:
令m=7,,所有ai=2,bi=2,ci=2,di=1,则可得n<=7,即n最大为7。
再看m=7且n=7的局面是否存在。
同样,直接计算因计算量过大不可能实现,考虑削减:
1,第一列取为AABBCCD。
2,除第一列之外其它各列均为a=2,b=2,c=2,d=1。(因为否则的话必取不到n=7)。
注:m=6情况中的削减条件“1,每列第一个字母取A。”不再成立,认为其成立将导致错误。
运用1,2后计算量变得非常小,由程序可立即得到:
A A A A D C A
A C C D C B C
B A D C B A C
B B C B A D A
C B B A C A D
C D A C A B B
D C B B B C B
所以m=7时n最大为7。
下面就是这个计算m=7且n=7局面的程序:

#include<iostream.h>
#define X -1//未填充
#define A 0
#define B 1
#define C 2
#define D 3
const int ncol=7;
const int nln=7;
int nSame(int mat[nln][ncol],int I,int J){//计算mat的第I,J两行相同位点个数
    int _nSame=0;
    for(int i=0;i<=ncol-1;i++){
        if(!(mat[I][i]==X||mat[J][i]==X)&&mat[I][i]==mat[J][i])_nSame++;
    }
    return _nSame;
}
void finn(int mat[nln][ncol],int I,int J,bool&gotit,int nA,int nB,int nC,int nD){//函数f的递归核
    if(I>nln-1){//转下一列
        I=0;J++;
    }
    if(I==0){
        nA=2;
        nB=2;
        nC=2;
        nD=1;
    }
    if(J>ncol-1){//出口
        gotit=true;
        return;
    }
    //暂存nA,nB,nC,nD
    int _nA=nA;
    int _nB=nB;
    int _nC=nC;
    int _nD=nD;
    //尝试各种填法
    for(int k=A;k<=D;k++){
        switch(k){
        case A:
            if(nA==0)continue;
            nA--;
            break;
        case B:
            if(nB==0)continue;
            nB--;
            break;
        case C:
            if(nC==0)continue;
            nC--;
            break;
        case D:
            if(nD==0)continue;
            nD--;
            break;
        }
        //用k填充mat[I][J]
        //但在填充前要先判断这种填法是不是行
        bool isOk=true;
        //找到本列前面各J元素为k的行
        for(int i=I-1;i>=0;i--){
            if(mat[i][J]==k){
                //判断这两行是否相容
                if(nSame(mat,i,I)>=1){//如果有2个以上对应位点,不相容
                    //注意,由于mat[I][J]还没填,所以用>=1而不是>=2
                    isOk=false;
                }
            }
        }//得到isOk
        if(isOk){//行则填充
            mat[I][J]=k;
            finn(mat,I+1,J,gotit,nA,nB,nC,nD);
            if(gotit)return;
            //恢复mat
            mat[I][J]=X;
            //恢复nA,nB,nC,nD
            nA=_nA;
            nB=_nB;
            nC=_nC;
            nD=_nD;
        }
    }
}
bool f(int mat[nln][ncol]){//计算一个解,返回是否得到解
    int I=0;
    int J=1;
    bool gotit=false;
    int nA=2;//可用的A的个数
    int nB=2;//可用的B的个数
    int nC=2;//可用的C的个数
    int nD=1;//可用的D的个数
    finn(mat,I,J,gotit,nA,nB,nC,nD);
    return gotit;
}
void print(int mat[nln][ncol],int m,int n){//打印结果
    for(int i=0;i<=m-1;i++){
        for(int j=0;j<=n-1;j++){
            switch(mat[i][j]){
            case A:
                cout<<"A";
                break;
            case B:
                cout<<"B";
                break;
            case C:
                cout<<"C";
                break;
            case D:
                cout<<"D";
                break;
            case X:
                cout<<"X";
                break;
            }
            cout<<" ";
        }
        cout<<endl;
    }
}
main(){
    int mat[nln][ncol];
    //---初始化---
    for(int i=0;i<=nln-1;i++){
        for(int j=0;j<=ncol-1;j++){
            mat[i][j]=X;
        }
    }
    mat[0][0]=A;
    mat[1][0]=A;
    mat[2][0]=B;
    mat[3][0]=B;
    mat[4][0]=C;
    mat[5][0]=C;
    mat[6][0]=D;
    //---初始化完毕---
    bool gotit=f(mat);//求解
    if(gotit){
        //输出解
        print(mat,nln,ncol);
    }else{
        cout<<"无解!"<<endl;
    }
}


对于m的其它值8~15可沿用类似方法讨论:由不等式确定范围,再用程序计算实例(并附加削减条件以减少计算量),不难得出结果,这里不再赘述,等有时间我会列出各m值对应的方案。

 

  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017