26
$\begingroup$

All the sheep were living peacefully in the Land of Shewo. But suddenly they were struck by a danger. A few wolves dressed up as sheep entered the territory of Shewo and started killing the sheep one by one.

To find a solution to this misery, the king of Shewo called upon all of his sheep to the palace hall. He made the following announcement:

From my secret sources, I came to know that the total number of 'sheep' (including the wolves) now present in my kingdom is 100. Among which 5 are wolves. Our doctors have come up with a very expensive blood test which could be used to differentiate the wolves and sheep.

Each test costs 1000$ and we don't have enough funds to test all the 100 'sheep'.

I discussed with our ministers and came to know that the tests can be done on pooled bloodsamples. i.e., I can collect bloods from any number of 'sheep' and mix them. Then if I test the mixture, I will get a positive result if the mixture contain blood from any wolf. I will get a negative result if all the samples are from actual sheep.

One caveat is that the test results are available to you after all the tests are done!

Now , I am looking for ideas where I can find ALL the wolves in minimum number of pooled tests. I request the brilliant young minds of this land to come up with a testing strategy.

Can you help the king by devising a strategy?

Hint 1:

Think of total number of ways 5 wolves can infiltrate 95 sheep.

Hint 2:

Think of binary sequences to distinguish each of the possible groups of 5 wolves

Note: I was also thinking of this problem and I realize that the above hints do not lead to any optimal solutions. I have figured out a better way of solving this which I could motivate through hints.

Hint :

K-separability of matrices

Let me know your comments!

$\endgroup$
  • 1
    $\begingroup$ This is close to a covering design (Lotto wheel) problem. $\endgroup$ – Arnaud Mortier Apr 13 at 23:04
  • 4
    $\begingroup$ First of all, does the government have enough funds to test 99 of the sheep? Because that would work, at a cost of $99,000. Congrats, you just saved 1,000 bucks. $\endgroup$ – user45266 Apr 14 at 1:19
  • 5
    $\begingroup$ Alternatively, you know the location of all 5 wolves. Take initiative and slaughter all 100. Now you have no more wolves, and food for a good while to come. $\endgroup$ – user45266 Apr 14 at 1:31
  • 2
    $\begingroup$ @JyotishRobin, while I'm definitely not requesting to see your solution yet, I'm wondering: do you believe you know a solution involving 98-or-fewer tests? Do you believe you know the optimal solution? And if "yes" to either, a followup question: how confident are you in those beliefs? :) $\endgroup$ – Quuxplusone Apr 16 at 16:58
  • 2
    $\begingroup$ @JyotishRobin, so are you going to post your solution, or accept an answer? It's been "a few weeks", and it seems unlikely to me that the question is going to draw new attention. $\endgroup$ – Andrew Savinykh May 8 at 1:39
16
$\begingroup$

Perform

66

tests of nine sheep on all but one sheep according to the illustrated patterns:

The two important properties exhibited are

1. All but one sheep are tested six times.
2. No pair of sheep shares more than one test.

The claim is that given a set of test results there is at most one possible group of five wolves. Suppose instead that some set of test results could have been produced by two different groups of five wolves A and B. Then both groups have a sheep that the other group does not have.

By property 1, at least one of these two sheep was tested six times, say Shaun in group A. Group B must have at least one of five sheep in each of these tests. By the pigeonhole principle, at least one sheep in Group B shares more than one test with Shaun, contradicting property 2.

This establishes the claim. Because we know there are five wolves, this guarantees that we can determine them using the test results.

UPDATE: We can remove any single test T to improve the total by one. Say Shaun is in group A but not B, and Shirley in B but not A.

The argument above only fails if neither sheep was tested six times, i.e., each was either in T or untested. By property 1, one of them, say Shaun, was in T and still tested five times. Because Shirley was either in T or untested, Shirley cannot appear in any tests with Shaun by property 2. Then Shaun's remaining five tests must be accounted for by the remaining four sheep of group B, which fails as above due to the pigeonhole principle and property 2.

UPDATE 2: We can save two more tests by replacing any one of the grids of eleven tests with a grid of nine tests along the rows:

bringing the total number of tests down to

63.

