More information/motivation/clarifications/background of the puzzle will be posted later. (Goal is to determine minimum # of engineers needed). Hopefully it's clear.

Follow-up question: What if both unknown substances had the same side-effects, and exactly two pints of beer were spiked?

**Edit (December 8th, 2010):**As promised, here is some additional information. This problem is a famous one and usually phrased as follows:

"The King has 1000 wines, 1 of which is poisoned. He needs to identify the poisoned wine as soon as possible, and with the least resources, so he hires the protagonist, a Mathematician. The king offers you his expendable servants to help you test which wine is poisoned.The standard solution is the binary representation one. An interesting generalization (that has not been solved yet and quite possibly is a hard problem) can be found here, which essentially asks if "k bottles of wine are poisoned, then what is the new minimum # of servants required?"

The poisoned wine is very potent, so much that one molecule of the wine will cause anyone who drinks it to die. However, it is slow-acting. The nature of the slow-acting poison means that there is only time to test one "drink" per servant. (A drink may be a mixture of any number of wines) (Assume that the King needs to know within an hour, and that any poison in the drink takes an hour to show any symptoms)

What is the minimum amount of servants you would need to identify the poisoned wine?"

The beer was poured more than an hour before it was going to be drank? Ugh, warm beer. >

I vote that you use 20 students, and test 6 pints on each of them. You'll end up replacing more beer than strictly necessary, but if you needed to set up a giant procedure involving double or triple that many students (I don't know what the actual answer is), the time eaten up by crowd management would ruin the test's effectiveness.

I never thought that would cause beer to get warm

lol

i say 1, mix all the pints together, and give it as an X-mas gift to your least favorite student

all of them

I would choose 8 engineers who can't use binary numbers. Each takes a sip from approximately 60 beers, so good for them I suppose :)

This method doesn't work for the second case. I'm going for a beer and will think about it on the way ;)

I agree--except the proper minimum number of engineers is seven, since 2^7=128. Since the symptoms are independent, you still only need seven.

Why settle for seven when you can get rid of eight, even nine or ten engineers in one fell swoop?

