Fog Creek Software
Discussion Board




bad king

Actually, even though 10 prisoners are needed to test the wine, not all of them will die if the testing method in the solution is used (at most, nine will).  Also note that even if there were 1024 bottles, the testing method would work (number the bottles beginning with zero), so the solution text isn't entirely accurate.

Philipp Rumpf
Saturday, April 19, 2003

Try this solution:

1. The kind will create a bottle holder in the form of a cube cabin, such that there are 10 shelves and each shelf has 100 bottles arranged like a 10x10 square.

2. The first day prisoners 1-10 sip all 100 wine bottles from one shelf each.

3. The second day prisoners sip all 100 winbottles on one lengthwise line, 10 from each shelf.

4. The third day prisoners sip all 100 wine bottles on one breadthwise line, 10 from each shelf.

5. On the 30th day one person will die surely. This will indicate the shelf on which the poisoned bottle was located.

6. On the 31st day 2things might happen:
a. Another person might die. Which gives an indication of which of the lengthwise line contains the wine bottle.
b. No one might die. Which gives an indication of the lengthwise line that was drunk by the previously dead person which contains the poissoned bottle.

In either case we now know that the poisonned bottle is on a particular shelf on a particular lengthwise line.

7.On the 32nd night 2 things might happen.
a. Another person(third) might die, which gives clearly an indication of which exact bottle is poisonned. (Solution will work for such a case).

b. No one might die, which might be attributed to 2 things:

i. the poisonned bottle to line in one of the 2 lines (the breadthwise line that was sipped by the first person to die, ii. the breadthwise line that was sipped by the second person to die).

Can people think in these lines ....

Thanks
Guru

Guru Sarma
Monday, July 07, 2003

Similar solution, but here's how I did it...

I would use a 3-dimension array. Are you familiar with arrays, used in programming... they are just an ordered set of variables. For this problem, one dimension of the array would be 1 to 10. Each of the elements in this array would have a 10 x 10 array (10x10x10 = 1000)

Think of this as a 10x10x10 cube holding all the wines.
From top to bottom, each row would be labled A1, A2, A3, etc
From left to right, each column would be labled B1, B2, B3, etc
From front to back, each column would be labled C1, C2, C3, etc

Each prisioner is labeled P1, P2, P2, etc.

The first day...
P1 would taste all the wines in the array for row A1 (100 wines)
P2 would taste all the wines in the array for row A2
P3 would taste all the wines in the array for row A3
(etc)

The second day...
P1 would taste all the wines in the array for column B1 (100 wines)
P2 would taste all the wines in the array for column B2
P3 would taste all the wines in the array column B3
(etc)

The thrid day...
P1 would taste all the wines in the array for column C1 (100 wines)
P2 would taste all the wines in the array for column C2
P3 would taste all the wines in the array for column C3
(etc)

At the end of four weeks...
The first prisoner to die would indicate which A row where the bad wine is located
The second prisoner to die would indicate which B column of the bad wine
The third prisoner to die would indicate which C column, thus identifying the exact bottle of the bad wine.

Steve B.
Tuesday, July 15, 2003

This doesn't work for a subtle reason:  suppose prisoner P1 died the first day, and then prisoner P2 died the next day, and no one else died.  There's more than set of coordinates that could cause this:

A bottle at (A1, B2, C1) or (A1, B2, C2) would both give this result.

Tim H
Friday, July 18, 2003

*  Recent Topics

*  Fog Creek Home