Ttdfjt

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.

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.

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

There are $100choose 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 $100choose 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 $6choose 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 wolves among 9 sheep in fewer than 8 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.

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.)

Here's my shot at it:

Pool 50 of the sheep. Of those 50, if the result comes back positive (wolf detected), split in half again, testing 25 pooled together. If this comes back positive, either 12 or 13 ofthe positive group. You see where this is going. Any negative results rule out all sheep in that group. Worst case scenario, it takes 54 tests (see image for explanation). Best case scenario, you get 14 tests. Price range: 14,000 - 54,000 dollars.

Not sure yet of the expected average, but I know this is better than 99 tests on average.

Diagram:

If this isn't the optimal solution, then my best bet on how to improve it would be to:

split into 1/5 the size of each group.

EDIT: Apparently, you can only do all your tests in one step. So that means you need 99 tests (the last one is obvious, it's either the 95th sheep or the 5th wolf), unless I'm missing something. Cost: $99,000.

I can do it in about 28 tests.

As Quuxplusone pointed out, for 5 wolves hiding among 100 sheep, there are $100 choose 5 approx 2^26.2$ scenarios. Thus you need at least 27 tests.

$ $

To solve this, we essentially perform 5 binary searches, each to find the first remaining unidentified wolf. But we don't want to simply split the group in half; there is about a 97% chance that the first wolf is in the first 50. The key is to recognize that the goal of each step in a binary search is not to cut the group in half, but to cut the number of scenarios in half.

$ $

If we test $n$ animals out of 100, of which 5 are wolves, then the probability of getting a "no" is $P(n;5,100) = 100-n choose 5 over 100 choose 5$. The goal is to select $n$ so that ratio is as close to 50% as possible. Also, if $n$ is not too large, then if the answer is yes, the odds are good that there is only one wolf in the test group, so a standard binary search is the best way to identify the wolf within the group. For efficiency, $n$ should always be a power of 2.

$ $

For 100 sheep, the first $n$ should thus be 16. A "no" answer would reduce the number of possibilities from 75 million to 30 million. While 13 would give a more exact split (37 million), a binary search on 13 animals takes as many tests as a binary search on 16, so we might as well test 16.

$ $

If the answer is no, we would test the next 16, where a "no" would reduce the number of possibilities to 10 million. As long as we kept getting "no", we could continue testing at 8, 8, 8, 8, 4, 4, 4, 4, 2, 2, 2, 2. After that we would be down to 12 animals and there would be no point in testing more than one at a time. Thus, if all 5 wolves are among the last twelve, that would lead to 21 to 25 tests.

$ $

Far more likely is the chance that some of the tests would yield "yes". There's an 87% chance that one of the first two tests would yield "yes". That would identify the first wolf as one of a group of 16. A standard binary search (first 8, then first 4 of one half, etc.) takes 4 more tests to identify the first wolf.

$ $

A side-effect of this approach is that once the first wolf is identified, all earlier animals are known to be sheep (because they were each part of a group that tested no). Worst case scenario is where the first animal is a wolf, in which case we took 5 tests to determine that, but learned nothing else.

$ $

Once we have determined the first wolf, we continue with the remaining wolves. Worst case is we have 99 more animals, of which 4 are wolves. In this case, testing 16 animals would cut the remaining scenarios roughly in half. Etc.

$ $

If the first three wolves are the first three animals, it would take 15 tests to identify them and learn nothing else. We then have 97 more animals, of which 2 are wolves (a total of 4656 combinations). We would want to test more than 16 animals to split the scenarios effectively. Testing 32 would split the scnearios to 2080 for no, or 2576 for yes.

$ $

The goal is that each "no" should reduce the set of remaining scenarios to less than half the previous. Each "yes" would then be followed by a binary search of several tests which each cut the number of scenarios almost exactly in half. Thus, we should be able to remain very close to the ideal number of tests.

$ $

A possible worst case, where we learn the minimum amount from each test, is when the wolves are the first 5 animals, yielding "yes" answers every time. That would take 5 tests to identify the first wolf, 5 more to identify the second, 5 to identify the third, 6 to identify the fourth, and 7 to identify the last, for a total of 28 tests.

It is possible that there is a scenario that requires more than 28 tests, but we would have to go through thousands of scenarios to check each to see which is worst. In any case, it should not be worse by more than one or two additional tests.