作者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