A brain teaser for fun
The following is inspired by a question I answered at my HS junior year:
Dr. Frankenstein likes wines and would (but not preferable to, of course) die drinking fine wines.
10 days before Dr. F's 21st birthday, Dr. Knuth sends him 1000 oak barrels of VERY good wine. However, 1 barrel among the 1000 is spiced with poison that kills anything in exactly 24 hours (not sooner nor later).
Dr. F is determined to figure it out and use the fine wines for his birthday party.
With the mere 10 mice he has to test the wine, how does he:
(2 separate questions/objectives)
Q1. find the bad wine in the shortest time?
Q2. find the bad wine will least number of dead mice?
a. 10 days
b. 1 barrel poisoned among 1000 barrels
c. 10 mice
Q2. find the bad wine WITH least number of dead mice (with the same requirements, of course)?
In TW, so that more people can try it:
A quick tip:
This is not a trick question. You need to have a good understanding on:
1. discrete math
4. worse - and use them at the same time.
5. worst - be very beautiful...
As I said before - you need to define clear steps for Dr. F to do.
To start, please define what "n" is. Being abstract is fine, my IQ is way above 170.
Ok, here is my solution to Q1:
step 1: 鼠編號0 to 9
step 2: 桶編號0 to 999 (可優化)用２進位方式寫在桶上(例：513號桶寫成 10 0000 0001)
step 3:位數指定：每一２進位位數指定一鼠(例：0號鼠被指定在個位數位,1號鼠被指定在下一個位數位 )
step 4: 鼠喝酒：命令各鼠喝一滴每個桶子 自己位數是1的桶(例：513號桶寫成 10 0000 0001 所以0號鼠與9號鼠個喝一滴 其它鼠不喝)
step 5:24小時以後數死鼠 把每個死鼠的編號 2的次方後加起來 就是毒酒桶編號(例：5,3,0號鼠死亡 就表示毒酒桶是2^5 + 2^3 + 2^0 = 41 桶)
optional step 2A: 把991桶改成1000號 把959桶改成1001號 把895桶改成1002號 把767桶改成1003號 把511桶改成1004號
- 6 years agoFavorite Answer
Let me re-post my answer, so master AP will NOT need to remove this question:
You mark the 1000 bottles of wine from 1 to 1000, and mark the 10 mice from 1 to 10.
Then you first let mice 1 to 10 drink bottle 1 to 10.
for bottle 11, you let mice 1 and 2, bottle 12, mice 1 and 3, as follows:
11 1, 2
12 1, 3
13 1, 4
14 1, 5
15 1, 6
16 1, 7
17 1, 8
18 1, 9
19 1, 10
20 2, 3
21 2, 4
22 2, 5
23 2, 6
24 2, 7
25 2, 8
26 2, 9
27 2, 10
28 3, 4
29 3, 5
30 3, 6
31 3, 7
32 3, 8
34 3, 9
35 3, 10
36 4, 5
37 4, 6
38 4, 7
39 4, 8
40 4, 9
41 4, 10
42 5, 6
As you can the pattern, basically, it uses permutation formula C(10, n). where n=1, 2 ... 10 (number of mice)
However, when n reaches 8, that C(10,8)=45, the total number of bottle consumed will be 1012. Therefore, the highest number of mice that need to drink from the same bottle will be 8. That means, the most of amount of mice get killed will be 8. However, such an algorithm can be done within 1 day, but all 10 mice will be dead drunk!
OK, this method will achieve the minimum amount of day to find the poisoned wine, but may not consume the least amount of mice. The other method stated in the opinion will only consume 3 or 4 mice. Hence, I think the method in opinion is good for minimal mice.
My answer was inspired by Cookie's answer by using permutation. Hence, I need to credit part of my answer to Cookie.
- 知足常樂Lv 76 years ago
Thanks for the great discussion!
AP is a she and Melon is a he.
Both of them are also experts in mathematics in additional to languages (no matter English or computer).
Melon has a second account.
AP is even closer to her final stage.
Melon and AP are nice!
- KookieLv 56 years ago
Sorry, my mind is totally befuddled. Let me try again.
My best try is 3 days without consideration of casualties.
2013-08-26 06:05:36 補充：
on DAY 1, separate 1000 barrels into 100 group, with every group contains 10 barrels.
Mouse A has to taste G1 to G18. Mouse B G10 to G27.
2013-08-26 06:11:38 補充：
A G1 - G18 (1-9, 10-18)
B 10 -27 ( 10-18, 19-27)
C 19-32 (19-27, 28-36)
D 28-45 (28-36, 37-45)
E 37-54 (37-45, 46-54)
F 46-63 (46-54, 55- 63)
G 55-72 (55-63, 64-72)
H 64-81 (64-72, 73-81)
I 73-90 (73-81, 82-90)
J 82-100 (82-90, 91-100)
DAY1 = 2 dead, 90 barrels left (or 1 dead 100 barrels left)
2013-08-27 00:56:48 補充：
I just tried to find a way to solve the problem and never focused on how to elaborate my algorithm. I did make some calculation errors, but still, to be tackled down by a question not so hard as it seems was full of fun.
- 6 years ago
I think he said:
with M mice, this method can decide m/(m+1) of the barrels are good in 1 day.
Doing that repeatedly, in 5 days, his method can find the bad barrel of wine with probably 5 dead mice.
Well, for both Q1 and Q2, 5+5 are pretty far from being optimal.
2013-08-26 01:20:44 補充：
oppps, I meant 4 days and 4 dead mice were far from being optimal for Q1 and Q2.
2013-08-26 02:17:29 補充：
I thought only metals can rust. Probably the melon believes in Amyloid Hypothesis?
2013-08-26 04:06:35 補充：
Oh, based on Melon theorem 011, you must be a jr high student, no?
2013-08-26 04:12:09 補充：
For cookie's 1) what if a mouse die at the 10th day and you still do not know which one of the 10 barrels it drinks at that day is bad?
For cookie's 2) 2 to 9 days are only wild guess - you need to come up with an algorithm (a set of clean steps) to show Dr. F how to do it.
2013-08-26 04:13:13 補充：
I used to think cookie has a lot of bran but I think it does have some brain too. Good try, but no cookies...
2013-08-26 04:45:02 補充：
Sure thing - do you want to have it now or wait for more smarty paints?
2013-08-26 05:26:59 補充：
What you described was not "algorithm" - an algorithm must:
1. with deterministic steps
2. must terminate with an answer.
There must be many ways to find an answer in 10 days - what Melon proposed was 1 good answer (4 days, up to 4 dead mice), but not optimal.
2013-08-26 05:31:43 補充：
With what you proposed at 021, at 0.01 probability, you may find the bad wine in 1 day with 1 dead mouse. But how about the other 0.99?
Yes, you may say repeat the same step till 10th day.
Then you have 0.01 probability to find it at 2nd day with 1 dead mouse.
2013-08-26 05:33:22 補充：
another 0.01 probability to find it at 3rd day with 1 dead mouse.
another 0.01 probability to find it at 10th day with 1 dead mouse.
But this algorithm only solve 0.1 of the problem but not the other 0.9
2013-08-26 05:57:13 補充：
To Cookie - please define "group"
2013-08-26 05:58:41 補充：
To Melon, please be reminded that, there are 2x questions:
1. is to find the fastest way
2. is to find in 10 (or less) days with least deaths.
2013-08-26 05:59:56 補充：
To cookie, yes - Melon used this way as well.
2013-08-26 06:12:07 補充：
To cookie, I think I understand your "group" now. But even 3 days is far from being optimal for Q1.
2013-08-26 06:14:48 補充：
Hmm, I think you are pointing to a good direction now... Try to think about the discrete math you took in the kindergarten...
2013-08-26 07:21:07 補充：
What excuses on the discrete math - it was too easy for old men anyway.
2013-08-26 12:12:06 補充：
Melon dude, Cookie claimed that 1 day is enough to find the answer for Q1. Does this get your juices going? Dude, fire your engine (or should I say brain?)
2013-08-26 18:33:42 補充：
c(10,6)=??? shouldn't it = c(10,4)?
2013-08-26 21:38:46 補充：
(10,6) = 10x9x8x7x6x5/6x5x4x3x2x1 = 10x9x8x7/4x3x2x1 = (10,4)
if you cancel 6x5 - I think this is too basic to use up more comments...
trust me, c(10,6) = c(10,4) and cannot be 420
2013-08-26 21:52:41 補充：
Ok, let's kill this once for all
when n >= m, c(n,n-m) = n!/((n-m)! (n-(n-m))!) = n!/(m!(n-m)!)=c(n,m)
2013-08-26 22:00:17 補充：
Sigma(c(10,i), for all 10>=i>=0) = 1024
Does that 1024 tell you something? if not, it is 2 ^ 10
2013-08-27 01:06:02 補充：
I do agree that Cookie dude deserves the Q1 idea originality which I think is more critical in problem solving process.
But why cannot the Little Mermaid have both legs?
2013-08-27 01:23:08 補充：
OK - since we have had an acceptable solution on hand, do I need to announce my algorithm now? It is actually very simple.
2013-08-27 02:01:17 補充：
Now, all answers are gone and this post will likely to be removed due to the absence of any answer.
You smarty paints - why did you do that???
2013-08-27 02:37:55 補充：
Now we do have a couple of "melons" for sure.
Sure - I will provide my version of the answer (if I can recollect at all.)
2013-08-27 03:40:35 補充：
1. I like to smoosh melons, not smash them.
2. You don't want to get me into troubles to do that during work hours, do you?
2013-08-27 07:49:28 補充：
Owning a Bentley is a big burden to any one, even to royalty.
2013-08-27 07:51:01 補充：
OK the solution has been posted in the question section (to avoid interleaving)
2013-08-27 09:46:39 補充：
>> human brain are not used to binary.
Indeed, I think human brain is programmed for trinary computation.
But I don't have much hope for melon bran... it gives me gas.
2013-08-27 09:49:49 補充：
Ok, unless you are still interested in pursuing Q2 or give my step 2A question a try, I will close up this question tonight, of course, disappointed...
And, if the princess is disappointed, the earth will quake!
2013-08-27 11:02:23 補充：
>> your method can kill up to 10 mice
not true - 10 dead mice can only occur if there is barrel numbered 1023 which does not exist.
Please see your own comment 058.
2013-08-27 11:07:19 補充：
Let's kill this once for all - the expected deaths is 4.927 mice for Q1 (1 day shortest time).
2013-08-27 11:09:06 補充：
Oh, I should have said:
without step 2a optimization, the expected death is 4.932.
but with step 2a, it is lowered to 4.927.
2013-08-27 11:14:08 補充：
Oh, then you were talking about Q2. The answer to Q2 is
the expected deaths of 1.90 in 10 days.
Your 3 or 4 is far from being the optimal either.
Well, you don't want me to tell you the solution again, do you?
2013-08-27 11:17:46 補充：
Melon dude, please observe the different objectives of Q1 and Q2.
2013-08-27 23:26:50 補充：
I can open up another question for your good answer?
2013-08-28 03:37:45 補充：
I knew curiosity kills cat but never realized that Melon kills curiosity.
- How do you think about the answers? You can sign in to vote the answer.
- 幻星Lv 56 years ago
I know every words DSG said, still have no clue about what he meant
- DaSaGwaLv 76 years ago
First, you take wine from every 100 barrels and place them together in a container. Give wine from each container to each mice respectively. 24 hours later you will find which container has the poisoned wine.
2013-08-26 00:34:00 補充：
This will eliminate 900 barrels of wine. Then, do the same thing to remaining 100 barrels, group them into 10 container for every 10 barrels. You will find which container has poisoned wine. At this time, the poisoned wine is within that 10 barrels.
2013-08-26 00:37:00 補充：
so far, you at most kill 2 mice, maybe just one.
Now, you group the 10 barrels wine into 5 group, and feed to 5 mice, you will then determine which group (contains only wine from 2 different barrels).
2013-08-26 00:42:24 補充：
At this time, you at most kill 3 mice possibly only 2.
Then, for the group contains the poisoned wine, you use 2 more mice to test them. You will find which barrel is poisoned.
2013-08-26 00:46:56 補充：
In the end you have killed 4 mice, possible only 3, because in the second step, you only have 9 mice, and all those 9 mice might survive, because the one that was not fed to mice might contain the poisoned wine.
2013-08-26 00:48:35 補充：
The total time it will take is about 4 days for 4 tests (1000==>100, 100==>10, 10 ==>5, 5==>1)
2013-08-26 01:52:57 補充：
I know, there is a better method, so I don't dare to place in the answer area. Hopefully, someone can enlighten me with a better method.
2013-08-26 01:58:44 補充：
If I were a junior HS student, maybe, I would have better idea! Brain has rusted for a few years now.
2013-08-26 04:39:19 補充：
My intelligent AP! If no one offers a strategy that can be done within 4 days and kill less than 4 mice, would you tell me your Jr. HS idea?
2013-08-26 05:47:14 補充：
master AP! Don't tell me the answer yet. I like to think it over again to see whether I can kill less than 4 mice or not.
2013-08-26 06:41:22 補充：
I will take Discrete Math in an Oldman University! Discrete math happened to be one of the math courses I didn't take. After all, that is more for computer science.
2013-08-26 07:48:22 補充：
No, not for this one! I figured out an answer, but not the optimal one. I think, it might have something to do with grouping and logic, but no brilliant idea yet. Anyway, there are a few more days left, maybe, I can get some inspirations later.
2013-08-26 07:48:45 補充：
This is the problem with rusted brain!
2013-08-26 13:41:03 補充：
I guess I learn discrete math a little bit!
2013-08-26 13:47:18 補充：
Cookie! Your using the permutation is NOT correct,
for n=2, you shall have 10x9/2x1 = 45
for n=3, you shall have 10x9x8/3x2x1 = 120
However, your using permutation gives me the inspiration! Thanks!
2013-08-26 21:15:42 補充：
(10, 6) = 420,
(10, 4) = 210
2013-08-26 21:27:23 補充：
Oh! I am not sure the math sign I use is correct or not, but what I mean by (10, 4) is 10x9x8x7/4x3x2x1
(10,6) = 10x9x8x7x6x5/6x5x4x3x2x1
2013-08-26 22:20:02 補充：
Ha! Ha! My brain is really rusted. You are right ! C(10,4) = C(10,6). I looked my scratching paper, I did make a small mistake to calculate C(10,6). Well! I guess the idea is right, but the calculation has some glitches.
2013-08-26 22:24:42 補充：
I understand your comment #050. It is just that I didn't think of it that way, but using hand calculation. After all, these math are too far from me, I only have the idea, but not the comprehensive idea you have presented in #050.
2013-08-26 22:26:54 補充：
Does my latest answer agrees with your HS answer? :-) ... If not, I think I need to give up, and enjoy others' brilliant offers.
2013-08-26 22:35:32 補充：
Oh! Since the computation mistake I made, it will KILL up to 8 mice "C(10,8)", if the poisoned wine is labeled close to 1000, like after 967, not 6 mice as I have originally stated.
2013-08-26 22:37:58 補充：
But of course, this is NOT an optimum solution for killing the least amount of mouse.
2013-08-27 01:49:47 補充：
Certainly! Maybe I will pull my hair out when I see your algorithm! Perhaps, it will serve as a lubrication for my rusted brain.
2013-08-27 01:51:12 補充：
Since my second answer is inspired by Cookie's answer, let me remove my answer to support his. After all, we need a talent like cookie to get promoted so he or she can have more discussion with us in the future.
2013-08-27 02:02:30 補充：
I thought I like to support Cookie's answer !
2013-08-27 02:31:58 補充：
This is a good question, so let me create another account to repost my answer.
2013-08-27 03:05:27 補充：
master AP has a habit of smashing melon, so a few more will ensure its survivability.
2013-08-27 03:21:06 補充：
Sound like master AP has some rusted brain too.
2013-08-27 07:12:31 補充：
The definition of smoosh is "to squash or mash". I wonder, is there any difference as far as the result is concerned between "smoosh" and "smash"?
2013-08-27 07:14:43 補充：
"work hour", I thought royal family doesn't work!
2013-08-27 09:35:26 補充：
Good news, I didn't choose computer science as major, otherwise, I will be like those mice, don't know why they need to drink :-) ...
2013-08-27 09:36:59 補充：
However, I can tell, such a method is easier for computer. After all, human brain are not used to binary.
2013-08-27 10:21:00 補充：
Gee! I finally get my rusted brain move, and master AP is still disappointed! About 2A question, I think it has something to do with binary! I didn't try to write it in binary, but my guts told me so.
2013-08-27 10:22:58 補充：
Master AP, your method can kill up to 10 mice, my method would only kill no more than 4. Don't tell me you can get it by killing only one mouse!
2013-08-27 10:23:43 補充：
rusted brain move ==> rusted brain moved
2013-08-27 11:10:00 補充：
I mean the first method I used will only kill 3 or 4 mice, the second method will kill up to 8 mice.
2013-08-27 22:23:10 補充：
Look like master AP cannot wait for me to come up another answer for Q2!
2013-08-28 01:15:35 補充：
Not really! I think I am going to surrender, after all, my rusted brain is hopeless.