As you’ll see, this post is somehow similar to boxes and coins problem.
Given 7 bowls, each with at least 80 candies. All the candies from some bowls weigh 10 grams, and all the candies from other bowls weigh 11 grams. Find what are the bowls that contain candies weighting 11 grams with one single weighting.
Solution (it is better to think a bit before to read the solution, you may have a better one):
To recap, we have 7 bowls and all the candies from each bowl weigh 10 grams or 11 grams. So all the candies from some bowls weigh 11 grams, and we need to find exactly what are those bowls.
One solution is to take candy from the first bowl, candies from the second bowl, candies from the third bowl , …. , candies from the 6-th bowl , and from the 7-th bowl. Let’s weigh all the candies taken above. The weight will be:
where is the weight of the candies from the bowl.
If all the selected candies would weigh 10 grams then their weight would be:
But some of them weigh 11 grams. The difference is:
where is if the corresponding candies weigh 10 grams or if the corresponding candy weigh 11 grams.
But wait! This representation should be familiar to you :). It seems that are the binary digits (base 2) of some number. That means that if we subtract w’ (which we can simply compute) from the weight of the selected candies we get a number and the base 2 representation of this number indicates what are the bowls having 11 grams coins.