Re: [中譯] PuzzleUp 2009 (17) Seventeen Interse …
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者killyou (xxx)時間16年前 (2009/11/14 01:50)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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
推
11/14 10:32, , 1F
11/14 10:32, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章
38
52