2
$\begingroup$

We have $7$ balls that at least $4$ of them are made from iron. In a step we can give two of them to a person that can recognize whether or not the balls are made from the same materials. How many steps are at least needed to find a ball that is made of iron?

My attempt: It is easy to see $4$ steps are enough. All that is needed is to divide the balls into $3$ sets of two balls and a single ball, then check those three sets of balls. Then we have to divide the cases according to the number of "Yes" or "No"'s that we hear. Finally, in some of those cases the three steps were enough, and in some a $4$th step is needed. But I can't prove $3$ steps can't be enough.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are there only two materials (iron and something else)? $\endgroup$
    – Jaap Scherphuis
    Commented Aug 12, 2017 at 9:12
  • $\begingroup$ how do y check 3 set of 2 balls with the extra ball whle you can give max 2 balls to a person? $\endgroup$
    – Oray
    Commented Aug 12, 2017 at 9:13
  • $\begingroup$ @Oray We do it in three steps in some cases the single ball doesn't need to be checked consider we got $3$ "no"s checking the sets of balls then we can say the last one is from the majority. $\endgroup$
    – Taha Akbari
    Commented Aug 12, 2017 at 10:23
  • $\begingroup$ @JaapScherphuis No it can be only one or $4$ materials or others.But the point is that we know that at least four of them are from the same material. $\endgroup$
    – Taha Akbari
    Commented Aug 12, 2017 at 10:24
  • $\begingroup$ @TahaAkbari "divide the balls into 3 sets of two balls and a single ball the check that three sets of balls." what does this mean exactly? explain it with an real example please. It is confusing because you say "we can give two of them to a person" but if we can compare "a single ball" with "set of two balls", that's totally another story... $\endgroup$
    – Oray
    Commented Aug 12, 2017 at 10:30

1 Answer 1

Reset to default
4
$\begingroup$

3 is small enough that you can just brute-force it to show you can't do better than 4 (I'd appreciate an elegant solution, but hey, this works).

Which two are the first pair doesn't matter, so let's say the person said they are made from the same material. Now the second pair can be one ball from pair 1 and one new ball or two new balls.

If we pick two new balls, our friend can tell us they are the same as well. Now for the third pair we can pick one ball from pair 1 and one from pair 2, one from a pair and one not from a pair, or two balls not from a pair. In the first case our friend tells us they're different and we still don't know which pair is iron; in the second case our friend tells us they are the same, and we still don't know if this group of 3 is iron or the minority; and in the third case our friend tells us they are the same and we can't tell which of the three pairs are iron balls. Either way we can't tell which ball is made from iron.

If we pick one ball from pair 1 and one new ball, our friend tells us they are the same. Now we have a group of 3 balls, but we don't know if they are the minority or if they are the majority. In fact, no question we ask will help us determine which one it is; if we ask about two balls not in the group our friend can tell us they are equal, and we still don't know if they are iron or not, or if we ask about a ball in the group and a ball not in the group, our friend tells us they are different and there's still the possibility that the balls not in the group are the 4 iron balls.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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