[問題] 骨子裡是數學的智力測驗

[jurian0101 (Hysterisis)]

http://www.mbti123.com/

結論是前面題目都像預期之中的一樣無聊，可以直接按跳過沒有什麼損失，

但最後一題是

"有16名學生參加一次數學競賽。考題全是選擇題，每題有四個選項。
考完後發現任何兩名學生的答案至多有一道題相同。
問：這次競賽最多有多少道選擇題？"

A.4題  B.5題  C.6題  D.7題


出乎意料的難算。

或是說，原本以為這類智力測驗的鑑別題會是那類邏輯奇怪/沒邏輯的爛題，卻出現了
一題似乎可以推理的數學。

但最後仍束手無策，我用暴力構造出4題16人以及5題16人的，符合條件的答案組存在。

而6題只能造出9人的解，但我只抽樣一萬次 (4題組則抽樣了十萬次)，跟整個天文數字
尺度的解空間相比，實在不能說是證明了4/5/6題最多能容納的人數分別是16/16/9，有
(小小的)可能其實更高。

- - -

令我想起好久之前Puzzle Up的難題 Pool of Problems

"用含有X題的題庫構造20份考卷，須滿足以下條件:

1.每份考卷題數一樣
2.任一題不能出現在多於10份考卷中
3.任意五份試卷至少要有2題共同題目

試問X最少必須是多少？
"
http://www.puzzleup.com/2013/puzzle/?246

- - -

實在對這種Combinatorics苦手，這兩題，版大若有任何線索、關鍵字或思路請不吝指點。

不過Puzzle Up還沒結束，依規定不能劇透，啊啊啊。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.213.88
推 werul:答案我猜5人?
→ werul:5題
→ FAlin:數學版 18734 18735 18738
→ FAlin:http://www.ptt.cc/bbs/Math/M.1385094161.A.CAC.html
→ FAlin:http://www.ptt.cc/bbs/Math/M.1385113274.A.F17.html
→ FAlin:以上兩個是18735跟18738網頁版、含解答
→ jurian0101:原來關鍵字是Steiner design，編列女學生問題，我錯想
→ jurian0101:成高維度的城堡問題。
→ jurian0101:18735的構造錯誤，但構造好像本來就沒有很直觀
推 bill750121:我個想法 假設總共有 n 題 那 n 題中答對1題的機率為P
→ bill750121: 那當n等於多少時 期望值接近 2/16 = 1/8
推 bill750121:說錯 期望值接近 C16取2
推 jenny2921:我可以補充四樓那個連結的想法: 一定是每個選項4人
→ jenny2921:想法: 一個選項最多可以幾個人選呢?
→ jenny2921:      如果是5個人 那下一題這5個人都要選不同的選項
→ jenny2921:      而那是不可能的
→ jenny2921:      那如果一個選項最多只能4個人選 那即使A,B,C選項
→ jenny2921:      都讓最多人選 D選項還是剩下4人
→ jenny2921:也就是 每個選項 最多=最少=一定都有四個人選它
→ jenny2921:得出以上的結論以後 可以用每組四人的排列組合去硬爆
→ jenny2921:或用四樓連結的想法去推論
→ jenny2921:(更正: 如果是5個人 那'其他題'這5個人都要選不同的選項
→ theknight:列出來就很清楚了 先鎖前面兩個 AA-DD 供16組
→ theknight:個人覺得概念像數獨