34
$\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!

Improve this question
$\endgroup$
12
  • 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
    Commented Apr 14, 2019 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
    Commented Apr 14, 2019 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
    Commented Apr 16, 2019 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
    Commented May 8, 2019 at 1:39
  • 2
    $\begingroup$ I have added a solution with 60 tests in the site math.stackexchange (I don't think it's optimal). I don't have enough points to post a solution here. $\endgroup$
    – Elaqqad
    Commented Jan 4, 2020 at 19:54

9 Answers 9

Reset to default
21
$\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.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ Seems convincing to me. Any idea how this could relate to OP's hint about binary representations? $\endgroup$
    – Ergwun
    Commented Apr 17, 2019 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
    Commented Apr 17, 2019 at 16:31
  • 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
    Commented Apr 18, 2019 at 23:22
  • 2
    $\begingroup$ FYI @noedne, I have asked for more information on the math underlying your solution on math.stackexchange here: "Partition a set into g groups, k different ways, such that no pair of elements is ever in the same group together more than M times?" $\endgroup$
    – Quuxplusone
    Commented Apr 21, 2019 at 0:10
  • 3
    $\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
    Commented May 5, 2019 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
Improve this answer
$\endgroup$
7
  • $\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
    Commented Apr 15, 2019 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
    Commented Apr 20, 2019 at 19:47
  • 1
    $\begingroup$ @Quuxplusone, nice to see that you are still working :) $\endgroup$
    – wanderer
    Commented Apr 20, 2019 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
    Commented Apr 21, 2019 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
    Commented Apr 25, 2019 at 15:13
8
$\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)

Improve this answer
$\endgroup$
7
$\begingroup$

I asked a question over on Math.SE, pointing to this puzzle, and @Elaqqad gave a very long answer with lots of links to math that might help. @Elaqqad also produced a concrete solution with only 59 tests — beating @noedne's long-standing solution of 63 tests!

Background math

The "wolves and sheep" puzzle is a specific case of non-adaptive group testing. The problem is exactly equivalent to:

Find the smallest 5-separable matrix with exactly 100 columns.

A "5-separable" matrix is a matrix of 0s and 1s where no two sets of 5 columns have the same bitwise-OR. In terms of wolves and sheep, this is the same as saying that if we know which blood tests came up positive (i.e. we have the bitwise-OR of some 5 columns corresponding to wolves), then we can "decode" those results and deduce exactly which 5 animals (i.e. columns) contributed the positive results (i.e. were bitwise-ORed together).

59 tests: the math part

@Elaqqad's solution starts with a mathematical structure called a $(60,6,1)$-pairwise balanced design. At least I think that's what we have here. I could be wrong. Anyway, I have no insight into how this particular structure was derived.

BaseBlocks = [
    {(0,0,0,0), (0,1,0,2), (0,2,1,0), (1,0,1,1), (1,1,1,2), (1,2,+∞,+∞)},
    {(0,0,0,0), (0,1,0,1), (1,0,0,2), (1,1,0,2), (1,2,1,1), (0,2,+∞,+∞)},
    {(0,0,0,0), (0,1,0,0), (0,2,1,1), (1,0,0,0), (1,1,0,3), (1,2,+∞,-∞)},
    {(0,0,0,0), (0,1,0,3), (1,0,1,3), (1,1,1,1), (1,2,0,3), (0,2,+∞,-∞)}
]
Blocks = [ 
   { (a, b+i, c+j, d+k) for (a,b,c,d) in B }
   for B in BaseBlocks
   for i in {0,1,2}
   for j in {0,1}
   for k in {0,1,2,3}
]

There are exactly 96 blocks in Blocks. Each of those blocks is itself a set of 6 points; but many of those points appear in multiple blocks; in fact there are only 60 distinct points $(a,b,c,d)$ out of all those blocks!

Define the 5-separable matrix $M$ by $$ M_{t,n} = \begin{cases} \text{1}&\text{if point}_t\in \text{block}_n\\ \text{0}&\text{if point}_t\not\in \text{block}_n\\ \end{cases} $$ for each of the 96 blocks (animals) and 60 points (tests). This matrix $M$ is 5-separable, and so we can use it to find 5 wolves among 96 animals using only 60 tests.

To get up to 100 animals, we take our 96 Blocks and add the following 8 more:

