[今天我们思考01]1000瓶葡萄酒的问题

[pongba]

波利亚的《How To Solve It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。

我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生——从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。

题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。

我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。

我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。

要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"——把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

从一道题目中获得最多的东西，这是做题的目的。

你有没有这样的经历，一道题目你做不出来，你拿去问某个人，某个人想了一会儿，然后指出某个关键的step，于是一切豁然开朗。

但这不是全部！

如果你继续问他是怎么想到的，经验告诉我，几乎所有的可能性都指向一个答案"我也不清楚"。

为什么？根据我自己的经验，我相信是因为绝大多数人都没有仔细反省自己思考的过程。如果想不出来，拉倒。如果想出来了，万事大吉。但波利亚在《How to Solve it》中说到，他在教学的过程中总是碰到这样的问题"你是怎么想到的"？这个问题促使了他去总结思维的规律，有了这些规律，即使不那么富有灵感的人，也可以运用这些规律，让自己的思维的触角能够伸展开去。

答案不重要，如果你直接告诉我关键的一步，我什么也没有得到。甚至就算我自己想出了最关键的一步，也许我还是什么都没得到。因为这样的经验只能极其有限地对我下一次的问题产生帮助；除非我能进一步思考思维背后的规则。

所以，重要的是思考的过程，不管这个过程是不是带领你得到答案。我相信只有最深刻了解了思考的真正过程，才能够从做题中获得最多的东西。

如果你对以往做题的思路有很好的思考，也欢迎和大家分享～

1000瓶葡萄酒的问题：
题目来自：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
友情感谢silwile同学提供地址，伯克利的这帮家伙的确很生猛～里面的题目几乎都很有价值。

An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

今天，我们思考。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[alai]

提示：2^10 = 1024 > 1000

在 08-4-9，pongba<pon...@gmail.com> 写道：

> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

[windstorm]

this king knows that he needs to murder no more than 10 prisoners to

figure out what bottle is poisoned?

总共就一瓶有毒的吧。

另外，the effects of the poison take one month to surface，是不是限定了只要30天我们就知道
结果？

[alai]

1000瓶酒中只有1瓶有毒，稀释至1000000倍仍有毒，但要1个月才见效，用10个人来试，时间不超过5周

在 08-4-9，windstorm<likunar...@gmail.com> 写道：

[windstorm]

5周应该 = 一个月+1周 = 药效发作+ 7天

right？

[鋆邓]

没细看英文，只看了你们回复
觉得摆明了二进制问题，十个人喝不同的可表示2^10种了……1024>1000
剩下几天给你用来配药啥的吧……

2008/4/9 windstorm <likunar...@gmail.com>:

[hg]

找出一瓶毒酒，忽然间想到以前学过能找出错误的纠错码--海明码

pongba 写道：
> �����ǵġ�How To Solve
> It��������һ���½��г���һ��ѵ�Heuristics���������Ʃ�����Ŀ���������������������ȡ����ܷ��ӵ�ʲô��������ܷ��޸�ʲô�����ʱ��ע��δ֪ ...�ȵȡ�
>
> ����һ�������ν����У�����һ������Ĺ�����Ȼ��з�������ʶ���棨�ο���׷Ѱ����ĺۼ��������¶��Լ���̬�ȸı������Ӱ�졷����Ͷȣ���"���´̼�"�½ڣ��������޷������֮ǰ������ʶ�����쵽��е���Ĺ�̣�Ȼ�����ǵ�ȷ��������з���֮��ͨ��ع˺ͺ��������ܽ�����п��ܵ�˼·����ѧ�ķ�չij����������ľ�������һ�����飬�������ص����?����ѧ�����IJ���������ۡ���ʽ�߼�����ѧ���ɷ�����ȡ�������Щһ��˼ά���򵽸���ԭ�?��ֵԭ�?̰7ԭ���������ض������ԭ�?��һ���Ƕ�˼ά��̵��º��ܽ�����?Ʃ���Ҿ����ʽ�߼����������º������4��˼ά������������������ʶ����;���������f���μ�Ƥ�ǽܵ���֪��չԭ�?������Ҳ�?��Ȼ���Ǹ�ֲ�ڴ�������ĸ���һ����Щ�����ǽ��4�ģ���������ʶ����ܹ���w���á�Ȼ��Ҫ�������ǵõ���չ������������ʽ����ֽ�ϣ���Ϊ�κ��˶��ܲ���ķ����ۣ�����Ҫ��ʶ�IJ��롣
>
> �췢�����ϵ��"��������˼��"����4����д"������������"�����뵽������۵�Ŀ����ʵ��˼��������ˣ�����Ҷ����Լ���Ϊ��ʵ���Ŀ����4������ʱ�����[��������˼��<���>]�����Ժ����������һ����һ�������ڼ����Ƿdz���������顣
>
> ��Ŀδ��Ҫ�£��ҵ��뷨�ǹؼ���Ҫ���䣬���ϵ�еĹؼ�����Ҫ���������˼·��������Ŀ���?����ȫ����Ŀ�ģ�����ò���𰸵�˼·Ҳ�кܴ�ļ�ֵ��������뵽��һЩ˼·��������ȥ��𰸻������Զ��û���κι�ϵ������4��Ҳ��Ա��˵�˼·�кܴ��������һ���ʼ��б��ڵ�ͷ�Է籩��������뵽�˴𰸣������ܹ��ܽ���Լ�˼·�еĹؼ���������ô�뵽�ģ��������Ҷ��������dz��
>
> �������⡢���⡢���⣬������Ϊ������w��Ψһ�취�������⣬��Ϊֻ����ͷ������ܹ������f����Ȼ��wϰ�DZ�Ҫ���������Щwϰ����һЩwϰ����Ч��
>
> ���ǿ�˼ڤ�룬��ij��˲��õ���У����ǻ���ȸԾ������ʱ������ƣ���������ʱ��Ҳ���Խ4Խ�࣬����������Ϊ���������Ч��wϰ�������Ҳ���ô��Ϊ���Ҿ����Ŀ�����˼ά�������ͨ�ģ�ͨ��һ�δεĵȴ����4wϰ���DZ����ġ�����г���֮���ܽ�Ϊʲô��л���֣����������ʲô���˼ά���򣬿����ܷ񷺻���һ����Ŀ����������°빦���ķ�������Ϊ���ǵ���ʶ�����޷���쵽����ʶ����������߼�����������ֻ�ܾ������Ϊ������һ�δν��������������ʶ�������Ԫ�õ���v֮�������Ȼ������ij���ȴ����������۵㣬��ν�����ʵ����"ԭ������������ʶ����""��4����ʽ�������4����������ʶ4ָ���ķ���"���ܽ����˼ά�ķ��������´α��п��ܲ��þ���صȴ������ŵ���е����֣����ǿ���ϵͳ���س��Ը��ֿ��е��ַ���������ˡ�
>
> Ҫʵ�����Ŀ�ģ����ܽ��Լ�����б����˼ά������Ϊһ���ԵĽ���˼·��������Ϊһ�ַ����ǿ�ȡ�ģ�����ν��"�����ŵ�˼��"���������˼�������ϸ��д��ֽ�ϡ��˵���ʶ�����ҹ��ĵƹ⣬ֻ������һ���С�ľֲ������д��4��˼ά�ĵƹ��������޵ģ��п����ߵ��������ǰ�棬Ҳ�п��ܸɴ��û������˼����д��4�����Ա���������⣬˼ά�Ϳ��������ߣ��Ϳ����յ�Խ4Խ��ĵط������⣬д��4���ܹ�ʹ���Լ��ܹ��ع�ͷ4�����Լ������˼����̣�Ҳ��ǰ��ij��ʱ�����뵽һ�����������4��ͺܿ����ˣ������4��ͷһ��Ҳ�������кܴ�����Ҳ�?����˼ά��ijһ����������������һ���뵱Ȼ�ļ��裬�Ӷ������˼ά���Ƶ����壬ͨ��д��4���Ϳ���һ���̶��ϱ�����������塣
>
> ��һ����Ŀ�л�����Ķ������������Ŀ�ġ�
>
> ����û������ľ���һ����Ŀ�����4������ȥ��ij���ˣ�ij��������һ���Ȼ��ָ��ij��ؼ��step������һ�л�Ȼ���ʡ�
>
> ���ⲻ��ȫ����
>
> ����������������ô�뵽�ģ���������ң��������еĿ����Զ�ָ��һ���"��Ҳ�����"��
>
> Ϊʲô��������Լ��ľ��飬����������Ϊ�������˶�û����ϸ��ʡ�Լ�˼���Ĺ�̡�����벻��4��-����������4�ˣ����´󼪡����������ڡ�How to
> Solve
> it����˵�������ڽ�ѧ�Ĺ�������������������"������ô�뵽��"����������ʹ����ȥ�ܽ�˼ά�Ĺ��ɣ�������Щ���ɣ���ʹ����ô������е��ˣ�Ҳ����������Щ���ɣ����Լ���˼ά�Ĵ����ܹ���չ��ȥ��
>
> �𰸲���Ҫ�������ֱ�Ӹ����ҹؼ��һ������ʲôҲû�еõ������~������Լ��������ؼ��һ����Ҳ���һ���ʲô��û�õ�����Ϊ����ľ���ֻ�ܼ������޵ض�����һ�ε����������������ܽ�һ��˼��˼ά����Ĺ���
>
> ���ԣ���Ҫ����˼���Ĺ�̣�����������Dz��Ǵ�����õ��𰸡�������ֻ��������˽���˼���������̣����ܹ��������л�����Ķ���
>
> ���������������˼·�кܺõ�˼����Ҳ��ӭ�ʹ�ҷ��?
>
> 1000ƿ���ѾƵ����⣺
> ��Ŀ4�ԣ�http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
> �����лsilwileͬѧ�ṩ��ַ������������һ��ȷ�����͡��������Ŀ������м�ֵ��

>
> An evil king has 1000 bottles of wine. A neighboring queen plots to kill the
> bad king, and sends a servant to poison the wine. The king's guards catch
> the servant after he has only poisoned one bottle. The guards don't know
> which bottle was poisoned, but they do know that the poison is so potent
> that even if it was diluted 1,000,000 times, it would still be fatal.
> Furthermore, the effects of the poison take one month to surface. The king
> decides he will get some of his prisoners in his vast dungeons to drink the
> wine. Rather than using 1000 prisoners each assigned to a particular bottle,
> this king knows that he needs to murder no more than 10 prisoners to figure
> out what bottle is poisoned, and will still be able to drink the rest of the
> wine in 5 weeks time. How does he pull this off?
>

> ���죬����˼����
>
> --
> ��δ��(pongba)|C++���޸���

[windstorm]

