Demonstrating objects are of equal weight

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Demonstrating objects are of equal weight

Postby ekim » Thu Nov 06, 2014 8:25 pm UTC

Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Demonstrating objects are of equal weight

Postby Nitrodon » Thu Nov 06, 2014 8:42 pm UTC

This may or may not be optimal.
Spoiler:
ceil(log2 N)

Weigh 1 vs 2, then 1+2 vs 3+4, then 1+2+3+4 vs 5+6+7+8, and so forth. At each step, all objects that have been weighed are known to have the same weight. When there are not enough objects to do this, weigh all remaining objects against the same number of already tested objects.

rmsgrey
Posts: 3412
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Demonstrating objects are of equal weight

Postby rmsgrey » Thu Nov 06, 2014 8:50 pm UTC

ekim wrote:Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?


I can do it with Ceiling(log[sub]2[/log]N) weighings:

Spoiler:
Weigh one against another; weigh both against another pair; all four against another four; and so on until you can weigh N/2 known against N/2 unknown

If you have n known to be the same weight as each other, since there are only 2 possible weights, any combination of n unknown objects that has the same total weight as the n known must each have the same individual weight.

Or you could work the other way by weighing half of them against the other half, then analysing one half the same way. If N is odd, then set one object aside before splitting and weighing, then add it into the half you analyse further. For example, with N=7, you'd weigh 3v3 then add the spare to one of the 3s to make 4 which you'll weigh 2v2 then take one of those pairs to weigh 1v1

CharlieP
Posts: 397
Joined: Mon Dec 17, 2012 10:22 am UTC
Location: Nottingham, UK

Re: Demonstrating objects are of equal weight

Postby CharlieP » Wed Apr 01, 2015 1:56 pm UTC

Deleted because I didn't read the question properly. :(
This is my signature. There are many like it, but this one is mine.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Demonstrating objects are of equal weight

Postby Qaanol » Thu Apr 02, 2015 4:02 am UTC

Zero. The problem can be solved without using a balance scale at all.

Spoiler:
1. Weigh all the objects on a digital scale of sufficient precision and accuracy.
2. Weigh a single object on the same digital scale.
3. Divide the results.

If the quotient equals the number of objects—meaning in particular it is an integer to within the precision of the scale—and the scale is both precise and accurate enough to distinguish between “all the same weight” and “all-but-one the same weight”, that answers the question.


Or one, if weighing on a balance is the only permissible method to compare weights.

Spoiler:
1. Move the lever arm so the length on one side of the fulcrum is exactly (N-1) times the length on the other side.
2. Weigh one object on the long side against the rest on the short side.
3. If the scale balances, they are all equal.
wee free kings

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6170
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Demonstrating objects are of equal weight

Postby Thesh » Thu Apr 02, 2015 7:23 am UTC

Qaanol wrote:Zero. The problem can be solved without using a balance scale at all.

Spoiler:
1. Weigh all the objects on a digital scale of sufficient precision and accuracy.
2. Weigh a single object on the same digital scale.
3. Divide the results.

If the quotient equals the number of objects—meaning in particular it is an integer to within the precision of the scale—and the scale is both precise and accurate enough to distinguish between “all the same weight” and “all-but-one the same weight”, that answers the question.


Spoiler:
(1+1+1) = (1+1.5+0.5)
Summum ius, summa iniuria.

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: Demonstrating objects are of equal weight

Postby SPACKlick » Thu Apr 02, 2015 7:33 am UTC

Thesh wrote:
Qaanol wrote:Zero. The problem can be solved without using a balance scale at all.

Spoiler:
1. Weigh all the objects on a digital scale of sufficient precision and accuracy.
2. Weigh a single object on the same digital scale.
3. Divide the results.

If the quotient equals the number of objects—meaning in particular it is an integer to within the precision of the scale—and the scale is both precise and accurate enough to distinguish between “all the same weight” and “all-but-one the same weight”, that answers the question.


Spoiler:
(1+1+1) = (1+1.5+0.5)

Spoiler:
1, 1.5, 0.5 = 3 different weights
ekim wrote:Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?

emphasis mine

User avatar
jaap
Posts: 2081
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Demonstrating objects are of equal weight

Postby jaap » Thu Apr 02, 2015 7:37 am UTC

Thesh wrote:
Qaanol wrote:Zero. The problem can be solved without using a balance scale at all.

Spoiler:
1. Weigh all the objects on a digital scale of sufficient precision and accuracy.
2. Weigh a single object on the same digital scale.
3. Divide the results.

If the quotient equals the number of objects—meaning in particular it is an integer to within the precision of the scale—and the scale is both precise and accurate enough to distinguish between “all the same weight” and “all-but-one the same weight”, that answers the question.


Spoiler:
(1+1+1) = (1+1.5+0.5)

The problem specifies exactly two distinct weights, so that objection doesn't work.

The problem states "... how many balance-scale tests are required to show ..."
Normal people infer that what is meant is ".. if you were to use only a balance scale in the normal way, how many weighings are required to show ..."
I can only conclude that Qaanol is not normal :D.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6170
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Demonstrating objects are of equal weight