Blocks += [ 
   {(0,0,+∞,+∞), (0,1,+∞,+∞), (0,2,+∞,+∞), (1,0,+∞,-∞), (1,1,+∞,-∞), (1,2,+∞,-∞)},
   {(0,0,+∞,-∞), (0,1,+∞,-∞), (0,2,+∞,-∞), (1,0,+∞,+∞), (1,1,+∞,+∞), (1,2,+∞,+∞)},
   {(0,0,0,0), (0,0,0,1), (0,0,0,2), (0,0,0,3), (0,0,1,0), (0,0,1,1), (0,0,1,2), (0,0,1,3)},
   {(0,1,0,0), (0,1,0,1), (0,1,0,2), (0,1,0,3), (0,1,1,0), (0,1,1,1), (0,1,1,2), (0,1,1,3)},
   {(0,2,0,0), (0,2,0,1), (0,2,0,2), (0,2,0,3), (0,2,1,0), (0,2,1,1), (0,2,1,2), (0,2,1,3)},
   {(1,0,0,0), (1,0,0,1), (1,0,0,2), (1,0,0,3), (1,0,1,0), (1,0,1,1), (1,0,1,2), (1,0,1,3)},
   {(1,1,0,0), (1,1,0,1), (1,1,0,2), (1,1,0,3), (1,1,1,0), (1,1,1,1), (1,1,1,2), (1,1,1,3)},
   {(1,2,0,0), (1,2,0,1), (1,2,0,2), (1,2,0,3), (1,2,1,0), (1,2,1,1), (1,2,1,2), (1,2,1,3)}
]

This modification increases the size of Blocks from 96 to 104, and it preserves the magic "PBD-ness" of our block design (again, I have no insight as to why this is so), but it doesn't actually add any more points — we still have 60 points in our "alphabet." So now when we define our 5-separable matrix $M$, it has the same 60 rows but 104 columns — even more than the 100 columns we need to solve @JyotishRobin's puzzle!

