Roy Tang

I hate you. Now I can't continue doing accounting.

Day 1: T1 = B1-B100 T2 = B101 – B200 T3 = B201 – B300 T4 = B301 – B400 T5 = B401 – B500 T6 = B501 – B600 T7 = B601 – B700 T8 = B701 – B800 T9 = B801 – B900 T10 = B901 – B1000 Day 2: T1 = B101 – B150, B201 - B225, B301 - B312, B401 - B406, B501 - B503, B601 - B602, B701 T2 = B201 – B250, B301 - B325, B401 - B412, B501 - B506, B601 - B603, B701 - B702, B801 T3 = B301 – B350, B401 - B425, B501 - B512, B601 - B606, B701 - B703, B801 - B802, B901 T4 = B401 – B450, B501 - B525, B601 - B612, B701 - B706, B801 - B803, B901 - B902, B001 T5 = B501 – B550, B601 - B625, B701 - B712, B801 - B806, B901 - B903, B001 - B002, B101 T6 = B601 – B650, B701 - B725, B801 - B812, B901 - B906, B001 - B003, B101 - B102, B201 T7 = B701 – B750, B801 - B825, B901 - B912, B001 - B006, B101 - B103, B201 - B202, B301 T8 = B801 – B850, B901 - B925, B001 - B012, B101 - B106, B201 - B203, B301 - B302, B401 T9 = B901 – B950, B001 - B025, B101 - B112, B201 - B206, B301 - B303, B401 - B402, B501 T10 = B001 – B050, B101 - B125, B201 - B212, B301 - B306, B401 - B403, B501 - B502, B601 Day 3: Same as Day 2, but add 150. If it exceeds 1000, go around to 0. The combination and time of deaths will tell you what barrel is poisoned. Edit: Changed Day 3 to add 150 instead of 50.

It's probably wrong somewhere, but my head hurts, and I have accounting to do. =/ I didn't maximize the testers yet, and I didn't 100% check my answer, but the theory is there, yeah?

Your solution is wrong, magkakaproblem if the tasters die in the wrong order

In this case, modify Day 3 to be add 150 instead of 50. Oops.

Kapos ako sa Day 2 test cases. I don't check the ranges between BX25-BX50, BX75-BX99 that well. It only works with 100% accuracy if the poison is on barrels BX01-BX025. I can just add more barrels though, otherwise, it's accurate to within 50 barrels. I'd modify but am lazy. =/

10-digit binary string assignments sa barrels. pero hanggang dun lang alam ko.

Label each with 3 digits. Eg barrel 000, barrel 001.. 998, 999. Taster N will taste Nxx on first day, xNx on second day, xxN ok third day. In addition to this, on third day, taster N+1, N+2, N+3 will drink xxN. This is to narrow down the case when for example taster 0 dies on first day taster 1 dies on second day. The final digit is determined by some other people dying. If 010, taster 2 and 3 must die. If 011, taster 2 3 4 must die. Correction: should be up to N+4

OMG Ryan, genius. The labelling thing makes it so intuitive and clear. Why don't you work on a Ph. D or something and advance Mathematical frontiers?

GAAAAAAH, I hate that I wasted so much time on this. I'll never ever get that time back!

Baka 2 other tasters Pwede for the last digit. I just wanted to be super sure. Lol.

To be fair, the solution is to not serve the wine in the party. Must we be so barbaric as to potentially kill 10 innocent food tasters when we know the food is already poisoned?

haha king and slaves kasi unang version niyan :) )

1000 lang, hindi 1024? Wait let me get back to you on this. :D

Of course the wine tasters can all die? ;-)

Maan, yup I think it's possible for every taster to die. Also, after 7 days I think malalaman na. No need to wait for 10 days.

if all winetasters die, mas madaling malaman malamang.

Ayoko nang isipin. After 7 days pa pala mamamatay. Akala ko malalaman agad.

ryan, what if one or more of the tasters died not from the poison, but from drinking too much. tasting 100 barrels of wine per day! hehe

