Fog Creek Software
Discussion Board




about "Bad King"

This is actually set up a one-to-one mapping from set N = {1,2,3,...,1000} to set S= 2^{k1,k2,..., k10}

Here S={ null set, {k1}, {k2},..., {k10}, {k1,k2}, {k1,k3}, ...,{k9, k10}, {k1,k2,k3} ..., ..., {k1,k2,...,k10}}

|S|= C(10,0) + C(10,1) + ... + C(10,10) = 2^10=1024 >1000, so the mapping could be settled as follows:

1 -> {}  means bottle 1 will not be tested by anybody;
2-> {k1}          bottle 2 will be tested by prisoner 1;
3-> {k2}
...
11->{k10}

12-> {k1,k2}
13-> {k1,k3}
...
...

Since each bottle corresponding to a unique combination of prisoners, in one month after the testing, just checking the dead people match which bottle's signature will identify the poisoned bottle.

Yu Wang
Friday, February 28, 2003

*  Recent Topics

*  Fog Creek Home