Furthermore, it turns out that — as in @noedne's solution — we can just skip at least one of those tests and we'll still be able to use the process of elimination to find the last wolf if necessary. (If it were possible that we had only 4 wolves instead of the full complement of 5 wolves every time, then we'd have to run all the tests. Mathematically, this is the difference between requiring that our matrix $M$ be 5-disjunct or only 5-separable.)

Here is the $59\times 100$ matrix $M$ that I got by following @Elaqqad's algorithm. Each of the 59 rows represents a test; each column represents an animal. Each test $t$ combines blood from the animals $i$ where $M_{t,i} = 1$. For the counting-impaired, the numbers in the left margin simply count up the tests from 1 to 59; the (numbers) in the right margin indicate how many animals are involved in each test. This series of 59 tests can identify the 5 wolves from among our 100 animals.

59 tests: TLDR

The C++ code that produced this diagram is available at github.com/Quuxplusone/wolves-and-sheep.

 1 11111111111.........................................................................................  (11)
 2 1..........1111111111...............................................................................  (11)
 3 1....................1111111111.....................................................................  (11)
 4 1..............................1111111111...........................................................  (11)
 5 1........................................1111111111.................................................  (11)
 6 1..................................................1111111111.......................................  (11)
 7 1............................................................1111111111.............................  (11)
 8 1......................................................................1111111111...................  (11)
 9 .1.........1.........1.........1.........1.........1.........1.........1.........111................  (11)
10 ..1.........1.........1.........1.........1.........1.........1.........1........1..11..............  (11)
11 ...1.........1.........1.........1.........1.........1.........1.........1.......1....11............  (11)
12 ....1.........1.........1.........1.........1.........1.........1.........1......1......11..........  (11)
13 .....1.........1.........1.........1.........1.........1.........1.........1.....1........11........  (11)
14 ......1.........1.........1.........1.........1.........1.........1.........1....1..........11......  (11)
15 .......1.........1.........1.........1.........1.........1.........1.........1...1............11....  (11)
16 ........1.........1.........1.........1.........1.........1.........1.........1..1..............11..  (11)
17 ....1..............1.......1....1................1.....1............1.......1.....1...1.............  (10)
18 ........1......1.............1......1....1.................1.......1......1.........1.1.............  (10)
19 ....1.............1...........1.....1.....1..............1...........1.....1.......1...1............  (10)
20 .....1.....1............1..............1.........1........1.......1..........1.......1.1............  (10)
21 ...1........1.............1.............1....1...........1............1.......1...1.....1...........  (10)
22 .........1.......1.....1...........1..............1.......1..1..............1.......1...1...........  (10)
23 ..........1.....1..........1.......1............1...........1.1..........1.........1.....1..........  (10)
24 ......1...........1..........1.......1.......1.......1.......1.................1.....1...1..........  (10)
25 ......1.............1.......1.....1........1...............1..1..............1....1.......1.........  (10)
26 ..........1.1................1........1........1...1............1...........1..........1..1.........  (10)
27 ........1....1........1.................1.........1.....1.......1............1.....1.......1........  (10)
28 .........1.1..................1......1........1.......1.......1...............1.......1....1........  (10)
29 ..........11................1....1..........1............1.......1..............1...1.......1.......  (10)
30 ..1................1.1..................1..1..............1........1.......1.............1..1.......  (10)
31 .......1...........1.....1.......1.......1..................1...1.............1......1.......1......  (10)
32 ........1...........1......1...........1..1..........1...........1.....1................1....1......  (10)
33 ...1............1...........1..1..................1....1.............1....1..........1........1.....  (10)
34 .1.............1..............1.......1....1................1.....1.....1...............1.....1.....  (10)
35 .........1....1......1...........1........1.............1...........1..........1..........1...1.....  (10)
36 .....1.......1...............1..1...............1.....1...............11....................1.1.....  (10)
37 .1................1......1........1..............1......1.............1..1..........1..........1....  (10)
38 ...1...........1......1................1......1....1................1...........1........1.....1....  (10)
39 ......1............1...1..............1.....1.......1................1.1...................1...1....  (10)
40 .........1..1...........1......1................1..........1...1...........1.................1.1....  (10)
41 .......1......1........1........1............1.............1......1.............1..1............1...  (10)
42 .1..............1.......1...............1......1....1............1.............1......1.........1...  (10)
43 ..1..............1........1............1.1............1..............1...1................1.....1...  (10)
44 ....1...............1....1...........1............11...........1........1...................1...1...  (10)
45 .....1...........1....1.............1.......1...............1..1...............1..1..............1..  (10)
46 .......1............11.............1..........1.....1.................1...1............1.........1..  (10)
47 ..........1...1...........1....1.................1...1.............1....1..................1.....1..  (10)
48 ..1..........1................1...1............1.......1.....1..................1............1...1..  (10)
49 ...1..........1..........1..........1..........1..........1...1........1..........................1.  (9)
50 ........1...1........1...............1......1..........1..........1......1........................1.  (9)
51 .1...............1..........1...1.............1......1..........1..........1......................1.  (9)
52 ....1..........1..........1......1..............1...1........1...............1....................1.  (9)
53 .........1..........1........1..........1........1..........1........1..........1.................1.  (9)
54 ..................................................................................1.1..1.1.1.11.1.1.  (9)
55 ......1......1..........1..........1.....1...............1..........1...1..........................1  (9)
56 ..1........1...............1..........1......1..........1......1..........1........................1  (9)
57 .......1..........1...1........1...........1..........1..........1..........1......................1  (9)
58 ..........1........1..........1........1..........1........1..........1........1...................1  (9)
59 ...................................................................................1.11.1.1.1..1.1.1  (9)
Improve this answer
$\endgroup$
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.

Improve this answer
$\endgroup$
11
  • $\begingroup$ +1! Are the diagonals required? $\endgroup$
    – user45266
    Commented Apr 14, 2019 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$
    – wanderer
    Commented Apr 14, 2019 at 5:15
  • $\begingroup$ Oops, that's a spoiler, probably should learn that rot13 thing I see everywhere on this site $\endgroup$
    – Andrew Williamson
    Commented Apr 14, 2019 at 5:16
  • 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
    Commented Apr 14, 2019 at 6:52
  • 1
    $\begingroup$ @cag15 unfortunately you're right. In some scenarios, this solution will only narrow it down to the 5 wolves and four sheep $\endgroup$
    – Andrew Williamson
    Commented Apr 14, 2019 at 7:11
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Apr 14, 2019 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
    Commented Apr 14, 2019 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$
    – wanderer
    Commented Apr 14, 2019 at 15:56
  • $\begingroup$ But I think there is one more step left of how you test. $\endgroup$
    – wanderer
    Commented Apr 14, 2019 at 16:21
  • 7
    $\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
    Commented Apr 14, 2019 at 16:25
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.

Improve this answer
$\endgroup$
0
$\begingroup$

@noedne's answer from the beginning struck me as a good one, but I have recently come to the conclusion that it is also the optimal answer. I'll be first to admit that I don't understand everything going on, but I feel the need to at least try and explain it.

The basic strategy that yields the 99-test solution isn't complicated. We don't want any one test to have any sheep in common with any other test, thus one test per sheep. We get to use 99 tests instead of 100 because the last test becomes moot.

The advanced strategy is to let us allow tests that have at most 1 sheep in common with any other test. Not just that, but we still want tests that have no sheep in common as much as possible. @noedne made a set of patterns that did this. Each block represents a set of tests that have no sheep in common with eachother. Beyond a single block, no two tests would have more than a single sheep in common.

The next strategy up would be to allow at most 2 sheep in common between tests... this is where I was dabbling for a while until I realized how ineffective it was. Clearly, it isn't preferred for 100 sheep.

Assume, then, we want to optimize the "at most 1-sheep in common" strategy. The place where it is most "powerful" is when the blocks are square and they cover every sheep once. Technically, that's "every sheep except one" because it ends up being okay to always leave one sheep out of the testing. I'm having trouble explaining why being "square" is optimal, but it seems obvious having played with it for a while.

Next, how many test blocks do we need before the combinations become unique? Again, I don't know why, but the answer is definitely based on how many wolves the problem contains. Every time you add a wolf to the mix, you need an additional block to make the combinations unique. If you never experimented with other #'s of wolves you may never have noticed.

Additionally, as @noedne noted in the 1st update, you don't actually need the last test you run. It ends up being moot, exactly like it did in the first, simple, strategy. Why? I have no idea, but I suspect magic.

enter image description here

So this is how I fill in the chart representing best-possible scenarios. The blocks are square, so sheep per test = tests per block. We always need one block more than the # of wolves. Then the # of tests we need to make unique combinations is tests per block x required blocks - 1. This chart only includes prime numbers of sheep per test because that's what @noedne's pattern works for. None of these scenarios reflect the "100 sheep" condition we are given in the question, but for their respective sizes (max sheep) they must be optimal because everything is as good as it could be.

You maybe noticed that for small test sizes the required tests are actually worse than what the simple strategy would have given you. That means we know there's a cutoff for where the advanced strategy is better. (This is why I suspect there's also a cutoff for when the third strategy would be better)

