0
$\begingroup$

This question already has an answer here:

One of my friends shared this picture to me, actually I don't know from where it came from but it seems interesting to solve.

Please check below:

enter image description here

$\endgroup$

marked as duplicate by ffao, boboquack, Alconja, Rubio, Techidiot May 17 '17 at 4:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Duplicate of a duplicate? This Q is a simpler problem in which we are given that an object is heavier, not just that it differs in weight. I think that if we must mark it as a duplicate, we should make the duplicate problem one that actually indicates this. Nobody is going to be making this extremely convoluted algorithm to solve the simpler version. $\endgroup$ – greenturtle3141 May 17 '17 at 1:46
  • $\begingroup$ @ffao & greenturtle3141, If you think it's duplicate no offense from me. I can say it's pure logical and there is unique explanation to solve. $\endgroup$ – CR241 May 17 '17 at 2:22
  • $\begingroup$ @greenturtle3141 The simpler version is marked as a duplicate of the question I linked to, but I didn't think the duplicate chain would go even deeper (by the way, the algorithm is not at all convoluted) $\endgroup$ – ffao May 17 '17 at 2:26
  • $\begingroup$ Why downvote? With out proper explanation, don't make assumptions and personal opinions. Thanks @stackreader and greenturtile3141 for posting better answers (but I'm looking for more precise one). I will post answer here shortly. $\endgroup$ – CR241 May 17 '17 at 2:58
  • $\begingroup$ What do you mean you're not looking for weight tests? That's the only given way to solve the problem. Short of finding eight rats and feeding each one a pill. $\endgroup$ – Tim May 17 '17 at 3:45
5
$\begingroup$

This may be a duplicate, but the trick for these types of problems is to divide and conquer, but not into two halves, but thirds. The idea is that if we divide the balls into 3 even groups and weigh 2, there are THREE outcomes. Let's call the groups A, B, and C, and weight A and B against each other:

If A outweighs B, A has the answer. If B outweighs A, B has the answer. If A equals B, C has the answer.

Unfortunately here, we have 8 pills, which is not divisible by 3. We can at least pretend there is one though. Make the division 3, 3, 2. Weigh the groups of three against each other. If one outweighs the other, you have narrowed it down to three. If they equal each other, you have narrowed it down to two, which is strictly better. With three left, we divide into thirds again, this time with each "group" having one pill. Weight two against each other, and you're done.

$\endgroup$
  • $\begingroup$ Well try, it's not correct answer what I am looking for. In your 1st balance check if 3 pill set are not equal how can you say which one is more weight. $\endgroup$ – CR241 May 17 '17 at 2:15
  • 2
    $\begingroup$ the pan that is lower indicates that the contents have more weight...? $\endgroup$ – greenturtle3141 May 17 '17 at 2:19
  • $\begingroup$ Then how can you say exactly which pill is poisoned? (more weight) $\endgroup$ – CR241 May 17 '17 at 2:24
  • 2
    $\begingroup$ I don't. But I know it's among the three, and proceed to phase 2. $\endgroup$ – greenturtle3141 May 17 '17 at 2:49
2
$\begingroup$

Here is how I would do it.

First weight 3 VS 3 on the scale and leave 2 on the side.
If the weight is the same, weight compare the 2 others and you will get the heavy one.
Else you take the group of 3 that was heaviest and compare 2 of them.
If one is heavier, it's the poison, else, the one you didn't weight is the poison.

$\endgroup$
0
$\begingroup$

