The Hamilton Puzzler The Continental Conundrum The Befuddled Blue

Logic Puzzle #1: Solutions Page

The puzzle

A brief summary of the winning solution

The winning solution, by Yuqi Mao, '09

Longer solutions for 16, 8, and 7 testers, which may be helpful for understanding the winning solution.

Liz Farrington '10 provided a nice solution for seven testers, including spreadsheets of assignments!

Honorable Mentions:

Robert Kosar '10, and Chuck Borton, Chemistry Department, also provided excellent solutions using 5 testers.

Thomas Helmuth '09 and David Goldberg '11 also provided very nice solutions for 7 testers.

 

Puzzle #1 (October 2008)

Family Weekend is upon us, and Dean Urgo is preparing a champagne brunch at which 240 bottles of champagne will be served. Unfortunately, some pranksters have tampered with one of the bottles, injecting a magic potion that, though otherwise harmless, will turn the teeth of anyone who drinks even the tiniest drop of it Continental Blue. The person’s teeth will remain dyed for a full week. (The effects of the potion are systemic, and not due to contact between the wine and the teeth.)

The dye is triggered between 8 and 11 hours after drinking, at which time its effects are immediate and obvious. The time of the trigger varies both with the person and with the wine. It is now 6pm on Saturday, and the brunch begins at 10:30am on Sunday.

Dean Urgo wants to find the single bottle that has been contaminated. He is willing to open all 240 bottles of champagne for testing. Since testing only requires the smallest drop, removing any number of drops of champagne will not reduce the quantity in the bottle significantly. The pranksters have also sabotaged the chemistry labs, so the only way to determine if a bottle has been contaminated is by drinking a sip.

Dean Urgo insists on using students to test the champagne. There are over 240 students of drinking age available for testing, but the dean wishes to avoid subjecting more students than necessary to the test. There are 16 students whose parents are not coming to Family Weekend.

Questions:

1. Can Dean Urgo determine which is the single, contaminated bottle using only the 16 students whose parents are not coming to Family Weekend? Provide a solution.

2. Eight of the 16 students whose parents are not coming to Family Weekend have been caught with open containers this term. Can Dean Urgo determine the single contaminated bottle using only these eight students? If so, provide a solution.

3. Can Dean Urgo reduce any further the number of students that must drink from the bottles to be sure to find the contaminated bottle before the brunch begins? If so, provide a solution.

Bonus: Given the minimum number of testers, what is the probability that any one of them will have blue teeth at the beginning of the brunch?

 

 

 

 

 

 

 

 

The Puzzler's version of the winning solution:

Number the bottles using base 3, from 00001 to 22220 (which in base 10 is 240).  Assign each of the six testers one place in the base 3 expansion (1s, 3s, 9s, 27s, 81s, and 243s).  There will be two rounds of testing, one at 6pm, from which the results will emerge between 2am and 5am, and a second round at 10pm, from which the results emerge between 6am and 9am. For each bottle, if the number in the tester's place is 1, then s/he sips in the first round; if the number in the tester's place is 2, s/he sips in the second round; if the number in the tester's place is 0, s/he does not sip.  Construct a five-digit base 3 number as follows: For each tester, if his/her teeth turn blue during the results of the first test, put a '1' in his/her place.  If his/her teeth turn blue during the results of the second test, put a '2' in his/her place.  If the tester's teeth do not turn blue, put a '0' in his/her place.  The resulting number is the number of the contaminated bottle. Each bottle will have a unique set of tasters, and each taster sips either once or not at all from each bottle, so there is no ambiguity in the result. Each tester (except for the one assigned to the 243s place, who tastes slightly fewer) tastes two-thirds of the bottles, so the chance of each person's teeth turning blue is just under two-thirds.

The same method can be used with 8 and 16 testers, of course, with the extra testers not drinking any champagne at all.

Our puzzle winner, Yuqi Mao, mentioned afterwards that since the test took place on the evening we turned our clocks backwards, there would be time for a third round of testing, which could bring the total number of students needed down to four.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Solutions for 16, 8 and 7 testers

