找回密码
 立即注册
搜索
总共850条微博

动态微博

查看: 1371|回复: 6
打印 上一主题 下一主题
收起左侧

外国饭店推广解答

[复制链接]

158

主题

544

帖子

9110

积分

跳转到指定楼层
楼主
发表于 2005-11-16 20:34:30 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

www.ddhw.com

你和四个朋友一起去一家外国饭店吃饭。菜单上有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个菜。

www.ddhw.com

 
回复

使用道具 举报

210

主题

3101

帖子

8万

积分

沙发
发表于 2005-11-16 21:54:01 | 只看该作者

如果我有实力都能做做你的好题多好! [@};-][@};-][@};-][@};-]


  如果我有实力都能做做你的好题多好!




回复 支持 反对

使用道具 举报

226

主题

1358

帖子

1万

积分

板凳
发表于 2005-11-16 23:37:53 | 只看该作者

Nice!


  Nice!




回复 支持 反对

使用道具 举报

158

主题

544

帖子

9110

积分

地板
 楼主| 发表于 2005-11-17 00:21:19 | 只看该作者

回复:如果我有实力都能做做你的好题多好! [@};-][@};-][@};-][@};-]


You did well on the Cube kissing problem. Other sites (WXC and QQSH) has only 20 so far.
www.ddhw.com

 
回复 支持 反对

使用道具 举报

105

主题

486

帖子

6801

积分

5#
发表于 2005-11-17 01:07:53 | 只看该作者

[:((]


  




回复 支持 反对

使用道具 举报

105

主题

486

帖子

6801

积分

6#
发表于 2005-11-17 01:11:41 | 只看该作者

[:((]


這裡果然藏龍臥虎﹐俺數學不好﹐最近老上這來﹐ 結果晚上做夢到考數學﹐厚厚的一迭捲子﹐死也做不完﹐嚇醒﹗
www.ddhw.com

 
回复 支持 反对

使用道具 举报

210

主题

3101

帖子

8万

积分

7#
发表于 2005-11-17 09:55:13 | 只看该作者

[:))][:))][@};-][@};-][@};-][@};-]


  




回复 支持 反对

使用道具 举报

24小时热帖
    一周热门
      原创摄影
        美食美文
          您需要登录后才可以回帖 登录 | 立即注册

          本版积分规则

          Archiver|手机版|珍珠湾ART

          Powered by Discuz! X3 © 2001-2013 All Rights Reserved