Mrthdrb

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,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 (other than the edges which are 0 and column 2 which is ⌈lg n⌉, and I believe I've convinced myself that the right edge is just n-1)? I've got my laptop working on the eleventh row 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

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.

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.

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)

If the results are available after all the tests are done, then I think can do it in minimum of 60 tests with 100% accuracy.

Explanation

I would number everyone from 1-100 and then arrange them in a hypothetical 5x5x4 (Row x Column x Depth) 3-D grid like this one shown here.

[Check out the 3-d grid here]

Then I would make 60 pools total. Three such pools are shown in the image - one for R3 across all Columns (C), one for C3 across all Depths (D) and another for D4 across all Rows (R). The intersection of three pools for each wolf will confirm its location in the grid, and can be identified using the number assigned at that position.

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 $Ccdot 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:

beginequationR_i,j = cup_k=1^100(c_i,kcap m_k,j)endequation

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_mathrmleft$, a left inverse of $C$.

Then $M$ = $C^-1_mathrmleftcdot 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_mathrmleft=(C^Tcdot C)^-1cdot 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.