三角形邊長限制下的組合

howt · January 8, 2010

給定一正整數n，

令滿足三角形邊長總和為n，

且三邊長為整數的所有三角形數目組合有f(n)個，求f(n)。

如 f(7)=2 ，(3,2,2)、(3,3,1)

此內容已被編輯, January 10, 2010 ,由 howt
少給條件

曾阿牛 · January 9, 2010

光是看到題目如此給　　最適當的回答就是 f(n) ＝ ∞

題目沒有交代全等的三角形是否看做同一個

也沒交代三角形的邊長是否限制為整數

此內容已被編輯, January 9, 2010 ,由曾阿牛

曾阿牛 · January 20, 2010

嗯....　怎麼這帖這麼少人問津哩？

昨天卯起來解這題　算是有一個結果了　:^)

$gif.latex?%20\displaystyle%20\mbox{Give an}~n\in\mathbb{N}.~~\mbox{Let}~p=\Big\lfloor\frac{n}{2}\Big\rfloor+1,~m=\Bigg\lfloor\frac{3\Big(\big\lceil\frac{n}{2}\rceil-1\Big)-n}{2} \Bigg\rfloor+1\mbox{, and}\\ t=\Bigg\lceil\frac{\big\lceil\frac{2m}{3}\big\rceil}{2}\Bigg\rceil.~~\mbox{Then we have that}$