没这么简单吧......我总觉得说5周是有原因的。

不然为啥要5周？直接组合一个月就出来了。

好歹这还是relatively hard的题目啊

[Shao Feng]

两个人能试出4个酒瓶吗？

[windstorm]

当然能。理论上讲。

[windstorm]

这道题说得有问题

Rather than using 1000 prisoners each assigned to a particular bottle,
this king knows that he needs to murder no more than 10 prisoners to
figure out what bottle is poisoned

没有说king只能"使用"10个人，是murder no more than 10 prisoners

那方法海了去了，比如矩阵计算什么的，而且和那个5周没有任何关系

[lijian]

我的答案是二分查找，每次把酒分两份，第一次将1000瓶分成两个500瓶，各500瓶混合了给两个囚犯喝（反正毒性恶劣，dilute许多次都有
效），必死一个；然后是在死人的那500瓶里再分两份，每250混合给两个囚犯喝，又死一个......第10轮剩下2瓶，让最后一个囚犯挑一瓶喝，幸
运的话他不用死。总之最后知道哪一瓶有毒。

[windstorm]

这个方法是错的，毒性一个月后才能发作

[Shao Feng]

if diluted more than 1,000,000 times, is it still be fatal?

On Wed, Apr 9, 2008 at 9:58 PM, windstorm <likunar...@gmail.com> wrote:

这个方法是错的，毒性一个月后才能发作

[windstorm]

I don't know....But obviously it's not the crucial point of this riddle..

--
web: http://www.forwind.cn
msn: likunarmstrong at hotmail.com

[alai]

再加点提示：10个人喝完酒后，每个人有中毒和不中毒两种可能的结果，10个人就有1024种可能的结果。只要设计好每个人喝的酒是如何混合得到的，每一种可能结果就可以代表某一瓶酒有毒。

在 08-4-9，alai<ala...@gmail.com> 写道：

[windstorm]

这就是简单的纠错码设计思路......

问题是alai考虑过，为什么它会提到这5个月没有？

[windstorm]

5周，不好意思。

如果仅仅是这个思路，没理由归类于hard的。

[alai]

我认为，5周就是1个月加几天而已，应该没有其它意思

2008/4/9, windstorm <likunar...@gmail.com>:

[hayate]

我想答案并不重要。重要的是怎么想到的？
2008/4/9 alai <ala...@gmail.com>:

[zhang]

如果是这样的，一人喝一瓶，只会死一个人，应该是最好的方法了。

[Shao Feng]

人编号为0，1，2，3，4，5，6，7，8，9
瓶子编号为1, 2, 3, 4, 5, ..., 999, 1000

编号为n的人需要喝的瓶子号m是满足下面条件的:
((m>>n) & 1) == 1

一个月后，所有对死人的编号 n1, n2, ..., nk
pow(2, n1) + pow(2, n2) + ... + pow(2, nk)
即是有毒瓶子的编号。

[pongba]

启发法一：考虑简单的特例。

2008/4/9 hayate <haya...@gmail.com>:

[meta]

5周指的是找出有毒的那瓶酒,外加喝完剩下的全部无毒酒的总时间. 这就意味着只有一次观察所有实验结果的机会, 你不能找1个人用最多1000个月的
时间来找出有毒的那瓶.

[meta]

你这个二分要根据前面的试验结果才能决定下一步, 在5周的时间内无法完成的. 即使没有时间限制, 每次判断有毒瓶的区间, 也不用两个人当替死
鬼, 一个就可以了.

[meta]

bottles | A | B
1 | 0 | 1
2 | 1 | 0
3 | 1 | 1
4 | 0 | 0

1 = drink
0 = no-drink

On Apr 9, 9:49 pm, "Shao Feng" <sevene...@gmail.com> wrote:
> 两个人能试出4个酒瓶吗？

[Mr Shore]

是这样
1000内的数必可由10位二进制数表示
由10个人分别表示相应的权位
并让其喝掉所有二进制表示时期所在位为1的酒
最后
相应权位上喝死的为1，反之为0
即可求得有毒酒

不知道这种思路是怎么来的

在08-4-10，meta <carma...@gmail.com> 写道：

[Mr Shore]

10个人的生死总共10比特的信息
可以描述1024种情况
所以理论上是可以覆盖这1000种情况的
但是必须设计的十分精细
各种情况应该正交
而二进制的各个位正好满足这个特性

在08-4-10，Mr Shore <shore...@gmail.com> 写道：

[alpswy]

我从纠错编码的表示来理解，1000个数据位，其中有一位是错的，不妨假设没有毒的用0表示，有毒的用1表示，则这1000个数据位中只有一位
是1。现在要用10个校验位来表示出错的位置，可以用汉明码，理论上是可以找到错误位置的，因为2^10>1000，符合汉明码的纠错条件。
设X是1×1000行向量，H是1000×10的(0,1)矩阵，现在的问题是，找到1个矩阵H，使得，使得当X中的那个1分别处在这1000
个位置时，行向量XH，分别对应1000个不同的值。
简单的构造方法是查表找到这个矩阵，但这显然不是我们的初衷。具体的构造方法，我再想想，也请各位指教。

[hayate]

这个问题算是很熟悉的一道题了，以至于看到题目就知道答案了。过去的经验和知识起到了很大的作用，使得搜索和联想的范围都变得更广。所以很难找到一个从"零"开始的思路了。

[kenical]

我想是不是可以这样子做呢？
1、为1000桶酒编号，1~1000；
2、为每个人编号：A~J；
3、第一天，把酒分为10组，每份100桶，有1~100，101~200，···901~1000，然后每个人对应其中一份，即A对应于
1~100；
4、第二天，把酒取序号重新编组：如取原来每一组的前10个分为一组，即1~10，101~110，···901~910分为第一组。其它的类似，然后
让每个人又对应其中的一组。
5、第三天，把酒又重新编组：取（4）中所有分组中每个取出10个，即1、11、21、···991为一组，2、12、22、···992为一组，其它
的类似，然后让每个人又对应其中的一组。
6、这样，一个月后先死的一人就可以确定出哪一百桶有毒。
7、第二个死的人可以确定第一份里的哪10桶有毒。
8、第三个死的人可以确定10桶里哪一桶有毒。

[kenical]

1、把酒编号，分成10份，每份100桶。
2、把囚犯编号，每人对应一份。第一天让他们喝下自己对应的酒。
3、把酒重新编号，在原来的每份里抽起10桶，组成新的10份。让囚犯在第二天喝下新的那份酒。
4、酒重新编号，在第一次分配各第二次分配对应的10桶里取出一桶，重新组成10份。让囚犯在第三天喝下新的那份酒。
5、根据囚犯死的时间可能依次推出：哪100桶里有毒，100桶里哪10桶有毒，10桶里哪一桶有毒。

[windstorm]

不对，从题目的意思看，死的时间是不能"精确推算"出来的

不然一个人就可以了，让他不断喝，到时候看具体到某一秒死的，就能知道什么酒有毒。

[alai]

kenical的方法很有创意，虽然如windstorm所言，题目没有给出毒发时间的精确度，所以不够严谨，但还是还有创意的，值得加分。
不过，就算题目给出毒发时间的精确度为一天，kenical的方法还是存在一个小漏洞，因为"人死不能复生"。
为简单起见，假设酒桶编号为000-999，囚犯编号为0-9。第一天，第n位囚犯喝的是编号为nxx的酒，x为0-9；第二天，第n位囚犯喝的是编号为xnx的酒；第三天，第n位囚犯喝的是编号为xxn的酒。假定编号010的酒有毒，结果是一个月后的第一天，0号囚犯毒发，第二天1号囚犯毒发，但是第三天没有人再毒发。你只能判定有毒的酒桶编号前两位是0和1，无法判定最后一位是0还是1，即010号和011号酒都可能有毒。如果是第二天没有人毒发，则还好办，可以肯定毒酒编号的前两位相同。但如果是第三天才出现没有人毒发，问题就大了。

在 08-4-10，kenical<ken...@126.com> 写道：

[kenical]

那就这样子：用2的10次方推算出1024>1000的方法。
用4个人模拟16桶酒中有一桶有毒的情况。
1、为16桶酒编号为1~16。4个人编号为A、B、C、D；
2、把16桶酒分成两组，让A喝下第一组，即1~8；
3、把每一组的8桶分成两组，每组4桶，即1~4为一组，5~8为一组，9~12为一组，12~16为一组；让B喝下第一组（1~4）和第三组
（9~12）；
4、同样把上面的每一组分成两组，每组2桶，让C喝下1、3、5、7四组。
5、剩下的还是把上面的每一组分成两组，每组1桶，让D喝下1、3、5、7、9、11、13、15八组。
6、这样就可能根据ABCD四个的置位算出哪一桶有毒。1000桶酒10个人的推理也类似。

[windstorm]

我昨天想过你这个方法，但是1000瓶酒，10个人不够用。你可以自己算一下。

当然也许是我算错了

[kenical]

应该够的啊，2的10次方1024>1000啊
即，第一个人确定了哪500桶中有毒；
第二个人确定了500桶中哪250桶中有毒；
这样推下来就相当于对上一次的除2操作了啊，除到最后是小于1的，所以应该是足够的啦

[windstorm]

1000
500 500
250 250 250
250
125 125 125 125 125 125 125 125

往下我们就不说了，你意思说要确定哪个125里面有毒，只需要3个人？那你谈一谈怎么确定吧。一旦这个确定不了，往下就不用想了

[鋆邓]

8组，编号 0 1 2 3 4 5 6 7
A B C 三个人
A 吃 4 5 6 7
B 吃 2 3 6 7
C 吃 1 3 5 7
三个人的8种组合，分别对应8组

完毕。

2008/4/10 windstorm <likunar...@gmail.com>:

[xxmplus]

这个题目的论述确实有问题，即使我找了1000个囚犯来喝酒，也不会毒死超过10个人。。。。

2008/4/10 鋆邓 <tdzl...@gmail.com>:

--
Any complex technology which doesn't come with documentation must be the best
available.

[kenical]

确定125里面有毒，需要7个人啊，但是前面我们用3个人就确定了哪125桶里面有毒，所有刚好10个人啊，记住，当第一个人喝了1000桶里面的
500桶时，另外500桶是不需要喝的，只要确定这个人有没有中毒就可以知道毒是在这500桶里还是在剩余的500桶里。而接下来的哪个人要喝的不仅是
第一个人喝的500桶里的前面250桶，也包括剩余500桶里的前面250桶。这样第一个人确定了哪500桶有毒，每二个人确定了哪500桶里的250
桶中有毒。如此类推，第三个人确定了哪250桶里的125桶中有毒。

[kenical]

//鋆邓 查看个人资料

