0809.1: Solution


Congratulations to Yuqi Mao, '09, whose winning solution can be seen here.

 

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.

 

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 162=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:

 

Taster

First Test Bottles

Second Test Bottles

1

1-15

1, 17, 33,...,225

2

16-30

2, 18, 34,...,226

3

31-45

3, 19, 35,...,227

n

15(n-1) +1 to 15n

n, n+16, n+16(2), n + 16(3)...

16

226-240

16, 32, 48,...,240

 

 

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 148th 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:

 

Decimal

Binary

1

00000001

2

00000010

3

00000011

4

00000100

5

00000101

...

 

100

01100100

101

01100101

102

01100110

...

 

238

11101110

239

11101111

240

11110000

 

We assign each of eight students one of the binary places. The nth student is assigned the 2n-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

             22 + 25 + 26 = 50

 

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

 

             20 + 26 + 27 = 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.