I want to give my possible precise explanation/answer to above question. Thanks @greenturtle3141 (But I know it's among the three, and proceed to phase 2)

Precise Answer in my simple version:

Assume all 8 Pills like P1,P2 ..... P8 and Place Pills P1, P2 & P3 on one side of the scale and pills P4, P5 & P6 on the other side of the scale. If the Scale is balanced remove all the pills from the balance. Place Pilla P7 on one side of the scale and pill P8 on other side of the Scale. The heavier one is the poisonous pill.

Scenario 1: If the scale is not balanced, assume pills P1, P2 & P3 are heavier than pills P4, P5 7 P6. Remove all the pills from the balance.

Place pill P1 on the one side of the scale and pill P2 on the other side of the scale. If theScale is balanced, then pill P3 is the poisonous pill. If the scale is not balanced, the heavier one is the Poisonous pill.

Scenario 2: If the scale is not balanced, assume pills P4, P5 & P6 are heavier than pills P1, P2 & P3. Remove all the pills from the balance.

Place pill P4 on the one side of the scale and pill P5 on the other side of the scale. If the Scale is balanced, then pill P6 is the poisonous pill. If the scale is not balanced, the heavier one is the Poisonous pill.

$\endgroup$
  • 2
    $\begingroup$ This answer is exactly the same as greenturtle's and stackreader's answers. How is it supposed to be different? $\endgroup$ – Tim May 17 '17 at 3:51
  • $\begingroup$ @Tim, I agree it almost same as greenturtle's and stackreader's answers (but not exactly), why because here I explained possible senario's (small difference) $\endgroup$ – CR241 May 17 '17 at 3:55
  • $\begingroup$ Observing that you have unaccepted my answer, I will explain. Your answer is concrete, but lacks spirit. It describes the complete process, but does not go over intuition. My answer shows the complete thought and how to approach the general issue. We observe that there are three possible outcomes, and therefore if we can achieve a division by 3 for the possibilities upon each weighing, we have achieved optimality. If tasked with a larger problem, for instance, 1000 pills, your answer fails to imply that you would need only 7 weighings. $\endgroup$ – greenturtle3141 Jul 27 '17 at 21:47
0
$\begingroup$

This is one of the easiest puzzles of its kind (and has been correctly answered among the other answers). As such, I'm going to aim for a more complete answer, explaining what sort of reasoning goes into solving this sort of question (thus, indirectly, how to gauge its difficulty). As a bonus, we can actually exhaustively determine all possible correct strategies for this puzzle. First, the strategies themselves:

The strategies are all almost the same, differing only by a single number p in the range 0 to 1 inclusive. (Most strategies for solving this problem will either use p=0 or p=1, but values in between also solve the problem in a somewhat more complex way.) Here's the algorithm you use:

  1. Split the pills into two groups of 3, and one group of 2.
  2. Weigh the two groups of 3 against each other.
  3. If one of the groups was heavier, weigh two of the pills from that group against each other. The heavier one is the poisonous pill. If the two are equal, the pill from that group that you didn't weigh is the poisonous pill.
  4. Otherwise (the scales were balanced), call the pills you didn't weigh A and B, and a random pill you did weigh C. With probability p, weigh A against B. With probability 1-p, weigh A against C.
  5. If one of the pills was heavier on the second weighing, it's poisonous. Otherwise, the poisonous pill is B.

And now, how you reach this result:

The first thing to do is to count the number of possible results we have. If we only have "left side of the scale is heavier" or "right side of the scale is heavier" as possible results for each weighing, then we have four possibilities (left/left, left/right, right/left, right/right); we're trying to distinguish between eight cases, so that clearly isn't going to work out directly. As such, we need to find some other information we can get from the scale.

The question isn't stated precisely, but it's clear that the extent to which one side is heavier is not useful information; for one thing, we don't know how much heavier the poisoned pill is, and for another thing, even if we did, the scales can only potentially be unbalanced by the weight of a pill (if we load them in an unbalanced way, which is not useful), or by the difference in pill weight. As such, we have to make use of the situation in which the scales are balanced. If we weigh all eight pills, this will never happen, so we're going to have to leave some off the scales.

We now have nine possibilities (left, right, or balanced on the first weighing, and left, right, or balanced on the second, gives 3×3=9). Next, we're going to look at the problem backwards: how many pills can we solve for with one weighing? There are three possibilities, so perhaps we can distinguish between three pills? We clearly can't do more. There's only one algorithm that has any chance of giving useful information (weigh one of the unknown pills against another, leave a third off the scale), and as luck would have it, that algorithm happens to do exactly what we need, giving a distinct result in each of the three cases.

Now we know that we can distinguish between three pills in the second weighing, the first weighing therefore needs to narrow down the number of pills that could potentially be poisonous to no more than three. (It's OK if we end up with less than three candidates; we can just take a pill that we know is safe, and forget that we know it's safe, in order to reduce the two-candidate case to the three-candidate case we already know how to solve.) This means that we can't place more than three pills on a single side of the scale (otherwise there'd be four or more pills we couldn't distinguish between), nor leave more than three pills off the scale (for the same reason). If we only put two pills onto the scales, we'd have to leave four off, and thus we need to put three pills on each side (leaving two off the scale).

We can verify that the first weighing narrows down the set of poisonous pills to either 2 or 3, so we now have a solution (weigh three against three on the first weighing; then take the heavy group, or (if the scales were balanced) the two omitted pills plus a random pill, and weigh one against one, with the heavy pill being poisonous or the omitted pill if the scales are balanced). Are there any other solutions? Well, we proved above that we can't change the first weighing. The second weighing also has only one possibility if the scales were unbalanced the first time. The only case that we can change is the second weighing after a balanced first weighing; we can choose to weigh the two omitted pills against each other (always), or weigh one against a known safe pill (always), rather than choosing at random. These are all generalizations of a single spectrum of strategies, in which you vary the probability of weighing two unknown or one known pill on the second weighing after a balanced first weighing.

$\endgroup$

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