《信息学奥林匹克联赛初赛试题(c-普及组)--推理题》由会员分享，可在线阅读，更多相关《信息学奥林匹克联赛初赛试题(c-普及组)--推理题（4页珍藏版）》请在金锄头文库上搜索。
1、在平面内任取在平面内任取 n n 个整点（横纵坐标都是整数），其中一定存在两个点，它们个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么连线的中点也是整点，那么 n n 至少是？至少是？建立直角坐标系来解决这个问题 设所取得 n 个点的坐标为 （X1，Y1），（X2，Y2），（Xn，Yn） 1）当有三个点时 显然，三个点可以保证存在两个点使其中点的横坐标为整数 （这是因为任意三个数肯定存在同奇或同偶两个数） 但是不能保证这两个点中点的纵坐标也是偶数 比如取（奇，偶），（奇，奇），（偶，奇）这三个点就是一个反例 2）当有四个点时 接着用上面的方法进行分析，可知，如下情况
2、是一个反例 （其中“奇”代表奇数；“偶”代表“偶数”） （奇，奇），（奇，偶），（偶，奇），（偶，偶） 3）当有五个点时 当有五个点时，至少存在三个点，其横坐标同奇或同偶，而这三个点中，至少存在两个点是同奇或同偶的，那么可以判定，这两个点的横纵坐标的奇偶性完全一样，因此这两个点的中点是个整点 综上所述，平面上任取五个整点,可以保证其中存在两个点，其中点为整点想象横纵交错的网格纸，就像棋盘那样的，每个横纵线交点就是一个整点。如下图向左转|向右转任意三个点如果共线，即处在水平，竖直，或者对角线上，则其中定存在两个点满足连线中点是整点。点共如果 n=2，取两个连续的整点，那么连线中点不是整点。如果
3、n=3，取水平两个连续的点，垂直也两个连续的点，组成三角形。那么连线中点不是整点。如果 n=4，取四个整点组成一个正方形，则连线中点不是整点。而取 5 个点的话，必然有两个点的连线中点是整点。在 NOI 期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有五名大陆选手和五名港澳选手共同进膳。为了增进交流，他们决定相隔就做，即每个大陆选手左右相邻都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么，这一桌共有多少种不同的坐做方案？（注意：如果在两个方案中，每个选手左右相邻的选手均相同，则视为同一个方案。）这是个排列着组合问题啊。就是我没明白 5 个大陆人算是一种人还是分别
4、不 同的人、港澳的也是 如果分别为不同的人。则。总共 10 个人，以餐桌中任意一个座位开始，以大 陆人中五个选一个放在第一个座位，即 C5 1 他旁边的是港澳的 C5 1 。 然后大陆剩下四个人 C4 1 港澳也是 C4 1 同理依次推出。5*5*4*4*3*3*2*2*1*1=你自己算一下 啊 如果他们只代表的是大陆和港澳，算一种人，则只有一种方法，就是岔开做相当于 1 个圆，十个人。先随便找个座，让人去坐，有 10 个可能，然后顺 时针走，下一个座就有 5 种可能，再下一个就 4 个，再下一个还是 4 个，以此 类推，就是 10*5*4*4*3*3*2*2*1*1。这其中有重复的，同一种坐
5、法，可以绕着桌子走一圈，就是上一个人坐到下一个人的位置，串一下，这样所有坐法就算 重复了 10 次，再除以 10 就行了。就是 5*4*4*3*3*2*2*1*15！*5！/5=14400/5=2880 种两个 5！分别是大陆选手和港澳选手的就坐方案，相乘后，再除以 5 中重复的方案。小陈现有小陈现有 2 2 个任务个任务 A A，B B 要完成，每个任务分别有若干步骤如下：要完成，每个任务分别有若干步骤如下：A=a1-a2-A=a1-a2-a3a3，B=b1-b2-b3-b4-b5B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步。在任何时候，小陈只能专心做某个任务
6、的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3a2-b2-a3-b3是合法的，而是合法的，而a2-b3-a3-b2a2-b3-a3-b2是不合法的。是不合法的。小陈从小陈从 B B 任务的任务的 b1b1 步骤开始做，当恰做完某个任务的某个步骤后，就停工回家步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经
7、完成了整个任务吃饭了。当他回来时，只记得自己已经完成了整个任务 A A，其他的都忘了。试，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有计算小陈饭前已做的可能的任务步骤序列共有 种。种。解法一：解法一：相当于以前的相当于以前的 A 到到 B 路程的问题，呵呵路程的问题，呵呵a3 0 1 4 10 20 35a2 0 1 3 6 10 15a1 0 1 2 3 4 50 1 1 1 1 1b1 b2 b3 b4 b5看懂了吗？学过奥数的应该能明白吧。然后把看懂了吗？学过奥数的应该能明白吧。然后把 a3 那一行加起来那一行加起来 1+4+10+20+35=70。解法二：解法二：排列组合排
8、列组合+加法原理加法原理B 任务中的任务中的 b1 一定做，而且肯定是第一个做的。除了一定做，而且肯定是第一个做的。除了 b1 外，外，第一类：完成第一类：完成 A 任务任务 只有只有 1 种。种。第二类：完成第二类：完成 A 任务和任务和 b2 有有 C(4,1)=4 种。种。第三类：完成第三类：完成 A 任务和任务和 b2、b3 有有 C(5,2)=10 种。种。第四类：完成第四类：完成 A 任务和任务和 b2、b3、b4 有有 C(6,3)=20 种。种。第五类：完成第五类：完成 A 任务和任务和 b2、b3、b4、b5 有有 C(7,4)=35 种。种。加起来加起来 1+4+10+20
9、+35=70。给定给定 n n 个有标号的球，标号依次为个有标号的球，标号依次为 1 1，2 2，33，n n，将这，将这 n n 个球放入个球放入 r r 个相同的盒子个相同的盒子里，不允许有空盒，其不同放置方法的总数为里，不允许有空盒，其不同放置方法的总数为 S S（n n，r r），例：），例：S S（4 4，2 2）=7=7，这，这 7 7 种不同种不同的放置方法依次为的放置方法依次为 （1 1），（），（234234） ， （2 2），（），（134134） ， （3 3），（），（124124） ， （4 4），），（123123） ， （1212），（），（3434） ， （13
10、13），（），（2424） ， （1414），（），（2323） 。当。当 n=7n=7，r=4r=4 时，时，S S（7 7，4 4）= =将这将这 n n 个球放入个球放入 r r 个相同的盒子里，不允许有空盒，因为是个相同的盒子里，不允许有空盒，因为是“ “相同的盒子相同的盒子“,“,所以是一个组所以是一个组合问题合问题. .既将既将 n n 个球分成个球分成 r r 份份. .这样当这样当 n=7n=7，r=4r=4 时，将时，将 7 7 个球分成个球分成 4 4 份份, ,有三种分法有三种分法:(1):(1)分分为为 4,1,1,1(2)4,1,1,1(2)分为分为 3,2,1,1(3)3,2,1,1(3)分为分为 2,2,2,12,2,2,1 第一种分法有第一种分法有 C74=35C74=35 种种 第二种分法有第二种分法有 C73C42=210C73C42=210 种种 第三种分法有第三种分法有(C72C52C32)/3!=105(C72C52C32)/3!=105 种种 共计共计 350350 种种, ,所以所以 S S（7 7，4 4）= = 350350
