※ 引述《bugmens (那些年,我們一起)》之銘言：
: JohnMash 版友您好
: 在 Math 版常看到...
: 於是便想向您討教一下
: http://tinyurl.com/3ljagll
: 這是建中通訊解題八十三期的題目
: 裡頭的 8302
: 若是將裡頭的 4x4 推廣到 nxn
: 是否可推導出通解呢?
: 我的想法是分成兩類 偶數x偶數 跟 奇數x奇數 去討論
: 本來想說除了一個一個算之外 能不能用遞迴去推論
: 但是發現 4x4 => 6x6 和 6x6 => 8x8 的三角形形狀
: 三角形可旋轉的形狀變多 還是得要一個一個處理
: 您有什麼看法嗎??
: 不好意思 冒昧向您討教
: 謝謝您的回覆 :)
: 我好不容易在google找到線索,只是原來的文章卻被刪除了
: 沒發表的話有點可惜,但看來是沒有公式
: Number of right triangles whose vertices are lattice points
: in {1,2,...,n} X {1,2,...,n}.
: http://oeis.org/A077435
我的想法是
n>1
從nxn點陣中取一點(a,b)
令f(n,a,b) = 符合以下兩點的直角三角形個數
(1) 以此 nxn 點陣中的點為頂點 的直角三角形
(2) (a,b)為90度角的頂點 的直角三角形
令F(n) = Σ f(n,a,b)
1≦a,b≦n
則F(n)即為所求
以下我只考慮
1 ≦ b ≦ a ≦ (n+1)/2 的情形
之後再利用對稱性得到所有的f(n,a,b)
考慮過(a,b)點的兩條互相垂直的線L1、L2
令 Am = 此nxn點陣落於L1上的點的個數 - 1
Bm = 此nxn點陣落於L2上的點的個數 - 1
當L1、L2為水平、鉛垂線時，Am = Bm = n-1
0<m<∞
L1: (y-b)/(x-a) = m
L2: (y-b)/(x-a) = -1/m
則 f(n,a,b) = (n-1)^2 + Σ (Am * Bm)
0<m<∞
n-b
=(n-1)^2 + Σ ( Σ (
j=1 1≦i≦n-a
gcd(i,j)=1
(min(floor((n-a)/i),floor((n-b)/j))+min(floor((a-1)/i),floor((b-1)/j)))
*(min(floor((n-b)/i),floor((a-1)/j))+min(floor((b-1)/i),floor((n-a)/j)))
))
則
當n為偶數時：
n/2 (n-1)/2 n/2
F(n) = 4 * Σ f(n,a,a) + 8 * Σ Σ f(n,a,b)
a=1 b=1 a=b+1
當n為奇數時：
(n-1)/2 (n-1)/2
F(n) = 4 * ( Σ f(n,a,a) + Σ f(n,(n+1)/2,b) )
a=1 b=1
(n-3)/2 (n-1)/2
+ 8 * Σ Σ f(n,a,b)
b=1 a=b+1
+ f( n, (n+1)/2, (n+1)/2 )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.83.174
※ 編輯: kanoki 來自: 61.228.83.174 (11/23 15:56)
心血來潮寫一下程式，附上code來驗證
http://pastebin.com/rHpMXKcv
※ 編輯: kanoki 來自: 111.240.135.23 (05/19 21:49)