這一題出自某本謎題書,號稱用排列組合就能解出,
之前出在數學板,不過沒人給出證明
因此繼續來本板懸賞QQ
最先給出完整證明者,小妹給3000批幣
(提高懸賞,覺得不夠可再提)
問題:
萬能中學要辦全能運動會,共有五項運動分別為籃球、棒球、網球、足球、羽球
由於場地限制,每個運動在同一時段只能排兩隊彼此對抗
全校總共有八個隊伍參加。(設編號分別為1~8)
希望排出一個賽程表,滿足:
1.每個隊伍都希望能玩過每個運動項目,但最多玩一次
2.任兩個隊伍只要對戰過,就希望不要再對上
3.在每個時段,所有隊伍都必需比賽
(此條件等價於:最多排m個時段,m等於運動項目數)
試證明這樣的賽程表是排不出來的
--------------------------------------------
範例:
以這樣的賽程表來說:(國字數字表示賽程,阿拉伯數字表示哪兩隊比賽)
籃球、棒球、網球、足球、羽球
一 1:2 3:4 5:6 7:8
二 3:5 1:6 2:7 4:8
三 4:6 2:8 3:5 1:7
四 7:8 1:3 2:6 3:5
五 5:7 4:8 1:4 2:6
如此一來,每個隊伍確實都玩過每項運動「一次」,但注意四號對八號對戰過
兩次,這樣就違反第二個規則了!
事實上能合乎兩項規則的賽程表排不出的,但怎麼證明呢?
--------------------------------------------
進階討論
n個隊伍在m個比賽項目的情況?
--
之前出在數學板,不過沒人給出證明
因此繼續來本板懸賞QQ
最先給出完整證明者,小妹給3000批幣
(提高懸賞,覺得不夠可再提)
問題:
萬能中學要辦全能運動會,共有五項運動分別為籃球、棒球、網球、足球、羽球
由於場地限制,每個運動在同一時段只能排兩隊彼此對抗
全校總共有八個隊伍參加。(設編號分別為1~8)
希望排出一個賽程表,滿足:
1.每個隊伍都希望能玩過每個運動項目,但最多玩一次
2.任兩個隊伍只要對戰過,就希望不要再對上
3.在每個時段,所有隊伍都必需比賽
(此條件等價於:最多排m個時段,m等於運動項目數)
試證明這樣的賽程表是排不出來的
--------------------------------------------
範例:
以這樣的賽程表來說:(國字數字表示賽程,阿拉伯數字表示哪兩隊比賽)
籃球、棒球、網球、足球、羽球
一 1:2 3:4 5:6 7:8
二 3:5 1:6 2:7 4:8
三 4:6 2:8 3:5 1:7
四 7:8 1:3 2:6 3:5
五 5:7 4:8 1:4 2:6
如此一來,每個隊伍確實都玩過每項運動「一次」,但注意四號對八號對戰過
兩次,這樣就違反第二個規則了!
事實上能合乎兩項規則的賽程表排不出的,但怎麼證明呢?
--------------------------------------------
進階討論
n個隊伍在m個比賽項目的情況?
--
All Comments