作者jurian0101 (Hysterisis)
看板puzzle
標題[問題] 骨子裡是數學的智力測驗
時間Mon Dec 9 03:13:06 2013
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
1F：推 werul:答案我猜5人? 12/09 03:50
2F：→ werul:5題 12/09 03:50
3F：→ FAlin:數學版 18734 18735 18738 12/09 07:58
6F：→ FAlin:以上兩個是18735跟18738網頁版、含解答 12/09 07:59
7F：→ jurian0101:原來關鍵字是Steiner design，編列女學生問題，我錯想 12/09 12:32
8F：→ jurian0101:成高維度的城堡問題。 12/09 12:33
9F：→ jurian0101:18735的構造錯誤，但構造好像本來就沒有很直觀 12/09 12:36
10F：推 bill750121:我個想法 假設總共有 n 題 那 n 題中答對1題的機率為P 12/11 16:23
11F：→ bill750121: 那當n等於多少時 期望值接近 2/16 = 1/8 12/11 16:23
12F：推 bill750121:說錯 期望值接近 C16取2 12/11 16:26
13F：推 jenny2921:我可以補充四樓那個連結的想法: 一定是每個選項4人 12/12 22:51
14F：→ jenny2921:想法: 一個選項最多可以幾個人選呢? 12/12 22:53
15F：→ jenny2921: 如果是5個人 那下一題這5個人都要選不同的選項 12/12 22:54
16F：→ jenny2921: 而那是不可能的 12/12 22:55
17F：→ jenny2921: 那如果一個選項最多只能4個人選 那即使A,B,C選項 12/12 22:56
18F：→ jenny2921: 都讓最多人選 D選項還是剩下4人 12/12 22:56
19F：→ jenny2921:也就是 每個選項 最多=最少=一定都有四個人選它 12/12 22:56
20F：→ jenny2921:得出以上的結論以後 可以用每組四人的排列組合去硬爆 12/12 22:57
21F：→ jenny2921:或用四樓連結的想法去推論 12/12 22:57
22F：→ jenny2921:(更正: 如果是5個人 那'其他題'這5個人都要選不同的選項 12/12 23:00
23F：→ theknight:列出來就很清楚了 先鎖前面兩個 AA-DD 供16組 12/13 10:08
24F：→ theknight:個人覺得概念像數獨 12/13 10:13