enter image description here

So we can adjust the # of wolves in these smaller cases to something smaller, and then the 2nd strategy becomes best again. This is nice to know because it makes for some puzzles you could try by hand, instead of trusting a computer program.

enter image description here

So here's where things get interesting. The 11x11 blocks would allow you to solve a 121-sheep problem using 65 tests. Sounds familiar? That's @noedne's answer after his first update. But we see it is inefficient, because there's a theoretical 10x10 block good for 101 sheep, and it will solve in 59 tests. The problem is that 10 isn't prime and @noedne's pattern doesn't work for it. @noedne's pattern isn't itself a requirement, though, and we shouldn't exclude the possibility that 10x10 could still somehow work.

But getting 6 blocks of 10x10 tests is quite impossible, according to the requirements of the 2nd strategy: tests within blocks have nothing in common with each other, and tests from anywhere have no more than 1 sheep in common. I can get 3 blocks of 10x10, and maybe I would believe somebody could get a 4th block with enough effort... maybe. It isn't enough either way and that's why 10x10 blocks will never be a reality. I would comfortably say 59 tests is the lower bound, however, since it would have been optimal if it were possible. Edit: It seems that OEIS A001438 nearly confirms that 10x10 doesn't work for us. There is a conjecture on that page that a(10) = 2 which would translate to 4 total blocks for us.

So lastly we need to address @noedne's 2nd update. The gist of it is that @noedne was using 9x11 blocks, which covers the required 99 sheep in testing. This also means an 11x9 block would work as well. @noedne swapped out just one block, and it didn't break the requirements. I used my program to test this idea, and it does indeed check out.

If you could show that a second 11x9 block could be swapped without breaking the requirements, then the total tests would drop to 61... a not unbelievable number. Even if you managed it, at some point you would lose definition, after all the theoretical 9x9 block scenario isn't itself good for 100 sheep.

That's everything I've got. I know it has lots of holes, and maybe somebody could help me fill them if they were interested. A lot of this is beyond my reasoning. I think I'm burned out on it now, so I'm going to stop.

