关于煮鸡蛋问题的广而推之 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#1

发表于 2008-8-4 12:01 资料文集短消息看全部作者

关于煮鸡蛋问题的广而推之

首先是煮鸡蛋问题，这是一道小学一年级的数学题，原帖因为比较搞笑所以在水版：
http://xycq.moddiy.com/forum/thread-174441-1-1.html
为了方便不想看上面这个帖子的人，月月在这里把问题重复一下：煮1个鸡蛋需要6分钟，现在问煮6个鸡蛋要多长时间。
这个题目没有给出锅子的容积，所以我个人认为标准答案是6分钟，也就是假设锅子的容积可以装6个鸡蛋，并且假设不管多少个鸡蛋一起煮，所需时间不变。那么上面这样恶搞完以后，月月开始很严肃地思考：如果我们把问题推广化：假设我们有M个鸡蛋，每个鸡蛋煮T分钟后可以熟，而锅的容积是N个鸡蛋（M≥N），问最少多长时间可以煮熟，而且在最短时间内的煮熟方法。
首先还是要定几条前提条件的，这样就杜绝了我这样爱刨根问题钻牛角尖的人。前提条件一是：忽略水越煮越少的问题；前提二：不管是分几次煮的，只要煮够T分钟，鸡蛋就可以熟；前提三：忽略把鸡蛋拿进锅子和拿出锅子的时间；前提四：时间可以细分，比如我们可以精确测量出1/n这种很细微的时间；前提五：鸡蛋是一模一样的，而且该系统是在完全理想的情况下进行的，忽略诸如大气压变化、空气温度变化、火焰大小变化等影响因素。
那么，第一个问题很好回答，最小时间一定是t=M*T÷N。麻烦的是，在t时间内，我们如何煮熟M个鸡蛋。
首先，我们用M除以N，假设商是a，余数是b，也就是说，M=a*N+b。我们把M个鸡蛋分成两部分，第一部分是（a-1）*N个，第二部分是N+b个。可见，N+b介于N和2N之间。当然，如果M本身就介于N和2N之间，那就意味着a=1，所以第一部分是0个鸡蛋，第二部分是M个鸡蛋。第一部分的鸡蛋比较好煮，只要N个N个地煮就可以了，因为锅子被充分应用了，所以热量没有浪费，这样煮出来的时间一定是最短的，最终需要（a-1）*T分钟。
出于简便，我们把第二部分的鸡蛋数设为m。显而易见地，如果锅子里无论什么时候的鸡蛋数都是最大容积数，也就是N，那么，所用的时间一定是最短的。也就是说，在T分钟内同时煮熟N个鸡蛋，是最省时间的（也就是按照第一部分的煮法）。在这种模式下，平均每个鸡蛋煮熟的时间是T/N。但是实际上通过常识我们可以知道，煮熟N个鸡蛋和煮熟1个鸡蛋所用的时间是一样的。之所以一锅只煮1个鸡蛋是不经济的，就是因为有部分时间（T-T/N）被浪费掉了。
那么就可以知道，实际上，当N个鸡蛋充分利用T分钟的时候，所需要的时间是最短的。那么具体鸡蛋的煮法呢？
首先，我们把鸡蛋编上号：1、2、3……N-1，N，N+1……m-1，m，然后把前N个鸡蛋放进锅里，等T/N分钟后，把1拿出来，把N+1放进去；再过T/N分钟，把2拿出来，把N+2放进去……这样，每过T/N分钟，都把锅里编号最小的放进去，然后把锅外面编号最小的放进去。直到第（m-N+1）*T/N分钟，这时候最后一个鸡蛋已经在锅里了，这个时候把锅里编号最小的鸡蛋拿出来，把1放进去；第（m-N+2）*T/N分钟，把锅里编号第二小的拿出来（此时编号最小的是1，刚刚放进去），把2放进去……这样轮换，直到T分钟后，所有鸡蛋煮熟。按照这种方法煮，每个鸡蛋被煮了N次，每次被煮的时间是T/N，因而是最高效的。
之前我们将M个鸡蛋进行了分组，实际上，如果不分组的话，按照上述的方法也是可以煮的，所需的总时间也没有变化。但是所有鸡蛋都这么折腾实在是有点累，所以首先我们N个N个地煮，然后剩下N+b个的时候再如上操作（因为仅剩b个的时候就只能一锅煮了，肯定是浪费时间的）。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#2

发表于 2008-8-4 13:07 资料文集短消息看全部作者

楼上高人！！
其实另一种情况是这样的：锅的容积和鸡蛋的个数有公因数，也就是am和bm，这个时候其实是可以按照a和b的情况来看的，只不过每次换的鸡蛋数是m个而已。
比如锅能装6个鸡蛋，一共9个鸡蛋要煮，这时候的策略其实是：
1、2、3、4、5、6
1、2、3、7、8、9
4、5、6、7、8、9

嗯，我们把问题改一改，改成在最短的时间内，最少换多少次才能煮熟所有的鸡蛋。
顺便得到的结论一：在这种最优策略下，隔多少时间换一次鸡蛋？
顺便得到的结论二：是不是每次更换鸡蛋的间隔都一样？
楼上已经给出了结论二，即不是每次更换鸡蛋的时间间隔都一样。那么还有一个问题：
顺便得到的结论三：在何种情况下，每次更换鸡蛋的时间是不一样的？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#3

发表于 2008-8-4 17:45 资料文集短消息看全部作者

QUOTE:

原帖由 水镜门生 于 2008-8-4 17:23 发表
应该发到射虎

之前是觉得那里全是谜语什么的，现在我也觉得应该在那里了。哪位有权限的牛人帮月月挪一下？

[广告] 真诚支持说岳，携手共创辉煌


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#4

发表于 2009-2-26 18:11 资料文集短消息看全部作者

老题了，想到现在，依然不明白……

[广告] 真诚支持说岳，携手共创辉煌