對於正整數m和n,用$A(m,n)$表示滿足下列條件的最大正整數k:存在k個非負整數數列${S_1}$,${S_2}$,...,${S_k}$,其中${S_i} = \left\langle {{a_{i1}},{a_{i2}}, \cdots ,{a_{im}}} \right\rangle $,同時滿足下面兩個條件:
(甲)對$1 \le i \le k$,${a_{i1}} + {a_{i2}} + \cdots + {a_{im}} = n$恆成立。
(乙)如果$1 \le i < j \le k$,則${a_{i1}} \ne {a_{j1}}$,${a_{i2}} \ne {a_{j2}}$,...,${a_{im}} \ne {a_{jm}}$。
例如,$A(1,3) = 1$,因為數列$\left\langle 3 \right\rangle $滿足(甲)和(乙)兩個條件,而且不會有2個數列滿足(甲)和(乙)。又如,$A(2,3) = 4$,因為$\left\langle {0,3} \right\rangle $,$\left\langle {1,2} \right\rangle $,$\left\langle {2,1} \right\rangle $,$\left\langle {3,0} \right\rangle $這4個數列滿足(甲)和(乙)兩個條件,而且不會有5個數列滿足(甲)和(乙)。
(1)求$A(3,3)$之值,並說明理由。
(2)求$A(3,4)$之值,並說明理由。
(3)求$A(3,n)$之值,並說明理由。
(4) 求$A(4,4)$之值,並說明理由。
(5) 求$A(4,n)$之值,並說明理由。
(6) 求$A(m,n)$之值,並說明理由。
如果將上述的條件(甲)改為「對$1 \le i \le k$,${a_{i1}} + 2{a_{i2}} + 3{a_{i3}} + \cdots + m{a_{im}} = n$恆成立」,但條件(乙)不變。這樣所得的最大正整數k記為$B(m,n)$。顯然$B(1,3) = 1$。
(7)求$B(2,n)$之值,並說明理由。
(8)求$B(3,n)$之值,並說明理由。
(9)求$B(4,5)$之值,並說明理由。
(10)求$B(4,n)$之值,並說明理由。
(11)求$B(m,n)$之值,並說明理由。

Log in to comment

sgod 的個人頭像
sgod replied the topic: #578 6 年 9 個月 ago

以下解法為ptt網友 tml 的解法
大家請參考看看
<一>
A(1,n) = 1
A(m,n) =$[{{2n} \over m}] + 1$ 中括號是高斯符號),$m > 1$
簡單來說就是用鴿籠先找出上界,再建構達成上界的方式。 
${S_1}$${a_{11}}$${a_{12}}$${a_{1m}}$n
${S_2}$${a_{21}}$${a_{22}}$${a_{2m}}$n
$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $$ \vdots $
${S_k}$${a_{k1}}$${a_{k2}}$${a_{1m}}$n


和 ${S_1}$ ${S_2}$ …${S_m}$ nk
因為直排的每個數字各不想同,所以最小的情況就是0到k-1的重排,所以
${s_1} \ge 0 + 1 + 2 + \cdots + (k - 1) = {1 \over 2}k(k - 1)$
$nk = {s_1} + {s_2} + \cdots + {s_m} \ge m\left( {{1 \over 2}k(k - 1)} \right)$
上式可推得$k \le {{2n} \over m} + 1$,所以理論上的上界就是$[{{2n} \over m}] + 1$。
再來是構造的問題,先來看m = 2的情況(m = 1只有一組應該沒什麼好討論的)
A(2,n)的建構方式就是第一直排填0, 1, ..., n,第二直排反過來,
每個橫排的和都是n,共n+1排,和理論上限相符。
再來看m = 3的情況,這個時候情況比較複雜,比起考慮給定n時去推出k的上限,
給定k時來推出n的下限其實更簡單,而且兩者的對應關係可以很容易的逆推回去。
上面的關係式移項一下並代入m = 3得到$n \ge {{3(k - 1)} \over 2}$,所以我們可以對k做奇偶分組
k = 2r + 1為奇數時,$n \ge 3r$ 是下界,建構方式如下:


0r+12r-1
1r+22r-3
$ \vdots $$ \vdots $$ \vdots $
r-12r1
r02r
r+112r-2
$ \vdots $$ \vdots $$ \vdots $
2r-1r-12
2rr0