Everything below is what I said the first time-around. It is of no importance.

Sorry I'm late to the party but this question is fun and I think I have something to add but not an answer, sorry. @ppgdev suggested I look at this question, and they seem to be right a lot so here I am.

enter image description here

I've been focusing on thinking of every test as being effectively random, without trying too hard to build specific patterns like @noedne and others had.

Each row is labeled with every possible combination of wolves among the sheep (there are over 75 million). Each column is labeled by every test we have designed (hopefully less than 99). At the intersection of every wolf combination and test there is a definite binary output of whether the test was positive or negative. Each row of binary outputs can be thought of as a code that will help us determine the uniqueness of each of the 75 million+ combinations. @Razvan Socol said that he wrote a program in C# that proved @noedne's solution had unique "66-bit results" for every combination. I'm calling them codes, but we are talking about the same thing.

As others have mentioned, the smallest number of bits to make a unique code for every combination is 27. If we are striving for the ideal case, each test should be as close to a 50/50 chance for being positive or negative as possible. Testing 13 sheep at a time is the best in this regard, though I can't claim it is the ideal strategy. Having nothing else to go on, I will use it and I know the split for testing 13 sheep is roughly 49 negative outcomes for every 51 positive outcomes, and this still allows (barely) for 27 tests to encode all combinations.

So the next problem is that each test isn't going to quite perfectly split up everything before it. The first few tests should do fine, but as we start testing sheep that were (in some way) together before, the "power" of each test is going to start diminishing. How much weaker the tests get over time is difficult to even estimate, not without a fancy computer algorithm (I would assume).

Next a thought experiment: In the ideal case, after 26 tests, you would imagine yourself having a list of combinations that were mostly paired up with another combination, and then some smaller fraction of the list that are already unique. You would think that this means we just need to find one near-perfect test that breaks up all of those pairs, and then we will be done. But think for a second, if we chose a test that was 13 sheep at random, it would break up roughly half of those pairs, and certainly not all of them. We could try guessing at new tests all we like, but finding a test that breaks them all apart is kind of like flipping a coin a few million times and getting all heads. Can you do better than halving the pairs every time? Sure, probably, but it won't be anything terribly game-changing. The problem is that this suggests the amount of tests to break up "mostly pairs" is nearly equivalent with the number of tests it took to get there. This suggests a realistic answer is something closer to 50 tests, and that's without considering that tests are getting weaker all the time.

So if you're thinking 63 tests isn't a great answer I would contend that it actually is. Between weakening tests and that the problem is nearly twice as hard as it seems on the surface, I would say 63 looks really good.

I am, in spite of the above, going to write out a plan to randomly generate a "decent" set of tests:

@Razvan Socol already did a lot of this, presumably. We have 75 million+ combinations and something like 63 tests, then we know we are calculating those binary outputs many billions of times. We have to be somewhat efficient. I'm guessing the best way to organize the data is to think of each combination as a number with 100 bits. Each wolf being a "1" and regular sheep are "0". Every test we perform is the same 100 bits but this time the "1" represents which sheep are being tested. There is a bitwise "and" operation that should be fast and will let us compare each number, outputing a 0 if both have nothing in common.

I am using 13 random sheep in each test. Maybe we could have a little program making sure we aren't using the same sheep in the same test, or using one sheep too often in general. Every time we add a test to my list and calculate the binary outputs, we must solve for the following metrics:

What is the size of the largest grouping of codes (the rows)?

How many groups of that size exist? (This breaks a tie)

I hope you see where I'm going. Try a number of random tests, keep the one that worked the best (minimizes the metric). Keep doing that until all combinations are unique. I would assume that earlier tests aren't terribly important and that later tests deserve much more computing time. Even if somebody writes that code (I might try but this is so far beyond me) and even if the process doesn't have an absurd run-time (it will), do I think it will beat 63? Not really, no.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Here is a 59-test solution, which shows that 63 is not the lower bound, and therefore no amount of verbiage can possibly explain why 63 should be the lower bound. $\endgroup$
    – Quuxplusone
    Commented Jan 21, 2020 at 16:32
-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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Apr 18, 2019 at 2:44
  • $\begingroup$ I was worried about something like that. Can't figure out how to fix it. $\endgroup$
    – Dr Xorile
    Commented Apr 18, 2019 at 5:46

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