Equilibrium Property

[BMAD]

Given thirteen gears, each weighing an integral number of grams.  It is known that any twelve of them may be placed on a pan balance, six on each pan, in such a way that the scale will be in equilibrium.  Prove that all gears must be of equal weight.

[Rob_G]

Well

Assume that 12 are already balanced on the scale. If I switch any gear for the 13th one the scale would still remain balanced. Therefore the 13th gear and the gear I would replace have the same weight. I can take the same 13th gear and repeat this for the other 11 gears for the same result making all 13 of them the same weight.

[CaptainEd]

Is your first if-statement necessary and sufficient?

Suppose the 13th gear weighs 2 grams, and we swap out a 4 gram gear. Now that pan is 2 grams lighter than the other, so maybe I can swap a 3 gram from that pan with a 4 gram from the other pan. Now they are balanced again, even though your "if I switch..." and your "Therefore..." sentences are both false.

[Logophobic]

A simple proof:

Assuming the scale is balanced: If the gear not on the scale differed in weight from any of the gears on the scale, then swapping those two gears would put the scale out of balance. In order to balance the scale, you would need to transfer half the difference from the heavier pan to the lighter pan. This will not be possible if the swapped gears had the minimum difference in weight. There must therefore be no difference in weight between any two gears.

[plasmid]

A simple proof:

Hidden Content

You're probably on the right track, but that's not an airtight proof. Here's a counterexample. (It uses four weights per pan instead of six in order to make it easier to see what's going on, but it would still apply to the case of having six gears per pan.)

Left pan: 2.5 + 8 + 11.5 + 19 = 41

Right pan: 1 + 10 + 14 + 16 = 41

Off the balance: 18

Minimum difference between gear weights: 1 (between 18 and 19)

 

Weights 18 and 19 are the minimum difference, so swap them.

Then swap weights 2.5 and 10, so the balance shifts by 15.

And swap weights 1 and 8, so the balance shifts by 14.

Left pan: 10 + 1 + 11.5 + 18 = 40.5

Right pan: 8 + 2.5 + 14 + 16 = 40.5

[Logophobic]

You have overlooked the integral weight requirement, but your argument against my 'simple proof' still holds.

I was trying to simplify a more complete proof that I had in mind:

1) No two gears can differ in weight by an odd number of grams.

Proof: If the scale is balanced, the total weight on the scale must be even (an integral weight on each pan). If any of the twelve gears on the scale differs in weight from the thirteenth gear by an odd number of grams, then swapping those two gears would cause the total weight on the scale to be odd and therefore impossible to balance.

2) No two gears can differ in weight by 2n grams for any odd integer n.

Proof: If the scale is balanced and any of the the twelve gears on the scale differs in weight from the thirteenth gear by 2n grams, then swapping those two gears would leave one pan 2n grams heavier than the other. In order to balance the scale, you would need to transfer n grams from the heavier pan to the lighter pan. Since n is odd and no two gears differ in weight by any odd number of grams, it is not possible to balance the scale.

3) No two gears can differ in weight by 2^kn grams for any integer k and any odd integer n.

This is an extension of the above. In order to balance the scale, you would need to be able to transfer 2^k-1n grams for any k. This implies the need to transfer 2^1-1n = n grams, which is not possible.

Edited December 7, 2015 by Logophobic

[plasmid]

Ah, thanks for catching the requirement about integer weights.

If you multiply the terms in that example by 2 to make them integers, it would be a counter to the second point above where n=1. Regardless, based on the first point, I believe you're very close to a solution that's far more elegant than the sort of approach I initially thought this problem was going to require.

[Logophobic]

Your example is not a counter to my second point because it is in opposition to my first point: it contains both even- and odd-weight gears. The validity of my second point is implied by the validity of my first point. There does not exist a counter-example to the second point that does not contradict the first. The first (k=0) and second (k=1) together are a proof by induction of the third.

 

[plasmid]

Ok, I see what you're saying now, and I think your proof is correct. For what it's worth, this is what I had in mind.

 

A solution set of weights cannot have both odd and even weights, because then omitting either an odd weight or an even weight from the balance must leave an odd amount of weight on the pans left to balance, which is impossible.

Suppose you had a set of weights that is a solution. If you add a constant value to every weight, or if you multiply every weight by the same factor, then the resulting set of weights must also be a solution because it won't affect the scale's balance.

Call the largest weight in the proposed solution w. Find the smallest power of two that's greater than w, and add (2ⁿ-w) to each weight so now the largest weight will be 2ⁿ. Next, repeatedly divide all of the weights by 2 until one of them is odd. If there are any weights smaller than the largest weight, then they will become odd before the largest weight becomes odd because the largest weight is a power of 2, and you would be left with a mix of odd and even weights to show that the set of weights is not a solution.

 

Edited December 10, 2015 by plasmid
attempting to put a spoiler in, but the [spoiler] tag doesn't seem to be working

[Logophobic]

I like your solution. I attempted to come up with a logical proof by adding/subtracting a constant value, but couldn't sort it out.