Re: [其他] TC題 (2) 排列組合/空間座標 (Sol)
※ 引述《TimcApple (肥鵝)》之銘言：
: Problem 2
: 設 x, y, z 為 {-2, -1, 0, 1, 2} 中的任一數
: 因此 S = {(x, y, z)} 共有 125 個座標點
: 試問有多少正三角形的三頂點皆在 S 內？
設三角形三頂點為 A, B, C
則向量 AB + BC + CA = 0, 且三向量各坐標絕對值皆不超過 4
因為同種類的向量可以一起算，用向量(距離差)來算會好算很多
================================================================
(Lem) 給定任意空間中的三角形 ABC
存在唯一一個最小長方體包含該三角形
若 A, B, C 皆為格子點，則該長方體頂點也是
(pf) 取該長方體被以下六個平面包圍
x = max{xA, xB, xC}, y = max{yA, yB, yC}, z = max{zA, zB, zC}
x = min{xA, xB, xC}, y = min{yA, yB, yC}, z = max{zA, zB, zC}
由此即可得到 Lem 的結論
================================================================
(Lem) 若 AB, BC, CA 皆為 (a, b, c) 調換順序、任意加正負號
a >= b >= c >= 0, 則 a = b + c
(pf) 考慮 x 坐標相加為 0，將帶有負號的項移到等號對面
必定會形成 x1 = x2 + x3 的形式，且 x1, x2, x3 >= 0
因此三個 x 坐標的絕對值，兩個小的相加必為最大的
現在將 aaabbbccc 分成三組
(1) 任一組有 aa
a = a + a, 則 a = b = c = 0
a = a + b, 則 b = c = 0，第三個 a 那組會給出 a = 0
a = a + c, 則 c = 0
若其他組有 cc, 則 a = b = 0
若各一個 c, 則 a = b, 此時有 a = b + c
(2) 每組都一個 a
必定有至少一組會出現 a = b + c
================================================================
有以上兩個引理之後，會比較容易完成本題的證明
Solution to Problem 2
首先先列表計算所有可能的 (x, y, z) 向量長度(平方)
z=0 z=1 z=2 z=3 z=4
x\y 4 3 2 1 0 x\y 4 3 2 1 x\y 4 3 2 x\y 4 3 x\y 4
4 32 25 20 17 16 4 33 26 21 18 4 36 29 24 4 41 34 4 48
3 18 13 10 9 3 19 14 11 3 22 17 3 27
2 8 5 4 2 9 6 2 12
1 2 1 1 3
0 0
可以注意到重複的長度有：
9 : (3, 0, 0), (2, 2, 1)
17: (4, 1, 0), (3, 2, 2)
18: (3, 3, 0), (4, 1, 1)
(Step 1) 三向量皆為相同組成
由第二個 Lemma 可知必須有 x = y + z，因此可能有以下幾種
外包矩形 每個矩形內 有幾個矩形
(1, 1, 0) 1 x1 x1 8 種 64 個
(2, 2, 0) 2 x2 x2 8 種 27 個
(3, 3, 0) 3 x3 x3 8 種 8 個
(4, 4, 0) 4 x4 x4 8 種 1 個
(2, 1, 1) 2 x2 x2 8 種 27 個
(3, 2, 1) 3 x3 x3 16 種 8 個
(4, 3, 1) 4 x4 x4 16 種 1 個
(4, 2, 2) 4 x4 x4 8 種 1 個
-----------------------------------------------
計 1168 個正三角形
(Step 2) 三向量不同組成
僅有長度平方為 9, 17, 18 的情況，有不同種類的向量
考慮 x + y + z 的奇偶性：
9 : 奇, 奇
17: 奇, 奇
18: 偶, 偶
選三組向量總和必為偶數，9 和 17 直接排除
由試誤法可得 (3, 3, 0) = (4, -1, 1) + (-1, 4, -1)
外包矩形 每個矩形內 有幾個矩形
4 x4 x1 8 種 12 個
-----------------------------------------------
計 96 個正三角形
(Last step)
共有 1168 + 96 = 1264 個正三角形
註：可參考原篇底下 LPH66 的詳解，有圖
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.48.74 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1589643691.A.A6D.html