3個人去打飯，滿足所有可能的需求需要多少個盤子？

12-02

現在有3個人去打飯，
食堂的打飯師傅是個非常精確的人，說打一兩飯就絕對是一兩飯。而且他有一個分析天平，可以在大家還沒來打飯之前就稱好飯的重量，並放到不同盤子裡面。
現在問：這個打飯師傅至少需要多少個盤子才能使得無論這3個人分別要多少飯都可以精確地得到滿足？每個人的飯量在一兩到兩斤（二十兩）之間，最小單位是兩。

註：打飯的時候可以combine幾個盤子給一個人。天平只能在一開始的時候使用。

@管清文的答案早了一步TAT
12個是可以的，方案是1,1,1,2,2,3,4,5,7,9,12,16

我是這樣想的，首先加強條件，要求「三個人都打相同數目的飯n」，再考慮只需要滿足「已有盤子中的飯的總重量超過需要供應的飯的總重量」，這時所需要盤子的數目的下界顯然也是原問題的一個下界。
n=1時，顯然需要1,1,1這3個盤子；
n=2時，共需要分量為2*3=6的飯，而已有盤子中的分量為3，至少再要2個分量&<=2的盤子；
n=3時，共需要分量為3*3=9的飯，而已有盤子中的分量至多為7，至少再要1個分量&<=3的盤子；
n=4時，共需要分量為3*4=12的飯，而已有盤子中的分量至多為10，至少再要1個分量&<=4的盤子；
n=5時，共需要分量為3*5=15的飯，而已有盤子中的分量至多為14，至少再要1個分量&<=5的盤子；
n=6時，共需要分量為3*6=18的飯，而已有盤子中的分量至多為19，此時不需要額外的盤子；
n=7時，共需要分量為3*7=21的飯，而已有盤子中的分量至多為19，至少再要1個分量&<=7的盤子；
n=8時，共需要分量為3*8=24的飯，而已有盤子中的分量至多為26，此時不需要額外的盤子；
n=9時，共需要分量為3*9=27的飯，而已有盤子中的分量至多為26，至少再要1個分量&<=9的盤子；
依此類推，在n=12、16時各再需要一個分量&<=12和&<=16的盤子。
因此，12個盤子是盤子數目的下界，至少需要12個盤子才能滿足「都打相同數目的飯」的情況下對"總重量"的要求（但可能不滿足原問題的要求）。

注意到上述過程中給出了一個12個盤子的組合，就是(1,1,1,2,2,3,4,5,7,9,12,16)，經程序驗證（╮(╯_╰)╭），這個組合可以解決原問題（只需要使用貪心的做法，不斷地把當前最大的盤子提供給當前最需要飯的那個人），因此原問題的答案就是12個盤子。

附醜陋的代碼：

num = [16, 12, 9, 7, 5, 4, 3, 2, 2, 1, 1, 1] n = 20

for i in range(n): for j in range(n-i): for k in range(n-i-j): a = i + 1 b = j + i + 1 c = k + j + i + 1 left = [a,b,c] for i1 in range(12): j1 = 0 while j1&<3: if left[j1]&>=num[i1]: left[j1] = left[j1] - num[i1] j1 = 3 else: j1 = j1 + 1 if left != [0,0,0]: print(a,b,c) print("end")

如果只有1個人打飯，則需要的盤子有:
1, 2, 4, 8, 16, ...
F(n) = [F(1) + ... + F(n-1)] + 1

如果只有2個人打飯，則需要的盤子有:
1, 1, 2, 3, 4, 6, 9, 14, ..
F(n) = [F(1) + ... + F(n-1)] / 2 + 1

如果只有3個人打飯，則需要的盤子有:
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 22, ...
F(n) = [F(1) + ... + F(n-1)] / 3 + 1

證明(終於想到怎麼證明了)
對於答案的下界，已經由 @Richard Xu 很好的證明。
對於答案的可行性，證明如下:
我們證明一個更強的結論，用前n個盤子，可以組成 $a + b + c le sum_{i=1}^n {F_i}$ , 其中 $a ge b ge c ge 0$ ，的所有組合。
通過數學歸納法來證明。

1. 當n很小的時候，可以通過枚舉證明。
2. 假設原本問題對於n-1成立，對於n的情況，
2.1 如果 $a le (F_n - 1) = lfloor frac{1}{3} sum_{i-1}^{n-1} F_i floor$
則 $a + b + c le 3a le 3 (F_n - 1) le sum_{i=1}^{n-1} F_i$
可以用前n-1個盤子就組成需要的組合。
2.2 如果 $a ge F_n$ ，則
$(a - F_n) + b + c le sum_{i=1}^{n-1} F_i$ ，只需用前n-1個盤子組成 $a - F_n, b, c$ 的組合，再把第n個盤子給第一個人即可。

(?Д?≡?д?)!?

看到這個問題以及目前的八個回答的我

管清文的答案應該是正確的。

更一般地，對於有 m 個人買飯的情況，每個人可以買 1~n 兩，則需要的盤子的數列滿足：

$f(k)=1, k=1,2,..m$
$f(k)=left[ frac{sum_{i=1}^{k-1}{f(i)} }{m} ight]+1 , kgeq m+1$