《数学奥林匹克竞赛题解》第五章 组合数学第二节 计数和离散最值

第五章 组合数学 第二节 计数和离散最值 E2-001 某人给六个不同的收信人写了六封信，并且准备了六个写有收信人地址的信封，有多少种投放信笺的方法，使每封信笺与信封上的收信人都不相符． 【题说】 1960年～1961年波兰数学奥林匹克三试题3．本题中的6可以改为n． 【解】 根据“容斥原理”可得投放信笺方法的种数为 将6改为n时，答案为 E2-002 n个点由线段连结着，已知其中每两点都有一条且只有一条折线相连，证明：线段的总条数为n-1． 【题说】 1961年全俄数学奥林匹克九年级题3． 【证】 从n点中任选一点A作“根”，将整个图看作一个“树”，从每个“枝”的顶端一节一节地将线段折下来，于是一个端点对应一个线段，直至最后剩下一个“根”点A．因此，线段恰有n-1条． E2-003 从0，0，1，2，3，4，5这七个数字中，任取三个组成三位数，问可组成多少个不同的三位数？又在这些三位数中有多少个是5的倍数？ 【题说】 1964年成都市赛高二一试题3．由题意知1，2，3，4，5不重复使用，0只能用两次． 【解】 百位数字只能从1，2，3，4，5中选，共有5种取法，若十位数字取0，则个位数字取法有5种；若十位数字不取0，则十位数字取法有4种，个位数字取法也有4种，故共能组成 5×5+5×4×4＝105 个不同的三位数，在这些三位数中，末位数字为0的共有5×5=25个，末位数字为5的共有4×4=16个，故5的倍数共有 25+16=41 个． E2-004 在一次中学数学竞赛中共出了A、B、C三题．在所有25个参加者中，每个学生至少解出一题，在没有解出A的那些学生中，解出B的人数是解出C的人数的两倍，只解出A的人数比余下的学生中解出A的人数多1．只解出一题的学生中，有一半没有解出A．问有多少学生解出B？ 【题说】 第八届（1966年）国际数学奥林匹克题1．本题由原苏联提供． 【解】 设不仅解出A的为x人，仅解出B的为y人，解出B与C 由（1）、（2）得 由（3），x≤7．由（4），x=7，4，1． 仅解出B的人数为6． E2-005 在方格的边长为1cm的方格纸上，画一个半径为100cm的圆，这个圆不经过方格的顶点而且不与方格的边相切，问这个圆能穿过多少个方格？ 【题说】 第二届（1968年）全苏数学奥林匹克八年级题3． 【解】 所画的圆穿过200条水平线和200条竖直线．每一条都穿过两次．因此，交点有800个．这800个点把圆分成800份，其中每一部分都在一个格里面，所以圆最多穿过800个格． 同时，可能得出，某两个部分在一个格内，即圆与某个方格相交两次（如图）．我们证明，这样的“奇异”方格不会多于1个． 考虑以O为圆心、半径为200的与某个方格的边AB相交两次的圆． 从这个圆的圆心O到A点和B点的距离大于100，而从直线AB到O的距离小于100，所以，O点在以A和B为圆心、半径为100的圆以外，并且在与AB距离为100的两条平行线之间．这种点，充满两个曲边三角形内部（图中画有斜线的是其中一个）． 显然，对于不同的线段AB，这些轨迹没有公共点．所以，奇异的方格不多于1个． 因此，这个圆穿过800或799个方格． E2-006  一个长方体盒子能用单位立方体填满，如果我们改放尽可能多的体积是2的立方体，且使立方体的边平行盒边，则恰好能填到盒 【题说】 第十八届（1976年）国际数学奥林匹克题3．本题由荷兰提供． 40％×a1a2a3=2b1b2b3 当a＞10时，b≥8，所以 综上所述，所求的盒子尺寸为2×3×5或2×5×6． E2-007  如图，有10个村庄，分别用点A1，A2，…，A10示，某人从A1出发，按箭头所指的方向（不准反向）可以选择任意一条路径走向其他某个村庄，试问：1．按图中所示方向从A1到A5（不绕圈）有多少种不同的走法？2．从A1出发，按图中所示方向，绕一圈后再回到A1，有多少种不同的走法？ 【题说】 1979年湖北省赛二试题3． 【解】 为方便计，设从A1到Ai的走法有ai种，这些走法分为两类：一类是从A1出发，经过Ai-2到达Ai（不经过Ai-1），这时从A1到Ai-2的走法为ai-2，从 Ai-2不经过Ai-1到Ai的走法只有一种，所以这类走法共ai-2种．第二类是从A1出发，经过Ai-1到达Ai，共ai-1种，而这两类走法是互不相同的，所以，从A1到Ai的走法共 ai=ai-1+ai-2（种） 显然a2=1，a3=2．于是a5=2a3+a2=5，a6，a7，a8，a9，a10，a11分别为8，13，21，34，55，89．所以从A1到A5有5种不同的走法，从A1出发，绕一圈回到A，有89种不同的走法． E2-008 在直角坐标平面的第一象限中，把坐标都是整数的点按以下方法编号：（0，0）点第1号，（1，0）点第2号，（1，1）点第3号，（0，1）点第4号，（0，2）点第5号，（1，2）点第6号，（2，2）点第7号，（2，1）点第8号，（2，0）点第9号，…按图中箭头的顺序，求第2000号的点的坐标． 【题说】 1979年北京市赛二试题1． 【解】 设k为正整数，则满足条件： 0≤x≤k，0≤y≤k 的坐标为整数的点（x，y）共有（k+1）2个，而满足条件： （k+1）2＜2000 的最大整数k=43．因此编号为2000的点的纵坐标为44或横坐标为44． 因44为偶数，故应从点（0，44）往右数，又因 2000-442=64＞44 故第2000号的点的横坐标为44．其纵坐标是 44-（64-45）=25 所以编号2000的点的坐标是（44，25）． E2-009  散步时，每步长为1，向南、北、东、西任一方向均可，如果每一点不通过两次，则称这散步为自身回避的，设从原点开始的、n步的、自身回避的散步种数为f（n）．求 f（1），f（2），f（3），f（4），并证明 2n＜f（n）＜4·3n-1 【题说】 第十一届（1979年）加拿大数学奥林匹克题5． 【解】容易算得 f（1）=4 f（2）=4×3=12 f（3）=4×3×3=36 对于4步的自身回避散步，则有 f（4）=4×3×3×3-8=100 假设每次均向北或西两个方向走，当然不会出现有一点通过两次的情况，所以 2n＜f（n） 如果仅考虑不反过身来往回走，那么共有4×3n-1种（其中可能出一点通过两次的情况），所以f（n）≤4×3n-1（当n=1，2，3时取等号）． E2-010 十个赌徒在开赌时，每人都有相同的赌本，每次由一个人掷五粒骰子，如果骰子的点数之和为n，那么这个人向其他九人中的每一 每人掷一次骰子后，每个人的赌本又恢复到开赌时的原有的赌本．最后一次掷出的点数之和为12．求各次掷出点数之和． 【题说】 1980年五国国际数学竞赛题5．本题由荷兰提供． 【解】 不妨设每人赌本为1，又设第i次的点数之和为ni（1≤ni≤10），容易知道第i个人在第i次时，钱由x变为 所以最终钱数为 特别地， 而 由此逐步得出n9=13，n8=14，…，n1=21． E2－011 设n和k是正整数，S是平面上n个点的集合，满足： （1）S中任何三点不共线； （2）对S中的每一个点P，S中至少存在k个点与P距离相等． 【题说】 第三十届（1989年）国际数学奥林匹克题3，本题由荷兰提供．条件（1）可以取消． 【证】 以S中的两个点为端点的线段称为“好线段”． 另一方面，以S中任一点P为圆心，可以作一个圆，圆上至少有k 计算在内）．从而至少有 条弦是好线段．   E2－012 学校举办足球循环赛，每个参赛队都与其他队各赛一场，胜一场积2分，平一场积1分，负一场积0分，已知仅有一个队积分最多，但他胜的场数最少，问至少有几队参赛，才有可能这样？ 【题说】 第十六届（1990年）全俄数学奥林匹克九年级题5． 【解】 称积分最多的为冠军，设冠军胜n场，平m场，则他共积2n+m分，由题设，其余各队胜的场数不少于n+1，即积分不少于2（n+1）．由2n+m＞2n+2得m≥3．从而有队踢过平局，他们的积分不少于2（n+1）+1，由2n+m≥2n+3，得m≥4． 冠军队至少胜1场，否则，它的积分不多于S-1（S是参赛的队数）．其余队的积分少于S-1，于是所有参赛队积分之和少于S（S-1）．而每赛一场，双方积分之和总是2分，因此所有队积分之和应是2·S（S-1）/2=S（S-1），矛盾． 这样，m≥4，n≥1，因此冠军队比赛场数不少于5，参赛队数（包括冠军队）不少于6． 下面的比赛积分表表明，有6个队（分别用A、B、C、D、E、F表示）参赛且满足题设的比赛结果．因此至少6队参赛．   E2－013 设n≥3．考虑在同一圆周上的2n-1个互不相同的点所成的集合E．将E中一部分点染成黑色，其余的点不染颜色．如果至少有一对黑点，以它们为端点的两条弧中有一条的内部（不包含端点）恰含E中n个点，则称这种染色方式为好的．如果将E中k个点染黑的每一种染色方式都是好的，求k的最小值． 【题说】 第三十一届（1990年）国际数学奥林匹克题2．本题由捷克提供． 【解】 将E中的点依次记为1，2，3，…，2n-1，并将点i与i+（n-1）用一条边相连（我们约定j+（2n-1）·k，k∈Z，表示同一个点j）．这样得到一个图G．G的每个点的次数均为2（即与两个点相连），并且相差为3的两个点与同一点相连． 由于G的每个点的次数为2，G由一个或几个圈组成． 在3 2n-1时，1， 2，…，2n-1中每一点j都可以表示成3k的形式（即方程3x≡j（mod2n-1）有解），因此图G是一个长为2n-1的圈．在这圈上可以取出n-1个互不相邻的点，而且至多可以取出n-1个互不相邻的点． 为 共可取出n-2个点互不相邻． 综上所述，在3 2n-1时，mink=n．在3|2n-1时，mink=n-1．  E2－014 地面上有10只小鸟在啄食，其中任意5只鸟中至少有4只在一个圆周上，问有鸟最多的一个圆周上最少有几只鸟？ 【题说】 1991年中国数学奥林匹克题3． 【解】 9只鸟在同一圆周上，1只鸟不在这圆周上，满足题目条件． 设有鸟最多的圆上至少有l只鸟，则4≤1≤9． 首先证明，l≠4．由l≤9，必有4只鸟不在同一圆周上，过其中每3只作一个圆，共得4个圆，其余6只鸟中的每一只与上述4只鸟组成5元组，因而这只鸟必在（上述4个圆中）某一个圆上，6只鸟中必有2只在同一个圆上，从而这个圆上至少有5只鸟． 其次，如果5≤l≤8，设圆C上有l只鸟，则C外至少有两只鸟b1、b2．对圆C上任三只鸟，其中必有两只与b1、b2共圆，设C上的b3、b4与b1、b2共圆，b5、b6与b1、b2共圆，C上第5只鸟b7及b3、b5，这3只鸟中没有两只能与b1、b2共圆，矛盾． 所以l=9．  E2－015 给定空间中的9个点，其中任何4点都不共面，在每一对点都连着一条线段．试求出最小的n值，使得将其中任意n条线段中的每一条任意地染为红、蓝二色之一，在这n条线段的集合中都必然包含有一个各边同色的三角形． 【题说】 第三十三届（1992年）国际数学奥林匹克题3，本题由中国提供． 色的线段至多3条． 若点A1引出不染色的线段，去掉A1及所引出的线段，若剩下的图中，还有点A2引出不染色的线段，去掉A2及所引出的线段．依此进行，由于不染色的线段至多3条，所以至多去掉3个顶点（及从它们引出的线段），即有6个点，每两点之间的连线染上红色及蓝色． 熟知这里存在一个同色三角形． 如图表明染色的边少于33条时，未必有同色三角形（不染色的边1—9、2—8、3—7、4—6没有画出），其中1、9与2、8间的虚线表明1—2、1—8、9—2、9－8均为虚线，5与4、6间的实线表明5—4、5—6均为实线等等． 因此n=33．  E2－016 10人到书店买书，如果已知 （1）每人都买了三本书； （2）任二人所买书中都至少有一本相同，问最受欢迎的书（购买人数最多者）最少有几人购得？为什么？ 【题说】 1993年中国数学奥林匹克（第八届数学冬令营）题5． 【解】 设最受欢迎的书有k人购买．每人买3本书，共买30本书．若k≤4，由于4 30，不可能每种书均被4人购买．设第一个人购的书为a、b、c，并且买a的人≤3个，则与第一个人的公共图书为a的，不超过2人；为b或c的，均不超过3人．从而总人数≤1+2+3+3=9，矛盾！因此k≥5． 现给出一种k=5的购书法： 因此，被购买人数最多的一种书，最少有5人购买．  E2－017 某市发出车牌号码均由6个数字（从0到9）组成，但要求任意2个车牌至少有2位不同（如车牌038471和030471不能同时使用）．试求该市最多能发出多少个不同车牌？并证明． 【题说】 第三届（1993年）澳门数学奥林匹克第三轮题5． 【证】 最多发出100000个．事实上，若发出了100001个车牌，则由抽屉原则知至少有10001个号码首位相同，同理这10001个号码中至少有1001个号码第2位亦相同，…，依此类推，至少有2个号码前5位均相同，违反规定．另一方面，可发出100000个车牌并符合规定；号码的后5位任意填写但没有两个完全相同（有105种填法），首位则为后5位数字之和的个位数字．若有2个号码后5位数字仅有1位不同，则其首位也必不同．所以这100000个号码符合规定．  E2－018 若干个学校参加网球比赛，同一学校之间的选手不比赛，每两个学校的每两个选手都要比赛一场．在两个男孩或两个女孩之间进行的比赛称为单打；一个男孩和一个女孩之间的比赛称为混合单打．男孩的人数与女孩的人数至多相差1．单打的场数和混合单打的场数也至多相差1．问有奇数个选手的学校至多有几个？ 【题说】 第二十五届（1993）加拿大数学奥林匹克题4． 【解】 设有n个学校，第i个学校派出xi个男选手、yi个女选手，i=1，2，…，n． 由题意，有 场．由题意，有 ≤1+2=3 即在（xi-yi）（i=1，2，…，n）中至多只有三项不为零，而且这n项都应为1． 这就是说，至多3个学校的人数xi+yi为奇数． 如果只有3个学校，其中2个各派1名男孩，另1个学校派1名女孩，那么题目中的条件全满足，而奇数个选手的学校恰好3个．  E2－019 用水平和垂直的直线网把一块正方形黑板分成边长为1的n2个小方格，试问对于怎样的最大自然数n，一定可以选出n个小方格，使得任意面积不小于n的矩形中都至少包含有上面选出的一个小方格？（矩形的边是沿着直线网的） 【题说】 第十九届（1993年）全俄数学奥林匹克十年级二试题7． 【解】 显然，如果选出n个小方格满足问题的条件，那么，在每一行、每一列都恰有一个选定的小方格．右图表明n=7时，有满足要求的选法． 设n＞7，称第一个方格被选定的行为A．若A是第一行，则称第二、三行为B、C．若A是第n行，则称第n-1、n-2行为B、C．若A不是第一行与第n行，则称与A相邻的两行为B，C． 两个长方形中都不含有A、B两行中选定的小方格．而C这行中只能有一个选定的小方格，所以这两个长方形中必定有一个是不包含有选定的小方格的． 因此，所求的最大值为n=7． 【注】 n=6时，符合问题要求的选法不存在．  E2—020 设n、k∈N且k≤n并设S是含有n个互异实数的集合．设T是所有形如x1+x2+…+xk的实数的集合，其中x1，x2，…，xk是S中的k个互异元素．求证T至少有k（n-k）+1个互异的元素． 【题说】 第三十四届（1993年）IMO预选题．本题由爱尔兰提供． 【证】 n=k时结论显然．假设命题对n-1（≥k）成立．考虑由s1＞s2＞…＞sn组成的n元集S． 由归纳假设，对S0=｛s2，s3，…，sn｝存在k（n-1-k）+1个形如x1+x2+…+xk的互不相等的数，其中x1，x2，…，xk是S0中不同元素． 显然                    s1+s2+…+sk＞s1+s2+…+sk-1+sk+1                                               ＞s1+s2+…+sk-2+sk+sk+1                                               ＞…＞s1+s2+s4+…+sk+1                                               ＞s1+s3+s4+…+sk+1 并且这k个数中最小的大于s2+s3+…+sk+1，即大于S0中任k个元素的和．所以对n元集S，相应的集T至少有k（n-1-k）+1+k=k（n-k）+1个元素． 于是，本题结论对一切自然数n≥k成立． E2-021 S是{1，2，…，1989}的一个子集，而且S中任意两个数的差不能是4或7，那么S中最多可以有多少个元素？ 【题说】 第七届（1989年）美国数学邀请赛题13． 【解】 将1，5，9，2，6，10，3，7，11，4，8顺次放在圆周上．如果从中选出6个数，那么必有两个在圆周上相邻，即它们的差为4或7，所以从1，2，3，…，11中最多能选出5个数，每两个的差不为4或7．这5个数可以是1，3，4，6，9． 同理，在每11个连续自然数中最多能选出5个数，每两个的差不为4或7．{1，2，…，1989}可分拆为181个子集{11j+1，11j+2，…，11j+11}（j=0，1，…，179）及{1981，1982，…，1989}，所以|S|≤5×181=905．11j+1，11j+3，11j+4，11j+6，11j+9（j=0，1，…，180）．这905个数中，每两个的差不为4或7（若其中有（11j+b）-（11j+a）=4或7，则a-b=7或4）．因此S最多可以有905个元素． E2-022 整数1，2，…，n的排列满足条件：每个数或者大于它之前的所有数，或者小于它之前的所有数，试问有多少个这样的排列？ 【题说】 第二十一届（1989年）加拿大数学奥林匹克题1． 【解】 设所求排列数为 A（n），不难求得 A（1）=1，A（2）=2，A（3）=4 对自然数1，2，…，n，设n排在第k个位置（1≤k≤n），则在它之后只有一种排法： n-k，n-k-1，…，1；而在它之前有A（k-1）种排法，故 A（n）=1+A（1）+A（2）+…+A（n-1）（n≥2） 借助这递推关系，由归纳法易知A（n）=2n-1． 【别解】 除第1位外，其余的位置有两种选择：在这位上的数大于它以前的数，或小于它以前的数，设第j1＜j2＜…＜jl位是前一种，则它对应于排列：在这l个位上从右至左放n，n-1，…，n-l+1；在其余位上自左至右放n-l，n-l-1，…，2，1．选择有2n-1种，排列也有2n-1种． E2-023 求证：集中{1，2，…，1989}可以分为117个互不相交的子集Ai（i=1，2，…，117）．使得 （1）每个Ai含有17个元素； （2）每个Ai中各元素之和相同． 【题说】 第三十届（1989年）国际数学奥林匹克题1．本题由菲律宾提供． 【证】 考虑17行117列的表： 不难验证各列的和均相等，将第i行各数加上（i-1）×117（i=1，2，…，17），则各列的和仍然相等，这时表中的数即1～1989．第j列元素组成的集Aj（j=1，2，…，117）满足题中所有要求． E2-024 设n是正整数，我们说集合{1，2，…，2n}的一个排列（x1，x2，…，x2n）具有性质p，如果在{1，2，…，2n-1}当中至少有一个i使|xi-xi+1|=n成立． 求证：对于任何n，具有性质p的排列比不具有性质p的排列个数多． 【题说】 第三十届（1989年）国际数学奥林匹克题6． 【证】 设（x1，x2，…，x2n）中k与k+n相邻的排列的集合为Nk（1≤k≤n），则具有性质p的排列个数 而|Nk|=2×（2n-1）！，|Nk∩Nh|=22×（2n-2）！，将k与k+n、h与h+n并在一起，2n-2个“数”有（2n-2）！种排列，其中k与k+n，h与h+n并成的“数”可以将k+n与k，h+n与h的位置交换，各有两种排列，所以 ＝（2n）！2n×2（n-1）×（2n-2）！ ＝2n×（2n-2）！×n E2-025 在坐标平面上，横坐标和纵坐标均为整数的点称为整点．对任意自然数n，连结原点O与点An（n，n+3），用f（n）表示线段OAn上除端点外的整点个数，求 f（1）+f（2）+…+f（1990） 的值． 【题说】 1990年全国联赛一试题2（4）．原题为填空题． 【解】 OAn的方程是y=（n+3）x/n（0＜x＜n）．因为n不能整除x，若x、y是整数，n不与n+3互素，必为3的倍数．设n=3m，则y=（m+1）x/m，x只可取m、2m两个值．小于1990的3的倍数有663个，故所求的值是2×663=1326． E2-026 8个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，求共有多少种不同的排列方法？（只要把圆圈旋转一下就重合的排法认为是相同的．） 【题说】 1990年全国联赛一试题2（6）．原题为填空题． 【解】 因旋转重合认为相同，可让某女孩G固定不动，从25个男孩中任选16人，使每两人随一个女孩，这16人可任意排列；对每一种排列，除G外的7个女孩各与其后的两个男孩看成一个“个体”，连同其余9个男孩，总共16个“个体”，又可任意排列，其总数为   E2-027 一个正三角形，每边被等分为n份，过各分点作其它两边的平行线．一共产生多少个三角形（包括原来的三角形在内）？ 【题说】 1990年中国集训队测试题17． 【解】 设原三角形的边长为n，记边长为k（1≤k≤n）的“头 数为yl，则头朝上的三角形共有： x1=2+2+…+n=n（n+1）/2 x2=1+2+…+（n-1） … xn-1=1+2，xn=1 头朝下的三角形共有： y1=1+2+…+（n-1）=n（n-1）/2 y2=1+2+…+（n-3）=（n-2）（n-3）/2 … yl=1+2+…+（n-2l+1） =（n-2l+1）（n-2l+2）/2 … （1）当n为偶数时，由上式可知 （2）当n为奇数时， E2-028 在一次射击比赛中，有8个泥制的靶子挂成如图所示的三列（其中两列3个，一列2个）．一位神枪手按下面的规则打中所有靶子： 1．首先选择一列； 2．再打掉所选一列的最下面未打过的靶子，问打中这8个靶子共有多少种不同的顺序？ 【题说】 第八届（1990年）美国数学邀请赛题8． 【解】 随意射击8个靶子有8！种方法．由于每列靶子的顺序已经确定，所以现在的射法共有 种不同的顺序． E2-029 设S={1，2，…，n}，A为至少含有两项的、公差为正的等差数列，其项都在S中，且添加S的其他元素于A后均不能构成与A有相同公差的等差数列．求这种A的个数．（这里只有两项的数列也看作等差数列．） 【题说】 1991年全国联赛二试题1． 【解】 对于n=2k，所述数列A必有连续两项，一项在{1，2，…，k }中，另一项在{k+1，k+2，…，n}中，反之，从{1 ，2，…，k}中任取一个数，{k+1，k+2，…，n}中也任取一个数，以它们的差为公差、并以这两数为该数列的连续两项可作出一个A．此对应是一一对应，故这种A的个数为k2=n2/4． 对于n=2k+1，情况完全类似，注意集合{k+1，k+2，…，n}中有k+1个数，故这种A的个数为k（k+1）=（n2-1）/4． 两式可统一为[n2/4]．（[x]表示不超过x的最大整数．） E2-030 用A、B两个字母排成的长为15的序列中，满足下列条件的有多少种？ 条件：连续二个字母AA在序列中出现五次，AB、BA、BB各三次． 例：排列AABBAAAABAABBBB中因为AA五次，AB三次，BA二次，BB四次，所以不满足上面的条件． 【题说】 1991年日本数学奥林匹克预选赛题1． 【解】 从第一个项开始，设由A组成的段依次为a1，a2，…，由B组成的段依次为b1，b2，…． 满足条件的排列形状必为 a1b1a2b2a3b3a4                                                                                                          （1） b1a1b2a2b3a3b4                                                                                                         （2） 若一段由k+1个A组成，则这段中AA有k个．各段至少包含一个A（或B）．其余5个A，3个B的分配方法如下： =420（种）． 故满足条件的排列共有980种． E2-031 在一种“咬格子”的游戏中，两名选手轮流“咬”一个由单位正方形组成的5×7网格．所谓“咬一口”，就是一个选手在剩下的正方形中挑一个正方格子去掉（“吃掉”）它的左面的一条边（朝上延长）与底边（朝右延长）所确定的象限中的全部正方形格子，如图a所示，有阴影的格子是选定的，吃掉的是这个有阴影的及打“×”的四个格子．（虚线部分是在这之前已被“吃掉”的）游戏的目标是要对手“咬”最后一口．图b所示的是35个正方形组成的集合的一个子集，它是在“咬格子”游戏过程中可能出现的一个子集． 在游戏过程中，可能出现的不同的子集总共有多少个？整个网格及空集也计算在内． 【题说】 第十届（1992年）美国数学邀请赛题12． 【解】 根据游戏规则，每次“吃”剩下的图形有如下特点：从左到右，各列的方格数不增．因为如某一方格被“吃”，那么它右面和上面的格子全部被“吃”．于是每次剩下的图形从A到B的上边界是一条由7段横线与5段竖线组成的折线，且它是不增的；反之，每一条这样的折线，也对应一块“吃”剩下的方格集．   E2-032 1克、30克、50克三种砝码共110个，总重量为1000克，问其中30克的砝码有多少个？ 【题说】 第一届（1990）希望杯高一二试题2（4）．原是填空题． 【解】 设1克、30克和50克砝码数分别有x、y、z，则有以下关系： （2）-（1）得 29y+49z=890                                                （3） 因29 890，49 890，所以y≠0，z≠0．即y≥1，z≥1．从而 890=29y+49z≥29+49z 由于z是整数，故z≤17． 令z=1，2，…，17，代入（3），知：只有当z=1时，y=29是唯一整数解．又由（1）知，x=80． 即这一组砝码中有29个30克的砝码． E2-033 下图中将等边三角形每边3等分，过等分点作每边平行线，这样所形成的平行四边形个数，记为f（3），则f（3）=15．将等边三角形每边n等分，过各分点作各边平行线，所形成的平行四边形个数记为f（n），求f（n）表达式． 【题说】 第二十三届（1991年）加拿大数学奥林匹克题5． 【解】 如图所示的平行四边形，由a、b、c、d四个数决定．这4个数满足 a≥1， b≥1， c≥0，d≥0 2≤a+b+c+d≤n 即 0≤a1+b1+c+d≤n-2 其中a1=a-1，b1=b-1，c，d均为非负整数． 因此平行四边形的总数为 【别解】 在BA、BC的延长线上分别取E、F，使BE=BF=n+1，则EF=n+1．图中的平行四边形，每一边恰好与EF相交于一点．这四点不同，都是EF上的格点（即将EF等分为n+1份的分点）． 反之，从EF的n+2个格点（包括E、F在内）中任取四点，过靠近E的两点作AB的平行线，过另两点作BC的平行线，便可得到一个图中的平行四边形，所以 E2-034 若平面上有997个点，如果每两点连成一条线段，且中点涂成红色．证明：平面上至少有1991个红点．你能找到一个正好是1991个红点的特例吗？ 【题说】 1991年亚太地区数学奥林匹克题2． 【证】 在给定的997个点中，设M、N两点间的距离最大，分别以 M、N为圆心，MN/2为半径作圆，这两个圆仅有一个公共点，即MN的中点E． 于是MP的中点必在⊙M内部或圆周上，这样的995个点互不相同．同理，NP的中点必在⊙N内部或圆周上，这样的995个点互不相同，而且与上面的995个中点均不相同，加上点E，共有2×995+1=1991个红点． x轴上横坐标分别为1，2，…，997的997个点就是满足要求的例子．  E2-035 A，B分别是坐标平面上的格点的集合： A={（x，y）|x，y为正整数，1≤x≤20，1≤y≤20} B={（x，y）|x，y为正整数，2≤x≤19，2≤y≤19} A中的点分别染成红色或蓝色．染成红色的点有219个，其中有180个包含于B中，又四个角上的点（1，1），（1，20），（20，1），（20，20）都染成蓝色． 将水平或垂直方向上相邻两点按下列要求用红、蓝、黑色的线段连接起来：两点均为红色时，用红线连接；两点均为蓝色时，用蓝线连结；两点为一红一蓝时，用黑线连结． 问：（长度为1的）黑线有237段时，（长度为1的）蓝线有多少段？ 【题说】 1992年日本数学奥林匹克预选赛题9． 【解】 集合A中有400个点，其中红点有219个，蓝点有181个，在B内有蓝点144个．A的四周有76个点，其中红点39个，蓝点37个（包括四个角上的点）．每个角上的点引出2条线段；每个边界上（除四个角）的点引出3条线段；每个B内的点引出4条线段．因此，对于蓝点共引出线段 2×4+3×33+4×144=683（段） 其中黑线有237段，所以蓝线有 683-237=446（段） 这些蓝线在上述计数时，被重复计算了一次，故实际上有蓝线 446÷2=223（段）  E2-036 设集合A={1，2，…，10}．A到A的映射f满足下列两个条件： （1）对任意X∈A，f(30)（x）=x； （2）对每个正整数k，1≤k≤29，至少存在一个a∈A，使得f(k)（a）≠a． 其中f(1)（x）=f（x），f(2)（x）=f（f（x）），…，f(k+1)（x）=f（f(k)（x）），…．求这样的映射的总数， 【题说】 1992年日本数学奥林匹克预选赛题12． 【解】 设A划分成3个互不相交的子集： {a1，a2，a3，a4，a5}∪{b1，b2，b3}∪{c1，c2} 并且定义映射f：f（a1）=a2，f（a2）=a3，f（a3）=a4，f（a4）=a5，f（a5）=a1；f（b1）=b2，f（b2）=b3，f（b3）=b1；f（c1）=c2，f（c2）=c1．5，3，2两两互素，30是它们的最小公倍数．由条件知，f不是恒等映射，且 f由若干个循环组成，这些循环的阶数的最小公倍数应为30．从而，f是满足条件（1）、（2）的唯一一类映射． 所以，f的总数相当于从10个元素中选取5个，再从剩余的5个中选3个，它们再分别进行循环排列的个数．故所求映射的总数是   E2-037  一副牌有 2n+ 1张，由一张王及标 1至 n的牌每种各两张组成．这2n +1张排成一行，王在正中间，对每个k，1≤k≤n，两张标k的牌之间恰有k-1张牌．确定所有不超过10并且有这种排法的n．对哪些n，不可能这样排？ 【题说】第二十四届（1992年）加拿大数学奥林匹克题5． 【解】设标i的牌，从左数起位置为ai与bi（ai＜bi，i=1，2，…，n．因为王牌位置为n+1，bi=i+ai，所以 即 因此4｜n（n+1）． n=1，2，5，6，9，10不满足上述要求． n=3时，解为232J311． n=4时，解为2423J4311． n=7时，解为2723563J7546114． n=8时，解为78426247J86531135．  E2-038  在4000至7000之间有多少个四个数字均不相同的偶数？ 【题说】第十一届（1993年）美国数学邀请赛题1． 【解】答：728． 若千位数字为4或6，这时千位数字有2种选法，个位数字有4种选法，百位数字有8种选法，十位数字有7种选法．所以共有2×4×8×7=448个数符合要求． 同理，若千位数字为5，有 1× 5× 8× 7= 280个偶数符合要求． 所以，共有448+280=728个．  E2-039  令S为一个有6个元素的集合．问有多少种不同的方法可以把S分成两个不一定不同的子集，使得这两个子集的并恰好是S？两子集的顺序不必考虑，如{a，c}，{b，c，d，e，f}与{b，c，d，e，f}，{a，c}算一种分法． 【题说】第十一届（1993年）美国数学邀请赛题8． 【解】365． 设S=AUB，S中每一个元素，或属于A，或仅属于B，或同时属于A、B，共3种情况． 所以如果S中有n个元素，共有3n种方法选择集合A和B．除了A=B=S的情况，如果不计顺序每种情形算了2次，所以共有 种分法．特别地，n=6时，共有365种分法． E2-040  红色和白色的椅子各有5张，围成一个圆圈，共有多少种不同的排法？同色的椅子是没有区别的，经旋转后排列的顺序一致的排法只算1种． 【题说】1994年日本数学奥林匹克预选赛题7． 【解】将椅子的位置编号为0～9．红色椅子的位置是集合A={0， 然有f(10)（R）=f（R）．从而使得f(n)（R）=R的最小正整数n0必是10的约数．每种这样的排法R都被重复计算了n0次． r1+r2+…+r5≡（r1+5）+（r2+5）+…+（r5+5）（mod10） ≡（r1+…+r5）+25（mod10） 所以 25≡0（mod10） 这不可能．所以n0≠5． 若n0=2，易知只有R={0，2，4，6，8}和{1，3，5，7，9}满足要求．除此以外的250种R，其n0均为10．故所求的排法数为   E2-041 A={0，1，2，3，4，5，6，7，8，9}，满足下列条件（1），（2）的子集S有多少个？ （1）S的元素有5个； （2）S中任意两个不同元素的和的个位数字恰好是0到9这10个整数． 【题说】 1994年日本数学奥林匹克预选赛题10． 【解】 这样的子集不存在，即满足条件的S的个数为0． 事实上，若存在满足条件的子集S={a1，a2，a3，a4，a5}，由于 4（a1+a2+a3+a4+a5）≡0+1+…+9（mod10） 上式左边为偶数，右边为奇数，不可能． E2-043 用94块大小尺寸均为4″×10″×19″的砖，一块放在另一块的上面堆积成一个94块砖高的塔，每块砖可随意摆放为塔提供4″或10″或19″的高度．若94块砖全部用上可摆放多少种不同高度的塔？ 【题说】 第十二届（1994年）美国数学邀请赛题11． 【解】 设有x块砖提供10″的高度，y块砖提供19″的高度，x、y都是非负整数，且x+y≤94，则塔的高度为 h=4（94-x-y）+10x+19y=376+3（2x+5y）            （1） 如果x≥5，则将x换成x-5，y换成y+2，由（1）表示的塔高取同样值，并且（x-5）+（y+2）≤94．所以可以假定x≤4．这时相同的x，不同的y表示的塔高h显然不同．如果x取不同值x1、x2（0≤x1＜x2≤4），那么对任意的y1、y2， （2x2+5y2）-（2x1+5y1）=2（x2-x1）+5（y2-y1）   （2） 前一项不被5整除，后一项被5整除，所以（2）不为0，即相应于x1、x2的塔高不同． 当x=0，1，2，3，4时，y分别有95（0～94），94，93，92，91种取法．所得的塔高均不同．所以共有 95+94+93+92+91=465 种不同高度的塔．  E2-044 设p是一个奇素数，考虑集合{1，2，…，2p｝的满足以下两条件的子集A： （i）A恰有p个元素； （ii）A中所有元素之和可被p整除． 试求所有这样的子集A的个数． 【题说】 第三十六届（1995年）国际数学奥林匹克题6． 与V={p+1，p+2，…，2p}外，每一个p子集与U、V的交均非空．将这些子集分类，如果子集S、T与V的交S∩V=T∩V，并且S∩U的每个元加上k（mod p）就得到T∩U的每个元，这里k∈{0，1，2，…，p-1}，那么就将S与T归入同一类．对于{0，1，2，…，p-1}中不同的k1、k2，由S得到的集T1、T2，元素和σ（T1）、σ（T2）的差≡（k1-k2）m（modp），这里m=S∩U的元素个数．由于S与U、V的交均非空，0＜m＜p，所以（k1-k2）m 0（modp），即T1≠T2．因此，每一类中恰好有p个集，并且这些集的元素之和modp各不相同．于是其中恰有一个集元素之和被p整除．从而所求子集A的个数为   E2-045 4对夫妇去看电影，8个人坐成一排．若女性的邻座只能是其丈夫或其他女性，共有几种坐法？ 【题说】 1995年日本数学奥林匹克预选赛题6． 【解】 先将女性排定，有4！种方法．女性与女性之间若坐着男性（包括这些女性的丈夫）必不少于两个．同样，在男性与男性之间坐着的女性也必不少于两个．把座位连在一起的女性视为一组，则4位女性的分组方式有4，3+1，2+2，2+1+1，1+1+1+1等五种． 孤立坐着的女性必须在这一排座位的两端，所以1+1+1+1的分组方式不合要求．女性分成2+1+1时，两端必须坐着女性，这时男性只能分成2+2，即下表中的第1类，男性的排法只有1种．女性分成2+2时，有下表的2，3，4，5四类，男性的排法分别有2，1，1，1种．女性分成3+1时，有下表的6，7，8三类，男性的排法分别有2，1，1种．女性4人连排时，有下表的9，10，11三类，男性的排法分别有3！，2！，2！种．于是排法总数为 4!×（1+2+2×1+2×1+1+2×2+2×1+2×1+2×3!+2×2!+2!） =24×34=816 1．女男男女女男男女 2．女女男男男男女女 3．女女男男男女女男 或  男女女男男男女女 4．女女男男女女男男 或  男男女女男男女女 5．男女女男男女女男 6．女女女男男男男女 或  女男男男男女女女 7．男男女女女男男女 或  女男男女女女男男 8．男女女女男男男女 或  女男男男女女女男 9．女女女女男男男男 或  男男男男女女女女 10．男男男女女女女男 或  男女女女女男男男 11．男男女女女女男男 E2-046 用六种不同颜色中几种染一个正方体各面，要求相邻两面不同色，问有多少种不同的染色法？（两个染色正方形，如果能通过转动、翻身使二者各面颜色对应相等，则认为是染色法相同） 【题说】1996年全国数学联赛一试题2（5），原为填空题． 【解】 分4种情况讨论： 1°用了6种颜色．将一种颜色染下底，则上底有5种染法．固定一种颜色朝东，其它三面有3！种染法．共有5×3！=30种． =90种． 所以染色法共有30+90+90+20=230种．  E2-047 在直角坐标平面上，以（199，0）为圆心、以199为半径的圆周上，整点的个数有多少个？ 【题说】 1996年全国数学联赛一试题2（6），原为填空题． 【解】 该圆方程为 （x-199）2+y2=1992                                                                                （1） 显然，（1）有4个整数解：（0，0），（199，199），（199，-199），（389，0）． 当y≠0、±199时，|y|与199互素，故由（1）知|x-199|、|y|、199是一组基本勾股数． 由勾股数基本公式知，存在二正整数m、n使199=m2+n2． 由于平方数≡0或1（mod4），所以m2+n2≡0，1或2（mod4），但 199=4×49+3≡3（mod4） 矛盾．因此当y≠0、±199时，（1）无整数解． 综上所述，在（1）圆周上的整点只有4个．  E2-048 白（围棋）子5个、黑（围棋）子10个排成一横行，要求每个白子的右邻必须是黑子，共有多少种排法？ 【题说】1996年日本数学奥林匹克预选赛题2． 【解】先将10个黑子排成一行，每个黑子的左邻都留一个空位，从   E2-049 设n为正整数，S={1，2，…，n}．S的（非空）子集A，B，C，D满足A∪B∪C∪D=S且A∩B∩C=φ，这样的集合组（A，B，C，D）有多少个？ 【题说】 1996年日本数学奥林匹克预选赛题10． 【解】根据k（1≤k≤n）是否属于A，B，C，D，分别有24=16种情形．在这些情形中，（1）k不属于A，B，C，D；（2） k属于A，B，C，但不属于D；（3）k属于A，B，C，D．这3种情形与要求不符．其余13种情形均合要求．对每个k（1≤k≤n）都有13种情形，故共有13n个满足题设要求的集合组． E2-050 一个7×7的棋盘的2个方格着黄色，其余的方格着绿色．如果一种着色法可从另一种着色法经过在棋盘的平面中的旋转而得到，那么这两种着色法看做同一种．可能有多少种不同的着色法？ 【题说】 第十四届（1996年）美国数学邀请赛题7． 如果这一对方格关于棋盘中心中心对称，那么旋转后可与另一对方 不关于棋盘中心中心对称，那么绕中心旋转90°、180°、270°，分别与另外三对方格重合，经过旋转也只可能与这三对重合．因此不同的 E2-051 对每个实数x，以[x]记不超过x的最大整数．有多少个正整数n，使得n＜1000且[log2n]是正偶数？ 【题说】 第十四届（1996年）美国数学邀请赛题2． 【解】 22k≤n＜22k+1时，[log2n]=2k．所求n的个数为 23-22+25-24+27-26+29-28=340  E2-052 两个正数的调和平均是它们的倒数的算术平均的倒数．有多少个正整数的有序对（x，y），使得x＜y且x与y的调和平均等于620？ 【题说】 第十四届（1996年）美国数学邀请赛题8．   E2-053 一个150×324×375的长方体由1×1×1的单位立方体胶合在一起而做成的．这长方体的一条内对角线穿过多少个单位立方体的内部？ 【题说】 第十四届（1996年）美国数学邀请赛题14． 【解】 从左到右151个互相平行两两距离为1的平面与对角线有151个交点，将对角线分为150段．同样从上到下，从前到后的两两距离为1的平面又增加一些分点，除去对角线的一端外，共有 150+324+375-（150，324）-（150，375）-（324，375）+（150，324，375） =768 个分点．将对角线分为768段，每段属于一个单位立方体，即对角线穿过768个单位立方体．  E2-054 在1至1000000的自然数中，包括可表为完全平方数与完全立方数之和形式的自然数，以及不能表为这种形式的自然数．试问哪种形式的数较多？ 【题说】 第二十二届（1996年）全俄数学奥林匹克九年级题1． 【解】 不能表为这种形式的自然数较多． 设n=k2+m3，其中k、m∈N，n≤1000000．显然，这时k≤1000，m≤100．所以能表成这种形式的数不超过100×1000=100000个，少于1000000的一半．  E2-055 有多少对正整数x、y满足x≤y，并且最大公约数（x，y）=5！，最小公倍数[x，y]=50！？ 【题说】 第二十九届（1997年）加拿大数学奥林匹克题1． 【解】 设x=5！a，y=5！b，a、b为互质的自然数，则[x，y]=5！[a，b]=5！ab．所以 其中a1，…，a15都是正整数． 由于a、b互质，所以每一因数pa（p∈{2，3，5，…，47}）或者是a的因数，或者是b的因数，两种情况恰好出现一种，而 a≤b，   E2-056 平面上给定五个点，这些点两两之间的连线互不平行，又不垂直，也不重合，从任何一点开始，向其余四个点两两之间的联线作垂线，如果不计已知的五个点，所有这些垂线间的交点数最多是多少？ 【题说】 第六届（1964年）国际数学奥林匹克题5．本题由罗马尼亚提供． 再因每三点构成一个三角形，这个三角形的三条高共点，应从中减 所以，交点最多有 E2-057 某委员会开了40次会议，每次有10人出席，而且委员会任意两个成员都未在一起出席过一次以上的会议，证明：该委员会成员一定多于60． 【题说】 1965年全俄数学奥林匹克十年级题2． 会议，可以组成不同的两人组共有45×40=1800个，但由60人最多只 定多于60． 次会议，与他同出席会议的人都不相同，从而人数≥7×9=63＞0，矛盾．  E2-058 在平面上给出n（≥3）个点，其中任两点的距离最大为d．距离为d的两点间的线段称为这组点的直径．证明：直径的数目至多n条． 【题说】 第七届（1965年）国际数学奥林匹克题6．本题由波兰提供． 【证】 假定直径多于n条．如果从某个点出发的直径少于两条，我们就把这点除去，剩下的n-1个点至少有n条直径，显然n-1≥3，故不妨假设从每一点都至少引出两条直径． 因为直径数目比点多，而每条直径都连结两个点，所以至少有一点A引出三条直径AB、AC、AD，每两条直径的夹角不超过60°，否则另一端的距离大于d．不妨设AD在AB与AC之间，因此，⊙（A，d）（以A为圆心，d为半径的圆）、⊙（B，d）、⊙（C，d）的公共部分覆盖了整个点集，而与D距离为d的点只有A点一个（图中， 以DG＜CG=d．同理可证D到除A外的其它点距离＜d）．即D点只引出一条直径，矛盾！故命题成立．  E2-059 某国已经建立起航空网，任何一个城市与不多于三个城市相连结，而且任何一个城市到另一个城市最多只换乘一次，问这个国家最多有多少个城市？ 【题说】 第三届（1969年）全苏数学奥林匹克八年级题5． 【解】 任一城市O与三个城市A、B、C连结．这三个城市中的每一个至多分别与两个城市相连结．这样，城市的个数≤1+3+3×2=10． 如图所示，恰有10个城市的图在图论中称为彼得森图．  E2-060 有20个队参加全国足球冠军决赛．为了使任何三个队中都有两个队相互比赛过，问至少要进行多少场比赛？ 【题说】 第三届（1969年）全苏数学奥林匹克九年级题6． 【解】 把20个队分成两个组，各有k个队和20-k个队，使每个组中的所有队之间都比赛一次，这样比赛的次数为 由于任何三个队中至少有两个队在同一组，而同一组的两个队都相互比赛过，所以至少需90场比赛，当两组各有10个队时，恰好比赛90场．  E2-061 网球协会为全体会员排定名次，最强的为第1号，其次为第2号等等．已知，在名次相差高于2的运动员比赛时，总是高名次的运动员获胜．在由1024名最强的选手参加的循环赛中（即参加者为1号选手到1024号选手），按奥林匹克规则进行：每一轮比赛的每对选手都由抽签决定，胜者进入下一轮．因此，每一轮比赛后参赛者将减少一半．这样一来，第十轮后将决出胜者．试问，胜者的最大号码是多少？ 【题说】 第七届（1973年）全苏数学奥林匹克九年级题4． 【解】 胜者的最大号码是20号． 因为不计比他强的选手时，k号选手只可能输给k+1号和k+2号选手，所以，胜1号选手的号数至多为3，胜3号的号数至多为5，…．因此，冠军的号数不可能低于1+2×10=21．但在冠军号数为21时，第一轮比赛后应淘汰1号和2号选手，他们分别败于3号和4号选手；在第二轮中3号，4号被淘汰，5号、6号取胜，等等．依此类推，直到第九轮，在该轮比赛中19号和20号选手应分别战胜17号和18号选手，这样，21号选手将不会进入决赛． 下面举一个第20号选手获胜的赛例，全体参赛者按每组512人分成两组，第一组中包括第19号，20号及其他510名较弱的选手，该组的比赛使得第20号选手获胜（显然，这是可能的）．在第二组中有1号至18号选手及其余较弱的选手，在该组比赛中使第18号选手获胜，这只要出现前面所说的情况，是可以作到的：第一轮中3号，4号分别战胜1号，2号；第二轮中5号，6号战胜3号，4号等等；到第八轮，第17号和18号选手战胜15号和16号选手，在第九轮中18号选手战胜17号选手．这样，参加决赛的将是第20号选手和第18号选手，于是，20号选手可能获胜．  E2-062 把一个8×8的棋盘（指国际象棋棋盘）剪成p个矩形，但不能剪坏任何一格，而且这种剪法还必须满足如下条件： （1）每一个矩形中白格和黑格的数目相等； （2）令ai是第i个矩形中的白格的个数，则 a1＜a2＜…＜ap 求出使上述剪法存在的p的最大可能值，同时对这个p求出所有可能的a1，a2，…，ap． 【题说】 第十六届（1974年）国际数学奥林匹克题4．本题由保加利亚提供． 由此可知p≤7．p=7时只有五种可能的组合： 第一种组合不可能在棋盘上实现，因为棋盘上剪出的矩形不可能是22格的，其他四种情况都是可以实现的，如上图所示（图中数字表示该块含方格数）． E2－063 在一张正方形纸上画出n个边与纸的边平行的矩形，这些矩形中任两个都没有公共内点，证明：如果剪下所有的矩形，那么纸片数不大于n+1． 【题说】 第十届（1976年）全苏数学奥林匹克十年级题3． 【证】 设纸片数为k，在每张纸片上标出4个顶点（纸片上可能不止四个顶点），这些顶点每一个都是矩形的顶点，或原正方形的顶点，如果两张纸片上标出的两个顶点实际上是同一个点，那么这一点一定是原来靠在一起的两个矩形的共同顶点．因此 4k≤4n+4 从而得                                           k≤n+1  E2－064 某区学生若干人参加数学竞赛，每个学生得分都是整数，总分为8250，前三名的分数是88、85、80，最低是30分，得同一分数的学生都不超过3人．问至少有多少学生得分不低于60分（包括前三名）？ 【题说】 1979年全国联赛二试题7． 【解】 除了前三名外，得分为30～79，总分为8250-（88+85+80）=7997．其中分数为30～59的人至多（每种分数三人），共得（30+31+…+59）×3=4005分，因此至少有7997-4005=3992分分配给60～79分的人．由于（79+78+…+61）×3=3990＜3992，所以60～79的人数至少为3×（79-61+1）+1=58． 故得分不低于60分的学生总数为61人（包括前三名）．  E2－065 一个团体有1982人，在任何4人的小组中，至少有一人认识其他3人，问在此团体中，认识其他所有人的最少人数是多少？ 【题说】 第十一届（1982年）美国数学奥林匹克题1． 【解】 认识可能是双方的，也可能是单方的． 1．假设认识按双向性理解，作一个有1982个点的图G，每点代表一个人，若两人彼此不认识，就将相应两点连一条边，认识者不连．于是，我们的问题变为：已知在此图中，每四点所成之子图，至少有一孤立点，问图中最少有多少个孤立点？ 设G中有边AB．若又有边CD连结另两点C、D，则A、B、C、D四点所成子图中无孤立点，矛盾．因此G中任一点或者是孤立点，或者与A或B相连．设点C与A相连，则对任一点D，由于A、B、C、D所成子图中有孤立点，所以D不与A、B相连，从而（根据上面所证）D为G的孤立点．于是G中至多有A、B、C三点非孤立点，至少有1979个孤立点，即该团体中至少有1979个人认识其他所有人． 2．若认识是单向的，设1982人围成一圆圈，每人皆不认识其右邻，但认识其余的人．容易证明，任4人中都至少有一人认识其他三人，但团体中无一人认识其他所有人，即认识所有其他人的人数最少是0．  E2－066 设S是边长为100的正方形，L是在S内自身不相交的折线段A0A1，A1A2，…，An-1An（A0≠An）．假定对于边界上每一 有两点X、Y，它们之间的距离不大于1，沿折线L，它们之间的距离不小于198． 【题说】 第二十三届（1982年）国际数学奥林匹克题6． 【解】 根据题设，对于正方形的顶点S1，S2，S3，S4，在折线L 在沿L由A0到An时，不妨假定先经过L1，并且在L2与L4中，先出现的是L2． 将S1S4上的点分为两类：如果Q在A0L2这一段，P在第一类，如果Q在L2An上，P在第二类．显然S1在第一类，S2在第二类，所以两类都是非空的，这两类可以有公共点（原因见后）．如果P0是公共点，那么 另一方面，从Q1沿着L到Q2必须经过L2，而Q1到L2这段长≥ 以Q1、Q2之间的L的长≥198． Q1、Q2就是要求的点X、Y． 最后来说明上面定义的两个类的公共点P0是存在的．设在边S1S4的从S1到S4的方向上，第一类的点最远能延伸到P0，从S4到S1的方   E2－067 在平面上画出n（n≥2）条直线，将平面分成若干个区域，其中一些区域上涂了颜色，并且任何两个涂色的区域没有相邻的边界．证明：涂色的区域数不超过（n2+n）/3． 【题说】 第十九届（1985年）全苏数学奥林匹克十年级题4．只有一个公共点的两个区域，不认为是有相邻接的边界． 【证】 如果所画的直线都互相平行，那么它们将平面分成（n+1）个区域，这时能涂色的区域不超过n个．因为 （n2+n）/3=n（n+1）/3≥n（2+1）/3=n 所以此时命题成立． 设并非所有直线都互相平行，每个区域的边界由若干条位于不同直线上的线段或射线组成，这些线段和射线称为区域的边．每个区域的边数不少于2．用m2表示有两条边的涂色区域的个数；m3表示有三条边的涂色区域的个数，等等，我们用mk表示边数最多的涂色区域的个数． 首先证明m2≤n．任何有两条边的区域的边界是由两条射线组成的，并且每条射线只能是一个涂色区域的边界，所有这样的射线不超过2n条（每条直线上的射线不超过两条）．所以有两条边的涂色区域的边数不超过2n，即m2≤n·n条直线中的每一条被分成的区间（线段或射线）数不多于n，所以所有的区间数不超过n2，因而所有区域边的总数也就不超过n2条．由于每个区间至多是一个涂色区域的边，所以2m2+3m3+…+kmk≤n2，涂色的区域数 m2+m3+…+mk ≤n2/3+（2m2+3m3+…+kmk）/3 ≤n/3+n2/3=（n2+n）/3  E2－068 儿童计数器的三个档上各有十个算珠，如图，将每档算珠分为左右两部分（不许一旁无珠）．现在要左方三档中所表示的三个珠数的乘积等于右方三档中所表示的珠数的乘积．问有多少种分珠法？ 【题说】 1987年北京市赛高一题5． 【解】 不妨设左方上中下三档珠数分别为a、b、c，则右方上中下三档珠数分别为10-a、10-b、10-c，依题意得： abc=（10-a）（10-b）（10-c）                                               （1） 即  abc=500-50（a+b+c）+5（ab+bc+ca） 因1≤a、b、c≤9，且5|abc，故a、b、c三数中至少有一个是5 若只有一档珠数为5．不妨设a=5．（1）式化为： bc=（10-b）（10—c）=100-10（b+c）+bc 即                                                          b+c=10 这时b可以取1，2，3，4，6，7，8，9；而c相应取9，8，7，6，4，3，2，1．共得8种分珠法． 同理，若b=5（a、c均不等于5），或c=5（a、b均不等于5），也各有8种分珠法． 显然a=5，b=5，c=5时，也是一种分珠法（注意：若a、b、c中有两个是5，则第三个也必然是5）． 综上可知，总计共有8+8+8+1=25种分珠法．  E2－069 五对孪生兄妹参加k个组的活动，若规定：（1）孪生兄妹不在同一组；（2）非孪生关系的任意两个人都恰好共同参加过一个组的活动；（3）有一个人只参加两个组的活动．求k的最小值． 【题说】 1987年全国联赛一试题2（5）．原题为填空题． 【解】 用A、a、B、b、C、c、D、d，和E、e表示五对孪生兄妹． 不妨设A只参加两个组的活动，要同时满足（1）、（2），这两组要包含除a外的其余8人，同时每组各为5人（不然，则有一组包含一对孪生兄妹）．由对称性，这两组可以设为（A，B，C，D，E）和（A，b，c，d，e）．再考虑a，为使编组尽可能地少，可在B，C，D，E与b，c，d，e中各取一个（二者非孪生兄妹）编为4组： （B，a，c），（C，a，b），（D，a，e），（E，a，b） 最后，将余下没有编在一组的非孪生关系的，每两人编为一组，共8组： （B，d）（B，e）（C，d）（C，e）（D，b）（D，c）（E，b）（E，c） 总共14组，所以k的最少值为14．  E2－070 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程．求所有可能出现的比赛过程的种数． 【题说】 1988年全国联赛一试题2（4）．原题为填空题． 【解】 设甲队胜，则甲队必在前13场比赛中胜7场，可能情况有   E2－071 给定平面上的点集P=｛P1，P2，…，P1994｝，P中任三点不共线，将P中点任意分成83组，使每组至少有3个点，每点恰好属于一组．将每组中任二点均连成一线段，不在一组的两点不连线段．这样得到了一个图G．显然，不同连结线段的方式，得到不同的图．图G中所含以P中点为顶点的三角形的个数记为m（G）． （1）求m（G）的最小值m0； （2）设G*是使m（G*）=m0的一个图，若将G*的线段用4种颜色染色，每条线段恰好染一种颜色．则存在一种染色法，使G*中线段染色后，不含有同色边三角形． 【题说】 1994年全国联赛二试题4，这是一个图论问题． 【解】（1）设各组所含点数为x1，x2，…，x83，则x1+x2+…+x83=1994．且 若x1-x2＞1，将第一组移到第二组．因为 m（G）将减小．所以在m（G）最小时，每两个xi的差≤1． 因                              1994=83×24+2=24×81+2×25 故符合条件（*）的分组法只有一种：81组各含24点，2组各含25点．这时 （2）对25点的组染色如下：将点分为5组y1，y2，y3，y4，y5，每组5点；每组线段按图a染a、b二色；不同组间的连线，按图b方式染另二色c、d． 这样染色，没有同色边的三角形．至于24点的组，只须从25点的组中去掉一点，以及连结它的所有线段即可，当然也不会有同色边的三角形出现．  E2－072 某城市是长宽各为10km的正方形．城内有间隔各为1km的棋盘街，东西走向和南北走向各11条．东西走向道路所在的直线记为y=m（m=-5，-4，…，4，5），南北走向道路所在的直线记为x=n（n=-5，-4，…，4，5）．某公司在该市开设5个分店Ak（k=1，2，…，5），它们分布在棋盘街道路沿线，其坐标（xk，yk）分别是（-5，1.3），（2，4.5），（4.4，3），（4，-1），（-2.7，-2）．分店各派出1名店员，沿棋盘街道路行走，到街道沿线的某地会合．要使得店员们行走的路程总和S（x，y）最小，求该地的坐标． 【题说】 1994年日本数学奥林匹克预选赛题12． 【解】 易知，所求的坐标（x，y）中至少有一个为整数，且 若（x，y）不是格点（x，y均为整数的点），例如，设m、n为整数，而x=n，m＜y＜m+1．在（x，y）不是分店时，5个店员中有a人自北向南而至，b人自南向北而至．当会合点向来人较多的方向移动时，S（x，y）将变小．直到这个会合点移至格点或某个分店为止．可能存在这样的分店Ak，其坐标xk≠n，m＜yk＜m+1．由它出发，到（x，y）点的路程不论由南向北来还是由北向南来，都是相等的．此时（x，y）向南或向北移动，该店店员所走的路程都是减少的，因而只需考虑其他的人． 当y是整数而x不是整数时，考虑会合点东西向的移动，可得同样的结论． 综上所述，所求的点必为格点或某分店所在地． 由于题中的坐标xk（k=1，…，5）与yk（k=1，…，5）的中位数分别是x=2，y=1.3．而最接近（2，1.3）的是格点（不是某分店）（2，1）．即在格点（2，1）处会合，S（x，y）最小．  E2－073 一块用栅栏围成的长方形的土地大小为24m×52m，一位农业科技人员欲将这块土地从内部分割为一些全等的正方形试验田．要求这块土地全部被划分而且分割成的正方形的边与土地的边界平行．试问若有1994m栅栏，最多可将这块土地分成多少块正方形试验田？ 【题说】 第十二届（1994年）美国数学邀请赛题12． 总长度是 （m-1）52+（n-1）24=k（6·52+13·24）-（52+24）                                                   =624k-76≤1994 所以 故k的最大值为3，此时正方形的总数为 mn=（6·3）（13·3）=702  E2－074 某种绘图装置可沿横、纵、斜方向以每秒1cm的速度移动，该装置可在纸面上描出线来，也可以离开纸面在空中运行．现用这个装置绘制右边的图形，问至少要用几秒？图中各角均系直角，该装置离开纸面的时间略而不计． 【题说】 1995年日本数学奥林匹克预选赛题2． 【解】 当图形成一笔画时用时最少．但上图有4个奇顶点，要使之成为一笔画，须用一条线段连接其中两个奇顶点．显然，用线段将AB连接，则由C开始到D结束构成一笔画图形，其中该装置在A到B部分   E2－075 在100×25的长方形表格中每一格填入一个非负实数，第i行第j列中填入的数为xij（i=1，2，…，100；j=1，2，…，25）（如表1）．然后将表1每列中的数按由大到小的次序从上到下重新排列为x′1j≥x′2j≥…≥x′100j，j=1，2，…，25．（如表2） 2，…，100），则当i≥k时，在表2中就能保 【题说】 1997年全国数学联赛二试题3． 【解】 将表2中x′98,1，x98,2，…，x′98,25，…，x′100,1，x′100,2…，x′100,25所在的行划去，至多划去75行，剩下的每一行，行中的第j个数不小于x′97，j（1≤j≤25），因此表2中第97行的行和≤表1中剩下的每一行的行和．在表1各行的行和≤1时，表2的第97行的行和≤1，第98、99、100行的行和当然更≤1． 另一方面，作表1，使得1—4行中，第一列数为0；5—8行中，第二列数为0；…；96—100行中，第25列数为0，其余的数均为1/24．显然，此表中各行之和均为 满足条件．由此表1得到的表2，1—96行的数全是1/24，故第96行的和 综合以上两方面，知k的最小值为97．  E2－076 已给集合S=｛1，2，3，…，1997｝，A=｛a1，a2，…，ak｝是S的子集，具有下述性质：“A中任意两个不同元素之和不能被117整除”．试确定k的最大值，并证明你的结论． 【题说】 1997年江苏省高中数学竞赛题5． 【解】 将集合S划分为两两不相交的子集的并；F0∪F1∪…UF116，这里Fi是S中除以117余数为i的元素的集合（i=0，1，…，116），Fi的元素个数记作|Fi|，则 |F0|=17，|F1|=|F2|=|F3|=…=|F8|=18，|F9|=…=|F116|=17.F0中的元素最多只能有一个选入A中，而Fk与F117-k中只能有一个集合的元素全在A中．为使A中元素尽量多，故应将F1，F2，…，F8全部选入A中．因此这个A中元素共有1+|F1|+|F2|+…+|F58|=995， 故kmax=995． E2－077 在平面上画出30条不同的线段时，线段的不同端点数至少有几个？ 【题说】 1997年日本数学奥林匹克预选赛题2． 点中的两个点引线，便得到30条线．因此，所求的端点数至少是9．