//8组，编号 0 1 2 3 4 5 6 7
//A B C 三个人
//A 吃 4 5 6 7
//B 吃 2 3 6 7
//C 吃 1 3 5 7
//三个人的8种组合，分别对应8组

//完毕。

//2008/4/10 windstorm <likunarmstr...@gmail.com>:

就是这样。

On 4月10日, 下午12时37分, "鋆邓" <tdzl2...@gmail.com> wrote:
> 8组，编号 0 1 2 3 4 5 6 7
> A B C 三个人
> A 吃 4 5 6 7
> B 吃 2 3 6 7
> C 吃 1 3 5 7
> 三个人的8种组合，分别对应8组
>
> 完毕。
>

> 2008/4/10 windstorm <likunarmstr...@gmail.com>:

[alai]

LS的E文要好好补习一下了。

在 08-4-10，xxmplus<xxm...@gmail.com> 写道：

[roychen]

如果加上限制条件：每个人酒量有限只能喝1瓶葡萄酒，并且都十分贪婪一滴都不肯少喝
就比较符合初衷了

On Apr 9, 9:28 pm, alai <ala...@gmail.com> wrote:
> 1000瓶酒中只有1瓶有毒，稀释至1000000倍仍有毒，但要1个月才见效，用10个人来试，时间不超过5周
>
> 在 08-4-9，windstorm<likunarmstr...@gmail.com> 写道：

>
>
>
> > this king knows that he needs to murder no more than 10 prisoners to

> > figure out what bottle is poisoned?
>
> > 总共就一瓶有毒的吧。
>
> > 另外，the effects of the poison take one month to surface，是不是限定了只要30天我们就知道
> > 结果？- Hide quoted text -
>
> - Show quoted text -

[windstorm]

这个限制条件才是错的，不能这样限制，只能喝一瓶，10个人怎么够

1000瓶都要品的。

[Shao Feng]

意思是只让10个人冒被毒死的风险。

[windstorm]

To Kenical:

恕我愚笨，我还是不觉得这个方法能验证出来

鋆邓的方法是可以的，等于是组合方法，其实和编码的原理差不多的

--

[alai]

其实题意还是很严谨的：稀释至1000000倍仍有毒，表示只要喝掉1瓶酒的1/1000000就会中毒。所以，每个囚犯要喝掉由500瓶酒中各取出1/1000000所混合而成的酒，其实就只有1/2000瓶，一小口而已；而每一瓶酒要被取出10份1/1000000，也少了只是1/100000而已。

在 08-4-10，roychen<ROY.C...@gmail.com> 写道：

[windstorm]

这我知道，我是说我ls的限制方法是错的

[xxmplus]

this king knows that he needs to murder no more than 10 prisoners to
figure out what bottle is poisoned

我知道题目的意思，但是这句话确实没有表达出题目应该表达的东西。
还有，我问了下公司里的老外，他们都同意我的看法，所以补习英文就不必你操心了

2008/4/10 alai <ala...@gmail.com>:

[alai]

国王知道，他只需要杀死最多10个囚犯，就可以找出哪瓶酒被下了毒。

这句话说的是，国王比我们很多人都要聪明。

[Shao Feng]

2008/4/10 xxmplus <xxm...@gmail.com>:

1/1000000 的意思就是说，一个人喝一瓶酒的1/1000000，就算1000个人都喝到了这瓶酒，这瓶酒也只少了微不足道的1/1000

[kenical]

其实我的方法跟鋆邓的方法是一样的。
即假设有A、B、C三个人，1000桶酒编号为1~1000；
A喝了1~500的酒，
B喝了1~250、501~750的酒，
C喝了1~125、251~375、501~625、751~875的酒。
这样，如果A中毒了，确定毒在1~500，反之在501~1000，这里假设为在1~500；
如果B中毒了，由于先前A中毒了，所以毒在1~250；
如果C中毒了，由于A与B都中毒了，所以毒在1~125；

[Shao Feng]

2008/4/10 alai <ala...@gmail.com>:

1000个人担风险，肯定只要死1个人。
10个人担风险，最多死9个人。

哎。还是风险分布广一点好，把风险转嫁给别人总是一个好办法。

[windstorm]

明白了，靠。现在理解能力真的有问题。

我昨天也这样分过，不过我推了4层后，想找一个表达式来推广，没想到，所以直接就二进制编码来想了......

[kenical]

我觉得是这样的限制，只有10个囚犯可以用，而不是只需杀死最多10个囚犯。不然用1000个囚犯来测试就可以了，只要死一个囚犯。

On 4月10日, 下午12时58分, alai <ala...@gmail.com> wrote:
> 国王知道，他只需要杀死最多10个囚犯，就可以找出哪瓶酒被下了毒。
>
> 这句话说的是，国王比我们很多人都要聪明。
>

> 在 08-4-10，xxmplus<xxmp...@gmail.com> 写道：

>
> > this king knows that he needs to murder no more than 10 prisoners to
> > figure out what bottle is poisoned
>
> > 我知道题目的意思，但是这句话确实没有表达出题目应该表达的东西。
> > 还有，我问了下公司里的老外，他们都同意我的看法，所以补习英文就不必你操心了
>
> > 2008/4/10 alai <ala...@gmail.com>:
> > > LS的E文要好好补习一下了。
>

> > > 在 08-4-10，xxmplus<xxmp...@gmail.com> 写道：
> > > > 这个题目的论述确实有问题，即使我找了1000个囚犯来喝酒，也不会毒死超过10个人。。。。
>
> > > > 2008/4/10 鋆邓 <tdzl2...@gmail.com>:

> > > > > 8组，编号 0 1 2 3 4 5 6 7
> > > > > A B C 三个人
> > > > > A 吃 4 5 6 7
> > > > > B 吃 2 3 6 7
> > > > > C 吃 1 3 5 7
> > > > > 三个人的8种组合，分别对应8组
>
> > > > > 完毕。
>

> > > > > 2008/4/10 windstorm <likunarmstr...@gmail.com>:

[xxmplus]

罢了，反正大伙明白怎么回事就行了-_-

2008/4/10 kenical <ken...@126.com>:

[alai]

终于明白 xxmplus 的意思了，你的意思是找1000个人来喝，也就死1个，找10个人来喝，则可能死0-10个，平均的期望值是5个。看来这个国王果然既聪明又邪恶啊。
我只能猜想，这个国王手上没有1000个死囚那么多，而且他还没有邪恶到让无辜的人来冒险试酒。

在 08-4-10，alai<ala...@gmail.com> 写道：

[xxmplus]

你太善良了。。。题目开始就说他是evil king，自然是坏到家了。。。至于囚犯嘛，既然拥有一个vast
dungeons，犯人也少不到哪里去。。。我估计他只是没那么多杯子而已-_-

2008/4/10 alai <ala...@gmail.com>:

[alai]

又或者他不想太多人分享他的美酒。

[Bo.Z]

论述是有问题，应该是只能找到10个囚犯来测就严谨了。那个稀释的条件也误导，根本不必要给出，但是可能楼主是考虑到有些人思维比较发散吧。

我觉得能不能这样理解：
假设两个人A 和 B测四瓶酒1, 2, 3, 4的情况。
A和B 可以发生四种情况：两人都死，两人都不死，A死 或者 B死。
然后我们希望每种情况对应其中一瓶酒有毒的情况。
既，两人死对应酒4有毒，两人不死代表酒1有毒，A死代表酒2有毒，B死代表酒3有毒。
如果要让以上情况发生，我们必须安排他们以如下方式饮酒：
如果酒4有毒AB都死： AB都喝酒4
如果酒3有毒B死： B喝酒3，A不喝
如果酒2有毒A死： A喝酒2，B不喝
如果酒1有毒AB都不死： AB都不喝酒1
恰好，如果以BA为两位二进制数， 四种死亡情况表示为: 11, 10, 01, 00 (1 表示“死亡”情况的发生)， 四瓶酒就可以用这四个数
儿代表。

以此类推。
我觉得这种想法比较直观。但是和kenical思路殊途同归。

On Apr 10, 12:55 am, xxmplus <xxmp...@gmail.com> wrote:
> this king knows that he needs to murder no more than 10 prisoners to
> figure out what bottle is poisoned
>
> 我知道题目的意思，但是这句话确实没有表达出题目应该表达的东西。
> 还有，我问了下公司里的老外，他们都同意我的看法，所以补习英文就不必你操心了
>
> 2008/4/10 alai <ala...@gmail.com>:
>
>
>
> > LS的E文要好好补习一下了。
>

> > 在 08-4-10，xxmplus<xxmp...@gmail.com> 写道：
> > > 这个题目的论述确实有问题，即使我找了1000个囚犯来喝酒，也不会毒死超过10个人。。。。
>
> > > 2008/4/10 鋆邓 <tdzl2...@gmail.com>:

> > > > 8组，编号 0 1 2 3 4 5 6 7
> > > > A B C 三个人
> > > > A 吃 4 5 6 7
> > > > B 吃 2 3 6 7
> > > > C 吃 1 3 5 7
> > > > 三个人的8种组合，分别对应8组
>
> > > > 完毕。
>

> > > > 2008/4/10 windstorm <likunarmstr...@gmail.com>:

[LostBaidu]

总共有10个人，编号为1-10.
总共有1000瓶酒，编号为1-1000.

#include <stdio.h>
#include <vector>

void GetBottleIndexs(int nPrisonerIndex, std::vector<int>&
bottlesIndexs,
int nAllPrisonersNum, int nAllBottlesNum)
{
if ((2 << nAllPrisonersNum) >= nAllPrisonersNum)
{
for (int i = 1; i <= nAllBottlesNum; ++i)
{
if (nPrisonerIndex & i)
{
bottlesIndexs.push_back(i);
}
}
}
}

void PrintEachPrisonersBottles(int nPrisoner, int nAllPrisonersNum,
int nAllBottlesNum)
{
printf("Prisoner %d have to drink: ", nPrisoner);
std::vector<int> bottlesIndexs;
GetBottleIndexs(nPrisoner, bottlesIndexs, nAllPrisonersNum,
nAllBottlesNum);
for (int i = 0; i < bottlesIndexs.size(); ++i)
{
printf("%d ", bottlesIndexs[i]);
}
printf("\r\nPrisoner %d have to drink %d bottles..\r\n\r\n",
nPrisoner, bottlesIndexs.size());
}

int main(int argc, char* argv[])
{
int nAllPrisonerNum = 10, nAllBottlesNum = 1000;
for (int i = 1; i <= 10; ++i)
{
PrintEachPrisonersBottles(i, nAllPrisonerNum, nAllBottlesNum);
}
return 0;
}

[silwile]

wow~~~
大家讨论得好热闹啊。

