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

看板Tech_Job作者play714 (play)時間8年前 (2017/07/15 02:38)推噓5(5推 0噓 0→)

留言5則, 5人參與討論串3/3 (看更多)

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與丙相比果然也沒錯同一題 : 不會證明只會窮舉...寫的醜請多見諒 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.213.97 ※ 文章網址: https://www.ptt.cc/bbs/Tech_Job/M.1500057491.A.7CF.html

推

Rayyh

07/15 11:30, , 1^F

07/15 11:30, 1^F

推

zzzz8931

07/16 01:39, , 2^F

07/16 01:39, 2^F

推

Chaobig

07/16 22:47, , 3^F

07/16 22:47, 3^F