- What is the minimum number of weighings you need to determine k?
- Construct a scheme of weighings which achieves this minimum.
- What if there are originally eight bunnies (10 through 80)?

Source: Univ of Calif, San Diego, Math 187 (Cryptography) Puzzle #3

Solutions were received from Denis Borris, Larry Baum, Craig Gentry, Yaacov Weiss.

Craig Gentry solved both problems succinctly:

7 bunnies, 2 weighings 1) Weigh 3 and 4 on the left against 7 on the right (So we're on the same page, bunny 3 is the one that weighs 30 or 40.) 2) If left is heavier (and 1, 2, or 3 is the first heavy bunny), then weigh 1 and 2 against 3. If left is heavier, 1 is the first heavy bunny. If balanced, 2. If right, 3. 2) If right is heavier (and 5, 6, or 7 is the first heavy bunny), then weigh 5 and 6 against 7 and 4. If left heavier, 5 is the first. If balanced, 6. If right, 7. 2) If balanced (and 4 or 8 is the first heavy bunny (Saying 8 is the first heavy bunny is just shorthand for saying that none of the 7 bunnies is heavy)), weigh 4 against 1 and 3. If left is heavier, then 4 is the first heavy bunny; otherwise, there is no heavy bunny. 8 bunnies, 2 weighings Exactly the same as above, except if the first weighing (3 and 4 against 7) is balanced, we have 3 possibilities remaining (4, 8 and 9), and we weigh 4, 5 and 6 against 7 and 8. If left heavier, 4 is the first heavy bunny. If balanced, no heavy bunny. If right, 8 is the first heavy bunny. In general, you can do up to 3^n - 1 bunnies in n weighings. I'll explain how if there's any interest. This does not apply to the trivial cases of 1, 2, or 3 bunnies, which cannot be completely solved in any number of weighings. -Craig Gentry ts208@is5.nyu.eduOther Solutions:

- For the first problem of 7 bunnies, 2 weighings are needed.
Denis Borris sent:
1- weigh B6 against B1 B2 B3 3 cases will be even 3 cases will be B6 heavy 2 cases will be B6 light 2- 3 cases even; B3 B4 against B7 3- 3 cases B6 heavy; B4 B5 against B2 B7 4- 2 cases B6 light; B1 B2 against B3

Larry Baum assumed more than one of each bunny was available. Although that's not what I originally intended, his solution has the advantage of being able to determine both weighings prior to starting:Notation: 117 means two of bunny size 1 and one of bunny size 7 L1 = weight of left side on weighing 1 R1 = weight of right side on weighing 1 L2 = weight of left side on weighing 2 R2 = weight of right side on weighing 2 <= means L1

Yaacov Weiss sent:means L1 R2 etc. Weighing #1: 117 vs 45 Weighing #2: 1235 vs 56 k L1 R1 L2 R2 result 0 120 110 150 130 >> 1 100 110 140 130 <> 2 100 110 130 130 <= 3 100 110 120 130 << 4 100 100 120 130 =< 5 100 90 110 120 >< 6 100 90 110 110 >= 7 90 90 110 110 == (My unit is a 10gram unit - now i work with single digits.) First put bunnies 167 on one side and 2345 on the other. given k, all bun's up to k are the correct size, while the ones BIGGER than k are too big. K 1,6,7 <=> 2,3,4,5 0 2+7+8=17 < 18=3+4+5+6 1 1+7+8=16 < 18=3+4+5+6 2 1+7+8=16 < 17=2+4+5+6 3 1+7+8=16 = 16=2+3+5+6 4 1+7+8=16 > 15=2+3+4+6 5 1+7+8=16 > 14=2+3+4+5 6 1+6+8=15 > 14=2+3+4+5 7 1+6+7=14 = 14=2+3+4+5 if Result is '=' 6 ------- 123 K=3 7 > 6 K=7 6 = 6 else if Result is '<' 3 ------- 12 K=0 4 < 5 K=1 4 = 4 K=2 4 > 3 else (Result is '>') 47 ------- 56 K=4 12 < 13 K=5 12 = 12 K=6 12 > 11 As we see - whatever result we get after the first weighing we can solve it on the second weighing.

- For 8 bunnies, still only 2 weighings are needed. Denis Borris sent:
VARIABLE NAMES: Bunnies in ascending weight order: B1 B2 B3 B4 B5 B6 B7 B8 Bunnies before lunch: BBL Left side of scale : LFT Right side of scale : RGT (what tremendous imagination!) WEIGH #1: LFT = B1 + B2 + B7 + B8 RGT = B3 + B4 + B5 + B6 WEIGH #2: if LFT = RGT then perform EVEN if LFT > RGT then perform HEAVY if LFT < RGT then perform LIGHT EVEN LFT = B3 + B4 RGT = B7 if LFT = RGT then BBL = 8 if LFT > RGT then BBL = 0 if LFT < RGT then BBL = 4 HEAVY LFT = B1 + B4 + B8 RGT = B6 + B7 if LFT = RGT then BBL = 6 if LFT > RGT then BBL = 7 if LFT < RGT then BBL = 5 LIGHT LFT = B2 + B3 RGT = B5 if LFT = RGT then BBL = 2 if LFT > RGT then BBL = 1 if LFT < RGT then BBL = 3

Mail to Ken