m×n圖改造成一座森林的探討
本研究試圖找出一些策略,以了解在mxn的格狀街道中,最少應該放入幾個吸螞蟻的裝置,便保證能抓到所有螞蟻。這問題等價於在圖G(m,n)中,最少應放入幾個紅點後,便能使G中的所有環都能碰到至少一個紅點。更等價於在圖G(m,n)中,最少應扣除幾個點後,便可形成一森林。 我們將這些點數記作k(m,n)。特別地,當m=n時記作k(n) 。本文推得:k(m,n)≧[mn+1/3],並將等號成立時的k(m,n) 稱為完美的。經過構造後發現k(2n)、k(3,n)、 k(3n,m)、k(2+6m,2+6n),k(4+6m,4+6n) , 亦為完美的,並且將k(m,n)壓到只剩兩種可能。也得知了在無限擴張的格子圖中被移除點的密度為1/3。
多邊形的剖分圖形數量之探討
從參考資料[1]可知,將凸n+2邊形利用n-1條不相交的對角線剖分成n個三角形的圖形數量即為卡特蘭數Cn。而我利用不相交的對角線把n+2邊形剖分成數個多邊形和三角形的組合,並從此類的剖分圖形與三角剖分圖形之關聯,進而由卡特蘭數的一般式推導出此類剖分圖形數量的一般式。在本研究中可得,若到把n+2邊形剖分成一個k+2邊形和多個三角形的圖形數量是(2n-k+1 n+1) ;把n+2邊形剖分成一個k+2邊形、一個m+2邊形和多個三角形的圖形數量,當m≠k,數量為n+2/2(2n-k-m+2 n+2) ,當m=k時,數量為n+2/2(2n-2k+2 n+2) ;把n+2邊形剖分成一個k1+2邊形、一個k2+2邊形、一個k3+2邊形、和n-k1-k2-k3 個三角形的剖分圖形,當k1,k2,k3兩兩相異時,數量為(n+2)(n+3)(2n-k1-k2-k3+3 n+3) ;把n+2邊形剖分成一個K1+2邊形、一個K2+2邊形、一個K3+2邊形、一個K4+2邊形和n-K1-k2-k3-k4個三角形的剖分圖形當k1,k2,k3,k4兩兩相異,數量為(n+2)(n+3)(n+4)(2n-k1-k2-k3-k4+4 n=4)。並猜測若k1,k2,...,ki兩兩相異時,把n+2邊形剖分成一個k1+2邊形、一個k2+2邊形、…、一個ki+2邊形、和n-Σkj 個三角形的剖分圖形數量為(n+i)!/(n+1)!(2n-Σkj+i n+i) 。
3進位Kaprekar變換之結構
b進位的n位數字x,數字x各位數字由大到小排列為p,由小到大排列為q,定義Kaprekar變換T(b,n)(x)=p-q,例如T(10,3)(x)= 954-459。當T(b,n)(x)= x,稱x為Kaprekar常數。 Tk(b,n)( x)=T(b,n)( Tk-1(b,n)( x))= x, k >1時,稱x為k階Kaprekar循環數。本文解答了以下問題: 1. b進位的數字不包含數字b-1的Kaprekar常數的形式。 2. 3,4,5,6進位的Kaprekar常數的一般形式。 3. 對於2,3進位的情形,我們引入三元非負整數的形式來討論Kaprekar變換,轉換成Kaprekar數對(p,q),再進一步,由來探討比值p/q,將Kaprekar變換轉成Kaprekar函數g(x),解決 Kaprekar 循環數的所有形式及解。 最後我們得到Tl(b,n)( x)必是Kaprekar循環數。