2
$\begingroup$

OOOOOOK! So. Here we go.

Scenario

Your friend (a restaurant owner) calls you one afternoon in urgency. Something terrible has happened and he needs your support at once!! You borrow $50 from the neighbor's kid (as you are broke -as always-) and get a cab to his place. You see him sitting head-in-knees.

"What's up brah?" You ask.

"I'm ruined!" He replies. "A group of high dignitaries are coming to my restaurant and the special lamb-fried-rice I prepared for them is spiked with poison!"

You wonder for a moment why a group of high dignitaries would come to a useless place as this restaurant, but * ahem ahem *. So you go on to ask "Is all the dish spiked?"

"No. Only 1 plate. But demons take me, I don't know which plate it is!"

"Calm down man and tell me things from the start!" You tell him.

"OK here goes. A group of 16 dignitaries was coming to my place and they are all Asian. So I prepared our high specialty dish, lamb-fried-rice. Now it happens that one of my waiters was demanding me a salary increment for previous 4 months and I had been refusing him (oh you cheap skunk!). Now as a cook was passing around the kitchen area, he saw the waiter take out a small bottle from his pocket and add it to a plate (there were 16 plates on the row). He immediately went and confronted him about it, on which, that idiot jumped from the window of 3rd floor and ... died on the spot. In the meantime, other waiters had picked the plates up and left for placing them on the table. So now the idiot cook doesn't even know which plate it was that was poisoned.

"We have 4 poison testing machines with us which can detect the minutest amount of poison in given sample. But all machines can work on only one sample at a time and each machines take 55 minutes for producing the result. The dignitaries are arriving in 1 hours and 15 minutes. How the demons am I supposed to find the spiked plate in this time? Aaaaaaargh! I'm ruined. Ruined! Ruined! RUINED!!"

In Simple Words

There are 16 plates.

Only one plate is poisoned.

There are 4 poison testing machines.

Each machine can work on only one sample at a time. The result is delivered only as positive (sample contains poison) or negative (sample is not poisoned).

Each machine takes 55 minutes to process the sample.

The dignitaries are arriving in 1 hour and 15 minutes (75 minutes).

You must find the poisoned plate within this time.

NOTE: This is a puzzle which computer science students will be able to solve easily. Others will most probably not even get on the right thinking track. Not saying that it's impossible or something, but other people will probably make wrong assessments and start with wrong model in the very first place. THIS IS NOT A MATHEMATICAL PUZZLE

P.S. If you find the poisoned plate, don't expect your friend to pay you the 50$ you borrowed to reach him. If he was such a generous man, he would have increased the salary of the poor waiter!

Improve this question
$\endgroup$
13
  • 9
    $\begingroup$ I'm not sure that the dignitaries will be very happy even if you do find the poison. The food has been served 75 minutes before they've even arrived. Cold lamb fried rice - yummmmmy ;) $\endgroup$
    – Gordon K
    Commented Sep 18, 2015 at 8:38
  • 2
    $\begingroup$ Can I send you the poisoned plate for the support, sir? ^_^ $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 10:21
  • 2
    $\begingroup$ I disagree on this not being a mathematical puzzle. $\endgroup$
    – Taemyr
    Commented Sep 18, 2015 at 13:39
  • 4
    $\begingroup$ @You That is another branch of maths called 'combinatorics'. It is still maths. $\endgroup$
    – ghosts_in_the_code
    Commented Sep 18, 2015 at 15:11
  • 1
    $\begingroup$ @GordonK Don't worry, the testing machines can heat it up. $\endgroup$
    – aebabis
    Commented Sep 18, 2015 at 19:26

4 Answers 4

Reset to default
14
$\begingroup$

Number each plate from $0$ to $15$. Convert each plate number into binary. Number the machines 0-3. The $i$th machine takes in all samples with digit $i=0$. Each positive sample means $0$ and the rest mean $1$. Hence you know the poisoned sample.

Simplified:

  • Tester 0 has samples 0-7 mixed together
  • Tester 1 has samples 0-3, 8-11 mixed together
  • Tester 2 has samples 0-1, 4-5, 8-9, 12-13 mixed together
  • Tester 3 has samples 0, 2, 4, 6, 8, 10, 12, 14 mixed together

Start with a number 15. If tester 0 is positive, subtract 8. If tester 1 is positive, subtract another 4. If tester 2 is positive, subtract another 2. If tester 3 is positive, subtract another 1.

For example, testers 0 and 2 test positive. Poisoned sample $=15-8-2=5$

Improve this answer
$\endgroup$
2
  • $\begingroup$ @You I hope it is clear now. It's just that such questions (and solutions) appear so much simpler when written in mathematical form. $\endgroup$
    – ghosts_in_the_code
    Commented Sep 18, 2015 at 8:33
  • $\begingroup$ I understood it in the binary base model too, but for the sake of simplicity for fellow members, I thought it more acceptable to have it in a form which everyone can understand. $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 10:10
14
$\begingroup$

Basically, you have 2^4 plates to test, and 4 machines. This obviously hints of binary. You create a series of combinations to each plate occurs in a unique combination of testers.