那个所谓的答案我想大家都差不多清楚了。
顺便再追加一问：如果你是10个不幸的囚犯里的一个，10个囚犯的标号是从1到10，你会选择哪个标号？

On 4月9日, 下午2时23分, pongba <pon...@gmail.com> wrote:
> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>
> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生——从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。
>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>
> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"——把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。
>
> 从一道题目中获得最多的东西，这是做题的目的。
>
> 你有没有这样的经历，一道题目你做不出来，你拿去问某个人，某个人想了一会儿，然后指出某个关键的step，于是一切豁然开朗。
>
> 但这不是全部！
>
> 如果你继续问他是怎么想到的，经验告诉我，几乎所有的可能性都指向一个答案"我也不清楚"。
>
> 为什么？根据我自己的经验，我相信是因为绝大多数人都没有仔细反省自己思考的过程。如果想不出来，拉倒。如果想出来了，万事大吉。但波利亚在《How to
> Solve
> it》中说到，他在教学的过程中总是碰到这样的问题"你是怎么想到的"？这个问题促使了他去总结思维的规律，有了这些规律，即使不那么富有灵感的人，也可以运用这些规律，让自己的思维的触角能够伸展开去。
>
> 答案不重要，如果你直接告诉我关键的一步，我什么也没有得到。甚至就算我自己想出了最关键的一步，也许我还是什么都没得到。因为这样的经验只能极其有限地对我下一次的问题产生帮助；除非我能进一步思考思维背后的规则。
>
> 所以，重要的是思考的过程，不管这个过程是不是带领你得到答案。我相信只有最深刻了解了思考的真正过程，才能够从做题中获得最多的东西。
>
> 如果你对以往做题的思路有很好的思考，也欢迎和大家分享～
>
> 1000瓶葡萄酒的问题：
> 题目来自：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
> 友情感谢silwile同学提供地址，伯克利的这帮家伙的确很生猛～里面的题目几乎都很有价值。
>
> An evil king has 1000 bottles of wine. A neighboring queen plots to kill the
> bad king, and sends a servant to poison the wine. The king's guards catch
> the servant after he has only poisoned one bottle. The guards don't know
> which bottle was poisoned, but they do know that the poison is so potent
> that even if it was diluted 1,000,000 times, it would still be fatal.
> Furthermore, the effects of the poison take one month to surface. The king
> decides he will get some of his prisoners in his vast dungeons to drink the
> wine. Rather than using 1000 prisoners each assigned to a particular bottle,

> this king knows that he needs to murder no more than 10 prisoners to figure

> out what bottle is poisoned, and will still be able to drink the rest of the
> wine in 5 weeks time. How does he pull this off?
>
> 今天，我们思考。
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> TopLanguagehttp://groups.google.com/group/pongba

[alai]

那要看酒的分配方案啦，因为1000<1024，对于有些方案，10个囚犯中毒的机会不是完全相等的(如按二进制方法给000-999编码的方案)；不过也还是存在完全平等的分配方案的，因为1000是个偶数，可以做到每个囚犯刚好都是喝500瓶酒的混合物，那么每个人的中毒机会都是50%。

在 08-4-10，silwile<sil...@gmail.com> 写道：

> wow~~~
> 大家讨论得好热闹啊。
>
> 那个所谓的答案我想大家都差不多清楚了。
> 顺便再追加一问：如果你是10个不幸的囚犯里的一个，10个囚犯的标号是从1到10，你会选择哪个标号？
>
> On 4月9日, 下午2时23分, pongba <pon...@gmail.com> wrote:
> > 波利亚的《How To Solve
> > It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
> >

> > 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

> >
> > 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
> >
> > 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
> >
> > 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
> >
> > 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
> >

> > 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

[Mr Shore]

向量空间往标量空间的映射问题

在08-4-10，alai <ala...@gmail.com> 写道：

[silwile]

“存在完全平等的分配方案”？存在么？

On 4月10日, 下午5时30分, alai <ala...@gmail.com> wrote:
> 那要看酒的分配方案啦，因为1000<1024，对于有些方案，10个囚犯中毒的机会不是完全相等的(如按二进制方法给000-999编码的方案)；不过也还是存在完全平等的分配方案的，因为1000是个偶数，可以做到每个囚犯刚好都是喝500瓶酒的混合物，那么每个人的中毒机会都是50%。
>

> 在 08-4-10，silwile<silw...@gmail.com> 写道：

[何源]

我觉得是正解:
> 向量空间往标量空间的映射问题
那天一个月后多出的几天是有用的.
我的做法是这样的，大家看看对否：

1 我们将1000放入一个[100,10]的矩阵.绛紫：
000 010 ... 990
001 011 ... 991
002 012 ... 992
...............
009 019 ... 999

2 第一天让10犯人喝掉矩阵列向量兑的酒,正好10行
Pn -> [00n,01n,02n...99n]
这样保证在最后一个星期的第一天一定有个倒霉蛋，比如是Pm 那么毒酒就在这一行了
2 第二天让10犯人喝掉10个矩阵列向量兑的酒1，比如
Pn -> [n00,n10,n20...,n90]
[n01,n11,n21...,n91]
....
[n09,n19,n29...,n99]
这样保证在最后一个星期的第而天可能有个倒霉蛋，比如是Pk 那么毒酒就在这一系列的列中。如果没有人死掉说明前面的Pm喝了2次毒酒.
这样就可以将毒酒确定在10瓶中。如果国王罢手浪费9瓶酒可以换条命呢。看来真是邪恶!
3 第三天.我们已经确定毒酒在如下向量中:
[k0m,k1m,...,k9m]
未知的就是中间一位了kXm
我们要变换矩阵变成[10,100]的矩阵,绛紫：k m轮流变换,好像就是传说中的群吧
001,012,...,099
002,013,...,091
003,014,...,092
.....
009,011,...,098
.....
901,912,...,999
902,913,...,991
903,914,...,992
909,911,...,998
然后犯人上场喝掉列向量兑成的酒
最后一个星期的第三天死掉的第几号犯人就确定了kXm中的X.

4 其实5周35天也就一个月多4天，所以，在一个月后等三天就可以测试出毒酒的编号.

[alai]

当然是存在的，而且有很多很多。
我们来写出0~1023的二进制码，即0000000000~1111111111，它们可以被分为512对，每对中的两个二进制互为反码，即0000000000和1111111111一对，0000000001和1111111110一对，等等
只要从这512对中任取500对用作这1000瓶酒的编码，然后让每个囚犯对应这10个二进制位中的一位，分别根据1000个二进制数在同一位的值来决定是否取某一瓶酒来混合。如，如果某个二进制数在第n位为1，则这个数所对应的那瓶酒要取出一点点混合到第n个囚犯准备喝的"鸡尾酒"中。由于这1000个数由500对反码组成，所以每个囚犯恰好都喝到500瓶酒的混合物，每人的中毒概率均为50%。
这类分配方案的数量为512中取500的组合数，即512!/(500!*12!)种，不少吧
而且，这还远不是公平方案的全部。

在 08-4-10，silwile<sil...@gmail.com> 写道：

[陈怀兴]

yep. you are right. ;-)

2008/4/11 alai <ala...@gmail.com>:

[alai]

我们还可以考虑一种"最善良"的方案，即囚犯中毒概率最小的方案。
还是以1000个10位的二进制数表示1000瓶酒，10个囚犯分别代表1个bit。"最善良"的方案其实就是1000个二进制数中，某位为1的总次数最少的那个方案。例如，我们可以先去掉1111111111这个带有10个1的编码，再去掉10个带有9个1的编码，最后再从45个带有8个1的编码中去掉13个，那么我们总共去掉了24个编码，还剩1000个用于对酒瓶进行编码。囚犯中毒的期望值即为1000个编码中1的总数/10000：
(5120-10-10*9-13*8)/10000 = 49.16%
稍低于50%

在 08-4-11，alai<ala...@gmail.com> 写道：

[simore]

5 weeks 应该不是一个重要的条件。
将瓶子编号，1到1000.
从题目来看，犯人有得是（vast dungeons），所以，可以有足够的犯人来试药。
用2分法来划分瓶子，比如从1到500的瓶子各取出1滴，混合后给某个犯人喝（药性够猛，不怕稀释），如果有毒的瓶子在这里面，那么1个月后，他就挂
了。依此类推，由于2^10 = 1024 > 1000，所以，虽然有很多人试药，但是挂掉的no more than 10.
至于时间，所有试药的都在第一天一起喝下去即可，呵呵，都在第30天毒发。

On 4月9日, 下午2时23分, pongba <pon...@gmail.com> wrote:
> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生——从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"——把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

[pongba]

5周"可以"是一个重要的条件，我当时就是用上多余出来的5天的：取一个人，让他第一天喝第一个200瓶，第二天喝第二个200瓶，... 第五天喝第五个200瓶，观察他是在第31到35天的那一天挂，于是就确定毒是在哪一个200瓶。其它就跟kenical的一样了。但windstorm敏锐地发现了这个方案的漏洞：

windstorm wrote:
不对，从题目的意思看，死的时间是不能"精确推算"出来的

不然一个人就可以了，让他不断喝，到时候看具体到某一秒死的

，就能知道什么酒有毒。

2008/4/11 simore <mysi...@gmail.com>:

5 weeks 应该不是一个重要的条件。
将瓶子编号，1到1000.
从题目来看，犯人有得是（vast dungeons），所以，可以有足够的犯人来试药。
用2分法来划分瓶子，比如从1到500的瓶子各取出1滴，混合后给某个犯人喝（药性够猛，不怕稀释），如果有毒的瓶子在这里面，那么1个月后，他就挂
了。依此类推，由于2^10 = 1024 > 1000，所以，虽然有很多人试药，但是挂掉的no more than 10.
至于时间，所有试药的都在第一天一起喝下去即可，呵呵，都在第30天毒发。

On 4月9日, 下午2时23分, pongba <pon...@gmail.com> wrote:

> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[Jicai Ma]

我照着你的方法思考了下，发现还是有问题。
10个人编号0,1,2,....9
             第一天              第二天      第三天
0            0xx                     x0x            xx0
1            1xx                     x1x            xx1
2            2xx                     x2x            xx2
3            3xx                     x3x            xx3
4            4xx                     x4x            xx4
5            5xx                     x5x            xx5
6            6xx                     x6x            xx6
7            7xx                     x7x            xx7
8            8xx                     x8x            xx8
9            9xx                     x9x            xx9

