Re: [心得] 2017研替面試 (m/M/HTC/新代/群暉/華碩)

[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與丙相比果然也沒錯同一題

不會證明只會窮舉...寫的醜請多見諒

--
夫兵者不祥之器物或惡之故有道者不處君子居則貴左用兵則貴右兵者不祥之器非君子
之器不得已而用之恬淡為上勝而不美而美之者是樂殺人夫樂殺人者則不可得志於天下
矣吉事尚左凶事尚右偏將軍居左上將軍居右言以喪禮處之殺人wretch.twbbs.org勝以
喪禮處之道常無名樸雖小天下莫能臣侯王若能守之萬物將自賓天地相合以降甘露民莫
之令而自均始制有名名亦既有夫亦將知止知止可以不殆qllvv.Dorm12.NCTU.edu.tw海

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.128.228.181
※ 文章網址: https://www.ptt.cc/bbs/Tech_Job/M.1476284862.A.960.html
※ 編輯: qllvv (220.128.228.181), 10/12/2016 23:08:45
※ 編輯: qllvv (220.128.228.181), 10/12/2016 23:09:04
→ qllvv: 修個錯字
推 Hikkiaholic: 主管:ZZZZZ(根本沒在聽)
推 shan1470: 感謝證明 概念上大概理解了 只是你的O好像都少打一個w
→ shan1470: Case2的應該是乙跟A
推 Eleina: 簽名檔見證人不要臉天下無敵
推 kiedveian: 提供另個解法，兩兩配對共有200*199/2=19900種
→ kiedveian: 每測一題最多減少80*79/2種
→ kiedveian: 六題測完19900-3160*6=940種
→ kiedveian: 至少可以找到940種配對法
→ kiedveian: 但這方法會多扣，如每題答對人數從120改為101
→ kiedveian: 此方法就無法證明了
→ cha122977: 蠻清楚的，推
推 aa06697: 好厲害 想了20分鐘想不到怎麼解 還想說用排容試qq