Meta:Main Page

Welcome to the Math Puzzle Wiki

This is a collection of my favorite puzzles and brain teasers which contain some mathematical content. Most every puzzle here is taken from somewhere else, usually without express permission. When I can, I'll credit the source of the puzzle, but most come from "folklore" and have been retold many times by many people.

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.