$\endgroup$
  • 1
    $\begingroup$ Seems convincing to me. Any idea how this could relate to OP's hint about binary representations? $\endgroup$ – Ergwun Apr 17 at 14:15
  • 1
    $\begingroup$ Suppose your method failed to distinguish actual-wolf-grouping (a,b,c,d,e) from incorrect-wolf-grouping (a,b,c,d,f) — that is, sheep f is innocent — so, each of f's tests must have contained one of the actual wolves (a,b,c,d,e) in order for the frame to stick — which is impossible because f was tested 6 times and there's only 5 of (a,b,c,d,e). OR ELSE, f must be the one untested sheep! How does your logic rule out that possibility? $\endgroup$ – Quuxplusone Apr 17 at 16:31
  • 1
    $\begingroup$ @Quuxplusone If you take two different groups of five wolves, then each must contain at least one wolf that the other does not contain. In your example, e and f are the two "sheep that appear in one group but not the other." So you may not be able to take one of them (f), but you can still take the other (e). $\endgroup$ – noedne Apr 18 at 0:03
  • 2
    $\begingroup$ @Quuxplusone The construction takes advantage of the primality of 11, which ensures that distinct lines of tests intersect at most once but fails for composite numbers like 10. $\endgroup$ – noedne Apr 18 at 23:22
  • 2
    $\begingroup$ I have verified this solution using C# code and found out that all possible 75287520 arrangements did indeed produce different 66-bit results. $\endgroup$ – Razvan Socol May 5 at 14:44
13
$\begingroup$

Thinking out loud, not a solution yet, but spoilery enough that I didn't want to put it in a comment:

There are ${100\choose 5} > 2^{26}$ possible arrangements of the 5 wolves among 100 sheep. This indicates that we must use at least 27 tests, no matter what — that's just basic information theory.

Could we design a strategy to use the bare minimum? Well, if there were just one wolf, then yes we could. There are ${100\choose 1} > 2^6$ possible arrangements of a single wolf among 100 sheep. Assign each arrangement a number; express each number in binary (using 7 bits); then perform 7 tests to determine which arrangement is the right one. This is The blood test riddle (number theory) by another name.

However,

if there are two wolves, then I have seen proof that we cannot always do it in the bare information-theoretical minimum number of tests. Suppose we have 6 sheep, two of whom are wolves. There are ${6\choose 2} = 15 \leq 2^{4}$ possible arrangements of two wolves among 6 sheep. But I wrote a little Python script to do a brute-force exhaustive search, and it concluded that there is no way to unambiguously identify the two wolves out of six sheep, using only four blood tests.

This is evidence that the solution to this puzzle probably (but not definitely) requires more than 27 tests.

Still-not-an-answer UPDATE:

According to my new and improved brute-force script,
There is no way to find 2,3,4,5 wolves among 6 sheep in fewer than 5 tests.
There is no way to find 2,3,4,5,6 wolves among 7 sheep in fewer than 6 tests.
There is no way to find 3,4,5,6,7 wolves among 8 sheep in fewer than 7 tests.
There is no way to find 3,4,5,6,7,8 wolves among 9 sheep in fewer than 8 tests.
There is no way to find 3,4,5,6,7,8 wolves among 10 sheep in fewer than 9 tests.

However,

to find 2 wolves among 8 sheep, we don't need 7 tests — we can do it in 6 tests!
Test 1. T . . T T . . . Test 2. T . . . . T T . Test 3. . T . T . T . . Test 4. . T . . T . T . Test 5. . . T . T T . . Test 6. . . T T . . T .

Notice the nice symmetry of the first three columns (sheep), and then what we do with the next four columns in each pair of rows (tests). The eighth sheep doesn't need to be tested at all; we can figure him out by deductive reasoning.

Also, it looks like we can use the exact same series of tests, plus a one-on-one test of the newcomer, to find 2 wolves among 9 sheep in only 7 tests.

So this is evidence that perhaps the original puzzle can be done in fewer than 99 tests!

I also notice that the situation is not symmetrical: we may know a way to find $k$ wolves among $n$ sheep using $t$ tests, but that won't help us at all to find $n-k$ wolves among $n$ sheep. (Under the spoiler tags above, I show one concrete example where $(n, k, t)$ is possible yet $(n, n-k, t)$ is not possible.)

