某命題單位要出10份數學考卷，每份考卷至少要有4道題目，且任
意兩份考卷之中至多只有一道題目相同。試求此命題單位至少要
準備多少道題目
國中

回應

笑哥

2008-08-06 22:47
每次回答你的問題好像對牆壁說
沒半點回應
所以我再也不想算了
反正感覺有夠怪
沒有一題你告訴我寫對了沒
也沒有一題你告訴我寫錯了沒
那有人這樣的
上了國中大家都會這樣嗎

abc831128

2008-08-06 23:28
實際上我也沒有解答 有些是網站上的或書上的
我也沒有正確答案 不過我看你的解答應蓋是對的
像這就是能力競賽中的一題
婐是有用土法煉鋼方法算出好像室13不過好像怪怪的 我正試試能不能購造出12或用反證法

笑哥

2008-08-07 13:49
設a份試卷至少要b題
則(a,b)分別是(2,7),(3,9),(4,10),(5,11),(6,12),(7,13),(8,13),(9,13),(10,13)
其中六份試卷，我們可用正方體有12個邊，形成六個面，每兩個面共用一個邊
也就是說，12題最多只能組成六份試卷
所以要組合成10份試卷符合所求，至少要13題

abc831128

2008-08-07 22:39
設 題目A1~An各出現 P1~Pn次

10>=Pi>=1

P1+P2+...+Pn=40

出現題目A1的考卷, 共有3*P1+1道不相同題目 3*P1+1<=n

同理 3*P2+1<=n
...
3*Pn+1<=n
==> 3*40+n <=n^2
nn-n-120>=0
n>=12
---
if n=12
3*Pi+1<=12
==>每個 Pi都<=3
P1+P2+...+P12<=36
但是P1+P2+...+Pn=40
so, n 不等於 12
----
if n=13
3*Pi+1<=13 ==>Pi<=4
P1+P2+...+P13<=52, 與 P1+P2+...+Pn=40 不衝突
至於n=13 見以下排法
. ( 1)1 2 3 4
( 2)1 5 6 7
( 3)1 8 9 10
( 4)1 11 12 13
( 5)2 5 8 11
( 6)2 6 9 12
( 7)2 7 10 13
( 8)3 5 9 13
( 9)3 6 10 11
(10)3 7 8 12
n<13是不可能的
答案就是13

abc831128

2008-08-07 22:50
那這是第2種解法
假設總共出了n個題目，且令第i個題目出現在x(i)份考卷上

其中 1≦x(i)≦10，for i=1~n

則x(1)+x(2)+...+x(n)=40...........(1)

將10份考卷視為10個點，有相同題目的2份考卷
(點)，用一個邊連接

因為2份考卷最多有1個題目相同，所以任2點最多只有1個邊相連

10個點最多決定C(10,2)=45個邊

另一方面，因為第 i 題出現在x(i)份考卷上

所以這x(i)個點中任2點間都有一個邊相連，共有C(x(i),2)=x(i)*[x(i)-1]/2個邊

因此可得x(1)*[x(1)-1]/2+x(2)*[x(2)-1]/2+...+x(n)*[x(n)-1]/2 ≦ 45

即x(1)^2+x(2)^2+...+x(n)^2 ≦ 130............(2)



由(1),(2)配合柯西不等式

n*[x(1)^2+x(2)^2+...+x(n)^2] ≧ [x(1)+x(2)+...+x(n)]^2

n ≧ 40^2/[x(1)^2+x(2)^2+...+x(n)^2] ≧ 40^2/130≒12.308，n≧13

最少出13題即可
順便附上構造出來的圖
( 1)1 2 3 4
( 2)1 5 6 7
( 3)1 8 9 10
( 4)1 11 12 13
( 5)2 5 8 11
( 6)2 6 9 12
( 7)2 7 10 13
( 8)3 5 9 13
( 9)3 6 10 11
(10)3 7 8 12