31
$\begingroup$

You have 15 balls, 2 of them are radioactive. You have to run 7 tests (no more) on the balls which will sort out the 2 radioactive ones guarenteed every time. You can test them in groups, or even one by one.

A "test" comprises of taking a subset of the balls and checking if this subset contains a radioactive ball (one or more) or not. The test does not determine the number of radioactive balls in the tested subset.

  • 8
    Presumably, what the test will do is tell you whether there is at least one radioactive ball among the balls you are testing, and this test will be 100% accurate each time. (The way you phrased it, it would seem that you can just test all 15 balls together, and the test will tell you which two are radioactive)2011-06-06
  • 1
    You need n tests (at most) to find out one radioactive ball in a set of 2^n balls. It seems to me, then, that in this scenario 7 tests are enough to solve a stronger problem : 16 balls, always dividing the radioactive sets by two.2011-06-06
  • 1
    @leonbloy, why is that? If you have 4 balls there are 6 possible scenarios, but 2 tests can only yield 4 possible answers so I don't see how this can suffice.2011-06-06
  • 0
    @Alon: I meant 'one ball in a set with (just) one ball'. Then, say, in the first split (16 balls in two 8 sets), the test can return two types of result: if both sets are radiocative, then we need 3 tests for each set (ok); elsewhere, we continue splitting the (doubly) radioactive set2011-06-06
  • 0
    @leonbloy. I actually think testing $2^{n} - 1$ balls can require up to $2^{n-1} - 1$ test.2011-06-06
  • 0
    @Alon: Your addition is what is expected for the problem to be intelligible, but I think such an addition should wait for the OPs clarification.2011-06-06
  • 2
    A more common version of this problem: You have some balls that are all the same weight except for one. Using a scale, find the heavy ball using as few weighings as possible. Searching keywords like "heavy ball scale" bring up some solutions that might be useful for you.2011-06-06
  • 0
    Oops ... I had missed one detail...2011-06-06
  • 0
    @Arturo and mac: Thanks for pointing the flaw in my argument.2011-06-06
  • 0
    @Arturo: you are right, but this problem has making the rounds for some time now (usually with the "radioactive" narrative) so I took the liberty to clarify. I trust the OP will let us know if something else was intended.2011-06-06
  • 0
    yes, one test can only tell you there are radioactive balls in the group, but will not tell you how many.2011-06-06
  • 0
    8 test can easily find out the 2 balls, but how to do it in 7 tests?2011-06-06
  • 0
    The 8 ball version of this problem is in the current Puzzle Corner of the Australian Math Society Gazette, http://www.austms.org.au/Publ/Gazette/2011/May11/PuzzleCorner.pdf2011-06-07
  • 0
    Any solution has to involve more than partitioning. If you just split, test both halves, and recurse suitably on the halves which contain radioactive elements then 8 tests are required.2011-06-07
  • 0
    Look down. (Joking.)2011-06-09

10 Answers 10