MATH UPDATE:

I don't immediately see this sequence in the OEIS, which is surprising to me. Anyone spot a predictable pattern yet? (Well, the edges are 0, and column 2 is ⌈lg n⌉, and beyond a certain k the entries are all n-1. Which doesn't leave much room for the pattern to reveal itself.) I've got my laptop working on the missing elements as we speak.

k=       1  2  3  4  5  6  ...
      0
n=1   0  0
n=2   0  1  0
n=3   0  2  2  0
n=4   0  2  3  3  0
n=5   0  3  4  4  4  0
n=6   0  3  5  5  5  5  0
n=7   0  3  6  6  6  6  6  0
n=8   0  3  6  7  7  7  7  7  0
n=9   0  4  7  8  8  8  8  8  8  0
n=10  0  4  7  9  9  9  9  9  9  9  0
n=11  0  4  8 10 10 10 10 10 10 10 10  0
n=12  0  4  8 11 11 11 11 11 11 11 11 11  0
n=13  0  4  8  . 12 12 12 12 12 12 12 12 12  0
n=14  0  4  9  . 13 13 13 13 13 13 13 13 13 13  0
n=15  0  4  .  .  . 14 14 14 14 14 14 14 14 14 14  0
n=16  0  4  .  .  . 15 15 15 15 15 15 15 15 15 15 15  0
n=17  0  5  .  .  .  . 16 16 16 16 16 16 16 16 16 16 16  0
n=18  0  5  .  .  .  . 17 17 17 17 17 17 17 17 17 17 17 17  0
n=19  0  5  .  .  .  .  . 18 18 18 18 18 18 18 18 18 18 18 18  0
n=20  0  5  .  .  .  .  . 19 19 19 19 19 19 19 19 19 19 19 19 19  0
$\endgroup$
  • $\begingroup$ Your calculations confirm my suspicions. I was trying to figure out a process to arrive at the heavy-handed hint of 100C5 and 2^27 by assigning each permutation to a single binary number, but that fails miserably. The only saving grace was that 2^27 is almost twice as large as 100C5, so not all binary numbers have to be represented. Alas, I still cannot find a way. $\endgroup$ – Amorydai Apr 15 at 23:10
  • 2
    $\begingroup$ The optimal batch size to test should be 13 because doing so splits the original 100C5 possibilities into 87C5 possibilities if the test comes back negative, and 100C5 - 87C5 if the test comes out positive. 87C5 is 49.6% of 100C5 and it is the closest to 50% that you can get. Part of the reason that the 6C2 problem couldn't be done in 4 tries is because testing a batch of 2 (optimal) splits the problem into 9 if the test comes out positive and 6 if the test comes out negative, thus failing to reduce the problem by 50%. $\endgroup$ – JS1 Apr 20 at 19:47
  • 1
    $\begingroup$ @Quuxplusone, nice to see that you are still working :) $\endgroup$ – Jyotish Robin Apr 20 at 21:21
  • 2
    $\begingroup$ @noedne You're right. I think the problem with my previous statement is that it only works for the case where you can use the result of the first test to formulate the second test. Once the problem is reduced, then the optimal second batch size might be different than the first batch size. If you are forced to submit all batches simultaneously, then the optimal batch size apparently needs to be larger because you need to be testing "both sides" simultaneously, meaning ones you would have ruled out had you been able to see the results immediately. $\endgroup$ – JS1 Apr 21 at 1:16
  • 3
    $\begingroup$ Apparently the name of this problem is "non-adaptive [combinatorial / non-probabilistic] group testing." However, even though some variants of the problem have been well studied, I haven't been able to find any pre-computed tables for the basic problem. (I.e., I haven't found my triangle in any existing resource.) $\endgroup$ – Quuxplusone Apr 25 at 15:13
7
$\begingroup$

My dear king,

I can do it in 99 tests:

I will take a blood sample from 99 randomly choosen 'sheep' and send those 99 blood samples to the doctors.

Then we will wait for the result.

If the results shows 5 wolves, you got them.

Else:

If the results only show you 4 wolves, the 5th wolf is the untested animal.

Sincerely,

your most loyal servant H.Idden (not a wolf)

