外国饭店推广解答 - 珍珠湾ART

你和四个朋友一起去一家外国饭店吃饭。菜单上有9种菜，但是一个字都不认识，服务员说话也听不懂，要的菜也不知道谁要的是什么。唯一可以用来判别菜的是数量：如果你们要了三个 sdfdaskkj，两个 kljksdfsda，结果来了三个炸大虾，两个清蒸鱼，那 sdfdaskkj 就是炸大虾，kljksdfsda 就是清蒸鱼。假设你们每次要5个菜，你们去吃几顿饭才可以认清所有的菜？

如果一共m个人，去k次，最多可以认清几个菜？

原题野菜花已经给出正确答案。下面是推广题的答案。（很难看的答案。）

设最多可以认清的菜的数量为f(m,k)。对某一个菜，把每次要的数量放进一个k元数组：（2，0，3）表示第一次要了两个，第二次没要，第三次要了三个。如果两个菜的k元数组不一样，就能够区分开。这个问题于是变成找一个非负整数k元数组的集S，使得S中k元数组在每个坐标的和不大于m，并且使|S|最大。www.ddhw.com

为了让|S|大，每个k元数组中各坐标的和越小越好。对给定的i，各坐标的和等于i的k元数组共有C（k+i-1,i)个。这些k元数组在每个坐标的和等于C（k+i-1,i)*i/k = C(k+i-1,i-1)。把这两个数从1到i加起来，有

C(k,1)+C(k+1,2)+...+C(k+i-1,i) = C(k+i,i) - 1
C(k,0)+C(k+1,1)+...+C(k+i-1,i-1) = C(k+i,i-1)

即f(C(k+i,i-1),k) = C(k+i,i) - 1。k = 3, i = 2 时有 f(5,2) = 9，就是原来的题。

对不同的i之间的m值，f 基本上是线性的，即给定k之后，f(m,k)基本上是折线函数。更准确一点，设 m = C(k+i,i-1) + j，其中 i 是使 m >= C(k+i,i-1) 的最大值。则有

f(m,k) = C(k+i,i) - 1 + [j*k/(i+1)]。

例如10个人吃6顿饭，i=2, j=2。f(10,6) = C(8,2) - 1 + [2*6/3] = 31。即最多可以认清31个菜。