Seven orbs

Puzzle

You enter a magical cave to find seven orbs. A wizard tells you that each orb is colored on the inside, and that four or more of the orbs have the same color. Also, when two orbs of the same color are brought into contact with each other, they will glow, revealing the color. If two orbs touch but have different color, nothing happens. The orbs are heavy, so you can only touch two at a time. What is the least number of comparisons needed to find one of the orbs of the majority color?

Help

Expand

Solution

Let A be the set of orbs for which there are 3 or more others the same colour.

Let B be the set of orbs for which there are 1 or 2 others the same colour.

Let X be the set of orbs for which there are no others the same colour.

Goal is to prove that some orb is in A.

Possible combinations: (using the shorthand that A denotes an orb that's in A, etc)

A A A A A A A

A A A A A A X

A A A A A B B

A A A A A X X

A A A A B B B

A A A A B B X

A A A A X X X

Label the orbs 1, 2, 3, 4, 5, 6, 7 and test 1&2, 3&4, 5&6.

Comparing the results of testing those three pairs with the possible combinations, you can easily show that:

If two tested pairs glow the same colour, all members of those pairs are in A

If only one of the three tested pairs glows, members of that pair are in A

If two tested pairs glow different colours and the other doesn't glow, orb 7 is in A

If no tested pairs glow, orb 7 is in A.

In all cases, three tests suffice to prove that some orb is in A.

The only other thing required is to prove that two tests are not necessarily sufficient, which is trivial.

References

Problem Solving by Thomas DeFranco and Charles Vinsonhaler.