$\endgroup$
5
$\begingroup$

I'm not sure whether this should be an edit to my original attempt, or a new answer because it is a very different approach. What's the standard practice?

I think it can be done in 35 tests:

Split the population in half, in 7 different ways:
- every alternate sheep
- two sheep then skip two
- four sheep then skip four
- eight sheep then skip eight
- ...
- 64 sheep then skip 64

This gives groups like the following (where 1 means the sheep is selected, 0 means it is not selected):
A 01010101010101010101010101010101 B 00110011001100110011001100110011 C 00001111000011110000111100001111 D 00000000111111110000000011111111 E 00000000000000001111111111111111
Test each group. Shift all the sheep to the right, carry the last sheep around to the front, and repeat the same steps 4 times. This results in 7 * 5 = 35 tests being performed.

A simple example (partly because I'm lazy, and partly because it wraps around too much) of 32 sheep with 3 wolves among them, which requires only 5 tests and 3 iterations:
Iteration 1 = 11000000000000000000000000000001 Iteration 2 = 11100000000000000000000000000000 Iteration 3 = 01110000000000000000000000000000
Where 1 represents a wolf and 0 a sheep, then the test results for each iteration are:
| Iteration 1 | Iteration 2 | Iteration 3 A | Positive | Positive | Positive B | Positive | Positive | Positive C | Positive | Negative | Negative D | Positive | Negative | Negative E | Positive | Negative | Negative
Using these test results, we can narrow down the suspects:
Iteration 1 suspects = All sheep Iteration 2 suspects = All sheep & !C & !D & !E Iteration 3 suspects = All sheep & !C & !D & !E Iteration 1 suspects = 11111111111111111111111111111111 Iteration 2 suspects = 11110000000000000000000000000000 Iteration 3 suspects = 11110000000000000000000000000000
Now when we bring the front sheep of each iteration back to the end to re-align them:
Iteration 1 suspects = 11111111111111111111111111111111 Iteration 2 suspects = 11100000000000000000000000000001 Iteration 3 suspects = 11000000000000000000000000000011 Wolves = I1 suspects & I2 suspects & I3 suspects Wolves = 11000000000000000000000000000001

This still feels wildly inefficient. I'd love to see the OP's answer.

$\endgroup$
  • $\begingroup$ This matches what I was thinking. In one "iteration" of lg N tests, you can find a lone wolf. If you can make 2 independent sheep-to-number mappings, then you can find 2 wolves in 2 iterations of lg N tests. And so on. I couldn't figure out how to construct those mappings, but you show that it's super simple. :) So your method can find K wolves in K lg N tests. Your answer of 35 is not terribly far off the mathematically theoretical minimum of ceil(lg (100 choose 5)) = 27 tests. $\endgroup$ – Quuxplusone Apr 14 at 14:55
  • 1
    $\begingroup$ Why do you think this works? Do wolves in positions 2, 60, and 69 make all tests pass? $\endgroup$ – noedne Apr 14 at 15:39
  • $\begingroup$ Another hint as @Quuxplusone pointed out . 2^27~ 100C5. Consider assigning binary sequence of 0 & 1 for all sets of 5. $\endgroup$ – Jyotish Robin Apr 14 at 15:56
  • $\begingroup$ But I think there is one more step left of how you test. $\endgroup$ – Jyotish Robin Apr 14 at 16:21
  • 5
    $\begingroup$ This solution as presented can give ambiguous results. For example, using your 32 sheep example, if you have wolves in positions 30, 31, 32 - all tests for all iterations will be positive. You might say, well, that just means I can conclude that the wolves are at those positions. However, if the wolves are at positions 29, 31, 32 all tests will also be positive for all iterations. Now you don't know if a wolf is at 29 or 30, so this solution fails. $\endgroup$ – Amorydai Apr 14 at 16:25
3
$\begingroup$

I think this can be done in 39 tests.

