※ 引述《nonumber (空號)》之銘言：
: 2013 TRML 思考賽
: <一>
: 對於正整數m和n，A(m,n)表示滿足下列條件的最大正整數k:
: 存在k個非負整數數列S1,S2,...,Sk，其中Si=<ai1,ai2,...aim>
: 同時滿足下列兩個條件
: (甲)對1≦i≦k , ai1+ai2+...+aim = n 恆成立
: (乙)對1≦i<j≦k，ai1≠aj1,ai2≠aj2,...,aim≠ajm
: 例如A(1,3)=1，因為數列<3>滿足甲乙，且不會有第二個數列滿足甲乙
: 又如A(2,3)=4，因為<0,3>,<1,2>,<2,1>,<3,0>滿足甲乙，且沒有第五個數列滿足甲乙
: 求A(3,3)、A(3,4)、A(3,n)、A(4,4)、A(4,n)、A(m,n)，並說明理由
A(1,n) = 1
A(m,n) = [2n/m] + 1（中括號是高斯符號），m > 1
簡單來說就是用鴿籠先找出上界，再建構達成上界的方式。
和
S1 a11 a12 ... a1m n
S2 a21 a22 ... a2m n
: : : : :
Sk ak1 ak2 ... akm n
和 s1 s2 ... sm nk
因為直排的每個數字各不想同，所以最小的情況就是0到k-1的重排，所以
si ≧ 0 + 1 + ... + (k-1) = k(k-1)/2
nk = s1 + s2 + ... + sm ≧ mk(k-1)/2
上式可推得 k ≦ 2n/m + 1，所以理論上的上界就是[2n/m] + 1。
再來是構造的問題，先來看m = 2的情況（m = 1只有一組應該沒什麼好討論的）
A(2,n)的建構方式就是第一直排填0, 1, ..., n，第二直排反過來，
每個橫排的和都是n，共n+1排，和理論上限相符。
再來看m = 3的情況，這個時候情況比較複雜，比起考慮給定n時去推出k的上限，
給定k時來推出n的下限其實更簡單，而且兩者的對應關係可以很容易的逆推回去。
上面的關係式移項一下並代入m = 3得到n ≧ 3(k-1)/2，所以我們可以對k做奇偶分組
k = 2r + 1為奇數時，n ≧ 3r是下界，建構方式如下：
0 r+1 2r-1
1 r+2 2r-3
: : :
r-1 2r 1
r 0 2r
r+1 1 2r-2
: : :
2r-1 r-1 2
2r r 0
可以發現每一個橫排的和均為3r，符合要求的值，而且直排都是0到2r的重排。
k = 2r為偶數時，n ≧ 3r - 3/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構造的情況）
0 k-1 | 0 k-1
1 k-2 | 1 k-2
: : | : :
k-2 1 | k-2 1
k-1 0 | k-1 0
當n為偶數時，2(k-1) = n，k = n/2 + 1 = [n/2] + 1
當n為奇數時，把上面的某一直排整排+1，則有2k-1 = n，k = (n-1)/2 + 1 = [n/2] + 1
這樣可以類推到所有的m，不是最小情況的n就隨便找直排補數字即可。
故A(m,n) = [2n/m] + 1對所有m > 1成立，得證。
: <二>
: 將上述(甲)改為對1≦i≦k , ai1+2ai2+...+maim = n 恆成立 (係數改變
: 條件(乙)不變，這樣所得的最大正整數k記為B(m,n)。顯然B(1,3)=1。
: 求B(2,n)、B(3,n)、B(4,5)、B(4,n)、B(m,n)，並說明理由
B(1,n) = 1
B(2,n) = [n/2] + 1
B(m,n) = [4n/m(m+1)] + 1，m > 2
B的情況和A類似，一樣是拆開分組，只是分組的方式略有差異。
同A的討論方式，可以得到
nk = s1 + s2 + ... + sm ≧ (1+2+...+m)k(k-1)/2 = m(m+1)k(k-1)/4
所以 k ≦ [4n/m(m+1)] + 1
分組建構的方法則是先依奇偶性對m分組
m > 2為奇數時可將m分成(1,m-1) (2,m-2) ... ((m-1)/2,(m+1)/2) (m)這(m+1)/2組
m > 2為偶數時可將m分成(1,m) (2,m-1) ... (m/2,m/2+1)這m/2組
上面的每個分組的和都相同，所以這些組再依A(m,n)的方式去建構即可，
也就是說，把這(m+1)/2或m/2組拆成2+2+...+2或2+2+...+3然後用一樣的方式去填數字。
例如m = 3時先拆成(1,2)一組，(3)一組，這兩組再依第一小題m = 2的方式構造
組別 1 1 2 ←參考指標，同一組的都填一樣的數字，建構方式同A(m,n)
係數 1 2 3 加權和
0 0 k-1 3(k-1)
1 1 k-2 3(k-1)
: : : :
k-2 k-2 1 3(k-1)
k-1 k-1 0 3(k-1)
題目的例題B(4,5)其實只有兩組，建構如下
組別 1 2 2 1
係數 1 2 3 4 加權和
0 1 1 0 5
1 0 0 1 5
這裡注意到m = 2時候只有一組比較特殊，要分開討論。
這裡不能用求和來鴿籠，簡單的反例即B(2,3)，鴿籠的結果是3=((0+1+2)+(0+2+4))/3
但是很明顯的2 ×2 = 4這個數字自己就比3還大了，不可能有能填的位置。
所以這時的限制條件反而是第二直排最大的數字能填多少，所以就單純從0填到[n/2]，
共有[n/2] + 1組。
B(2,n)建構方式如下，因為第二排已經不可能再填下一個數字了，很明顯是最大組數。
係數 1 2
n 0
n-2 1
: :
n-2[n/2] [n/2]
這樣我們就完成所有B(m,n)的討論了。（m = 1明顯只能填1組，和A的情形相同）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.154