素敵な問題

問題17339・・・http://task.naganoblog.jp/c56195_1.html より引用 Orz～

解答

・わたしの...

デジャヴー ^^

300本最大で引けるはずなので、直線Lが222本引けたということは、

300-222=78個の点が重なってる...

半分で、39個重なる...

これらは、Lに対して対称に位置しているので...

39本新しい直線が引ける...

それ以外の点は対称になっていないので、直交する直線上にはない...

so...

222+39=261本の直線Lに直交する直線が引けるはずね ^^

↑

嘘でしたわ ^^; Orz...

↓

・鍵コメT様からのもの Orz～

lが座標軸と平行であれば，
指定された格子点を通りlと平行な直線は20本または15本となり不適．
また，lの傾きが無理数であれば，
指定された格子点を通りlと平行な直線は300本となり不適．

よって，lは0でない有理数を傾きとする直線である．
lの傾きが-1倍になると，図形全体が直線x=21/2に関して対称に移り，
lと平行な直線の本数，lと垂直な直線の本数はともに不変だから，
lの傾きは正である場合を調べればよい．
lの傾きをa/b (a,bは互いに素な自然数)とする．

「指定された格子点を通りlと平行な直線」を数えるには，
通る格子点を直線1本について1つずつ数えればよく，
複数の指定格子点を通る場合，例えばx座標が最小のものを数えればよい．
すると，数えるべき格子点は，(m,n) (m=1,2,…,20，n=1,2,…,15)のうち，
「m>aかつn>b」ではないもの
となる．

すると，条件より，
m=1,2,…20，n=1,2,…,15かつm>a,n>bであるm,nが78個ある
ことになり，a<20，b<15かつ(20-a)(15-b)=78.
(20-a,15-b)=(13,6),(6,13)から(a,b)=(7,9),(14,2)となり，
互いに素だから(a,b)=(7,9)に限る．

lの傾きが9/7より，lと垂直な直線は傾きが-7/9.
傾き7/9の直線を数えても同数である．
「m=1,2,…20，n=1,2,…,15かつm>9,n>7であるm,n」の分を300から引いて，
求める数は，300-11*8=212(本)．

小さい例で考えましょう．
格子点が(m,n) m=1,2,3，n=1,2,3,4として，
傾きが1/2の直線の場合を考えると，
格子点としてm>2,n>1であるものがカウントしないことになります．
(3-2)(4-1)=3(個)が除く分です．

実際に数えると，y=(1/2)x+kとして，
(1,1)はk=1/2
(1,2)はk=3/2
(1,3)はk=5/2
(1,4)はk=7/2
(2,1)はk=0
(2,2)はk=1
(2,3)はk=2
(2,4)はk=3
(3,1)はk=-1/2
(3,2)はk=1/2
(3,3)はk=3/2
(3,4)はk=5/2
となって，(3,2),(3,3),(3,4)をカウントしないことになります．
(もちろん(1,1),(1,2),(1,3)はカウントしないとダメです．)

*なるほど☆

わたしゃ一体...^^;...ほにゃららでしたわ...^^;;