The solutions below depend on the fact that every (decimal) number has a unique binary representation. We work to a seven-tester solution in three steps.

Step 1:

First, notice that we can conduct two sets of tests, in sequence, as long as we do not need the results of the first test before we administer the second test. If we start the first test at 6pm, the results will appear between 2 am and 5am. We can start the second test at 10pm, so that the results appear between 6am and 9am. Thus, we isolate the results of the first test from those of the second test. An independent third test would be impossible.

Consider a solution using only 16 students. Each bottle will be tasted by two students, but by a different, unique pair. Since there are 16²=256 unique pairs of students, there are more than enough pairs. A variety of different pairings will work. Assign fifteen bottles to each of the sixteen students in the first test. Then, assign one bottle from each of the sixteen first-test groupings to each student for the second test. The results of the first test will narrow the results to the sixteen bottles tasted by the person whose teeth turn blue between 2am and 5am. Each of those 16 bottles will have had a different taster in the second test. Here is a sample assignment:

In most cases, one person’s teeth will turn blue between 2am and 5am, and another person’s teeth will turn blue between 6am and 9am. Since some bottles (e.g. 1, 18, 35) will be tested by the same taster in the first and second test, if no one new has blue teeth by 9am, we know that the same person had the contaminated bottle in both tests.

Example: Let’s say that the 148^th bottle was contaminated. In the first test, Taster 10’s teeth will turn blue, which means that the contaminated bottle must have a number between 136 and 150 (inclusive). In the second test, each of those bottles will be tested by a different student. Taster 8 tests bottle 136, Taster 9 tests bottle 137, etc. Taster 4 tests bottle 148. So, by 9am, the teeth of Taster 10 and Taster 4 will turn blue, and we have our solution.

Example, in the other direction: Let’s say that Taster 7 has blue teeth at 5am, and Taster 12 has blue teeth, by 9am. Taster 7 tested bottles 91 through 105 in the first test. Taster 12 tasted bottles 12, 28, 44, 60, 76, 92... So, bottle 92 is the contaminated bottle.

Step 2:

We can reduce the number of tasters to eight. We assign each of the 240 bottles its own binary number. Since the maximum number of binary digits the dean needs in this case is eight, we can add the leading 0s in each number:

We assign each of eight students one of the binary places. The nth student is assigned the 2^n-1 position in each binary number. So, one student is assigned the units place, the second student is assigned the 2s place, the third student is assigned the 4s place... and the eighth student is assigned the 128s place. Each of the nine students tests each bottle that has a 1 in his/her assigned place and does not drink from any bottle that has a 0 in his/her assigned place. By 5am, the unique bottle will be determined.

Examples: Let’s say that after 11 hours only the teeth of testers 3, 6, and 7 are blue. Then bottle number

             2² + 2⁵ + 2⁶ = 50

was contaminated. If only the teeth of testers 1, 7, and 8 are garnet, then bottle number

             2⁰ + 2⁶ + 2⁷ = 193

was contaminated.

Note that we can assure Dean Urgo that at most six students will have blue teeth. The only eight-digit binary number with 1s in all digits is (decimal) 255. Since there are only 240 bottles of wine, we can arrange the assignment so that no bottle will be assigned that number. Furthermore, there are seven binary numbers with just one 0, such as

             01111111 = 127 and

             11101111 = 239.

We can avoid these assignments as well.

Note also that if there were 256 bottles, the probability of any tester getting garnet teeth would be precisely ½. With only 256 bottles, the probability will be slightly less than ½ for some of the testers.

Step 3:

We can reduce the number of testers to seven by combining the two above methods. First, we divide the number of testers into two groups, roughly in half. (We need to have at most 128 testers in either group.) Then, we assign each of the testers a place in a seven-digit binary number: 1, 2, 4, 8, 16, 32, and 64. The contaminated bottle will only appear in one group. If it appears in the first group, then we have the answer by 5am. If no one’s teeth are blue after the first set of tests, then we will have the answer by 9am.