Ok I think I got it na. Naka-kasa na sa text editor ko yung sagot, and I'm pretty sure this is the one. Pero hindi ko muna ipo-post para marami pang maka-enjoy sa pag hunt down ng solution. :) I think I'll give a couple of hints, though. 1. If there were as much as 1024 barrels of wine, you could still do it with 10 tasters. 2. If the poison was insta-kill and you only had an hour before the party, it could still be done (assuming infinite bladder capacity on the part of the tasters)

I love you guys, you're all so nerdy. :D I will post the binary solution in a while, pero tama naman si AJ. Too lazy to check if Ryan's solution is correct lol

1024. 10-digit binary strings nga. assign to each barrel.

Yes, Wes is correct that the problem was originally having slaves to test the wine, I was just too lazy to include the back story. Spens, they don't have to drink the whole barrel!

roy, if im one of the wine tasters, knowing there's a good chance i'll be poisoned, i would probably make the best out of it. free flowing wine!! hehehe

The binary solution (as implied by AJ) is as follows (spacing for spoilers): … … … You assign each barrel a binary string according to their barrel number like so: 1 0000000001 2 0000000010 3 0000000011 4 0000000100 5 0000000101 6 0000000110 7 0000000111 …and so on Wine taster #1 takes a sip of wine from each barrel that has a 1 in the right-most digit. Wine taster #2 takes a sip of wine from each barrel that has a 1 in the second right-most digit. Wine taster #3 takes a sip of wine from each barrel that has a 1 in the third right-most digit. …and so on After 7 days, some number of the tasters will die. You compose a binary string ordered by the taster for each place value. For each one that dies, you put a 1. Each one that lives gets a 0. The binary string you formed now corresponds to the barrel number that is poisoned. For example, if taster #2 and taster #3 are the only ones that died, your binary string would be 0000000110, which means barrel #6 is the poisoned barrel. This scheme is also fair to the wine tasters, they each have roughly 50% chance to survive. (Some might have slightly higher odds due to there being less than 1024 barrels)

In my defense, the max number of deaths in my approach is 5. Lol.

And the expected number of deaths is abysmal in the binary approach!

(spacing for spoilers) … … … We can also first consider the simple case of 8 barrels and 3 tasters, where 8 is 2 raised to the power of 3. Each taster will be assigned a unique combination of 4 barrels, like so: Taster A: 1 2 3 4 _ _ _ _ (alternating groups of 4) Taster B: 1 2 _ _ 5 6 _ _ (alternating groups of 2) Taster C: 1 _ 3 _ 5 _ 7 _ (alternating groups of 1) If you look closely, you'd notice that each taster was made to correspond to a binary digit. It takes 3 binary digits to uniquely represent 8 barrels. Under this special arrangement, we can then observe who among A, B, and C dies, and the combination of deaths will allow us to pinpoint the poisoned barrel, like so: No taster dies: 8 is poisoned C dies: 7 is poisoned B dies: 6 is poisoned B and C die: 5 is poisoned A dies: 4 is poisoned A and C die: 3 is poisoned A and B die: 2 is poisoned All tasters die: 1 is poisoned If you have 1000 barrels, then you need tasters that number the log2 of 1000, rounded up to the nearest integer, or 10. We can then apply exactly the same principle, except now with 10 binary digits instead of 3. With 10 binary digits, we can test a maximum of 1024 barrels, or 2 raised to the power of 10.

Roy, concede. May Mali Sa Sagot ko!

Roy , dahil pinahirapan mo kami, I have a slightly upgraded version of your problem for you (and everyone) to figure out: It is 10 days before a feast. There are 1024 barrels of wine for the feast, but one of them is poisoned. Whoever drinks from that barrel will die after exactly 7 days. You only have eight wine tasters. You have until just before the feast begins to figure out which one is the poison barrel. How will you do it? :D

Donate the barrels to Congress. You won't get any wine, but you did an important public service to the Filipino people.

fixed 7 days = 7 * 24hrs?

Suko na ko AJ lol. Can I add myself as the ninth taster? :p

Hahaha… eto clue: Sagad na sagad yung resources mo, as in manpower, as well as time. :)

Aaaah, I think I overlooked one exceptional corner case. Consider this a clue na rin: If no one dies after everything is done, you can't narrow it down to just one barrel. A small handful, yes… but not one.

