第142章 独特的城市,鸽笼原理

它往往是把锋利的武器。

眼下这道题也不例外。

既然是用鸽笼原理求解，那么首先，先制作一张21x21的表格，每一行每一列分别代表一个男生，一个女生，而中间围成的格子用来代表这个男生和这个女生同时做对的任意一道题目，由题设可知对于任一对男生和女生，至少有一道他们都做对了的题。

假设，如果这道题至少有三个男生答对，就在格子里填一个如果至少有三个女生做对，就填一个f，也就是说，如果3号男生和4号女生都同时做对的题目是q1，那么坐标（3，4）的格子就代表题目q1。

如果q1有三个男生做对，那么就在这个格子里填一个又正好有五个女生做对，那么就再填一个f。

于是，这道题的证明就变成了，证明这张表格中至少有一个格子里同时出现f。

我们假设这样一种情况并不存在，但是根据题设，每个参赛者最多作对了6道题，又对于任一对男生和女生，至少有一道他们都做对了的题，所以我们可以去构造这样一种最少的情况。

假设一个男生只答对了一道题，那么他做对的，就应该是格子对应的那道题，也就意味着这道题有21个女生做出，那么这个男生所在的这一行格子里都会被填上f。

为了让f尽可能的少，那么只能是这个男生答对了6道题，并且其中五道题都只有两个女生答对，那么剩下的一道题则有11个女生答对，所以只会产生11个f。

所以，男生所在的每一行都至少会有11个f，同样的，女生所在的每一列，都至少有11个

那么这样所产生的f的个数就为21x11x2，但是格子总数只有21x21，根据鸽笼原理，至少存在21个格子同时被填上了f和

只用了两分钟，陈辉就完成了第一道题的证明，他相信，这样一道题，就算是还在上小学的蕊蕊，也能很快做出

本章未完，请点击下一页继续阅读！ 第8页 / 共9页