※ 引述《andan (我从你的眼睛看出来楼~)》之铭言： : ※ 引述《kimjay (kim)》之铭言： : : 题目怎样我有点忘了 : : 内容大概如下 : : 有一位皇帝要十天後要宴客 : : 有1000瓶酒 : : 其中一瓶酒是有毒的 : : 喝下去後十天後会毒发身亡 : : 请问要如何利用十位罪犯来找出这一瓶有毒的酒 : 这类问题还有好几种变型 : 例如: : 1. 12瓶酒其中2瓶有毒 : 2. 12瓶酒其中1瓶有毒,1瓶是解药 : 3. 12瓶酒其中1瓶有毒, : 罪犯里面有一个人是郭靖乔装(百毒不侵) : 请问10个罪犯够吗? : 有办法同时找到毒酒,解药,跟郭靖吗? 要讲变型题目之前 我先从原始题目开始会比较好了解 原始题目(缩小版)是这样子的 有一位皇帝十天後要宴客，酒窖里面有12瓶酒， 其中1瓶是毒酒，喝了之後十天会毒发身亡。 请问要利用几名罪犯才能找出毒酒? 解答: 四名罪犯就足够了 010101010101 --->表示第一名罪犯喝下编号 2,4,6,8,10,12的酒 001100110011 我们会一直用0-1矩阵来表示罪犯跟酒的关系 000011110000 000000001111 仔细观察就可以知道，上面不管哪瓶酒有毒，死掉的罪犯都不会相同! 这表示我们可以从十天後死掉的罪犯，来得知哪瓶酒有毒! 例如:死的人就只有二号罪犯的话，那我们知道第3瓶酒有毒。 以下我们来看其他变型题目 变型1: １２瓶酒之中，有２瓶毒酒。 解答：可以！ 　　　　　　１１１１００００００００　　左边矩阵可以观察出 　　１０００００１１０１００　　1) 任意一瓶酒都有三个罪犯喝 　　１００００１００００１１　　2) 任意两瓶酒最多只会同时给一个罪犯喝 　　００１０１１０１００００　　由此可知　如果x不是毒酒的话 　　　　 　　０１０００００１１０１０　　至少会有一名罪犯喝了x这瓶酒 　　０００１０１１０１０００　　而且他又没喝到这两瓶毒酒 　　００１０００００１１０１　　 　　０１００１０１００００１　　所以，只要看没死的人喝了哪些酒， 　　０００１１００００１１０　　就知道哪些酒是没有毒的！ 　　　　 变型2： 　　１２瓶酒之中，有１瓶毒酒；１０大罪犯中，有１个是郭靖(百毒不侵)。 解答；没办法保证能同时找到！！ 　　解法同上个矩阵！ 　　如果x不是毒酒的话，至少会有两名罪犯喝了x这瓶酒但没死。 　　而如果x是毒酒的话，最多只会有一名罪犯喝了它却没事！ 　　 　　　　哪瓶酒喝了之後，只有一个人存活，那麽这瓶酒就是毒酒， 　　　　而这个人就是郭靖！ 　　　　　　但是！如果那瓶酒喝了之後没有人存活呢？！ 　　我们就没办法找出郭靖了！ 　　只能再花十天！ 变型3： 　　　 　　１２瓶酒之中，有１瓶毒酒，１瓶解药。 解答：没办法同时找出毒酒跟解药！（罪犯够多就可以！) 以下提供十天内单只找出解药的办法！ 解法同上个矩阵！ 　　（但０１代表的意思互换，也就是０代表要喝，１代表不喝） 注意变型1解答中的这段话 由此可知　如果x不是毒酒的话 　　　　 　　至少会有一名罪犯喝了x这瓶酒 　　而且他又没喝到这两瓶毒酒 　　经过０１意思互换之後，可以想成如下 　　任意两瓶非解药的酒，必定有一名罪犯会 　　喝下这两瓶酒，却没有喝到解药。 　　意思就是说，即使是没有毒的酒，也一定会有人同时 喝了它跟毒酒，却没有喝到解药。 　　 　　　　　　　　哪瓶酒喝了没死人，就表示它是解药！ 那罪犯要多少人才可以同时找出毒酒跟解药呢？ 　　一个简单的办法就是任两瓶酒给一名罪犯喝 　　　 　　　　没有毒的酒恰好只会造成一名罪犯死亡！ 此法需要 １２取２＝６６人 ＰＳ：目前最好的方法可以在２４人解决。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.22.206