可以發現每一個橫排的和均為3r,符合要求的值,而且直排都是0到2r的重排。
k = 2r為偶數時,$n \ge 3r - {3 \over 2}$,整數的下界即為3r - 1
這個的構造方法就是拿上面的來改,把最下面一列去掉然後把最右邊的每個數都減1。
最後稍微考慮一下n除以3餘1的情況,即n = 3r + 1,我們發現後面的+1沒有辦法
讓k也跟著+1,所以k仍然只有2r + 1,所以在上面的建構裡隨便找一直排每個數+1即可。
建構完m = 2和m = 3後,再來就是推廣到一般情況了。
其實推廣很單純,就是視奇偶性把m拆成m=2+2+...+2或把最後一個2改成3。
因為題目只要求直排的每個數字不同,所以直排切開就可以各自獨立討論了。
以下為m = 4的分組法(用兩個m = 2構造的情況)



0k-10k-1
1k-21k-2
$ \vdots $$ \vdots $$ \vdots $$ \vdots $
k-21k-21
k-10k-10



當n為偶數時,$2(k - 1) = n$,$k = {n \over 2} + 1 = \left[ {{n \over 2}} \right] + 1$
當n為奇數時,把上面的某一直排整排+1,則有$2k - 1 = n$,$k = {{n - 1} \over 2} + 1 = \left[ {{n \over 2}} \right] + 1$
這樣可以類推到所有的m,不是最小情況的n就隨便找直排補數字即可。
故A(m,n) =$[{{2n} \over m}] + 1$對所有m > 1成立,得證。



<二>
B(1,n) = 1
B(2,n) = $\left[ {{n \over 2}} \right] + 1$
B(m,n) =$\left[ {{{4n} \over {m(m + 1)}}} \right] + 1$,m > 2
B的情況和A類似,一樣是拆開分組,只是分組的方式略有差異。
同A的討論方式,可以得到
$nk = {s_1} + {s_2} + \cdots + {s_m} \ge (1 + 2 + \cdots + m)\left( {{1 \over 2}k(k - 1)} \right)$
$ = {{m(m + 1)k(k - 1)} \over 4}$
所以 $k \le \left[ {{{4n} \over {m(m + 1)}}} \right] + 1$
分組建構的方法則是先依奇偶性對m分組
m > 2為奇數時可將m分成$(1,m),(2,m - 1),...,({{m - 1} \over 2},{{m + 1} \over 2}),(m)$這${{m + 1} \over 2}$ 組
m > 2為偶數時可將m分成$(1,m),(2,m - 1),...,({m \over 2},{m \over 2} + 1)$這${m \over 2}$組
上面的每個分組的和都相同,所以這些組再依A(m,n)的方式去建構即可,
也就是說,把這${{m + 1} \over 2}$或${m \over 2}$組拆成2+2+...+2或2+2+...+3然後用一樣的方式去填數字。
例如m = 3時先拆成(1,2)一組,(3)一組,這兩組再依第一小題m = 2的方式構造



組別112←參考指標,同一組的都填一樣的數字,建構方式同A(m,n)
係數123加權和
00k-13(k-1)
11k-23(k-1)
$ \vdots $$ \vdots $$ \vdots $$ \vdots $
k-2k-213(k-1)
k-1k-103(k-1)



題目的例題B(4,5)其實只有兩組,建構如下
組別1221
係數1234加權和
01105
10015

這裡注意到m = 2時候只有一組比較特殊,要分開討論。
這裡不能用求和來鴿籠,簡單的反例即B(2,3),鴿籠的結果是$3 = {{((0 + 1 + 2) + (0 + 2 + 4))} \over 3}$
但是很明顯的2 ×2 = 4這個數字自己就比3還大了,不可能有能填的位置。
所以這時的限制條件反而是第二直排最大的數字能填多少,所以就單純從0填到$[{n \over 2}]$ ,
共有$[{n \over 2}] + 1$組。
B(2,n)建構方式如下,因為第二排已經不可能再填下一個數字了,很明顯是最大組數。
係數12
n0
n-21
$ \vdots $$ \vdots $
$(n - 2)[{n \over 2}]$$[{n \over 2}]$

這樣我們就完成所有B(m,n)的討論了。(m = 1明顯只能填1組,和A的情形相同)
sgod 的個人頭像
sgod replied the topic: #546 6 年 10 個月 ago
歡迎大家研究討論

Share this post

Submit to FacebookSubmit to Google PlusSubmit to Twitter