2017研替面試 (m/M/HTC/新代/群暉/華碩) - 面試

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. 存在一個人(乙)對五題，其他沒人全對
: ＸＯＯＯＯ
: ↑
: 這題一定要有120以上個人答對，假設叫Ａ好了，Ａ答題如下
: Ｏ？？？？…問號是什麼也不重要了，因為甲和Ａ絕對不會錯同一題
: case 3. 存在一個人(丙)對四題，其他沒人對5題以上
: ＸＸＯＯＯ
: ↑
: 這題一定要有120以上個人答對，假設叫B1, B2, ... B120好了，
: Ｏ□？？？...B1
: Ｏ□？？？...B2
: Ｏ□？？？...B3
: Ｏ□？？？...
: Ｏ□？？？...B120
: ↑上述方格中最多只能有79個Ｘ→不然第二題就少於120個人答對了
: ＯＯ？？？...Bn與丙相比果然也沒錯同一題
: 不會證明只會窮舉...寫的醜請多見諒

--