I hate you AJ lol. I had already turned off the PC and was trying to get to sleep when I thought of a solution. And I think I only need 7 tasters, not 8. Spacing for spoilers … … Assign each barrel a 7-digit base 3 number: 1 - 0000001 2 - 0000002 3 - 0000010 4 - 0000011 5 - 0000012 6 - 0000020 7 - 0000021 8 - 0000022 9 - 0000100 … and so on On day 1: Wine taster #1 tastes from all barrels that have a "0" in the rightmost digit Wine taster #2 tastes from all barrels that have a "0" in the second rightmost digit Wine taster #3 tastes from all barrels that have a "0" in the third rightmost digit … and so on On day 2: Wine taster #1 tastes from all barrels that have a "1" in the rightmost digit Wine taster #2 tastes from all barrels that have a "1" in the second rightmost digit Wine taster #3 tastes from all barrels that have a "1" in the third rightmost digit … and so on On day 3: Wine taster #1 tastes from all barrels that have a "2" in the rightmost digit Wine taster #2 tastes from all barrels that have a "2" in the second rightmost digit Wine taster #3 tastes from all barrels that have a "2" in the third rightmost digit … and so on On day 8: If wine taster #1 dies, then the poison barrel has "0" in the rightmost digit If wine taster #2 dies, then the poison barrel has "0" in the second rightmost digit If wine taster #3 dies, then the poison barrel has "0" in the third rightmost digit … and so on On day 9: If wine taster #1 dies, then the poison barrel has "1" in the rightmost digit If wine taster #2 dies, then the poison barrel has "1" in the second rightmost digit If wine taster #3 dies, then the poison barrel has "1" in the third rightmost digit … and so on On day 10: If wine taster #1 dies, then the poison barrel has "2" in the rightmost digit If wine taster #2 dies, then the poison barrel has "2" in the second rightmost digit If wine taster #3 dies, then the poison barrel has "2" in the third rightmost digit … and so on At the end of day 10, you should already know all the digits of the poison barrel, but all the tasters died D:

Hehe… you got the general idea of using time to supply the missing bits of precision. But don't forget that the poison isn't insta-kill and needs exactly 7 days to kick in, so the amount of time you have is only 4 days, from day 7 to day 10. (spoiler) … … … With 8 tasters, you will only be able to test 256 barrels in one sitting. You need two more testers/bits (i.e., a factor of 4) to test all 1024. You get those two missing bits by holding tasting sessions for 4 consecutive days with 256 barrels per day, and observing when the tasters start collapsing. This is why I was careful to explicitly say "exactly 7 days" when I wrote the problem… because it depends a lot on timing. If they die on day 7, then the poison is in the first day's batch. If they die on day 8, then the poison is in the second day's batch. If they die on day 9, then the poison is in the third day's batch. If they die on day 10 (right before the feast), then the poison is in the fourth day's batch. Once you know which batch of 256 barrels contains the poison, use the usual binary search approach to map the combination of taster deaths to the specific barrel among the 256 for that batch. The corner case I mentioned was when no one dies at all. If that happens, there will be four candidate barrels, one for each day, but you won't know exactly which one it is that's poisoned. :D

"After exactly 7 days" means if you drink on day 1, day 8 ka pa mamamatay :p

Anyway parang my answer was better haha

Ay oo nga, I actually misread your answer a while ago… sorry about that. I gave it another read now and I agree, your answer is much, much better! :D

On first day, divide 1000 by 10, each of them drinks a sip from 1-100. Say Person A drinks from 1-100, B sa 101 to 200 and so on. 2nd day, divide each of this 100 by 10. Person A will drink 1-10, B 11-20. Repeat this for each of the 100/10. 3rd day, divide 10 by 10, person A drinks on first, B on second, and so on. Start observing who dies in day 8, 9, 10. Max casualties, 3 persons.

Do not forget to label barrel 1-1000. If on 8th day, namatay si A, isa sa 1-100 yung may poison, same concept lang for 9th and 10th day.

help! i can't stop my epistaxis ^_^