Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
推理证明在前三天中, 对于任何参与者, 比如A来说, 它认识了9人N1, 且有6人M1不识。 在第四天第五天A将从M1中依次选出3人与其共进晚餐。对于M1中的任何一人 (因为A必然要与任何一人同桌), 假设为B来说, 它已认识的9人为N2, 它所不 认识的6人为M2, 则M2与M1相交数仅等于2时才会有可行的方案。假设M1与M2 不相交, 则B所不认识的M2(除掉A剩余5人)只能是从A所认识的N1中选取的, 但事实上N1所在的第一天、第二天、第三天的集合中抽取的互不相识的人数 最多只可能是3个。由此可以推出M1与M2的相交集合至少是1人。如果只有1人 相交的话则A, B无法同桌; 而如果M1, M2的相交集合大于2人的话, 那么M1, M2的并集总人数将少于7人, 第四天A,B包括交集中的两人可以在一块聚餐, 但 是第五天若A选取3人的话(此时至少有一人在交集), B将会因为剩余人数少于3人而无法聚餐。 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator