You are given 10 bags with 1000 coins in each bag. 9 bags hold 1000 coins that weigh exactly 1g. The remaining bag holds somewhere between 990-999 coins weighing exactly 1g. You're a technician at a metrology lab and your boss is a hardass about very expensive balance time, so you are only allowed to make one weighing. You're not allowed to take any coins out of the bag or tamper with the bags in any way or you'll get fired for corporate theft. You are being monitored via CCTV as you work. How do you determine which bag is short on coins?
Matthew Clark
with approximately* 1000 coins in each bag
Easton Kelly
Let a Jew sniff them. See which he wrinkles his nose at.
Angel Barnes
Load up all the bags on the scale and remove one at a time
Luis Walker
...
Isaiah Anderson
It prints I am a street shitting OOP niggermonkey
Logan Adams
But I am, I'm just removing the weight very carefully sir :^)
Robert Reyes
Sounds like a shitty job. What do I get paid for this foolish errand?
Parker Mitchell
1. Weigh 5 on either side, discard heaviest side 2. Weigh 2 on either side, if equal the fifth bag which you didn't way is the one you are looking for, else discard the heaviest side and continue. 3. Weigh the last to bags and discard the heaviest one. The bag that's left is the one you are looking for. 20% of the time it will take 2 operations, 80% of the time it will take 3 operations.
I'm lazy, but it probably wouldn't've been too hard to show that it will have an upper bound of ceil(log(n)) - 1 operations for n amount of total bags.
Jacob Davis
You split the group into 5 bags. You weigh one group, and select the half that didn’t sum up to 5000 grams. That gives you a 20% chance of randomly selecting a bag with missing coins. Although that seems low, it is the fairest probability. For example if you weigh 9 bags, you would get 100% of the remaining bag being correct if the weight was 9000 grams. But if it wasn’t, you would have 11% of getting a bag right to choose from.
