Maths Teaser

[YOmama]

There is a king. He has 1000 wine bottles. One of them is   poisonous. poison shows its effect on 31st day after the intake. King has a party scheduled on the 31st day where he has to serve wine. what is the minimum number of soldiers that he would require to identify which bottle is poisonous before the party. Condition: each soldier can drink the combination formed from any number of bottles. 

Edited September 10, 2015 by YOmama

[jasen]

How many bottles of wine will be served In the party ?

If only 1, the King just need 1 soldier.

if the soldier poisoned, so the wine that the soldier take is poisonous, serve other 999 bottles

if the soldier is not poisoned, so serve 1 bottles.

[YOmama]

@jasen bro,he is ,the king he can serve from any bottle ,so we need to find the poisonous bottle.

[dgreening]

If we assume that all 1000 bottles might be used ... one approach

number each bottle from 0 to 999 - use the binary representation [requires 10 bits]

For every binary position [1,2,4, ... 512] one soldier drinks from every bottle that has a 1 in that position and another drinks from every bottle with a 0 in that position:

• for the least significant bit - soldier A drinks from every bottle where that value is 0 [even], soldier B drinks from every bottle where that value = 1 [odd]
• for the next significant bit, soldier C drinks from every bottle where the value = 0 and solder D drinks from every bottle where the value = 1
•  ...
• for the most significant bit [512] soldier S drinks from every bottle where that value = 0 [less that 512] and Soldier T drinks from every bottle with the value = 1 [512 or greater]

At the end of 31 days half of the tasters [10] will die and the bits associated with them can be used to decode the poisonous bottle.

Minimum number is 10

[BobbyGo]

Here is a slightly reversed approach (using geometry):

Instead of finding out how many soldiers it would take to find the poison amongst x number of bottles, here we find out how many bottles can be investigated using x number of soldiers.

Take the number of soldiers used for testing and plot that many non-linear points onto a plane.  The total number of bottles that can be tested is equal to the sum of one plus every possible point, line, and shape that the plotted points are capable of creating.

For example, 3 soldiers could find the poisonous bottle from a total of 8 bottles. (3 points + 3 line segments + 1 triangle + 1)

4 soldiers could find the poison from 16 bottles.  (4 points + 6 line segments + 4 triangles + 1 square + 1)

...

On down to 9 soldiers testing 512 bottles. (9 points + 36 lines + 84 triangles + 126 squares + 126 pentagons + 84 hexagons + 36 heptagons + 9 octagons + 1 nonagon + 1).

And 10 soldiers testing 1024 bottles. (10 points + 45 lines + 120 triangles + 210 squares + 252 pentagons + 210 hexagons + 120 heptagons + 45 octagons + 10 nonagons + 1 decagon + 1)

So the least number of soldiers you would need to test 1000 bottles is 10.

Although...

If I were the King, I would want to minimize the number of deaths (the more soldiers that die, the harder it is to defend your kingdom).  With that in mind, I would have 999 soldiers each drink from a different bottle.  Maximum casualties = 1

Edited September 10, 2015 by BobbyGo

[bubbled]

Here's another approach:

 

For a given number of bottles B, minimize M such that:

B <= (M choose 0) + (M choose 1) + (M choose 2) + ... + (M choose M)

You are assigning a unique combination of soldiers (both identity and number) to each bottle. Note it and see who dies. Then have a great party! 

Gruesome and easy.

[bubbled]

I think I posted this one before. But it's certainly similar to the OQ. 

The king has 240 barrels of wine, one of which has been poisoned.  After drinking the poisoned wine, one dies within 24 hours.  The king has 5 soldiers whom he is willing to sacrifice in order to determine which barrel contains the poisoned wine.  How does he achieve this in 48 hours?

[jasen]

from bubbled question, I need only 4 soldier !!

The 240 barrels of wine is divided into 4 group (each group with 60 barrels), Let say group A to Group D

Each soldier drink a spoon of all wine from 1 group. Soldier A drink from group A, and so on.

 

Then each group divided into 4 smaller group (each group with 15 barrels), Let say group AA to group DD

