strategy - Wolves and sheep

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!

Answer

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.