Arrange the sheep in a 10x10 grid. Collect a sample from each row, column, and the diagonals in one direction. Once the results come back, draw a line across the grid for each positive test result. When three lines intersect, that's a wolf!
As a quick example, after arranging 25 sheep into a grid, we have the following:
S S W S S S W S S S S S S S S S S S S W S S S S S
This gives us positive test results for rows 1, 2, 4, columns 2, 3, 5, and diagonals (/ starting from the top left) 3, 8.
- 2 3 - 2 - 3 2 - 2 / | | | - 2 2 - 3 | | / |
This shows the wolves where there are 3 overlaps. It also shows the need for the diagonals - there are overlaps of 2 lines, which are just sheep that happen to line up with wolves. Without the diagonals, we wouldn't be able to tell the difference.

Unfortunately, as has been pointed out in the comments, there are some edge cases where this solution does not narrow down the results to only 5 wolves.

W S S W S S W W W
This results in a false positive on all of the sheep.

Edit

I've been thinking more about the maths behind this, and would like to try to refine it. The base line is testing all 100 sheep, which guarantees 5/100 positives and the rest negative.

In my answer above, I divide the sheep into groups of 10, which guarantees 5/10 positives and 5/10 negatives. By doing this, I've halved the number of sheep to search with only 10 samples.
As you can see with the grid example, by splitting the sheep in a different way, i.e. rows instead of columns, I can perform the search again and narrow down to 25 sheep with only 20 tests.

I don't exactly know how to explain what makes the distribution special, but when the sheep are arranged in a grid, I can use the following function to redistribute the sheep into new groups for each test: group(x, y, test) = (x + (y * test)) % 10
(With each iteration, shuffle each row across to the left according to its row number, e.g row 0 stays where it is, row 1 gets shuffled 1 to the left, row 2 gets shuffled 2 to the left).

With this distribution function, we can keep adding iterations to narrow down the suspected sheep, until the number is less than or equal to 5:
suspects = 100 * ((5 / 10) ^ iterations)
In order to be certain, we need to repeat this 5 times, which is 50 tests.

I think this might work for other group sizes as well:
suspects = 100 * ((5 / groups) ^ iterations)

Groups | Iterations | Samples -------|------------|--------- 7 | 9 | 63 8 | 7 | 56 9 | 6 | 54 10 | 5 | 50 11 | 4 | 44 12 | 4 | 48 13 | 4 | 52 14 | 3 | 42 15 | 3 | 45 16 | 3 | 48 17 | 3 | 51 18 | 3 | 54 19 | 3 | 57 20 | 3 | 60 21 | 3 | 63 22 | 3 | 66 23 | 2 | 46

So using this method, with a group size of 14 and 3 iterations, it looks like it might be possible with 42 tests to determine the wolves. However, I haven't managed to prove this, I think I've spent enough time on this puzzle. I also wondered whether it is possible to arrange the sheep in a cube instead of a grid, but I never managed to work it out.

$\endgroup$
  • $\begingroup$ +1! Are the diagonals required? $\endgroup$ – user45266 Apr 14 at 5:12
  • $\begingroup$ Could you elaborate on how the number 39 is obtained. Also more details on how the testing is done can help the reader understand it better. $\endgroup$ – Jyotish Robin Apr 14 at 5:15
  • $\begingroup$ Oops, that's a spoiler, probably should learn that rot13 thing I see everywhere on this site $\endgroup$ – Andrew Williamson Apr 14 at 5:16
  • $\begingroup$ It would be better if you could add the additional info to the answer itself instead of the comment. $\endgroup$ – Jyotish Robin Apr 14 at 5:32
  • 2
    $\begingroup$ Love this solution, but I'm not sure that it's correct. rot13: Vs gurer ner jbyirf ng (1,5), (2,3), (3,2), naq (4,4), gura (1,4) jvyy fubj hc nf n jbys ab znggre jung, fvapr ur'f va gur fnzr ebj, pbyhza, naq qvntbany nf n jbys. $\endgroup$ – cag51 Apr 14 at 6:52
2
$\begingroup$

Following Andrew Williamson theme I wrote a program to experiment with different splits and I found a solution with

$78$ tests

It is worse than @noedne solution, but it is still better than the trivial 99. So I will add my answer.

I number $100$ sheep by $1, 2, 3, ..., 100$ and split them in 6 different ways.

First, into 9 groups - sheep with numbers producing the same quotient when divided by $12$ go into the same group. The other five ways are done modulo $11, 13, 14, 15, 16$ respectively - for each way sheep with numbers producing the same remainder when divided by the corresponding modulus go to the same group. So we have total

