Discrete Mathematics

------------------------------'COMBINATORICS

255

(labels

of

balls in left pan, labels

of

balls in right pan)

"lH"

means ball 1 is heavy, "2L" means ball 2 is light, and so on.

Suppose that we wanted to solve the same problem with more balls, but still with only 2 weighings.

If

there are 5 balls, then we can apply pigeonholing to prove that no solution exists.

(Of

course we could do a

simple case analysis here too, but case analysis gets elaborate,

if

not prohibitive, when there are a lot

of

balls,

while pigeonholing can give simple bounds.)

Claim

The weighing problem with 5 balls cannot be solved with 2 weighings. The weighing problem with ...