PuzzleUp 2009 (17) Seventeen Interse … - 拼圖

※ 引述《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'.

--