Postby Thesh » Thu Apr 02, 2015 7:45 am UTC

Okay, I parsed it as "There are two pools of objects, x and y, pool x weighs a, pool y weighs b, a != b."
Summum ius, summa iniuria.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Demonstrating objects are of equal weight

Postby Qaanol » Thu Apr 02, 2015 5:09 pm UTC

jaap wrote:The problem states "... how many balance-scale tests are required to show ..."
Normal people infer that what is meant is ".. if you were to use only a balance scale in the normal way, how many weighings are required to show ..."
I can only conclude that Qaanol is not normal :D.

I am quite entirely comfortable with that conclusion. However to be fair, I did make a slight mistake in one of my answers.

Spoiler:
For the one-balance version, insert step 1.5, “Slide the counterweight (or tare) so that the scale balances with nothing on either side.”

Also, for the zero-balance version, an alternative is just to weigh each object individually on the digital scale, which suffices even when there are more than two possible weights.
wee free kings

User avatar
Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Demonstrating objects are of equal weight

Postby Wildcard » Fri Apr 24, 2015 11:14 am UTC

ekim wrote:Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?

This doesn't make complete sense to me...if there are two distinct weights, how can they all be the same weight?

Or do you mean they are SUPPOSED to be two distinct weights, but they're actually not?

Or do you mean it's a given that every object you get will either be of weight A or weight B, but you don't know for any given object whether it has weight A or weight B, and also you don't know how many objects of weight A you have nor how many objects of weight B you have, and also you don't know if A is greater than or less than B, and also you don't know the value of A or B—but you do know that A does not equal B—and the question is to determine in a minimum number of weighings whether you have been given a sample consisting entirely of weight A objects? (Or, equivalently, a sample consisting entirely of weight B objects, since you don't know the values of A or B and would be labeling them arbitrarily.)

I think this last one is complicated enough that it's probably the intention of the puzzle. :twisted:

In other words, if my guess is correct, you mean that you have N objects, which either (case 1) have all the same weight or (case 2) have exactly two distinct weights, and you're trying to determine which case is correct.

Is that right?
There's no such thing as a funny sig.

rmsgrey
Posts: 3412
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Demonstrating objects are of equal weight

Postby rmsgrey » Fri Apr 24, 2015 6:08 pm UTC

Wildcard wrote:
ekim wrote:Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?

This doesn't make complete sense to me...if there are two distinct weights, how can they all be the same weight?

Or do you mean they are SUPPOSED to be two distinct weights, but they're actually not?

Or do you mean it's a given that every object you get will either be of weight A or weight B, but you don't know for any given object whether it has weight A or weight B, and also you don't know how many objects of weight A you have nor how many objects of weight B you have, and also you don't know if A is greater than or less than B, and also you don't know the value of A or B—but you do know that A does not equal B—and the question is to determine in a minimum number of weighings whether you have been given a sample consisting entirely of weight A objects? (Or, equivalently, a sample consisting entirely of weight B objects, since you don't know the values of A or B and would be labeling them arbitrarily.)

I think this last one is complicated enough that it's probably the intention of the puzzle. :twisted:

In other words, if my guess is correct, you mean that you have N objects, which either (case 1) have all the same weight or (case 2) have exactly two distinct weights, and you're trying to determine which case is correct.

Is that right?


Yeah. Another way of looking at it is that you started with two large sacks of, say, 100N objects, one sack containing objects of weight A; the other containing objects of weight B, dumped them both out, the objects got mixed up, then you took a fairly small sample of N objects (half of 1% of the heap) and want to know whether you got a mixture of objects from both sacks, or all the objects in your sample came from the same sack.

The pools with 2 distinct weights means that out there in the general population of objects you could be working with, there are two (and only two) different weights. Having drawn some objects from that population, there's no guarantee you got a representative sample...

User avatar
Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Demonstrating objects are of equal weight

Postby Wildcard » Fri Apr 24, 2015 11:02 pm UTC

In that case
Spoiler:
Do Nitrodon's solution, but do it backwards to maximize time efficiency.

Regardless of the method used, the only way to "stop early" is if not all weights are equal. Therefore you want to maximize the chance of having this occur early in the weighings, if it is true.

So if N is even, split into two equal piles and weigh one against the other. If N is odd, leave one object out and weigh half of the rest against the other half. If the first (or ANY weighing) is not equal, you're done.

If the weighing returns equal, take one pile (plus the odd object out if there was one) as your new N and repeat.

It works by induction: If you prove that the new smaller pile is all of equal weight, then the original pile is all of equal weight as well.

And any weighing reduces the problem from size N either to size N/2 or to size (N+1)/2, depending on whether N is even or odd.

Worst case running time is still the same, but it should only occur if all weights are equal. Working out the probabilistic running time is beyond me, I confess, because worst case running time CAN occur in other ways. The "other ways" are left as an exercise for the reader. :wink:
There's no such thing as a funny sig.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests