Re:Some fun mathematical puzzles
by 124816 on Saturday November 20, 2010 @04:23AM
(#1924187)
> one dies within 24 hours
Is it really correct to interpret that as "dies in exactly 24 hours"?
Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings:
Given N slaves, you can test 2^N wines in a single iteration, as so:
- A set of size N has 2**N distinct sub-sets.
- Have each distinct sub-set taste a different wine.
- After 24h, everyone who drank the poisoned wine will be dead, and,
provided you took notes about which set consumed which wine, you
can look up which wine they drank.
- (Note also, you leave one wine untasted; if nobody dies, it is the
poisoned one.)
For our first iteration, we have each set taste multiple wines, like so:
- The set with five slaves will taste a single wine.
- Sets with four slaves will taste 2 wines.
- Sets with three slaves will taste 4 wines.
- Sets with two slaves will taste 8 wines.
- Sets with one slave will taste 16 wines.
- We leave 32 wines untouched.
Of course, in general: a set with N slaves will taste 2^(5 - N) wines.
After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states:
- One slave is dead. We know the 16 wines he drank, and we have 4
slaves left. As shown above, we can easily determine which of
the 16 wines is poisoned in a single iteration.
- N slaves are dead. We know which 2**(5-N) wines they drank, and
we have 5-N slaves left. So we can easily determine which of
the 2**(5-N) wines is poisoned in a single iteration.
Note that N = 0 is a valid case above.
So, we need to calculate how many wines we can test in this manner. Going through each set:
- 5 choose 1 * 16 = 80
- 5 choose 2 * 8 = 80
- 5 choose 3 * 4 = 40
- 5 choose 4 * 2 = 10
- The one wine that all slaves drink the first time.
- The 32 wines none of them drink the second time.
The sum is 243. Garçon!!! Fetch three more barrels!
Is it really correct to interpret that as "dies in exactly 24 hours"?
Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings:
Given N slaves, you can test 2^N wines in a single iteration, as so:
For our first iteration, we have each set taste multiple wines, like so: Of course, in general: a set with N slaves will taste 2^(5 - N) wines.After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states:
Note that N = 0 is a valid case above.So, we need to calculate how many wines we can test in this manner. Going through each set:
The sum is 243. Garçon!!! Fetch three more barrels!