6 hour latter. Each soldier drink a spoon of all wine from 1 group in each bigger group. Soldier A drink from group AA, and so on.

 

Then each group divided into 5 more smaller group (each group with 4 or 3 barrels), Let say group AAA to group EEE

6 hour latter. Each soldier drink a spoon of all wine from 1 group in each bigger group. Soldier A drink from group AAA, and so on.

 

Then each group divided into 5 more smaller group (each group with only 1 barrel), Let say group AAAA to group EEEE

6 hour latter. Each soldier drink a spoon of wine from 1 group in each bigger group. Soldier A drink from group AAAA, and so on

 

from the time each soldier died the King can identify which barrel is poisonous 

Edited September 11, 2015 by jasen

[jasen]

Correction 

Then each group divided into 5 more smaller group 

I mean 4 more smaller group, not 5.

[dgreening]

 

If we assume that all 1000 bottles might be used ... one approach

Hidden Content

While driving home last night I realized that I had made the problem much more complicated than it needed to be

Use the same "Binary Coding " approach that I described earlier .... BUT soldier only need to drink from the bottles with a value of zero [or one] for each power of 2. Therefore:

number each bottle from 0 to 999 - use the binary representation [requires 10 bits]

For every binary position [1,2,4, ... 512] one soldier drinks from every bottle that has a 1 in that position and another drinks from every bottle with a 0 in that position:

• for the least significant bit - soldier A drinks from every bottle where that value is 0 [even], soldier B drinks from every bottle where that value = 1 [odd]
• for the next significant bit, soldier C drinks from every bottle where the value = 0 and soldier D drinks from every bottle where the value = 1
•  ...
• for the most significant bit [512] soldier S drinks from every bottle where that value = 0 [less that 512] and Soldier T drinks from every bottle with the value = 1 [512 or greater]

At the end of 31 days some of the testers will die and the bits associated with them can be used to decode the poisonous bottle.

You do need 10 soldiers --- the number that die is purely a function of  the binary value of the poisonous bottle.

 

 

[bubbled]

from bubbled question, I need only 4 soldier !!

Hidden Content

If you read the question closely, you will see you can't use smaller slices of time than 24 hours. A person is guaranteed to die within 24 hours, but when they die, is unknown. I assure you, you will need all 5 soldiers.

[mivaz]

1000 soldier direct to know which one is poison . lower the amount should be 100 soldier.  cause you need find only 1 bottle in accurately we make the table like 100 x100 . after they drink spin the table again . then it will show which one in the end of the day .example No 1 soldier dead and No 52 soldier the bottle will be No .52

[jasen]

Ok I try again

Use base 3 numbering, from 0 to 22220 to the barrels

Example:  barrel no 10201 means :
Soldier 1 and 5 drink at time 0
Soldier 3 drink at time 24

Barrel no 22010 means :
Soldier 4 drink at time 0
Soldier 1,2 drink at time 24

Now to identify which barrel poisonous is like this :
if soldier 3 died first (form time 0 to 24)
then soldier 1 and 5 died (from time 24 to 48)
Means : barel no 20102 (or 173 (base 10)) poisionous

[bubbled]

Ok I try again

Hidden Content

Beautifully done. I had never considered going with a base-3 approach. That now answers a question I couldn't figure out. Given N soldiers, why is the maximum number of barrels one can investigate in two time periods equal to exactly 3^N?

[bubbled]

It appears that there's a general solution for how many barrels/bottles (B) of wine you can test given a number of soldiers (N) and a number of testing time periods (P).

B = (P + 1)^N.

If the poison killed in a day and you had 7 days and 3 soldiers, you could test 512 barrels. Cool.

 

[mivaz]

It appears that there's a general solution for how many barrels/bottles (B) of wine you can test given a number of soldiers (N) and a number of testing time periods (P).

B = (P + 1)^N.

If the poison killed in a day and you had 7 days and 3 soldiers, you could test 512 barrels. Cool.

 

no the will not kill in a day . it will only kill on the day party start .