Fog Creek Software
Discussion Board




1000 Bottles of wine


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.
Thursday, July 31, 2003

Nice. But actually, if we want to be consistent with this approach, we can use just _one_ prisoner, assuming the poison works in exactly one month, i.e., 60x24x30 minutes. The king has one extra-week, i.e, 60x24x7 minutes -- approximately 10 000 minutes(actually, more, but let's leave him some time for calculations etc). Take one prisoner and have him to sip from the first bottle, ten minutes later -- from the second etc. Watch the exact time when he'll die, go exactly a month back, this will be the time when the poisoned bottle was tried -- done.
But I think the author meant binary search method, illustrated in his solution(prisoners are bits in the bottle number).

Dmitri Krylov
Wednesday, August 13, 2003

*  Recent Topics

*  Fog Creek Home