$9 + 11 + 13 + 14 + 15 + 16 = 78$ groups.

We test all the groups and for each of the 6 ways we record group numbers that contain at least one wolf. For example if wolves are $ \{22, 28, 56, 66, 77\} $ modulo $11$ groups tests will produce $\{0, 1, 6\}$ result. Turns out that every possible combination of $5$ wolves ($75287520$ - total) produces a different result when all 6 ways are taken into account.

$\endgroup$
-1
$\begingroup$

I don't have a solution, but I might have an approach.

Define 3 binary matrices:

  1. $C$ is a list of all the combinations of 5 out of 100. So it has 100 columns, 75,287,520 rows and each row has 5 trues with the rest false.
  2. $M$ is the measurement matrix which tells you what to measure on a given measurement. Each column tells you which sheep to measure in that test. It has 100 rows and $m$ columns (one for each measurement).
  3. $R$ is the results matrix. It has 75,287,520 rows (one for each possible result) and $m$ columns (one for each test).

Then $C\cdot M = R$. Here we are doing normal matrix multiplication except that instead of multiplying the individual elements we are using the "and" operation, and instead of adding the pairs we are using the "or" operation. In other words:

\begin{equation}R_{i,j} = \cup_{k=1}^{100}(c_{i,k}\cap m_{k,j})\end{equation}

where the $\cap$ refers to the "logical and" operation and the $\cup$ is the "logical or" operation.

What we want is to find a matrix $M$ such that each row of $R$ is unique and $m$ is as small as possible.

Now we can define $R$ to be simply the binary numbers in any order which would make $m=27$.

Then we'd have to find a left inverse of $C$ (using the same matrix operations as define above).

Suppose we can find $C^{-1}_{\mathrm{left}}$, a left inverse of $C$.

Then $M$ = $C^{-1}_{\mathrm{left}}\cdot R$. This would be something like the transpose of @Quuxplusone's matrix for 6 sheep and 2 wolves.

Now, the inverse shoud be $C^{-1}_{\mathrm{left}}=(C^T\cdot C)^{-1}\cdot C^T$.

C is quite a big matrix to inverse and I'm not sure what python would do with binary matrices. But, in theory, this is an approach that could work, assuming $C$ has a left inverse.

Note, that if it does have an inverse, then it can be done in 27 measurements. It would be interesting to try get this working for some of the simpler cases.

$\endgroup$
  • 1
    $\begingroup$ If you substitute multiplication with "and" and addition with "or" C does not have a left inverse. I tried to figure out what the first row of the inverse matrix P would look like based on the fact that the first row of the product P*C should be (1, 0, ..., 0). To get 99 zeros the first row of P should be all zeros, but then there is no way to get the leading 1. $\endgroup$ – ppgdev Apr 18 at 2:44
  • $\begingroup$ I was worried about something like that. Can't figure out how to fix it. $\endgroup$ – Dr Xorile Apr 18 at 5:46
-2
$\begingroup$

I think it can be done in a maximum of 32 tests.

First divide the 100 sheep in groups of 10 and perform 10 tests by mixing them. You would get a maximum of 5 positive result. Now if there are 5 positive results, we would divide the group into two as 5 and 5 and make 5 tests. So now we would have 5 groups with positive result (i.e.) if a group is negative the other batch is positive. Now again divide the group into 3,2 and make 5 more tests. Now we would get 1 group that is positive. Considering the worst case if the group with 3 sheep is positive, we make 2 more tests. That makes a total of 30 tests. But now if there are less than 5 positive results, we divide the group into 10s into 3,3 and 1. This requires and test all the groups of 3s. This would require a maximum of 12 tests. So now we would get a maximum of 5 set of 3s with test positive among this 12 groups, which would require a maximum of 10 test to know the result. So this totals to 32 test maximum.

$\endgroup$
  • 1
    $\begingroup$ You cannot use the results of some tests to decide the next set of tests. You have to set up all the tests simultaneously because of the caveat in the OP: "One caveat is that the test results are available to you after all the tests are done". $\endgroup$ – Jaap Scherphuis May 3 at 7:41

protected by Rubio May 6 at 6:43

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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