Because the question asked for the minimum, by implication. ("...how many do you need?"

None, engineers are never strictly needed, they're just easier to find than physicists and mathematicians.

You'd be surprised how many mathematicians will come out of nowhere at the mention of free beer.

Not nearly as many as computer geeks at the mention of free software...

Assuming even a small amount of the pint will cause the symptoms, you just need 7 students. Order the students in some way, then have them drink from a pint (also ordered) only if the binary representation of the order of the pint contains 1 in that place. That is, for pint 5 = 0b0000101, only students 1 and 3 should drink from that pint. 7 students can test 2^7 = 128 > 120 pints. To figure out which pints were poisoned, convert the students with one of the symptoms back to a number. For example, if only students 1, 2, and 4 have rashes, then the 0b0001011 = 11th pint is poisoned.

I volunteer as the test subject, as I obviously can't calculate the logarithm of 120. :)

I had the same solution, with just one improvement. Each beer needs to be assigned a number between 0b0000000 and 0b1111111. This gives us 128 numbers and only 120 beers, hence 8 numbers will not be used. By choosing to skip the numbers with Hamming weight 6 or 7 (i.e. 0111111, 1011111, 1101111, 1110111, 1111011, 1111101, 1111110, 1111111), we minimise the amount of beer used for testing. We also minimise the expected number of engineers who experience the symptoms, although whether this is a benefit or not is a matter of opinion.

I wouldn't use hamming distance but leave out powers of 2 and zero. So every pint gets drunk by at least 2 bad engineers in the worst case.

Why you picking on the Engineers!!! Alright well funny story to tell about some silly engineers that I think are going to be hopeless. I'm doing Mathematical Physics as part of what I will call my Eng Phys program. Anyways teacher comes into class and says the following:

" I was too depressed to get around to marking your mid-terms because the PHYS 122 class I'm teaching made so many mistakes. Most common mistakes:

Question is, a block is moved from point A to point B and then back to Point A. The coefficient of friction on which the surface this block is moving on is (I can't quite remember, some number). What is the total work done.

Most common answer was 0, because it is a conservative force.

Second source of many mistakes:

_____ _____

| 3kg |--------| 4kg |----------->

--------------------------------

The blocks are being pulled with a constant force of 20N on a frictionless surface, find the tension in the string between the blocks.

Common answers, tension is 20N it is in equilibrium

tension is 0N

and other various non-sensical answers.

"

So to answer the above question. Find the students who most certainly won't get through engineering because of vary flawed logic and then get the smartest student of the class. Then ask the doomed students which beers that the smart student will sample. Chances are you will get the students that performed the prank and will point out those that have been spiked as they will want to see the smartest person of the class be silly. Reject them and safely assume that you have removed the spiked drinks.

If it makes you feel any better, the tattle-tale was a mathematician and got punished severly by the engineers afterwards.

hahaha, doesn't make me feel better. Personally I tell people that if I were to do a second undergrad it would be in Math. Hence most of my engineering peers think I'm a robot psycho.

Well first i counted with 22 engineer: 11 for rows and 11 for colums so id get coordinates of the spiked beers

But much better is to use interval halving method(or whatever is it called in English :-)) which can be applied here this way:

1st and the worst Engineer tests(glups) first 60 beers

2nd sips first 30 beers and 60-90

3rd 1-15, 31-45, 60-75, 90-105...

4rd 1-8, 15-23, 31-38... and so on...

in one hour id get few sick engineers whose should be enougth to get

the exact position(s) of the spiked beers

(its kinda binnary representation of the beer array)

For explame

Rash on 1st 2nd 4th engineer means 23rd beer

and Purple on 2nd engineer means 90th beer

Hah, i type so slow in english, i started at 5:22 :-D

Well for the second case there are only 120*119/2=7140 pairs of beers so we can do it with log(7140)=13 engineers.

I think you've only proven an information theoretic lower bound of 13. You still have to tell us which beers each of the 13 engineers should drink and I don't think there is always a choice of beers which splits the solution space in the way you want.

My current "best" solution requires 2*(1+2+3+4+5+6+7)=7*8=56 engineers which is not at all impressive compared to the upper bound of 120 (although it does work for n beers costing log_2(n)*(log_2(n)+1) engineers).

Well, its either that or 20 engineers and TWO hours (also scales to 2*log_2(n)+log_2(n)-1=3*log_2(n)-1 engineers and 2 hours).

It would have been cool if there were 130 beers, so two could be not drank, and still use only 7 engineers.

This problem is a good thing to worry about in advance, because when it actually happens you're going to have less than 120 seconds to remember the solution. I'm not sure all engineers can take a sip of a beer in less than a second. I sure can't.

What if your math was spiked instead of your beer?

But the results are clear in "less than an hour"--so you still have some leeway.

But drink-128-and-leave-two-unconsumed method doesn't uniquely identify which are the spiked beers. If the two unknown pranksters spiked the same beer, by discarding both extras you're wasting a beer!

you need 3 engineers. They each sip out of 1 pint each. The only beer you care about is the one you are going to drink.

Using your logic only 2 engineers are needed each one taking a sip of one pint only. Two things may happen:

a) both get sick - lucky one! all the other beers are safe.

b) at least one of them did not get sick - take the beer of the healthy one and let the others risk their lifes.

--

[]'s

So what you're really asking here seems to be, what is the minimum number of engineers you need to give a unique binary signature to each pint. One engineer yields yields two signatures, two yield four, three eight etc. With 7 engineers you can create 128 signatures which is ten more than necessary.

Oops, mighty shadow already got it, the only change I would make is I would assign one engineer to the ones place, one to the twos place and the fours, eights, sixteens, 32's, and 64's. And have them drink if they were a 1 in the number of the pint, it seems easier than his method by a little bit.

This problem could be approached using Hamming code:

align beer.

1st student- drinks 1st, skip one, drinks 3rd, skip one, etc

2nd student- drink 1+2, skip 3+4, drink 5+6, skip 7+8, etc

3rd student- drink 1+2+3, skip 4+5+6, drink 7+8+9, etc

total number of sick=position of spiked

so total 7 students

See, the problem is that you are assuming that all engineers who do poorly in class drink beer...which is definitely not the case. I've done poor in some engineering classes, yet I do not drink a drop of alcohol. Now, if it were Business majors, that would get the job done.

The minimum number of engineers is 7, but I don't think that's necessarily the best solution to this problem. If it were my beer, I'd rather minimize the amount I had to use for testing.

1 beer -> not distributed

7 beers -> given to 1 engineer

21 beers -> given to 2 distinct engineers

35 beers -> given to 3 distinct engineers

35 beers -> given to 4 distinct engineers

21 beers -> given to 5 distinct engineers

If it takes 1 ounce for the symptoms to show, then you're giving away 399 ounces of your precious beer [0(1)+1(7)+2(21)+3(35)+4(35)+5(21)], plus whatever you have to dump because it's spiked. If you're using imperial pints, you're losing about 17%-18% of your beer (~21%-22% for US pints).

If you have 119 engineers, they can each take a sip of, you lose closer to 6% (imperial) or 7%-8% (US)

So, really you should find 7 engineers, plus as many as you can find, up to 119 total.

The follow up is much trickier...

