Solving the Mystery of the Poisoned Wine Bottle: O(log n) Solution

  • Context: Graduate 
  • Thread starter Thread starter suki2
  • Start date Start date
  • Tags Tags
    Mystery
Click For Summary

Discussion Overview

The discussion revolves around a problem involving an evil king with n bottles of wine, one of which is poisoned. Participants explore methods to determine the poisoned bottle using a limited number of taste testers, specifically aiming for a solution that operates within O(log n) testers. The conversation includes theoretical approaches, algorithmic efficiency, and interpretations of the problem's constraints.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests a method where each tester is assigned to taste bottles based on their multiples, creating a unique combination of testers for each bottle, which could identify the poisoned one based on which testers die.
  • Another participant proposes a binary division approach, where testers taste half of the remaining bottles, iteratively narrowing down the possibilities, which they claim requires at most int(log2(N)) + 1 testers.
  • Some participants express confusion about the notation "O" in the context of the problem, with one clarifying that it refers to "Big Oh" notation, indicating worst-case efficiency.
  • There is a mention of an alternative solution that would use O(n) testers, where each tester samples one bottle, but this is noted as less efficient than the desired O(log n) approach.
  • One participant humorously suggests that the king should simply stop drinking wine, while another agrees with the proposed method of using testers.
  • Several posts reiterate the need for clarity regarding the problem's constraints and the meaning of "expending" tasters.

Areas of Agreement / Disagreement

Participants express differing views on the best method to solve the problem, with no consensus reached on a single approach. There is also confusion regarding the interpretation of the problem's notation and constraints.

Contextual Notes

Some participants note that the problem statement may be incomplete, particularly regarding the definition of "O" and the implications of "expending" tasters. There are also references to the potential for multiple interpretations of the problem's requirements.

suki2
Messages
1
Reaction score
0
An evil king has n bottles of wine, and a spy has just poisoned one of
them. Unfortunately, they do not know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill. Even so, it takes a full month for the poison to take effect. Design a scheme for determining exactly which one of the wine bottles was
poisoned in just one month's time while expending O(log n) taste testers.
 
Mathematics news on Phys.org
You need log base 2 of n testers (round up).

Nobody tests bottle 1
Tester A tests all bottles that are a multiple of 2.
Tester B tests all bottles that are a multiple of 4, as well as the 1 bottle before that bottle
Tester C tests all bottles that are multiples of 8, as well as all 3 bottles before that bottle
Tester D tests all bottles that are multiples of 16, as well as all 7 bottles before that bottle

etc.

So you get something that looks like:

1 - nobody
2 - A
3 - B
4 - AB
5 - C
6 - AC
7 - BC
8 - ABC
9 - D
10 - AD
11 - BD
12 - ABD
13 - CD
14 - ACD
15 - BCD
16 - ABCD
17 - E
18 - AE
19 - BE
20 - ABE
...

Each bottle will have a unique combination of testers that die after a month is up. If (for example) bottle 13 is poisoned, testers C and D will die. If bottle 16 is poisoned, A, B, C, and D die. If bottle 1 is poisoned, nobody dies.[/color]

DaveE
 
Last edited:
You can keep dividing the set in half, maybe making a rule that in the case of an odd numbered set the extra bottle goes in the first half. Each taster is then assigned to taste all the bottles in the first half of each subgroup.

That is, taster 1 tastes the first N/2 bottles. Taster 2 tastes the first N/4 bottles in each of the 2 groups of N/2 bottles. Keep going until someone is tasting every other bottle. In the end you'll get a tree, with each bottle. This demands that you use at most int(log2(N)) + 1 tasters.

Very similar in spirit to how many bits does it take to represent a number from 1 to N. Here, the "bi"t of information is poison or no poison (die or live).
 
Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J
 
denverdoc said:
Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J

"O" is notation for "worst case" in algorithmic analysis, and is called "Big Oh" notation. It's a way of telling *very* roughly what the worst case efficiency of the algorithm is. So you take the highest power term, strip it of any constants, and that's the notation.

So let's say I develop an algorithm for, I dunno, figuring out the shortest path between two nodes on a map of N nodes. If my algorithm always takes 3*N^2+1.5N+1 iterations, the "O" notation would be O(N^2). If my algorithm takes between 1 and N+1 iterations, "O" notation would be O(N). If it took 2N+5, it'd be O(N) again.

So O(log n) testers means that it takes at most some function of log n testers. You could easily devise an algorithm that took O(n) testers-- just have one tester for each bottle, and see who dies. But is there a better solution with worst case O(log n) testers?

DaveE
 
"An" answer

The answer can be ONE:biggrin:
 
didn't it say an evil king? let him die ;)

good job daveE i think that will be the best method
 
Just had this on a test

I gave the first combination answer (which is what I'm sure the teacher wanted).

I also gave an alternate solution. This one:
You could easily devise an algorithm that took O(n) testers-- just have one tester for each bottle, and see who dies.
The teacher specifically clarified that "expending" tasters means that they'd die. So in that case, the above solution is O(1) which is of course better than O(lgn).
 
denverdoc said:
Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J

When I see the O, I think of "On the Order of" so a function 4x^4+x^2+1 is On the order of N^4, or O(N^4). Basically like a comparison of magnitude/order of magnitude for a function.
 
  • #10
Healey01 said:
When I see the O, I think of "On the Order of" so a function 4x^4+x^2+1 is On the order of N^4, or O(N^4). Basically like a comparison of magnitude/order of magnitude for a function.
If you correct this to:

so a function 4x^4+x^2+1 is On the order of x^4, or O(x^4).

I'll delete this message.
 

Similar threads

MHB Optimizing Prisoner Selection for Poisoned Wine Detection in Medieval Empires
  • · Replies 1 ·
Replies
1
Views
2K
Chemically regenerating my auto's catalytic converter?
  • · Replies 19 ·
Replies
19
Views
10K
News Who Poisoned Alexander Litvinenko?
  • · Replies 39 ·
2
Replies
39
Views
9K
Proving log(n)^3 = O(n^(1/3)) using Big O notation
  • · Replies 1 ·
Replies
1
Views
12K
Solve Network Programming Challenge: O(n^3) & Linear Time Solutions
  • · Replies 22 ·
Replies
22
Views
5K
Kid Science: Humorous Quotes from 5th and 6th Graders
  • · Replies 11 ·
Replies
11
Views
4K
Mathematica This Week's Finds in Mathematical Physics (Week 259)
  • · Replies 1 ·
Replies
1
Views
4K
Mathematica This Week's Finds in Mathematical Physics (Week 230)
  • · Replies 1 ·
Replies
1
Views
3K
Mathematica This Week's Finds in Mathematical Physics (Week 230)
  • · Replies 1 ·
Replies
1
Views
4K
Mathematica This Week's Finds in Mathematical Physics (Week 242)
  • · Replies 1 ·
Replies
1
Views
4K