$gif.latex?%20\displaystyle%20f(n)=\left\{ \begin{array}{rl} 3t^2+t & \mbox{if}~~p\equiv 0~\mbox{mod 2\quad and}~~m\equiv 0~\mbox{mod 3}\\ 3t^2-3t+1 & \mbox{if}~~p\equiv 0~\mbox{mod 2\quad and}~~m\equiv 1~\mbox{mod 3}\\ 3t^2-t & \mbox{if}~~p\equiv 0~\mbox{mod 2\quad and}~~m\equiv 2~\mbox{mod 3}\\ 3t^2+2t & \mbox{if}~~p\equiv 1~\mbox{mod 2\quad and}~~m\equiv 0~\mbox{mod 3}\\ 3t^2-2t & \mbox{if}~~p\equiv 1~\mbox{mod 2\quad and}~~m\equiv 1~\mbox{mod 3}\\ 3t^2 & \mbox{if}~~p\equiv 1~\mbox{mod 2\quad and}~~m\equiv 2~\mbox{mod 3}\\ \end{array} \right..$

我正煩惱說自己的做法方向是正確的　應該不會錯才對　

還好　讓我發現原來是 m 一開始就設計錯了　現已修正　　

否則實在是想不出來自己的做法到底哪裡錯了　　:E

此內容已被編輯, January 20, 2010 ,由曾阿牛

howt · January 21, 2010

這答案好像有問題，如n=7、8都不對

不過能否勞煩你大致說一下想法

我算出來的f(n)：

當n是偶數 f(n) 為與 (n^2)/48 最接近的整數

當n是奇數 f(n) 為與 [(n+3)^2]/48 最接近的整數

曾阿牛 · January 21, 2010

酷　　有人回才有意思

既然大大有所質疑　那麼就來檢查檢查吧

$gif.latex?%20\displaystyle%20\mbox{When}~n=7,~~p=\Big\lfloor\frac{7}{2}\Big\rfloor+1=4,\\~m=\Bigg\lfloor\frac{3\Big(\big\lceil\frac{7}{2}\rceil-1\Big)-7}{2}%20\Bigg\rfloor+1=\Bigg\lfloor\frac{3\Big(4-1\Big)-7}{2}%20\Bigg\rfloor+1=2\mbox{,%20and}\\\%20t=\Bigg\lceil\frac{\big\lceil\frac{2\cdot%202}{3}\big\rceil}{2}\Bigg\rceil=1.\\%20\mbox{Since}~p\equiv%200~\mbox{mod%202\quad%20and}~~m\equiv%202~\mbox{mod%203},~f(7)=3t^2-t=3\cdot(1)^2-1=2.$

還有

$gif.latex?%20\displaystyle%20\mbox{When}~n=8,~~p=\Big\lfloor\frac{8}{2}\Big\rfloor+1=5,\\~m=\Bigg\lfloor\frac{3\Big(\big\lceil\frac{8}{2}\rceil-1\Big)-8}{2}%20\Bigg\rfloor+1=\Bigg\lfloor\frac{3\Big(4-1\Big)-8}{2}%20\Bigg\rfloor+1=1\mbox{,%20and}\\\%20t=\Bigg\lceil\frac{\big\lceil\frac{2\cdot%201}{3}\big\rceil}{2}\Bigg\rceil=1.\\%20\mbox{Since}~p\equiv%201~\mbox{mod%202\quad%20and}~~m\equiv%201~\mbox{mod%203},~f(8)=3t^2-2t=3\cdot(1)^2-2\cdot%201=1.$

嗯... 所以沒錯吧　　整個過程最容易出錯的地方在算 m　其次是算 t　

另外　等到大大對這公式再沒懷疑的時候　我再說做法

呃...　話說回來　光看到公式本身就這麼複雜　公式的推導過程恐怕不是兩三下就可以描述的

不過呢　大致上可以分成四個部分　就是

1. p 怎麼來的　　2. m 怎麼來的　　3. t 怎麼來的　　4. f 怎麼來的

______________________________________________________________________

從 howt 大大的公式來看　大大是將 n 分成奇數和偶數來各別處理　

這麼一來　問題變得乾淨多了　真是個好辦法　　　

當切入問題的角度不同　很可能就得到外觀看似不同的結果　

好比探險一樣　　酷

此內容已被編輯, January 21, 2010 ,由曾阿牛

howt · January 21, 2010

我以為[]全都是高斯符號，似乎缺上角的是高斯符號，缺下角的是取數值的整數上界?

我的作法有兩種，一種是考慮f(n)與f(n-3)的關係；

另一種是將滿足 (n/3)<= z <(n/2) 的整數z

對[(3z-n)/2]+1 作 sigma。

曾阿牛 · January 22, 2010

Re #6 howt 大大　　是的　缺上角的是高斯符號，缺下角的是取數值的整數(最小)上界

換言之　缺上角是地板函數(floor function)　缺下角的是天花板函數(ceiling function)

公式我是找到了(一個)　　而且個人認為這是最 precise 的公式

但是　我對這問題本質　卻沒有很多了解

若從那公式來看　可以發現共分成六類　是依除以2和除以3的餘數來分　

這暗指此問題本身的結構　含有兩個主軸

howt 大大　今天晚點我會說明做法

曾阿牛 · January 22, 2010

看樣子　我的公式即是 howt 大大在 #6 提出的第二種做法　只不過我把它嚴格地公式化罷了

先看兩個例子　當 n 是 17 和 n 是 18

當 n 是 17　　有以下 8 種情形　所以 f(17)=8

(8, 8, 1)　(8, 7, 2)　(8, 6, 3)　(8, 5, 4)

(7, 7, 3)　(7, 6, 4)　(7, 5, 5)

(6, 6, 5)　

當 n 是 18　　有以下 7 種情形　所以 f(18)=7

(8, 8, 2)　(8, 7, 3)　(8, 6, 4)　(8, 5, 5)

(7, 7, 4)　(7, 6, 5)

(6, 6, 6)　

再重新看 f(17) 和 f(18)　　f(17) 是 4+3+1　f(18) 是 4+2+1

(當然　覺得例子不夠的大大可自己再造例子)

可以發現 f(n) 必定[註]屬於以下的三種級數之一　只是或長或短而已

1+2+4+5+7+8+10+11+13+..... (沒有除以3餘0的)　稱此級數為 A 型

1+3+4+6+7+9+10+12+13+..... (沒有除以3餘2的)　稱此級數為 B 型

2+3+5+6+8+9+11+12+14+..... (沒有除以3餘1的)　稱此級數為 C 型

f(17)是 B 型　f(18)是 A 型　f(17)和f(18)的(非零)項數都是 3　最大項也都是 4

這裡　如果稍微細心點的大大就會發現　如果知道是哪一型的級數又知道項數(或知道最大項)的話

就可以得知該級數的加總結果

換言之　如果知道 f(n) 屬於哪一型的級數又知道項數(或知道最大項)的話　就可以知道 f(n)

但有另一個前提　就是要先知道 A, B, C 這三型級數的公式

要判斷f(n) 屬於哪一型的級數　我是用 p 和 m 來判斷　　t 則是級數的公式裡的重要參數

想來想去　我還是太懶　所以說明就先到此為止　　針對哪一部分需要特別解釋的話　再通知我

註：　說是"必定"　那也是有原因的　不過我懶得詳細說明　曾經鑽研過此問題的大大　應該不難歸納出原因

此內容已被編輯, January 22, 2010 ,由曾阿牛

登入

三角形邊長限制下的組合

Recommended Posts

howt 10

鏈接文章

分享到其他網站

曾阿牛 10

鏈接文章

分享到其他網站

曾阿牛 10

鏈接文章

分享到其他網站

howt 10

鏈接文章

分享到其他網站

曾阿牛 10

鏈接文章

分享到其他網站

howt 10

鏈接文章

分享到其他網站

曾阿牛 10

鏈接文章

分享到其他網站

曾阿牛 10

鏈接文章

分享到其他網站

請登入後來留意見

瀏覽

動態