一个月后可能出现的情况：
(1)第一天：m死了，第二天n死了，第三天q死了--->毒酒mnq          720例
(2)第一天：m死了，第二天没人死（m喝了2次毒酒），第三天没人死（m喝了3次毒酒-->毒酒mmm    10例
(3)第一天：m死了，第二天没人死（m喝了2次毒酒），第三天n死了------>毒酒是mmn      90例
问题就出在：
(4)第一天：m死了，第二天n死了，第三天没人死（不能确定是m喝了两次还是n喝了两次毒酒）
       有两种可能：m喝了两次----->毒酒mnm                90例
                                n喝了两次------>毒酒mnn                90例

如果毒酒的编号是(1)(2)(3)中一例的话 3天后就能确定毒酒，但毒酒编号是(4)时就需要犯人多喝一次，等一个月后第四天才能确定毒酒编号。
不知道我分析的对不对，请高人指教

在08-4-11，何源 <he.yuan...@gmail.com> 写道：

[lihuiba]

此乃正解！

On 4月9日, 下午11时11分, "Shao Feng" <sevene...@gmail.com> wrote:
> 人编号为0，1，2，3，4，5，6，7，8，9
> 瓶子编号为1, 2, 3, 4, 5, ..., 999, 1000
>
> 编号为n的人需要喝的瓶子号m是满足下面条件的:
> ((m>>n) & 1) == 1
>
> 一个月后，所有对死人的编号 n1, n2, ..., nk
> pow(2, n1) + pow(2, n2) + ... + pow(2, nk)
> 即是有毒瓶子的编号。

[Marshall]

不用时间的推断也可以算出来，10个囚犯都是在第一天喝的酒。
情况简化一下，有甲乙两个囚犯，甄别ABCD四瓶酒，那解决方案就是：
甲：AB，乙：AC，这样，甲乙都死了，那A有毒，甲死了，已没死，就是B有毒，以此类推
如果是甲乙丙三个囚犯，喝ABCDEFGH八瓶酒，那喝酒方案：
甲：ABCD
乙：ABEF
丙：ADEG
判断方案：
甲乙丙死：A
甲乙：B
甲：C
甲丙：D
乙丙：E
乙：F
丙：G
无：H
其实就先枚举出所有的2^n排列，然后把每个排列的结果与某一瓶酒对应，就可以得出喝酒的方案

2008/4/14 Jicai Ma <ipyt...@gmail.com>:

--
Marshall Wu,
Software Institute, Nanjing University

[何源]

我确实是这个意思。(4)情况的确无法确定啊。谢谢指点。

On 4月14日, 下午11时51分, "Jicai Ma" <ipyth...@gmail.com> wrote:
> 我照着你的方法思考了下，发现还是有问题。
> 10个人编号0,1,2,....9
> 第一天 第二天 第三天
> 0 0xx x0x xx0
> 1 1xx x1x xx1
> 2 2xx x2x xx2
> 3 3xx x3x xx3
> 4 4xx x4x xx4
> 5 5xx x5x xx5
> 6 6xx x6x xx6
> 7 7xx x7x xx7
> 8 8xx x8x xx8
> 9 9xx x9x xx9
>
> 一个月后可能出现的情况：
> (1)第一天：m死了，第二天n死了，第三天q死了--->毒酒mnq 720例
> (2)第一天：m死了，第二天没人死（m喝了2次毒酒），第三天没人死（m喝了3次毒酒-->毒酒mmm 10例
> (3)第一天：m死了，第二天没人死（m喝了2次毒酒），第三天n死了------>毒酒是mmn 90例
> 问题就出在：
> (4)第一天：m死了，第二天n死了，第三天没人死（不能确定是m喝了两次还是n喝了两次毒酒）
> 有两种可能：m喝了两次----->毒酒mnm 90例
> n喝了两次------>毒酒mnn 90例
>
> 如果毒酒的编号是(1)(2)(3)中一例的话 3天后就能确定毒酒，但毒酒编号是(4)时就需要犯人多喝一次，等一个月后第四天才能确定毒酒编号。
> 不知道我分析的对不对，请高人指教
>

> 在08-4-11，何源 <he.yuan.lam...@gmail.com> 写道：

[fenghou]

比较详细的没有知识前提的思考过程，不过还是要知道二进制表示法才行。

1000瓶酒，只有1瓶有毒，稀释无法减弱毒性。人喝下去后一个月才有反应。反应只有两个，中毒或者没中毒。需要在不超过10人中毒（参加测试）的前提下，在5周之内找出有毒的那一瓶酒。

看来所有试验要同时进行才行，一次就要看出结果。那么二分法就无效了。
能否用10个二进制位表示1000个数？可以。所以在理论上这个问题是有解的。
要想用10个二进制位表示1000个数，就必须让每个位都指示不同的事实，通过10个事实的真假来得到一个确定的数。
即要把1-1000分解为10个组，10个组的真假的组合可以指示其中任意一个确定的数。
二进制是怎样做到的？
最低位（第1位）代表该数的奇偶性；最高位（第10位）代表数在前2^9还是后2^9；第2位代表被4除之后的余数是0,1还是2,3；第3位代表被2^3除之后的余数是0,1,2,3还是4,5,6,7；……

因此，10个组可以分出来了：
第1组，奇数瓶混在一起，偶数瓶不管。如果中毒了，表示毒酒在奇数瓶中，没中毒则在偶数瓶。
第2组，先跳过2瓶酒，然后取2瓶酒加进去，然后再跳过2瓶，以此类推，直到取完或跳完。
第3组，先跳过2^2瓶酒，然后取2^2瓶酒加进去，然后再跳过2^2瓶，以此类推，直到取完或跳完。
第10组，先跳过2^9瓶酒，然后取2^9瓶酒加进去，此时已经取完了。

给10个人分别喝下此10组酒，一个月后观察反应，纪录成二进制数，换算成十进制即为结果。

[Justin L]

刚看1000的酒瓶的题目时想到，用信息量的守恒来进行计算，即10个人的不同死法进行排列组合能有多少种情况。理论上，这些情况都可以区分出不同的毒
酒的位置号。（如果编号了的话）
大概10个人的不同死法进行排列组合，其能表达的数早已经超过了1000。
因此打算采取将酒瓶标号，然后这五天死亡的人的模型来表达一个数字，通过数字来确定是第几号酒有毒。
后来打开calc一算，5天时间如果用来表示一个5位的数字，则得出(x为4时)4的5次方为1024。
也就是，用一个5位的四进制数来表示这个模型即可。
也就是说最多4个人，用5天的时间即可以把这个毒酒给测试出来。
测试方法我写到了上面的帖子。

btw:用数学表达式该怎么表达？

[Justin L]

将1000瓶酒按照顺序标上号：1～1000
囚犯A，每天喝200瓶酒，分成5天喝完。
喝法：（相当于把酒分成5大组（200瓶一组）每天喝一大组），此人第几天死就可以确认毒酒是在哪个大组。（精确到200瓶酒内）
第一天：1~200；第二天：201~400；第三天:401~600；第四天601~800，第五天:801~1000

囚犯B，每天喝200瓶酒，分成5天喝完。
喝法：(相当于把5大组，每个组分成5个小组，每天喝按顺序5个大组中的第n个小组)，此人第几天死就可以确认毒酒是在哪个小组。（精确到40瓶酒
内）
第一天：1~40, 201~241, 401~441, 601~641, 801~841
……………………………………
第n-1天:1+n*40~40+n*40, 201+n*40~241+n*40, 401+n*40~441+n*40,
601+n*40~641+n*40, 801+n*40~841+n*40

囚犯C，每天同样和200瓶酒，5天喝完。
喝法：在5个小组中又分出5个最小组（每组8瓶酒）每天喝所有小组中的第n个最小组。此人第几天死就可以确认毒酒是在哪个最小组中。（精确到8瓶酒
内）
剩下的7个囚犯，每天跟囚犯C同样的喝法。（最小组中有8瓶酒，7个人喝掉其中的7瓶，按顺序，例如7个人喝1-7号酒，而第8瓶酒留下来不喝）（这样
剩下七个人的死法，可以确定8瓶酒内具体的有毒的情况）

例如：
囚犯A在第二天就死掉了（从总的5个星期中的第31天算起，算作第一天），则说明毒酒在第二个大组中——201～400号酒中
囚犯B在第三天死掉了，则说明毒酒在（第二个大组的）第三个小组中——283～323号酒中
囚犯C在第四天死掉了，则说明毒酒在（第二个大组，第三个小组的）第四个最小组中——346～357号酒中（如果我没数错的话）
再通过剩下7个囚犯的情况，可以知道上面8瓶酒中，几号酒有毒。

[Justin L]

晚上回家看了一下自己发的帖子，和最后给出的解答有点出入。当时灵感确实是这么想起来的，但是实际解答不是这样的：

我的解答中，这个数字模型：
5位的四进制数，表示5个人，5天时间即可确定1024瓶酒。
0～4这五个数字，代表五天，五位数，每个位代表一个人。

现在就是要观察每个位上的数字是多少（从0到4）。
例如：43210
代表第一个人活了4天，第二个活了3天……

[怀宇范]

回复太多看不动了。。。不知道有没有人给正解。。。说说我的想法。。。

把酒排序对应着1～1000.然后让不同的人从不同的开始时间开始喝酒，每个人死得时间组合起来也就成了一个二进制数。喝的酒是混的，如果酒的编号的二进制数对应到那个人的开始位置为1，则混这种酒。如提示2^10 > 1000，得解。。。

只是这要求，这毒药死亡时间比较精准，半天之内不会乱序。。。

2008/4/9 pongba <pon...@gmail.com>:

波利亚的《How To Solve It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。

我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。

题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。

我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。

我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。

要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

从一道题目中获得最多的东西，这是做题的目的。

你有没有这样的经历，一道题目你做不出来，你拿去问某个人，某个人想了一会儿，然后指出某个关键的step，于是一切豁然开朗。

但这不是全部！

如果你继续问他是怎么想到的，经验告诉我，几乎所有的可能性都指向一个答案"我也不清楚"。

为什么？根据我自己的经验，我相信是因为绝大多数人都没有仔细反省自己思考的过程。如果想不出来，拉倒。如果想出来了，万事大吉。但波利亚在《How to Solve it》中说到，他在教学的过程中总是碰到这样的问题"你是怎么想到的"？这个问题促使了他去总结思维的规律，有了这些规律，即使不那么富有灵感的人，也可以运用这些规律，让自己的思维的触角能够伸展开去。

答案不重要，如果你直接告诉我关键的一步，我什么也没有得到。甚至就算我自己想出了最关键的一步，也许我还是什么都没得到。因为这样的经验只能极其有限地对我下一次的问题产生帮助；除非我能进一步思考思维背后的规则。

所以，重要的是思考的过程，不管这个过程是不是带领你得到答案。我相信只有最深刻了解了思考的真正过程，才能够从做题中获得最多的东西。