None! The rest 118 would be sealed while the 2 spiked would have the seal open!

You sir just sounded like a true engineer!

Just get to the two pranksters and beat them till they turn purple and they have scarring rashes.... and you're done.

I believe that for the second case, there is a better solution than the 11x11 grid.

You'd have to use the third dimension and create a 5x5x5 matrix

So you'd have people taste the pints if they belong to their X, Y, Z, and 2 sets of 3 people (some of which may be the same) will get sick.

Seconded. Thus only 5 engineers are needed.

well, you mean 15 engineers

I believe you will find that the Engineers believe that any one of them can solve the problem as long as you give them all the beers.

If the metabolosis is sufficiently uniform, then only two engineers are necessary. Construct a permutation of the 120 beers and an rational intervallic derangement. (A rational intervallic derangement is (A) a term I just made up because I can't remember the proper term and it's very early and (B) one in which the multiset of the ratios of the final position to the original position is actually a set. I.e. every element is shifted a different ratio from the "zeroeth" position.) Have the first engineer sip sequentially from the permutation. Have the second engineer sip sequentially from the derangement. (Arrange matters so that they may each take at least one sip per second.) Record the time of the onset of symptoms to a resolution of at least one second. Under the assumption above, the metabolosis will be such that only one element of the set of pints will have the observed ratio of onset times.

We would request $1.2M to evaluate the assumption of uniformly timed metabolosis of specific impurities in pints of beer in engineering students, but as this will entail the testing of poisonous substances in live humans, the additional safeguards, controls, and ethics board actions raise the cost to $5.4M. We understand that the grant committee shares our sense of the importance of this research and are confident that the committee will fund this groundbreaking research. We note that we will accept members of the committee as test subjects as long as (A) they are an engineer, have been an engineer, own a toy train, or are taking an engineering class and (B) they agree to consume several pints of beer.

Wow, I was 100% sure that it was impossible to solve this with less than 7 engineers (as each one could give only 2 bits of information by showing or not showing each symptom, and we need 14 bits of information to get the results). Until now.

Does this mean "given enough budget, engineering (and continuous mathematics) can defeat discrete mathematics"?

I should have added: "within acceptable error limits and tradeoffs". ;)

Any person with engineer skill (as myself) will say that your solution doesn't respect :

A) Time limitation : If you can have an easy verifiable solution, why take time to analyse a more complex solution.

