Reply
Wed 7 Nov, 2007 01:27 am
You are working for Fort Knox, and are responsible for storing the gold in large safes. One day your boss walks up and has some bad news:
"Ok, someone screwed up. They delivered a package here that contains fake gold. The only way to recognize the package is by its weight, so you will have to weigh every package and see if it is lighter than the others. I already spoke with the folks at registry and narrowed it down to 512000 packets, which is still a lot I guess. You have time until tomorrow to find the quickest way to get the job done. I can get 4 scales from town, but every scale will only hold 1000 packages max. Also you won't be able to get the weight from these scales, but you will easily see the difference if the fake package is on one of these scales, of course only if all the scales have the exact same number of packages on them. I want you to find the way that needs the fewest scale attempts for the worst case scenario.
For every scaling you can put a stack of packages (not more than 1000 for every stack) on each of the four scales, and see the difference between those four stacks of packages. When you have the procedure please find the number of scale attempts needed for the best case and the worst case and report with the numbers to me tomorrow. I hope it is better than mine, because if not I may just fire you."....
number of scaling attempts for best case scenario ______
number of scaling attempts for worst case scenario ______
number of scaling attempts for best case scenario ______ 2
number of scaling attempts for worst case scenario ______ 511119
Most efficient way of finding fake package, if all packages have to be checked _______ 137 (off the top of my head)
Best scenario takes pure chance into account, and means that you decide to weigh the packages in batches of three, placing one on each scale, starting with packages 1, 2, and 3, and just happen to pick up an imbalance on this very first (1)attempt, then trying (2) packages 2 & 3 on their own and finding them to be equal weight, so therefore it means that package 1 is the fake.
Worst scenario involves starting with weighing two packages at a time, each on a separate scale, (1) and then changing only one package per scaling (the remaining 511198 packages, meaning a further 511198 attempts) only to find that the very last remaining package is the fake, as it shows lighter than package 511999, which was of equal weight to all the others.
nope
nope i tried that and it didnt work...worst case scenario can only consist at max of a 5 digit number
Number of scaling attempts for best case scenario = 5
Number of scaling attempts for worst case scenario =133
You get to define one procedure, then determine the best and worst cases for that procedure.
I get 6 and 133.
It can take from 1 to 128 scalings to get down to 1000 packages by weighing 4 different stacks of 1000 in each scaling.
From there, continue to divide the stack into fifths. Weigh 4 and keep 1 on the side. If the 4 balance, the fifth contains the bad package.
After 1 extra scaling, you've narrowed it to 200.
After 2 extra scalings, you've narrowed it to 40.
After 3 extra scalings, you've narrowed it to 8.
Now divide the stack in to quarters.
After 4 extra scalings, you've narrowed it to 2.
(Now add 2 known good packages if every scaling must contain 4 stacks.)
After 5 extra scalings, you've narrowed it to 1.
5 + 1 = 6
5 + 128 = 133
Congrats
Tryagain got it the answer was best case 5 worst case 133... ill have more soon
How do you get it done in 5?
log5(1000) > 4 (log5 is log base 5)
So, if you start with 1000, it takes 5 scalings.
markr wrote:How do you get it done in 5?
Asked for help from mismi40.
I just figured it out.
After narrowing it down to 8, weigh 4 stacks of 1 with a stack of 4 on the side. 50% of the time the bad package will be on a scale (only 4 extra scalings required). The other 50% of the time the bad package will be in the stack on the side, and it will take 1 more scaling.
Re: nope
robdux wrote:...worst case scenario can only consist at max of a 5 digit number
Did I miss this 5 digit limit in the opening post?
I've just had another look and still can't see it.
Just of the top of my head I got
best: 6
worst 138
OK, I missed that the answer was given already!
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace