作者killyou (xxx)
看板puzzle
標題Re: [中譯] PuzzleUp 2009 (17) Seventeen Interse …
時間Sat Nov 14 01:50:11 2009
※ 引述《turing (涂妮)》之銘言：
: 首頁：http://www.puzzleup.com/2009/?home
: 時限：2009/11/12（四）19:00～11/17（二）18:59
: 答案可上傳５次，但每改１次扣２０分（基本分為１００分）
: 在比賽期間內可隨時回答，但只有在時限內回答者有額外加分
: ◆Seventeen Intersections
: 在紙上畫X條線。沒有任何三條線交在同一點。如果總共有17個交點，
: 那X的最小值為何？
: 如果問題是問5個交點，則答案是4。如圖所示。
推 stimim:我知道會小於等於，那等號永遠有辦法成立嗎？ 11/13 19:06
首先, 平面上
N條線最多
N(N-1)/2個交點, 這個不難証.
Induction on
N.
1.
N=1 沒點免証.
2.
N>1, 第
N線交前
N-1條線最多也就
N-1點,所以一共最多
(N-1)(N-2)/2 +
(N-1) =
N(N-1)/2 點
再來給個有
N(N-1)/2 交點的畫法,等號就成立了.
令
Li:
Y=i(X-i),
i=0,1,...,N-1 (第一條就是X軸)
則所有的交點解為 {(
i+j,
ij):
0≦i<j≦N-1}
證明這
N(N-1)/2 點都不同: (反證法)
Suppose
i+j=i'+j' &
ij=i'j' for some
i<j &
i'<j',
then
(j-i)^2 = (i+j)^2 - 4ij
= (i'+j')^2 - 4i'j' = (j'-i')^2,
j-i = j'-i' (>0),
=>
i=i' &
j=j'.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.231.114
1F：推 stimim:了解了，感謝 11/14 10:32