B) Profitability : Any solution who cost equally or more than 120*(cost of beer) (Let's say 2$/beer => 240$) isn't a good solution

You are confusing engineering with academic research

None. Rashes and purpleness are acceptable tradeoffs for a pint of beer.

But the testers only get a small sip.

I heard this on Car Talk so I had an advantage. I'm not sure about the 2nd case, though.

The question is: would I rather risk purpleness or rash to avoid whatever diseases the "tester" had when he sipped from my beer? Probably...

In the Car Talk situation it was wine casks (which many people would drink out of) and they were testing on rats. Also it was deadly poison.

I vote you test on 118 students. Turns out you are a very bad professor...

I'm amazed at the number of responses that came up with some detailed binary sort while, apparently, ignorant of the term,

"Engineers" no doubt.

No--I'm more a rusty mathematician...

An engineer can take up to 40 beer (the engineer song...), so it's no use to test the 120 beer.

So it will take 6 engineer to test that. (2^6=64 test possible)

With 120 beer it's 7 engineer.(2^7=128 test possible)

With same effect in two beer, it will take 9 engineer for 120 beer

(8 engineer for 40 beer.)

The only thing you have to do is to ask each a the 4 (3) student to take a sip from each beer. By alternating the student for each beer, you are sure to obtain a unique solution for each beer.

How to find it? Find the smallest binary group who give a number of different solution that exceed 120 (40).

Find x in binomial(x,floor(x/2))>=120

With minimization of the number of test for each student, that give

binomial(9,4)=126 ( binomial(8,3)=56 )

Is this bonus question an open problem or something. Maybe I'm just not thinking right. Why would you want to cover the complete graph with cliques so that no two edges are in (exactly) the same set of cliques anyway?

@Bakyra (and Anthon and MightyShadow): The grid solution doesn't work for the bonus. For example, if the (four) engineers drinking rows 1,2 and columns 1,2 get sick, you don't know if the bad beers are (1,1),(2,2) or (1,2),(2,1). Worse, you don't know which (subset) of 2 rows and columns you are to need more than, say, one extra engineer to distinguish between the two remaining cases.

@baffo32 (and Dathan who responded): It wouldn't even work with 129 beers. In the proposed solution for 128 beers, the beers are already encoded from 0 to 127. There is already an outcome where no engineers get sick. Beer #0 is the bad one in that case. If you have 129 beers, if no engineers get sick, there are two possible contaminated beers (for each substance).

@Johnny: I don't believe your second solution, especially because it breaks the (proved) lower bound of 13. Your second paragraph has some typos in it ("ask each a the") which I'm not sure how to fix.

I haven't anything better and I should probably elaborate on my log(n)(log(n)+1) solution.

It is based on the solution for the first question where the beers are labelled from 0 to 127 and the ith engineers drinks all beers with a 1 at the ith bit.

Now I also want log(n) more engineers where the ith engineer drinks all beers with a 0 at the ith bit.

Now, if the engineer drinking 1s at bit i get sick but the one drinking 0s at bit i does not then we know that both bad beers have a 1 in the ith bit. We get just as much information if the 0s engineer is sick and the 1s engineer is not.

The tricky part comes if both of them get sick. As mentioned in my reply to Bakyra, we know that one beer has a 1 at the ith bit and the other has a 0 (but not which one is which, for example, if there is more than one bit of this kind).

However, say both engineers for the leading bit get sick, then we know that amongst all beers with a leading 1, exactly one beers is bad. We can search for that beer using log(n)-1 engineers (as in the single substance problem). We can use log(n)-1 more engineers to search for the (unique) bad beer with a leading 0.

Unfortunately, it could also be that only one engineer gets sick for the leading bit and both engineers for the second bit get sick. But in this case, we can search all beers with leading ?1 (where ? is known). This takes log(n)-2 engineers. To account for the ?, we actually need them to drink, say all beers where the second bit is 1 and the ith bit is 1 (with no restrictions on the leading bit). Do the same thing for ?0 which also takes an extra log(n)-2 engineers.

Now, we have to do the same thing for ??1 and ??0 using 2(log(n)-3) engineers. And so on. We need to assign all these engineers because we don't know apriori which bits are going to be "mixed" (both engineers of the first 2log(n) drinking a complementary set of beers get sick).

Regarding the king/wine problem, if any single molecule of the 'poisoned wine' will cause anyone who drinks it to die, then surely it is 100% poison with no wine whatsoever. Perhaps some of the atoms in the poisonous compound were originally part of the wine, but they could hardly be called wine once they've reacted with whatever was added and become part of a molecule of poison.

In this case, I would suggest getting a skilled wine taster to sniff all of the wines, and find the odd one out that way (assuming breathing in a molecule of poison is not lethal; and I think we'll have to assume that, or else people near the wine will just be dying randomly.) It seems unlikely that 100% poison would have all the complex aromas of wine.

But the fact that molecules are so much smaller than us means that even a tiny amount of wine has huge numbers of molecules. 12g of carbon (under 1/2 ounce) still has 6x10^23 atoms--so even a small amount of an effective poison will have some molecules, likely millions, in a reasonable sip, even a tiny sip.

I'm aware of that, but I don't see how it relates to my comment.

Because, your argument notwithstanding, the poisoned wine, although it acts like poison, still is indistinguishable from unpoisoned wine--except by its effects on the human body. Otherwise, as you pointed out, the use of servants is silly, if not evil--even if a chemical test took that same hour to do, but did not chance killing anyone, would you not want to test the wines rather than give servants a sip?

I find it hard to believe that something composed entirely of deadly poisons (with not even a single molecule of anything else) could not be distinguished from wine by the nose of a trained wine taster (or by any slave, if we assume that breathing in single molecules would kill random bystanders, and that since such deaths were not mentioned in the riddle, that the poison somehow has near-zero vapor pressure and thus has no odour.) I assumed we had no access to chemical tests because whenever I see a riddle involving kings I assume it's set long, long ago. Which is weird, since there are still plenty of kings around.

This is very similar to Maxwell's Demon. Saying that there is only one molecule of poison can be compared to transferring only one molecule of higher energy to a lower energy room.

Who said there was only one molecule of poison? I thought there was at least a glassful of poison, possibly a whole bottleful.

1. one tries 50 and after that you have only 50 to consider regardless the outcome (if he dies, spiked beer is among that 50, if not among other 50).

2. then another one tries 25, and now by the same logic you have only 25 left.

3. then another one tries 12, and you have either 12 or 13 left.

4. then one tries 6, and you have either 3 or 4 left.

5. then one tries 2 and you have either 1 or 2 left.

6. if you have one left you do not the 6th student, but if you have then he tries one of 2 left and then you can determine which beer is spiked.

of course, if you are lucky, and your students do not ever drink spiked beer because they are only drinking good half, you only need one. depending on the location of the beer in 3. you would need 5-6 students if they all die, otherwise less.

"The nice professor" I'm out of here!