Recreational Mathematics – Identifying 2 Poisoned Wines out of 2^n Wines

puzzlerecreational-mathematics

This problem has been asked and discussed in following posts:

There are better optimized solutions to this problem. But, for easy comprehension, I formulated following solution with 6n tests (for $2^n$ wines). Are there any loop holes in it?

Part-I
Let's say there are $2^5$ (=32) wines. Represent them using binary system using 5 bits:

     A-B-C-D-E

Give wines with A=$0$ to one person. Give wines with A=$1$ to another person. Do such tests for all bits (10 tests). Let's say you got a result like the following:

     (0|1)-(0)-(1)-(0|1)-(0|1)

Bits B&C have fixed values (B=$0$. C=$1$). Bits A,D,E have two probable values each. The solution must be one from the following enumerations (Two solutions if you count both (a,b) and (b,a)). We represent the solutions in binary/decimal forms for clarity. It is easy to prove that they are just pairs of numbers with a constant sum (=27 in our case).

     (00100, 10111) = (4,23)
     (00101, 10110) = (5,22)
     (00110, 10101) = (6,21)
     (00111, 10100) = (7,20)
     (10100, 00111) = (20,7)
     (10101, 00110) = (21,6)
     (10110, 00101) = (22,5)
     (10111, 00100) = (23,4)

Part-II
Renumber the wines from (0,1,2,3,4,5 …) to (0,1,4,9,16,25 …) and put them into a bigger set of size $(2^5)^2$=$2^{10}$=1024 (We are squaring the numbers). Only 32 of the 1024 will be actual wines. Fill the rest of them with water.

Repeat the tests similar to that ones from Part-I on this bigger set (2*10=20 tests). This will give another set of solutions. Ignore all the solutions which contain water in one or both the bottles. Only the pair that matches with the corresponding pair from Part-I will be the actual solution (Two solutions if you consider duplicates).

If you get these from Part-I: $$(a,b),(c,d),(e,f),(f,e),(d,c),(b,a)$$
and if you get these from Part-II: $$(a^2,b^2),(g^2,h^2),(c^2,i^2),(i^2,c^2),(h^2,g^2),(b^2,a^2)$$

then the solution must be (a,b).

The reason is: Part-I satisfies $x+y=c1$, and Part-II satisfies $x^2+y^2=c2$. Given that x>=0 & y>=0, there is only one solution that satisfies these conditions (two solutions if you consider duplicates).

Number of tests required for $2^5$ wines with 2 poisons = $2*5 + 2*(2*5)$ = 30.
Number of tests required for $2^n$ wines with 2 poisons = $2*n$ + $2*(2*n)$ = $6n$.

Best Answer

If $$a+b=c+d$$ and $$a^2+b^2=c^2+d^2$$ then $a=c$ and $b=d$ is not always true. Let $$a=1\quad b=2 \quad c=2 \quad d=1$$ and note that $a\neq c$ and $b\neq d$.

So your test may work, but not for the reason you specified. For example, let there be $4$ wines labelled $0,1,2,3$ and let the wines $0,3$ be poisoned. In binary this is $(00,11)$. Your first test yields the solutions $$00,11\quad 01,10$$ Squaring, we have the wines labelled $0,1,4,9$ with the wines $0,9$ poisoned. In binary this is $(0000,1001)$. Your second test yields the solutions $$0000,1001\quad 0001,1000$$ which is $0,9$ and $1,8$. The last pairs are not perfect squares, yielding the solution $0,9$.

Squaring uniquely identifies which solution is correct because only two pairs of integers can satisfy $x+y=k_1$ and $x^2+y^2=k_2$, as these are the equations of a line and circle and can only intersect at two points. The two pairs are always mirrored solutions $(a,b)$ and $(b,a)$. These are the same two poisoned wines, so the test works.

Related Solutions

Recreational Mathematics – Logic Problem of Identifying Poisoned Wines

I asked this question on MathOverflow and got a great answer there.

For $k = 2$ I can do it with ${\lceil \log_2 N \rceil + 2 \choose 2} - 1$ servants. In particular for $N = 1000$ I can do it with $65$ servants. The proof is somewhat long, so I don't want to post it until I've thought about the problem more.

