Problem: there are $15$ boxes, of which $2$ contain candy and $13$ contain grass. There's also a candy-detector machine that can be used to tell whether a particular set of boxes contains candy boxes in it: e.g. you could take $10$ boxes of your choice and it would say 'yes' if there's a candy box among them and 'no' if there isn't one.
The machine can only be used 7 times. Find an algorithm to locate the candy boxes with 100% certainty.
I tried brute-forcing it, but it seems to be complicated. Is there a smart way of solving this?
Preliminary results.
Result-1
Immediate that if you know that there is exactly 1 candy box from a set of exactly $2^n$ boxes, then you will need exactly $n$ tests to guarantee determining which of the $2^n$ boxes has the candy.
Result-2
Suppose that you know that there are exactly 2 candy boxes from a set of exactly 7 boxes. Can the 2 boxes be determined in no more than 5 tests?
Label the boxes $1,2,3,4,5,6,7.$
$T_1~$ (i.e. test 1) : $~\{1,2\}.$
If this test fails, then you have 4 tests to determine which of the 2 boxes from $\{3,4,5,6,7\}$ have the candy. Simply test boxes $3,4,5,6$ one at a time.
Therefore, WLOG, $T_1 : \{1,2\}$ succeeded.
Now: $T_2 : \{3,4,5,6\}.$
If $T_2$ fails, then you have 3 tests left to check boxes $\{1,2,7\}.$ Simply check boxes $1,2$, one at a time.
Therefore, WLOG
$T_1 : \{1,2\}$ succeeded and
$T_2 : \{3,4,5,6\}$ also succeeded.
By Result-1, the situation can be resolved with the 3 remaining tests.
Result-3
Suppose that you know that there are exactly 2 candy boxes from a set of exactly 10 boxes. Can the 2 boxes be determined in no more than 6 tests?
Label the boxes $1,2,3,4,5,6,7,8,9,10.$
$T_1~$ : $~\{1,2,3,4\}.$
If this test fails, then you have 5 tests to determine which of the 2 boxes from $\{5,6,7,8,9,10\}$ have the candy. By Result-2, that is sufficient.
Therefore, WLOG, $T_1 : \{1,2,3,4\}$ succeeded.
Now: $T_2 : \{5,6,7,8\}.$
If $T_2$ succeeds, then Result-1 can be applied against
$\{1,2,3,4\}$ and $\{5,6,7,8\}$ so the 4 remaining tests are sufficient.
Therefore, WLOG
$T_1 : \{1,2,3,4\}$ succeeded and
$T_2 : \{5,6,7,8\}$ failed.
Now: $T_3 : \{9,10\}.$
If $T_3$ succeeds, then Result-1 can be applied against
$\{1,2,3,4\}$ and $\{9,10\}$ so the 3 remaining tests are sufficient.
If $T_3$ fails, then both boxes of candy are in $\{1,2,3,4\}$ so use the 3 remaining tests by testing $1,2,3$ one at a time.
Result-4
Suppose that you have 6 tests to use against
$\{1,2,3,4,5,6,7,8,9,10\}.$ Further suppose that you have used the first test as follows:
$T_1: \{1,2,3,4\}.$ Further suppose that this test succeeded.
Can the situation be completely resolved by the 5 remaining tests - here it is unknown whether $\{1,2,3,4\}$ contains 1 candy box or 2 candy boxes.
$T_2: \{5,6,7,8\}.$
This test can be assumed to have failed, since otherwise, Result-1 can be applied (re 4 remaining tests) against
$\{1,2,3,4\}, \{5,6,7,8\}.$
$T_3: \{9,10\}.$
Similar to the above, this test can also be assumed to have failed because otherwise, by Result-1, the 3 remaining tests can be applied against
$\{1,2,3,4\}, \{9,10\}.$
Consequently, with 3 tests remaining, it can be assumed that both candy boxes are in $\{1,2,3,4\}.$ Therefore, simply test $1,2,3$, one at a time.
Label the boxes $1,2,3, \cdots, 14,15.$
$T_1 : \{1,2,3,4,5\}.$
By Result-3, WLOG, $T_1$ succeeds, since otherwise, 6 tests are sufficient against $\{6,7,8, \cdots, 15\}.$
$T_2 : \{5,6,7,8,9\}.$
If $T_2$ fails, then the scenario precisely fits Result-4, with $\{1,2,3,4\}$ having been successfully tested, and $\{10,11,12,13,14,15\}$ still untested. Note how the hypothetical failure of $T_2$ eliminates $\{5\}$ and allows the supposition that $\{1,2,3,4\}$ has been tested successfully.
Therefore, by Result-4, WLOG, $T_2$ succeeds.
$T_3 : \{5\}.$
If $T_3$ fails, with $T_1$ and $T_2$ both assumed to have succeeded, then there must be 1 candy box in $\{1,2,3,4\}$ and 1 candy box in $\{6,7,8,9\}.$ Then, by Result-1, the 4 remaining tests are sufficient against $\{1,2,3,4\}$ and $\{6,7,8,9\}.$
Therefore, it may be assumed that $T_3$ succeeds.
$T_4 : \{10,11,12,13,14,15\}.$
Regardless of whether $T_4$ succeeds or not, Result-1 kicks in.
If $T_4$ succeeds, then 3 tests are sufficient against $\{10,11,12,13,14,15\}.$
If $T_4$ fails, then 3 tests are sufficient against $\{1,2,3,4,6,7,8,9\}.$