Based of the binary system, you make combinations so all different options are created. '0' means a plate is not included in the tester sample, '1' means it is included.

Such a way is shown below:

enter image description here

The test shows that there's 16 unique tester combinations, matching the 16 different outcomes for the 4 testers. Therefor, matching the results of the 4 testers in 55 minutes, means you have 20 minutes to prepare the samples and make the correct conclusion.

Rather then calculating (which you could fail in stressy situations) you can just look up which 'plate' matches the positive readings from the testers. If you insist on calculating, you could convert the readings to decimal, but you'd have to increase the result by 1 (plates start at 1, binary count at 0)

In the example above, you could see that if testers 1,2 and 4 come back negative, and tester 3 is positive, you know for certain plate 3 is the poisoned plate.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Answer is correct, but you presented it in a form which only programmers can understand. I have up-voted it but I am choosing another answer as solution which is easier to understand. $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 10:19
  • 1
    $\begingroup$ @YoustayIgo That's entirely your call. I found the graphic combination display as a guideline easier to comprehend then the math requirement. The rest of the answer is explaining WHY it works, so yea that bit is more technical. $\endgroup$
    – Tim Couwelier
    Commented Sep 18, 2015 at 10:25
  • $\begingroup$ Plus, your groups are designed in a manner that they fully satisfy the binary base model, but it is almost impossible to understand why or how they work. It's sort of like ... a magical answer that surely works, but nobody understands how/why. It's actually a good thing (i like mysticism :p) but here it would confuse the public. $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 10:28
  • $\begingroup$ Agreed, it appears to be 'falling out of the sky'. The binary buildup would've been more visible if I had built it differently. I started with the tester 1 row, and then filled up the alternatives (no extra x's, one extra x in three locations, then three setups for 2 x's, and finally three extra x's). Repeated that for the second block. $\endgroup$
    – Tim Couwelier
    Commented Sep 18, 2015 at 10:59
  • 1
    $\begingroup$ I think if you re-arranged the truth table in a more traditional ordering (0 to 15 or the reverse), it would actually make it easier for non-programmers to understand how to get the plate number from the set of testers with positive results. Highlighting an example solution in the table would make it even clearer. $\endgroup$
    – Simon
    Commented Sep 18, 2015 at 14:50
2
$\begingroup$

label the plates A to P, and the testers 1 to 4. Place a portion of the food from each plate into the coresponding tester

tester 1: Plates BFGHLMNP

Tester 2: Plates CFIJLMOP

Tester 3: Plates DGIKLNOP

Tester 4: Plates EHJKMNOP

then run all 4 machines at once after they are loaded up with small amounts of each sample. Once the 55 minutes are over, you can then read which testers (if any) read as containing poison and match that up to the corresponding plate. If no testers read any poison then it is plate A. follow the reverse of the table to figure out which plate is poisoned.

A no testers detected any poison
B 1
C 2
D 3
E 4
F 12
G 13
H 14
I 23
J 24
K 34
L 123
M 124
N 134
O 234
P 1234

so if testers 2 and 3 come back positive for example, it is plate I, Testers 23 and 4 being positive suggests plate O has poison

Improve this answer
$\endgroup$
9
  • $\begingroup$ Can you put your groups in a more read-friendly format instead of just throwing them all in one line? That would make it easier to read (and process :p) $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 7:32
  • $\begingroup$ lol. You will need to add TWO line breaks instead of one to begin a new paragraph. To just add a new line, finish the previous line with a underscore _ $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 7:34
  • $\begingroup$ So. We get a positive result from tester 2 while testing machines 1, 3, 4 give negative. Can you name which plate is poisoned? $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 7:44
  • 1
    $\begingroup$ Correct! And what if testers 1 & 2 are positive while testers 3 & 4 are negative? $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 7:48
  • 1
    $\begingroup$ How about plate H? ;) $\endgroup$
    – Youstay Igo
    Commented Sep 18, 2015 at 7:51
0
$\begingroup$

Working backwards, we can get an answer a non-programmer might come up with.

First, 75 minutes is a red herring. Since we can't do multiple rounds of testing and since the testers can't return partial results, we can't leverage the extra 20 minutes. We are done after 55.

Second, note that we could put rice from a specific plate into multiple testers or into no testers:

  • If multiple testers are positive, then the poisoned plate must be one whose rice was put into each of those testers.
  • If no testers are positive, then the plate must be one whose rice wasn't put into any testers.

Since any permutations of positive and negative results are now allowed, there are 2^4=16 ways to get results. Since there are 16 plates, we need to leverage each outcome.

For a given outcome, just work backwards, assuming outcome #X must indicate plate #X:

  • Outcome 1) No testers are positive. Since this situation must uniquely identify plate #1, we needed to have aside plate #1 and only plate #1.
  • ...
  • Outcome 8) The third tester is positive, others are negative. Rice from plate #8 must have been put into the third tester and only into the third tester.
  • ...
  • Outcome 16) All testers are positive. Since this situation must uniquely identify plate #16, we needed to put some rice from plate #16 into each tester. None of the other plates are in each tester.
Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.