1、Show that the transitive closure of a symmetric relation is also symmetric.
2、If no three diagonals of a convex octagon meet at the same point inside the octagon, into how many line segments are the diagonals divided by their intersections?
題目大概是說求由點跟點的交集分出的線段，不過求出邊的個數(C八取2)後，就不知該怎麼求了..
3、Let Dn be the set of all divisors of a positive integer n.
When is the poset ( Dn, | ) a complemented lattice?
互補落的性質不是avb=I, a^b=O，要怎麼應用到 | ？
以上，請多指教。
7 則留言:
第一題剛剛才寫到
R:symmetric → t(R):symmetric
for all a,b ∈ A
→若(a,b) ∈ t(R)
→exist i∈Z+ s.t. (a,b)∈R^i
→exist c1,c2,...,cn ∈ A s.t.
(a,c1),(c1,c2),....,(cn,b)∈R
→因為R具symmetric
→(c1,a)(c2,c1),......(b,cn)∈R
→(b,a)∈ t(R)
→t(R)具symmetric
這麼剛好@@
請問一下為什麼是→exist c1,c2,...,cn ∈ A
1. Tse 是假設 R 是定義在 A 上的 relation, 那麼因為 t(R) 是 transitive closure, 根據遞移包的定義 t(R) 中的每個關係就可以拆成 R 中 relation 遞移的過程
2. 可先討論intersection的個數, 假設那個八邊形的點依序是 a,b,...,h, 將diagonal的case分類如下:
(1) 第一種 diagonal 是像 a-c 這種, 那麼由 b 連到其他剩下的五個點的diagonal可產生 5 個和 a-c 交集的 intersection, 而由於像是 a-c 這種的 diagonal 共有 8 種 => 8*5=40
(2) 第二種 diagonal 是像 a-d 這種跨兩個點的, 和case1的討論方式差不多, 這裡可得到 8*8=64 個交點
(3)還有一種 diagonal 是像 a-e 這種, 這裡可得到 4*9=36 個交點
在上述的3個case裡, 每個交點都會被重複討論一次, 所以加總要再除以2, 所以intersection的總數為 (40+64+36)/2=70
因為3個diagonal必不共點, 最後可算出line segments總數為 (4*70+8(8-3))/2 = 160 (這裡我是把每個交點所連出去的line總共就 4 條, 加上連結交點與八個角之間的片段總數, 來確保每個line segment都恰好被多算了一次, 然後再除以2)
3. 在 Dn 裡, avb=I, a^b=O 的意思是
(1) 若 x|a, x|b => x=1 => gcd(a,b)=1
(2) 若 a|y, b|y => y=n => lcm(a,b)=n
由(1)(2)可推論出 n=p1p2...pk, 其中 p1,...,pk 全相異
這其實就是 Dn 為 Boolean Algebra 的充要條件,
也就是課本p10-50,51中定理12,13的結果
1.我了解了~
2.不是很懂你舉的case1~3..Orz
畫不太出來XD
3.所以其實只要證明不存在p:prime滿足p^2|n就是題意要求的嘛..感謝你
第2題我有疑問。其實這一題再前清大校長寫的那一本書裡有例題，題目幾乎一樣，唯一不同是C.L.Liu那一本裡面是10邊形。算法是這樣，題目說由對角線的交點分出了多少線段？所以8邊形的邊都不計算在內，我們要考慮的只是對角線，共C(8,2)-8=20條。我們又知道，這個凸八邊形任意四個點，一定可以畫出一個交點，又因為任三線不共點，所以交點共有C(8,4)=70個，而每一個交點都可以再多切出兩個線段來，所以線段數是20+2*70=160個。
mango: case1 就是討論兩點間間隔 1 點的那一種 diagonal, case 2 就是間隔2點的 diagonal, case 3就是間隔 3 點的; 如果還是不太清楚你也可以參考前面一位同學寫的那個版本
chen: 嗯嗯, in general 的 n 解法就像你說的, 我上面只是單純解octagon, 若是同樣的問題推廣到n-gon, 則intersection數即為c(n,4), 線段總數就是 c(n,2)-n+2*c(n,4)
感謝兩位分享，我了解了。
終於知道wynne的idea了..XD
張貼留言