Santa Claus and his elves are gearing up for another holiday season, busy filling orders and wrapping gifts for all of the good little boys and girls. Since snowglobes are popular gifts this year, Santa Claus has dedicated an entire department to build and wrap the 32,768 snowglobe orders that came across his desk. After several long days and nights, Santa and the elves have finished wrapping each snowglobe in preparation to be loaded onto Santa's sleigh.
However, just before loading all 32,768 boxes of snowglobes into Santa's sleigh, one of the elves realizes her wedding ring accidentally fell into one of the boxes that she was wrapping. The question is..."Which one?" The problem is the boxes are indistinguishable from each other and have been shuffled around so much, there's no way to narrow down which box, or even which group of boxes, is more likely to contain the missing ring.
One of the elves suggests opening all of the boxes to find the ring. That would take too much time, another elf points out. "We've only got a couple of days until Christmas Eve... there's no way we can re-wrap the snowglobe boxes in time."
Another elf, realizing they have two industrial-sized scales on hand, recommends weighing each package, two at a time, to find the package weighing the most. Each snowglobe box weighs exactly 3 pounds. Whichever package weighs more than 3 pounds, the elf reasons, must contain the missing ring. However, it will still take a considerable amount of time to weigh two boxes at a time, potentially as many as 16,384 different times.
A third elf chimes in and says, "Why not weigh half of the 32,768 boxes on the first scale and half on the second scale? We'll be able to see which scale weighs more, thus we'll be able to narrow the box containing the ring down to 16,384 boxes. Then, we'll split the 16,384 boxes in half and weigh 8,192 on one scale , and 8,192 on the other. We'll continue in a similar fashion until we're down to only two boxes. Then we'll be able to easily determine which box contains the ring. It turns out we'll only need to do this 15 times, since 2^15 = 32,768." The elves agree this process is more efficient and conclude it will allow them to locate the box containing the missing ring before Santa begins his journey.