如果你对以往做题的思路有很好的思考，也欢迎和大家分享～

1000瓶葡萄酒的问题：
题目来自：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
友情感谢silwile同学提供地址，伯克利的这帮家伙的确很生猛～里面的题目几乎都很有价值。

An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

今天，我们思考。

--

刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo(" fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[alai]

正解早就出来了，翻翻看吧，你的解法是不对的，前面的帖子也已经对此有解释。

在 08-4-25，怀宇范<dugu...@gmail.com> 写道：

[dailiangren]

我觉得这个问题可以从简单情形入手。不过，我总觉得这个问题肯定可以从编码的角度给一个完美完整的解释。

假如只有四瓶的话，则只要两个人，第一个人喝1，2瓶，第二个人喝2，3瓶。根据第一个，第二个人的生死情况，可以如下推理：
（第一个人用一简称，第二个人用二简称）
一活，二活： 第四瓶为毒酒；
一死，二活： 第一瓶为毒酒；
一死，二死： 第二瓶为毒酒；
一活，二死： 第三瓶为毒酒。

下面由此递推有8个人的情形。如此分配：第一个人喝1，2，3，4瓶，第二个人喝1，2，5，6瓶，第三个人喝2，3，6，7瓶。根据三个人的生死情
况，作如下推理：
一活，二活，三活：第八瓶为毒酒；
一活，二活，三死：第七瓶为毒酒；
一活，二死，三活：第五瓶为毒酒；
一活，二死，三死：第六瓶为毒酒；
一死，二活，三活：第四瓶为毒酒；
一死，二活，三死：第三瓶为毒酒；
一死，二死，三活：第一瓶为毒酒；
一死，二死，三死：第二瓶为毒酒。

如果为16瓶时，只需要四个人，其中第一个人喝1~8瓶，其他的和8瓶时一样。

如此可以递推到2^n时的情形。

On Apr 9, 2:23 pm, pongba <pon...@gmail.com> wrote:
> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生——从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"——把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

[duoduolo]

dailiangren wrote:

我觉得这个问题可以从简单情形入手。不过，我总觉得这个问题肯定可以从编码的角度给一个完美完整的解释。

假如只有四瓶的话，则只要两个人，第一个人喝1，2瓶，第二个人喝2，3瓶。根据第一个，第二个人的生死情况，可以如下推理：
（第一个人用一简称，第二个人用二简称）
一活，二活： 第四瓶为毒酒；
一死，二活： 第一瓶为毒酒；
一死，二死： 第二瓶为毒酒；
一活，二死： 第三瓶为毒酒。

下面由此递推有8个人的情形。如此分配：第一个人喝1，2，3，4瓶，第二个人喝1，2，5，6瓶，第三个人喝2，3，6，7瓶。根据三个人的生死情
况，作如下推理：
一活，二活，三活：第八瓶为毒酒；
一活，二活，三死：第七瓶为毒酒；
一活，二死，三活：第五瓶为毒酒；
一活，二死，三死：第六瓶为毒酒；
一死，二活，三活：第四瓶为毒酒；
一死，二活，三死：第三瓶为毒酒；
一死，二死，三活：第一瓶为毒酒；
一死，二死，三死：第二瓶为毒酒。

如果为16瓶时，只需要四个人，其中第一个人喝1~8瓶，其他的和8瓶时一样。

如此可以递推到2^n时的情形。



On Apr 9, 2:23 pm, pongba <pon...@gmail.com> wrote:
  

波利亚的《How To Solve
It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。

我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。

题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。

我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。

我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。

要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

从一道题目中获得最多的东西，这是做题的目的。

你有没有这样的经历，一道题目你做不出来，你拿去问某个人，某个人想了一会儿，然后指出某个关键的step，于是一切豁然开朗。

但这不是全部！

如果你继续问他是怎么想到的，经验告诉我，几乎所有的可能性都指向一个答案"我也不清楚"。

为什么？根据我自己的经验，我相信是因为绝大多数人都没有仔细反省自己思考的过程。如果想不出来，拉倒。如果想出来了，万事大吉。但波利亚在《How to
Solve
it》中说到，他在教学的过程中总是碰到这样的问题"你是怎么想到的"？这个问题促使了他去总结思维的规律，有了这些规律，即使不那么富有灵感的人，也可以运用这些规律，让自己的思维的触角能够伸展开去。

答案不重要，如果你直接告诉我关键的一步，我什么也没有得到。甚至就算我自己想出了最关键的一步，也许我还是什么都没得到。因为这样的经验只能极其有限地对我下一次的问题产生帮助；除非我能进一步思考思维背后的规则。

所以，重要的是思考的过程，不管这个过程是不是带领你得到答案。我相信只有最深刻了解了思考的真正过程，才能够从做题中获得最多的东西。

如果你对以往做题的思路有很好的思考，也欢迎和大家分享～

1000瓶葡萄酒的问题：
题目来自：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

显然，毒酒出现的情况有1000种可能，而十个人，没一个有中毒不中毒两个状态，可以表示1024种情况，所以这个题一定有解。
具体解法如下：
第一个人喝前500瓶，将1000瓶酒分成两种
第二个人喝两份酒中的前250瓶，将1000瓶酒分成四组
按此类推（不能被二整除时取中点附近的数），十个人足够把这酒分成1000组
他应该能在3个周以后喝到the rest吧，

[Gohan]

这样应该能对吧

[Gohan]

可以用排列数加和来解答，进而编程输出结果
10个人
c(10,10)+c(9,10)+c(8,10)+...+c(0,10)
c(x,y)是排列数
c(10,10)=1 一号酒，给十个人都喝
c(9,10)=10 二号到11号10瓶酒，从十个人中取九个的10种情况喝其中之一
...
最后可根据人死情况进行判断是哪一瓶酒
应该算组合数学的问题
10个人应该能够鉴别1024瓶酒

[王良晶]

这个不是某年smth上十大的贴子吗?


pongba wrote:
> �����ǵġ�How To Solve
> It��������һ���½��г���һ��ѵ�Heuristics���������Ʃ�����Ŀ���������������������ȡ����ܷ��ӵ�ʲô��������ܷ��޸�ʲô�����ʱ��ע��δ֪ ...�ȵȡ�
>
> ����һ�������ν����У�����һ������Ĺ�����Ȼ��з�������ʶ���棨�ο���׷Ѱ����ĺۼ��������¶��Լ���̬�ȸı������Ӱ�졷����Ͷȣ���"���´̼�"�½ڣ��������޷������֮ǰ������ʶ�����쵽��е���Ĺ�̣�Ȼ�����ǵ�ȷ��������з���֮��ͨ��ع˺ͺ��������ܽ�����п��ܵ�˼·����ѧ�ķ�չij����������ľ�������һ�����飬�������ص����?����ѧ�����IJ���������ۡ���ʽ�߼�����ѧ���ɷ�����ȡ�������Щһ��˼ά���򵽸���ԭ�?��ֵԭ�?̰7ԭ���������ض������ԭ�?��һ���Ƕ�˼ά��̵��º��ܽ�����?Ʃ���Ҿ����ʽ�߼����������º������4��˼ά������������������ʶ����;���������f���μ�Ƥ�ǽܵ���֪��չԭ�?������Ҳ�?��Ȼ���Ǹ�ֲ�ڴ�������ĸ���һ����Щ�����ǽ��4�ģ���������ʶ����ܹ���w���á�Ȼ��Ҫ�������ǵõ���չ������������ʽ����ֽ�ϣ���Ϊ�κ��˶��ܲ���ķ����ۣ�����Ҫ��ʶ�IJ��롣
>
> �췢�����ϵ��"��������˼��"����4����д"������������"�����뵽������۵�Ŀ����ʵ��˼��������ˣ�����Ҷ����Լ���Ϊ��ʵ���Ŀ����4������ʱ�����[��������˼��<���>]�����Ժ����������һ����һ�������ڼ����Ƿdz���������顣
>
> ��Ŀδ��Ҫ�£��ҵ��뷨�ǹؼ���Ҫ���䣬���ϵ�еĹؼ�����Ҫ���������˼·��������Ŀ���?����ȫ����Ŀ�ģ�����ò���𰸵�˼·Ҳ�кܴ�ļ�ֵ��������뵽��һЩ˼·��������ȥ��𰸻������Զ��û���κι�ϵ������4��Ҳ��Ա��˵�˼·�кܴ��������һ���ʼ��б��ڵ�ͷ�Է籩��������뵽�˴𰸣������ܹ��ܽ���Լ�˼·�еĹؼ���������ô�뵽�ģ��������Ҷ��������dz��
>
> �������⡢���⡢���⣬������Ϊ������w��Ψһ�취�������⣬��Ϊֻ����ͷ������ܹ������f����Ȼ��wϰ�DZ�Ҫ���������Щwϰ����һЩwϰ����Ч��
>
> ���ǿ�˼ڤ�룬��ij��˲��õ���У����ǻ���ȸԾ������ʱ������ƣ���������ʱ��Ҳ���Խ4Խ�࣬����������Ϊ���������Ч��wϰ�������Ҳ���ô��Ϊ���Ҿ����Ŀ�����˼ά�������ͨ�ģ�ͨ��һ�δεĵȴ����4wϰ���DZ����ġ�����г���֮���ܽ�Ϊʲô��л���֣����������ʲô���˼ά���򣬿����ܷ񷺻���һ����Ŀ����������°빦���ķ�������Ϊ���ǵ���ʶ�����޷���쵽����ʶ����������߼�����������ֻ�ܾ������Ϊ������һ�δν��������������ʶ�������Ԫ�õ���v֮�������Ȼ������ij���ȴ����������۵㣬��ν�����ʵ����"ԭ������������ʶ����""��4����ʽ�������4����������ʶ4ָ���ķ���"���ܽ����˼ά�ķ��������´α��п��ܲ��þ���صȴ������ŵ���е����֣����ǿ���ϵͳ���س��Ը��ֿ��е��ַ���������ˡ�
>
> Ҫʵ�����Ŀ�ģ����ܽ��Լ�����б����˼ά������Ϊһ���ԵĽ���˼·��������Ϊһ�ַ����ǿ�ȡ�ģ�����ν��"�����ŵ�˼��"���������˼�������ϸ��д��ֽ�ϡ��˵���ʶ�����ҹ��ĵƹ⣬ֻ������һ���С�ľֲ������д��4��˼ά�ĵƹ��������޵ģ��п����ߵ��������ǰ�棬Ҳ�п��ܸɴ��û������˼����д��4�����Ա���������⣬˼ά�Ϳ��������ߣ��Ϳ����յ�Խ4Խ��ĵط������⣬д��4���ܹ�ʹ���Լ��ܹ��ع�ͷ4�����Լ������˼����̣�Ҳ��ǰ��ij��ʱ�����뵽һ�����������4��ͺܿ����ˣ������4��ͷһ��Ҳ�������кܴ�����Ҳ�?����˼ά��ijһ����������������һ���뵱Ȼ�ļ��裬�Ӷ������˼ά���Ƶ����壬ͨ��д��4���Ϳ���һ���̶��ϱ�����������塣
>
> ��һ����Ŀ�л�����Ķ������������Ŀ�ġ�
>
> ����û������ľ���һ����Ŀ�����4������ȥ��ij���ˣ�ij��������һ���Ȼ��ָ��ij��ؼ��step������һ�л�Ȼ���ʡ�
>
> ���ⲻ��ȫ����
>
> ����������������ô�뵽�ģ���������ң��������еĿ����Զ�ָ��һ���"��Ҳ�����"��
>
> Ϊʲô��������Լ��ľ��飬����������Ϊ�������˶�û����ϸ��ʡ�Լ�˼���Ĺ�̡�����벻��4��-����������4�ˣ����´󼪡����������ڡ�How to
> Solve
> it����˵�������ڽ�ѧ�Ĺ�������������������"������ô�뵽��"����������ʹ����ȥ�ܽ�˼ά�Ĺ��ɣ�������Щ���ɣ���ʹ����ô������е��ˣ�Ҳ����������Щ���ɣ����Լ���˼ά�Ĵ����ܹ���չ��ȥ��
>
> �𰸲���Ҫ�������ֱ�Ӹ����ҹؼ��һ������ʲôҲû�еõ������~������Լ��������ؼ��һ����Ҳ���һ���ʲô��û�õ�����Ϊ����ľ���ֻ�ܼ������޵ض�����һ�ε����������������ܽ�һ��˼��˼ά����Ĺ���
>
> ���ԣ���Ҫ����˼���Ĺ�̣�����������Dz��Ǵ�����õ��𰸡�������ֻ��������˽���˼���������̣����ܹ��������л�����Ķ���
>
> ���������������˼·�кܺõ�˼����Ҳ��ӭ�ʹ�ҷ��?
>
> 1000ƿ���ѾƵ����⣺
> ��Ŀ4�ԣ�http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
> �����лsilwileͬѧ�ṩ��ַ������������һ��ȷ�����͡��������Ŀ������м�ֵ��

>
> An evil king has 1000 bottles of wine. A neighboring queen plots to kill the
> bad king, and sends a servant to poison the wine. The king's guards catch
> the servant after he has only poisoned one bottle. The guards don't know
> which bottle was poisoned, but they do know that the poison is so potent
> that even if it was diluted 1,000,000 times, it would still be fatal.
> Furthermore, the effects of the poison take one month to surface. The king
> decides he will get some of his prisoners in his vast dungeons to drink the
> wine. Rather than using 1000 prisoners each assigned to a particular bottle,
> this king knows that he needs to murder no more than 10 prisoners to figure
> out what bottle is poisoned, and will still be able to drink the rest of the
> wine in 5 weeks time. How does he pull this off?
>

> ���죬����˼����
>
> --
> ��δ��(pongba)|C++���޸���

[王良晶]

[JeanvaHe]

总结下我的思考过程
思考1：
条件中一个月后毒发，5个星期后可以饮用。具有时间上的关联。
条件中1000瓶酒，一瓶有毒，不超过10个犯人来试酒，具有数目上的关联。
1 2 3 "4" 5 6 7 8 9 ... 999 1000
poisonous
理解问题：
如果找1000个人来试酒，那么一个月后知道那瓶是毒酒。
如果找999个人来试酒，那么一个月后知道那瓶是毒酒。
因为每一瓶酒都有可能是毒酒，那么方法要保证每一瓶酒都被测试到，必然有一个犯人是喝很多杯酒。
这几个数字联想到 2^10=1024>1000 种结果，而一瓶酒有毒就对应一种结果，这样10和1000就对上了。(这里的思路如果能够把规模缩小
为2,4，即2个人能否识别出4瓶中的一瓶毒酒，则思路立刻出来。)
能不能把10个犯人排成一排，看做一个0和1的二进制数。0 和 1 分别表示什么？
把酒分成10份
1...100 101...200 201...300 ... 901...1000
（1） （2） （3）
10个人喝，每个人都喝几份，可能有多个人中毒。比如1号犯人喝了（1）（2），2号犯人喝了（2）（3）如果（2）中有毒酒，那么1号和2号多将中
毒。
中毒与不中毒可以成为犯人的标记来表示二进制数了。
可以想象：中 否 中 否 .... => "4" 有毒，一共有1024种情况。


思考2：
5个星期与一个月相差一个星期有什么用处？
因为5个星期末的时候有一批人的毒性开始发作，而他们应该是开始一个星期后服用的，为什么要推迟一个星期？这样的作用是相当于增加了人数。
如果（2）中有毒酒，1号犯人开始喝了（1），一星期后喝了（2），最后5星期后死亡，说明（2）中有毒酒，如果4星期后死亡，说明（1）中有毒酒。
这样的话，如果毒发是精确到1个月发作，那么每个犯人分配100瓶，在一个星期里把100瓶酒分开时段喝，则根据什么时候毒发就知道哪一瓶有毒了。
在这里题目应该没有那么简单，假定隔开一个星期才能区别毒发的是哪一瓶，这样我们只需要解决500瓶葡萄酒的问题。（这里思路有些问题，如果最开始的毒
酒在4星期末至5星期初发作，那么1星期开始喝得毒酒将在5星期末到6星期初发作，所以我们还是要解决1000瓶的问题）

思考3：
延续思考1，假如是这样子
第一人喝：1 3
第二人喝： 2 4
第三人喝：1 4
即第一个人喝了1，3瓶，第二个人喝了2，4瓶，第三个人喝了1，4瓶，那么哪个瓶有毒得出的死亡结果都不同，如3有毒，则只有1号死，如4有毒，则2
号，3号死。可以看出，第"4"瓶毒酒对应的二进制为：否 中 中 否 否.....
1 3 5
2 4 5
1 4
加入5依然可以辨别出来。一种死亡组合对应一瓶毒酒，加入组合相同，那么就无法判别是哪一瓶有毒，从10个人里面选所有组合，即2^10种死法。任意放
置1000种不同的组合就可能得出1000种中毒的方法，查表即可得到哪一瓶有毒，所以可以得出方法了。

其他人的点子：
（1）二分法（忽略了药性发作需要时间）
将1000瓶分成两组500瓶，混合成两瓶，给两囚犯喝，毒死一人，便知道毒酒在哪个500瓶中
以2为底的1000的对数为10，10人即可。
（2）分组法（忽略了药性发作时间不会精确）
即假设有A、B、C三个人，1000桶酒编号为1~1000；
A喝了1~500的酒，
B喝了1~250、501~750的酒，
C喝了1~125、251~375、501~625、751~875的酒。
这样，如果A中毒了，确定毒在1~500，反之在501~1000，这里假设为在1~500；
如果B中毒了，由于先前A中毒了，所以毒在1~250；
如果C中毒了，由于A与B都中毒了，所以毒在1~125；
如编号 0 1 2 3 4 5 6 7
A B C 三个人
A 吃 4 5 6 7
B 吃 2 3 6 7
C 吃 1 3 5 7
三个人的8种组合，分别对应8组
（3）位数法（忽视人死不复生）
假设酒桶编号为000-999，囚犯编号为0-9。第一天，第n位囚犯喝的是编号为nxx的酒，x为0-9；第二天，第n位囚犯喝的是编号为xnx-的
酒；第三天，第n位囚犯喝的是编号为xxn的酒。假定编号010的酒有毒，结果是一个月后的第一天，0号囚犯毒发，第二天1号囚犯毒发，但是第三天没有
人再毒-发。你只能判定有毒的酒桶编号前两位是0和1，无法判定最后一位是0还是1，即010号和011号酒都可能有毒。如果是第二天没有人毒发，则还
好办，可以肯定毒-酒编号的前两位相同。但如果是第三天才出现没有人毒发，问题就大了。
（4）具体的编码方式

人编号为0，1，2，3，4，5，6，7，8，9 瓶子编号为1, 2, 3, 4, 5, ..., 999, 1000
编号为n的人需要喝的瓶子号m是满足下面条件的: ((m>>n) & 1) == 1

一个月后，所有对死人的编号 n1, n2, ..., nk 毒瓶子的编号为pow(2, n1) + pow(2, n2) + ... +
pow(2, nk)

[dailiangren]

好，有启发

 

---

dailiangren

2008-05-08

---

发件人： JeanvaHe

发送时间： 2008-05-08 00:23:31

收件人： TopLanguage

抄送：

主题： [TopLanguage] Re: 1000瓶葡萄酒的问题

[Leo]

讨论来的一个有趣的想法，把1到10个人，按照二进制位数排列，2的10次方是1024.然后，把酒的排列数化为2进制数，按照人数排列的顺序喝下酒，
比如第一瓶酒的二进制数是1，给第一个人喝下，第二瓶酒是10，给第二个人喝下，第三瓶酒是11，给第一个和第二个人喝下，一个月后死了多少人，那么这
些人的二进制排列数就是毒酒的序号。

On Apr 9, 3:23 pm, pongba <pon...@gmail.com> wrote:
> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生----从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"----把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

>
> 从一道题目中获得最多的东西，这是做题的目的。
>
> 你有没有这样的经历，一道题目你做不出来，你拿去问某个人，某个人想了一会儿，然后指出某个关键的step，于是一切豁然开朗。
>
> 但这不是全部！
>
> 如果你继续问他是怎么想到的，经验告诉我，几乎所有的可能性都指向一个答案"我也不清楚"。
>
> 为什么？根据我自己的经验，我相信是因为绝大多数人都没有仔细反省自己思考的过程。如果想不出来，拉倒。如果想出来了，万事大吉。但波利亚在《How to
> Solve
> it》中说到，他在教学的过程中总是碰到这样的问题"你是怎么想到的"？这个问题促使了他去总结思维的规律，有了这些规律，即使不那么富有灵感的人，也可以运用这些规律，让自己的思维的触角能够伸展开去。
>
> 答案不重要，如果你直接告诉我关键的一步，我什么也没有得到。甚至就算我自己想出了最关键的一步，也许我还是什么都没得到。因为这样的经验只能极其有限地对我下一次的问题产生帮助；除非我能进一步思考思维背后的规则。
>
> 所以，重要的是思考的过程，不管这个过程是不是带领你得到答案。我相信只有最深刻了解了思考的真正过程，才能够从做题中获得最多的东西。
>
> 如果你对以往做题的思路有很好的思考，也欢迎和大家分享～
>
> 1000瓶葡萄酒的问题：
> 题目来自：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
> 友情感谢silwile同学提供地址，伯克利的这帮家伙的确很生猛～里面的题目几乎都很有价值。
>

> An evil king has 1000 bottles of wine. A neighboring queen plots to kill the
> bad king, and sends a servant to poison the wine. The king's guards catch
> the servant after he has only poisoned one bottle. The guards don't know
> which bottle was poisoned, but they do know that the poison is so potent
> that even if it was diluted 1,000,000 times, it would still be fatal.
> Furthermore, the effects of the poison take one month to surface. The king
> decides he will get some of his prisoners in his vast dungeons to drink the
> wine. Rather than using 1000 prisoners each assigned to a particular bottle,
> this king knows that he needs to murder no more than 10 prisoners to figure
> out what bottle is poisoned, and will still be able to drink the rest of the
> wine in 5 weeks time. How does he pull this off?
>

[pongba]

2008/5/14 Leo <firem...@gmail.com>:

讨论来的一个有趣的想法，把1到10个人，按照二进制位数排列，2的10次方是1024.然后，把酒的排列数化为2进制数，按照人数排列的顺序喝下酒，
比如第一瓶酒的二进制数是1，给第一个人喝下，第二瓶酒是10，给第二个人喝下，第三瓶酒是11，给第一个和第二个人喝下，一个月后死了多少人，那么这
些人的二进制排列数就是毒酒的序号。

这个是标准答案:-)
见上面的讨论:)

