|
| quote: | Originally posted by Floorfiller
You are given 5 bags. There are 10 beads in each of the bags. In four of the bags, the beads each weigh 10 kilograms. In the remaining bag, each bead weighs only 9 kilograms. All the bags and beads look identical. You must find out which bag has the lighter beads. The problem is that all the bags look identical and all the beads look identical. You can use a scale, but it has to be a single-tray scale, not a two-tray balance scale. Also, you may use the scale only once. How can you find out which bag has the lighter beads?
just pulled this off the web...looking at the solution its pretty fucking hard... |
Got this at an MS interview for the first time, answered it in 30 seconds . For 1<=n<=5, take n beads from bag n. The sum should be 10*n(n-1)/2, but will be short by (10-9)*n = n kilograms.
In general, the only necessary condition is that the number of bags must not exceed the number of items in the bag.
Last edited by Flyboy217 on May-21-2004 at 03:42
|