Weigh me (1 Viewer)

[z600]

Here is the situation:
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."
Now, thats your situation. Find the best answers fast and plug them in below.


Scaling attempts for the best case:
Scaling attempts for the worst case:

 

[KeypadSDM]

Brute forcing it: You need to perform 128 weighings to find the fake packet, within 1000 bars.
Then you do the whole:
200 on each scale, 200 off
40 on each scale, 40 off
8 on each scale, 8 off
1 on each scale, 4 off
1 on each scale, 0 off.

Thus:

Scaling attempts for the best case: 5
Scaling attempts for the worst case: 133

I dunno how you can avoid 128 weighings on the first set, and I can't think of a "mix and match" process being useful on the scales, rather than just a doubly fast binary sort.

 

[SeDaTeD]

Are you allowed to put scales on scales?

 

[KeypadSDM]

Would that really make it quicker?
Plus the scales might or might not be heavier than 1000 packets already.

For simplicity, and completeness, assume not. Otherwise it's a retarded question.

 

[milton]

just do a simple binary search

here's a very similar problem:
You're a govt spy performing a sting operation on a mafia group that has mass produced counterfeit diamonds. when you break into their hideout, you attempt to find the 2 real diamonds among 10,000 fakes. unfortunately they all look identical and you cant tell them apart by sight. fortunately, you brought along a set of scales and you know that the 2 real diamonds weigh 15g and 5g and that all the fake diamonds each weigh 10g. using your scales, you can weigh any set of diamonds together you wish, but you are only allowed to weigh 40 times. so waht is your strategy?

i haven't found a perfect strategy yet, but i have a non-deterministic (probabilistic) solutation that works 99.999999% of the time

 

[jyu]

just do a simple binary search

here's a very similar problem:
You're a govt spy performing a sting operation on a mafia group that has mass produced counterfeit diamonds. when you break into their hideout, you attempt to find the 2 real diamonds among 10,000 fakes. unfortunately they all look identical and you cant tell them apart by sight. fortunately, you brought along a set of scales and you know that the 2 real diamonds weigh 15g and 5g and that all the fake diamonds each weigh 10g. using your scales, you can weigh any set of diamonds together you wish, but you are only allowed to weigh 40 times. so waht is your strategy?

i haven't found a perfect strategy yet, but i have a non-deterministic (probabilistic) solutation that works 99.999999% of the time

How did you arrive at the figure 99.999999%? 1 miss out of 100000000.

Close enough is not good enough for a pure mathematician. Keeep trying.

:wave:

 

[ih8skool]

5
133

 

[bos1234]

5 and 133

whats the answer??????????????????????????/