--
刘未鹏(pongba)|C++的罗浮宫

[foxki...@gmail.com]

受到提示与二分法的启发，问题在于我们时间不够，那么需要妥善选择酒的混合方案（联想到了天平称球问题）让问题在一次性的尝试下解决

首先，解决4瓶酒2人的问题
对酒编号0,1,2,3
是用鸡尾酒1号和2号
used wine : 0 1 2 3
cocktail 1 : 0 0 1 1
cocktail 2 : 0 1 0 1
0表示cocktail中不含该瓶酒
1表示cocktail中含有该瓶酒
那么有四种情况：
cocktail 1 2
fatal 0 0 -> poisoned : 0 (说明1100 和 1010组合是有毒的，0号酒都是1，则该瓶
酒有毒）
0 1 -〉--------------- 1 (1100 and 0101)
1 0 -〉--------------- 2 (0011 and 1010)
1 1 -〉----------------3 (0011 and 0101)
我们又注意到
0，1，2，3的二进制分别为
00，01，10，11

于是得到解答：
对于0..1023号酒（其中1000..1023号酒为幻想虚构，无伤大雅）
我们是用一下鸡尾酒：
c0: 512..1023的混合物
c1: 256..511, 768..1023混合物
c2: 128..255, 384..511, 640..767, 896..1023的混合物
...
c(i): 混合物（2^(9-i)*k .. 2^(9-i)*(k+1)-1) k=1,3,5,7,...,2^(i+1)-1 的混合物
...
c(9): 1,3,5,7,9,...,1023的混合物

每种鸡尾酒为512种酒的混合物
我们假设，c(i)=0 表示 i 号鸡尾酒不能毒死人
1 表示 i 号鸡尾酒能毒死人
那么我们要找的酒就是
(c0,c1,c2,...,c9)代表的二进制数
也就是说
第sum(c(k)*2^(9-k),k=0..9)酒是有毒的

问题解决
严格的证明还是可行的，可惜身边没纸笔

On Apr 9, 2:23 pm, pongba <pon...@gmail.com> wrote:
> 波利亚的《How To Solve
> It》里面有一个章节列出了一大堆的Heuristics（启发法），譬如把题目泛化、考察问题的特例、类比、看能否扔掉什么条件、看能否修改什么条件、时刻注意未知量...等等。
>

> 我有一个信念，所谓的灵感，背后一定有它的规则，虽然灵感发自无意识层面（参考《追寻记忆的痕迹》（坎德尔），以及《态度改变与社会影响》（津巴度）的"阈下刺激"章节），我们无法在灵感之前就在意识层面觉察到灵感诞生的过程，然而我们的确可以在灵感发生之后通过回顾和合情推理总结出最有可能的思路，数学的发展某种意义上做的就是这样一件事情，从最朴素的推理，到数学方法的产生——从三段论、形式逻辑、数学归纳法、类比、分治这些一般思维规则到鸽笼原理、极值原理、贪婪原理这类解决特定问题的原理，无一不是对思维过程的事后总结和整理。譬如我觉得形式逻辑就是最大的事后整理出来的思维法则，人类天生在无意识层面就具有推理能力（参见皮亚杰的认知发展原理），就像（也许）自然数是根植在大脑里面的概念一样，这些概念是进化出来的，我们无意识间就能够熟练运用。然而，要想让它们得到发展、生长，乃至能形式化到纸上，成为任何人都能操作的方法论，则需要意识的参与。

>
> 遂发起这个系列"今天我们思考"（本来是想写"今天我们做题"，但想到这个讨论的目的其实是思考，遂改了），大家都把自己认为最精彩的题目发上来（发的时候加上[今天我们思考<编号>]便于以后搜索），我想一定是一件于人于己都是非常有益的事情。
>
> 题目未必要新，我的想法是关键是要经典，这个系列的关键是想要讨论做题的思路，而绝非题目本身，答案完全不是目的，就算得不出答案的思路也有很大的价值。如果你想到了一些思路，但看上去离答案还相差甚远，没有任何关系，贴上来，也许对别人的思路有很大启发。这是一个邮件列表内的头脑风暴。如果你想到了答案，并且能够总结出自己思路中的关键法则（你是怎么想到的），我想大家都会受益匪浅。
>
> 我们做题、做题、做题，往往认为到达熟练的唯一办法就是做题，认为只有埋头做题才能够提高能力。诚然，练习是必要条件。但有些练习比另一些练习更有效。
>
> 我们苦思冥想，在某个瞬间得到灵感，于是欢呼雀跃，随着时间的推移，这样的灵感时刻也许会越来越多，于是我们认为这就是最有效的练习方法。我不这么认为，我觉得题目背后的思维大抵是相通的，通过一次次的等待灵感来练习，是被动的。在灵感出现之后总结为什么灵感会出现，背后可能有什么样的思维法则，看看能否泛化到一类题目，这样才是事半功倍的方法。因为我们的意识层面无法觉察到无意识层面的推理逻辑，所以人们只能绝望地认为除了在一次次解题中让你的无意识层面的神经元得到锻炼之外别无它法。然而启发法的出现却正打破了这个观点，所谓启发法其实就是"原本被我们无意识运用""后来被形式化地提出来，可以由意识来指导的方法"。总结出了思维的法则，我们下次便有可能不用绝望地等待摸不着的灵感的闪现，而是可以系统化地尝试各种可行的手法（启发法）了。
>

> 要实现这个目的（即总结自己的灵感背后的思维规则进而泛化为一般性的解题思路），我认为一种方法是可取的，即所谓的"看得着的思考"——把你的思考过程详细的写在纸上。人的意识就像黑夜里的灯光，只能照亮一个很小的局部，如果不写下来，思维的灯光总是有限的，有可能走到后面忘掉前面，也有可能干脆就没法往下思考。写下来，可以避免这个问题，思维就可以往下走，就可以照到越来越多的地方。此外，写下来还能够使得自己能够回过头来检视自己的整个思考过程，也许前面某个时候你想到一个东西，但如果不记下来你就很快忘了，而记下来回头一看也许你又有很大的启发。也许，你在思维的某一个环节上无意间引入了一个想当然的假设，从而掉入了思维定势的陷阱，通过写下来，就可以一定程度上避免这样的陷阱。

[ordie]

On 4月10日, 下午12时14分, kenical <keni...@126.com> wrote:
> 那就这样子：用2的10次方推算出1024>1000的方法。
> 用4个人模拟16桶酒中有一桶有毒的情况。
> 1、为16桶酒编号为1~16。4个人编号为A、B、C、D；
> 2、把16桶酒分成两组，让A喝下第一组，即1~8；
> 3、把每一组的8桶分成两组，每组4桶，即1~4为一组，5~8为一组，9~12为一组，12~16为一组；让B喝下第一组（1~4）和第三组
> （9~12）；
> 4、同样把上面的每一组分成两组，每组2桶，让C喝下1、3、5、7四组。
> 5、剩下的还是把上面的每一组分成两组，每组1桶，让D喝下1、3、5、7、9、11、13、15八组。
> 6、这样就可能根据ABCD四个的置位算出哪一桶有毒。1000桶酒10个人的推理也类似。

>
> On 4月10日, 上午11时39分, windstorm <likunarmstr...@gmail.com> wrote:
>
>
>
> > 不对，从题目的意思看，死的时间是不能"精确推算"出来的
>
> > 不然一个人就可以了，让他不断喝，到时候看具体到某一秒死的，就能知道什么酒有毒。
>

> > --
> > web:http://www.forwind.cn
> > msn: likunarmstrong at hotmail.com- 隐藏被引用文字 -
>
> - 显示引用的文字 -

我觉得 kenical 的想法是对的，只不过用10进制说起来太麻烦，用二进制的方式说起来更简单一点:
1 一共1000瓶酒，编号0-999，二进制表示就是从0000000000到1111100111（10位二进制数）
2 一共10个犯人，编号1-10。
3 第1天，让1号犯人把所有编号为1xxxxxxxxx（二进制）的酒都尝一下，或者说把所有编号为1xxxxxxxxx（二进制）的酒每瓶取出一点
混在一起让他喝。
4 第2天，让2号犯人把所有编号为x1xxxxxxxx（二进制）的酒都尝一下。
5 ...以此类推
6 第10天，让9号犯人把所有编号为xxxxxxxxx1的酒都尝一下。
7 一个月后的第1天，如果1号死了，说明有毒的酒的二进制编号，第1位是1，否则第1位0
8 一个月后的第2天，如果2号死了，说明有毒的酒的二进制编号，第2位是1，否则第2位0
9 ...以此类推
10 一个月后的第10天，即可确定所有的位，总天数为40天，不超过题目限制

[justthegame]

对这1000个葡萄酒2进制编号，那么最多需要10位，
拿出第1位编号是1的葡萄酒混合给第一个罪犯喝，
拿出第2位编号是1的葡萄酒混合给第二个罪犯喝，
拿出第3位编号是1的葡萄酒混合给第三个罪犯喝，
。。。。。
拿出第10位编号是1的葡萄酒混合给第十个罪犯喝，
一个月后观察10个罪犯的生死（有点残忍），生的罪犯处标上0，死的罪犯处标上1，得到的二进制序列就是那个
毒酒的编号