I haven't been able to improve on the above result. Here's how it works. Let $n = \lceil \log_2 N \rceil$. Let me go through the algorithm for $k = 1$ so we're all on the same page. Number the wines and assign each of them the binary expansion of their number, which consists of $n$ bits. Find $n$ servants, and have servant $i$ drink all the wines whose $i^{th}$ bit is $1$. Then the set of servants that die tells you the binary expansion of the poisoned wine.

For $k = 2$ we need to find $n$ butlers, $n$ maids, and ${n \choose 2}$ cooks. The cooks will be named $(i, j)$ for some positive integers $1 \le i < j \le n$. Have butler $i$ drink all the wines whose $i^{th}$ bit is $1$, have maid $i$ drink all the wines whose $i^{th}$ bit is $0$, and have cook $(i, j)$ drink all the wines such that the sum of the $i^{th}$ bit through the $j^{th}$ bit, inclusive, mod 2, is $1$. This is how the casework breaks down for butlers and maids.

If both butler $i$ and maid $i$ die, then one of the poisoned wines has $i^{th}$ bit $0$ and the other has $i^{th}$ bit $1$.
If only butler $i$ dies, then both of the poisoned wines have $i^{th}$ bit $1$.
If only maid $i$ dies, then both of the poisoned wines have $i^{th}$ bit $0$.

The second two cases are great. The problem with case 1 is that if it occurs more than once, there's still ambiguity about which wine has which bit. (The worst scenario is if all the butlers and maids die.) To fix the issue with case 1, we use the cooks.

Let $i_1 < ... < i_m$ be the set of bits where case 1 occurs. We'll say that the poisoned wine whose $(i_1)^{th}$ bit is $1$ is wine A, and the other one is wine B. Notice that the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine A mod 2 is the same as the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine B mod 2, and we can determine what this sum is by looking at whether cook $(i_1, i_2)$ died. The value of this sum determines whether the $(i_2)^{th}$ bit of wine A is 1 or 0 (and the same for wine B). Similarly, looking at whether cook $(i_j, i_{j+1})$ died tells us the remaining bits of wine A, hence of wine B.

One last comment for now. The lower bound is not best possible when $k$ is large compared to $N$; for example, when $k = N-1$ it takes $N-1$ servants. The reason is that any servant who drinks more than one wine automatically dies, hence gives you no information.

[Math] Make $21$ out of $1,5,6,7$ (challenge).

See Generate a number by using a given list of numbers and arithmetic operators

This is an adjusted part of the answer from Ray

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from fractions import Fraction

L=[Fraction(1),Fraction(5),Fraction(6),Fraction(7)]
O={'+':10,'-':10,'*':10,'/':10}
N=Fraction(21)

P = {'+':lambda x,y:x+y,
     '-':lambda x,y:x-y,
     '*':lambda x,y:x*y,
     '/':lambda x,y:x/y}

def postfix_search(rest, stk):
    if len(stk) >= 2:
        y = (v2, r2) = stk.pop()
        x = (v1, r1) = stk.pop()
        for opr in O:
            if O[opr] > 0 and not (opr == '/' and v2 == 0):
                stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
                O[opr] -= 1
                if postfix_search(rest, stk): return 1
                O[opr] += 1
                stk.pop()
        stk += [x, y]
    elif not rest:
        v, r = stk[0]
        if v == N: print(r)
        return v == N
    for x in list(rest):
        rest.remove(x)
        stk += [x]
        if postfix_search(rest, stk):
            return True
        stk.pop()
        rest += [x]

if __name__ == "__main__":
    postfix_search(list(zip(L, map(str, L))), [])

Run

$ ./generate.py
(6/(1-(5/7)))

My ideas with arbitrary functions

$\varphi$ is Eulers totient function

$\varphi(5 \cdot 6-7)-1 = \varphi(23)-1 = 22-1 = 21$
$\varphi((1+7) \cdot 6)+5= \varphi(48)+5=16+5=21$

Best Answer

Related Solutions

Recreational Mathematics – Logic Problem of Identifying Poisoned Wines

[Math] Make $21$ out of $1,5,6,7$ (challenge).

My ideas with arbitrary functions

Related Question