5
$\begingroup$

The problem is formulated here. And it is also discussed here (the chosen answer to which I don't understand). I've found a few other links on this site (e.g. this), but they don't provide any explicit procedure.

My question is: what is the testing procedure for hitting the lower bound of 43 servants/rats needed to discover two poisoned objects out of 1000?

$\endgroup$
  • $\begingroup$ Maybe if you wrote a detailed description of what you find confusing. I found Ori Gurel-Gurevich's answer at MO easy to understand and, up to constants, it's tight. $\endgroup$ – Louis Jan 27 '12 at 17:16
  • $\begingroup$ @Louis I think the OP is interested in particular in optimal solutions. $\endgroup$ – Listing Jan 27 '12 at 19:37
  • $\begingroup$ @Louis Yup, as Listing said, I'd appreciate a concrete, step-by-step construction for a test which can discover the two objects with only 43 rats. Furthermore, I'm not a mathematician (I'm a hobbyist) so Gurevich's answer doesn't make much sense to me at a purely mathematical level, but that's a different issue. I can at least follow a step-by-step procedure. $\endgroup$ – JasonMond Jan 27 '12 at 20:07
2
$\begingroup$

Look again at the following url that you mentioned in your question. Now the post has been updated with explicit procedures. You can number the wines, run the tests as specified, check the results and determine the 2 poisons. Hope that helps.

Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints

Also look at Identifying 2 poisoned wines out of 2^n wines for a easier, guided explanation on how it can be solved using $6n$ tests given $2^n$ wines.

$\endgroup$
0
$\begingroup$

Frankl and Füredi actually prove a stronger result than what they state in their theorem. They actually prove that if $f(n)$ is the number of wines that can be tested with $n$ rats, then $f(4n) \leq 2^n$. This means that only $40$ rats are needed to test $1024$ wines. I'll try to explain their construction in a more accessible way.

The $40$ rats are divided into $4$ groups of $10$ called $A$, $A'$, $B$, and $B'$. In each group, the rats are numbered from zero to nine. As with the single poison problem, the bottles of wine are each labled with a pattern of ten zeros and ones.

For the rats in group $A$, we proceed as in the single poison problem. Rat $a_i$ is fed wine $[w_0, \dots, w_9]$ if $w_i = 1$.

For the rats in group $A'$, we do the opposite. Rat $a_i'$ is fed wine $[w_0, \dots, w_9]$ if $w_i = 0$.

Let's examine what this gains us. Suppose the poison wines are $p = [p_0, \dots, p_9]$ and $q = [q_0, \dots, q_9]$. Rat $a_i$ dies if and only if $p_i = 1$ or $q_i = 1$. In other words, from the results in group $A$ we have learned the bitwise-or of $p$ and $q$. Similarly, rat $a_i'$ lives if and only if $p_i = 1$ and $q_i = 1$. So from the results in group $A'$ we have learned the bitwise-and of $p$ and $q$. We can put together the bitwise-or and the bitwise-and to get the bitwise-exlusive-or. Call this $a$.

This is a good piece of information, but it isn't enough to solve the whole problem. To get the other half of the information, some more advanced algebra is used. The wines are identified with a more complicated structure called $GF(2^{10})$, the finite field with $2^{10}$ elements. The importants parts of this structure are that is a field (a structure where we can add, subtract, divide and multiply) and that it can be represented by vectors of ten elements of the two-element field. (The two-element field is the same as the integers modulo 2 with $1 + 0 = 0 + 1 = 1$ and $1 + 1 = 0 + 0 = 0$.) (Also, note that the field multiplication doesn't come from any usual vector product -- one example will be given later.) This gives us a natural identification between our wines and $GF(2^{10})$ via the ten element vectors we have already used to label the wines.

So, considering our $p, q \in GF(2^{10})$, we have deduced $p + q = a$ from the first twenty rats, as the sum of vectors over the two-element field is the same as a bitwise-exclusive-or. But we need a second equation so we can solve for two unknowns. A natural choice turns out to be $p^3 + q^3 = b$ for some constant $b$ (which we will later caculate from the rats in $B$ and $B'$). We will be able to solve this system of equations in $GF(2^{10})$ as follows (using the fact that in $GF(2^{10})$ anything plus itself is zero):

$$ b = p^3 + q^3 = (p + q)(p^2 - pq + q^2) = (p + q)(p^2 + pq + q^2) = (p + q)(p^2 + 2pq + q^2 - pq) = (p + q)[(p + q)^2 - pq] = a(a^2 - pq) $$ $$ pq = \frac{b}{a} - a^2 $$

There's not an explicit single formula for $p$ or $q$ due to symmetry, but given these explicit formulae for $p + q$ and $pq$, then we can find $p$ and $q$ as the two roots of $x^2 - (p + q)x + pq = x^2 - ax + \frac{b}{a} - a^2 = 0$.

We can find $p^3 + q^3$ the same way we found $p + q$ using the remaining twenty rats.

For the rats in group $B$, we feed rat $b_i$ wine $w$ if $(w^3)_i = 1$ and for rats in group $B'$, we feed rat $b_i'$ wine $w$ if $(w^3)_i = 0$. We can then similarly construct $b = p^3 + q^3$ as we did in the case with $A$ and $A'$.

For the sake of example, I'll give a concrete way of representing $GF(2^{10})$ as $GF(2)[x]/(x^{10}+x^3+1)$. $GF(2)$ is the finite field with two elements which is the same as the integers modulo $2$. $GF(2)[x]$ is the polynomials with coefficients in $GF(2)$. Dividing by that (irreducible) polynomial means that polynomials of degree $10$ or higher are going to get simplified by applying the equation $x^{10}+x^3+1 = 0$ (equivalent to $x^{10}=x^3+1$). (As an aside, this is sort of analogous to constructing the complex numbers by taking real polynomials and dividing out $x^2+1$.) Our vectors then represent the polynomials' coefficients so, for example, $p = p_9 x^9 + \dots + p_2 x^2 + p_1 x + p_0$.

Then, for example, we can calculate which rats will get wine $[0, 0, 1, 1, 0, 1, 0, 1, 1, 1]$. For group $A$, we match the ones to get rats $a_2, a_3, a_5, a_7, a_8, a_9$. For group $A'$, we match the zeroes and get $a_0', a_1', a_4', a_6'$. For the other two groups, we need to cube the wine. The corresponding polynomial is $x^9 + x^8 + x^7 + x^5 + x^3 + x^2$. Cubing, we get:

$$ (x^9 + x^8 + x^7 + x^5 + x^3 + x^2)^3 = x^{27} + x^{26} + x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{16} + x^{14} + x^{13} + x^8 + x^7 + x^6 = (x^3 + 1)^2(x^7 + x^6 + x^4 + x^3 + x^2 + x + 1) + (x^3 + 1)(x^9 + x^6 + x^4 + x^3) + x^8 + x^7 + x^6 = x^{13} + x^{10} + x^9 + x^6 + x^2 + x + 1 = (x^3 + 1)(x^3 + 1) + x^9 + x^6 + x^2 + 1 = x^9 + x^2 $$

From this we can see that in group $B$ the wine will go to $b_2, b_9$ and in group $B'$ it will go to $b_0', b_1', b_3', b_4', b_5', b_6', b_7', b_8'$.

Note that the proof only gives a lower bound of $1024$ wines testable with $40$ rats. It may be possible to test more wines with $40$ rats, or to test $1024$ wines with fewer rats.

$\endgroup$
-1
$\begingroup$

A054961 shows 27 rats are enough. In the link there's a C code to search a result to use 27 rats to find out the 2 poisoned bottles out of 1090. The code tries to evolute to a better solution removing some candidate wines and redistribute them among rats randomly again.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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