
about "Bad King"
This is actually set up a onetoone 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
