Re: [心得] 2017研替面试 (m/M/HTC/新代/群晖/华硕)

楼主: play714 (play)   2017-07-15 02:38:09
Proof: 可以找出两个学生,他们不会错同一题。
by 反证法,假设一: 找不出两个学生,他们不会错同一题。
=>即 任意找两个学生,他们都至少错同一题。
case 1:如果有一学生A全答对6题,那A配上任意一学生B,无论B错几题。
A和B都不会错同一题。=>矛盾
基于 case 1,得case 2
case 2:如果200个同学都至少错一题,假设A只错一题,为了我们的假设一成立(A
配上任意同学B都会错同一题),即其他199位同学都要错同一题,由题目可
知同一题最多答错的人数为200-120=80人,小于199人 => 矛盾
基于case 1和2,得case 3
case 3:如果200个同学都至少错两题,假设A答错第一、二题,同理,为了假设一成
立,即其他199个同学都要跟A错同一题,最好情况为99人错第一题,100人
错第二题,99和100 都大于80人 =>矛盾
基于case 1, 2 和3,得case 4
case 4:如果200个同学都至少错三题,此时,最小的答错总题数为200人*3题=
600题/人,但条件中说每题最多错80人,即总答错题数最多为 6题*80人=
480题/人 =>矛盾
即命题“任意找两个学生,他们都至少错同一题”与题目条件矛盾,故命题“可以
找出两个学生,他们不会错同一题”得证
※ 引述《qllvv (百事柠檬可乐儿)》之铭言:
: ※ 引述《shan1470 (ShanLin)》之铭言:
: : 1. 假设现在有200个学生,一起写6道题目,每道题目都至少有120人答对,那请证明:
: : 我们必定能够找出一个组合(两个学生)
: : 他们在这六题里面,不会有两个人都错同一题的情况发生
: : 这边其实后两题就比较经典题 第一题我最后还是没证出来...求强者解题
: claim. 至少有一个人对4题以上
: <proof> 假设大家都只对3题以下,那最多只会有600题被答对与题目
: 说每道题目都至少有120人答对→至少有720题被答对相矛盾
: 分下列case讨论
: case 1. 存在一个人(甲)全对
: 那就没什么好讲的…因为随便另一个人一定不会错同一题
: case 2. 存在一个人(乙)对五题,其他没人全对
: XOOOO
: ↑
: 这题一定要有120以上个人答对,假设叫A好了,A答题如下
: O????…问号是什么也不重要了,因为甲和A绝对不会错同一题
: case 3. 存在一个人(丙)对四题,其他没人对5题以上
: XXOOO
: ↑
: 这题一定要有120以上个人答对,假设叫B1, B2, ... B120好了,
: O□???...B1
: O□???...B2
: O□???...B3
: O□???...
: O□???...B120
: ↑上述方格中最多只能有79个X→不然第二题就少于120个人答对了
: OO???...Bn与丙相比果然也没错同一题
: 不会证明只会穷举...写的丑请多见谅
作者: Rayyh   2017-07-15 11:30:00
114厉害
作者: zzzz8931 (肥宅)   2017-07-16 01:39:00
114
作者: Chaobig (敲大)   2017-07-16 22:47:00
作者: Clansh (羽毛)   2017-07-18 23:33:00

Links booklink

Contact Us: admin [ a t ] ucptt.com