[Guest]

I think this one has not been posted.

There are 10 objects. Their total weight is 20 units. Each of the weights is a positive integer. Given that none of the weights exceeds 10 units, prove that the ten objects can be divided into two groups that balance each other when placed on 2 pans of a balance.

Enjoy.

[Guest]

22222 22222 = 10 10

[Guest]

see, i was thinking alnog the same lines as pyrojj, but surely that cannot be the actual answer, its way too easy!

perhaps a bit of clarification on the question?

[Guest]

too easy? this seems imposible if one of the objects have a mass over ten, if both sides should be equal, 20/2=10, so each side should have 10, right? and if one of the objects mass over 10, then it gets to be unsolvable

oh, oops, it says none of them exceed 10. not one. well, yes, then it becomes very easy. pyrojj is right

Edited August 14, 2008 by rockstar

[Guest]

too easy? this seems imposible if one of the objects have a mass over ten, if both sides should be equal, 20/2=10, so each side should have 10, right? and if one of the objects mass over 10, then it gets to be unsolvable

oh, oops, it says none of them exceed 10. not one. well, yes, then it becomes very easy. pyrojj is right

That is just one example. That is not a proof of why it must be true in all cases. I can prove it, but it is brute force.

If you order the objects starting with the heaviest first and try to distribute the remaining mass, then you will see there must be a collection of objects whose sum is ten and the remaing will also have a sum of ten.

If x1 has a mass of 10, then the remaining must have a cumulative mass of ten becuase the total mass is 20.

If x1 has a mass of 9, then there are 11 units to distribute amont nine other objects. Hence, at least one of those remaining objects, call it x10, must have a mass of 1. If x1 + x10 = 10, the the cumilative mass of the rest must also be 10.

you can do this on down the line until you get to x1=2.

[Guest]

22222 and 22222 is not correct. It is one solution but the answer is a proof not an example.

[Guest]

The answer is actually fairly simple.

We are dealing with positive integers and none of these weigh more than ten. In order to balance the two groups, one of the groups has to add to ten. Since the total weight has to add to twenty, the combined weight of the second group also has to add to ten. Every combination of weights from one to ten will be divisible into two equal groups as long as their total weight equals twenty.

[Prime]

Here is somewhat heuristic proof. But it is less than a page long.

Possible ways to have a misbalance (in pounds): (1,19), (2,18), …(8,12), (11,9).

Corresponding differences between two plates would be 18, 16, 14, …, 4, 2 lb.

Regard (1,19) combination. The plate with 1 lb can have no more than 1 object, leaving at least 9 for the 19 lb plate. The average weight of an object on that plate is just over 2 lb. Therefore, there have to be objects of 2 lb or less. If we transfer one such object from 19 lb plate, we’ll get a closer distribution – at least (3,17).

Same reasoning for (2,18), (3,17), (4,16).

With (5, 15), the 15 lb plate has at least 5 objects with average weight 3. Therefore, there must be at least one object of 3 lb or less. Transferring that object we achieve closer distribution again. Same for (6,14) and (7,13). E.g., if we transfer 4 lb object from 13 lb plate we get (11,9) which is closer than (7,13).

Consider (8,12). The 12 lb plate must have at least 2 objects. In which case all objects on the 8 lb plate are 1 lb each. Those could be used to make 2 lb difference with any object from 3 to 9 lb from the 12 lb plate. (If one object there weights 10 lb, then another got to weight 2 and could be transferred). If there are 3 or more objects on the 12 lb plate, then there must be an object of 3 lb or less and transferring it would make a closer distribution yet (at least 9 – 11).

All we have left is (9,11) distribution.

If 11 lb plate has 2 objects – one of them must be 5 lb or lighter and the other plate has at least 7 1-lb objects, which are more than enough to construct 1 lb difference with any 5-lb or lighter object.

11-lb plate has 3 objects – there is one 3-lb or lighter and at least 5 1-lb on the other plate.

11-lb plate has 4 or 5 objects – there is at least one 2-lb or lighter on it, and at least 3 and 1 1-lb objects respectively on the 9-lb plate.

If 11-lb plate has 6 or more objects – there got to be at least one 1-lb object on it, which could be transferred.

[Guest]

I think this one has not been posted.

There are 10 objects. Their total weight is 20 units. Each of the weights is a positive integer. Given that none of the weights exceeds 10 units, prove that the ten objects can be divided into two groups that balance each other when placed on 2 pans of a balance.

Enjoy.

I'm new and this is my first post. so hope I did not mess anything up.

we know that all objects must be between 1 and 10. and that each side will have between 1 and 9 objects on them. and that the total of each side much match the other side.

we have side A and Side B of the balance scale.

we will label all objects OA - OJ

lets say for now OA and OJ both = 6 and all other Objects are 1 unit.

OA + OB +OC +OD +OE = OF +OG +OH +OI +OJ

6 + 1 +1 +1 +1 = 1 + 1 +1 +1 +6

you can take any number of objects from one side, and add it to the other.

we will take 3 objects from side A and add them to side B and you get

OA + OB +OC +OD +OE + OF +OG + OH = OI +OJ

6 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 6

add the total number of units (in this case 1+1+1) to the side you took them from, divide between the remaining Objects any way you like, as long as they are never larger then 10. so. . .

OA + OB +OC +OD +OE + OF +OG + OH = (OI+3) +OJ

6 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = (1+3) + 6

then subtract the total number of units added to the other side (in this case 1+1+1) from any number of objects, as long as no object is made to be less then 1.

in this case, because all objects other then OA are 1, we have no choice but to take all 3 units from OA.

(OA -3) +OB +OC +OD +OE + OF +OG + OH = OI +OJ

6 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 6

(6-3) + 1 + 1 + 1 + 1 + 1 + 1 + 1 = (1+3) + 6

we used two 6s and eight 1s but as long as you follow the rules it should always be true that you can divide them into two equal groups.

i'm sure someone smarter then my self can word that much more eloquently, but it will work (I think).

[Guest]

Here is somewhat heuristic proof. But it is less than a page long.

Possible ways to have a misbalance (in pounds): (1,19), (2,18), …(8,12), (11,9).

Corresponding differences between two plates would be 18, 16, 14, …, 4, 2 lb.

Regard (1,19) combination. The plate with 1 lb can have no more than 1 object, leaving at least 9 for the 19 lb plate. The average weight of an object on that plate is just over 2 lb. Therefore, there have to be objects of 2 lb or less. If we transfer one such object from 19 lb plate, we’ll get a closer distribution – at least (3,17).

Same reasoning for (2,18), (3,17), (4,16).

With (5, 15), the 15 lb plate has at least 5 objects with average weight 3. Therefore, there must be at least one object of 3 lb or less. Transferring that object we achieve closer distribution again. Same for (6,14) and (7,13). E.g., if we transfer 4 lb object from 13 lb plate we get (11,9) which is closer than (7,13).

Consider (8,12). The 12 lb plate must have at least 2 objects. In which case all objects on the 8 lb plate are 1 lb each. Those could be used to make 2 lb difference with any object from 3 to 9 lb from the 12 lb plate. (If one object there weights 10 lb, then another got to weight 2 and could be transferred). If there are 3 or more objects on the 12 lb plate, then there must be an object of 3 lb or less and transferring it would make a closer distribution yet (at least 9 – 11).

All we have left is (9,11) distribution.

If 11 lb plate has 2 objects – one of them must be 5 lb or lighter and the other plate has at least 7 1-lb objects, which are more than enough to construct 1 lb difference with any 5-lb or lighter object.

11-lb plate has 3 objects – there is one 3-lb or lighter and at least 5 1-lb on the other plate.

11-lb plate has 4 or 5 objects – there is at least one 2-lb or lighter on it, and at least 3 and 1 1-lb objects respectively on the 9-lb plate.

If 11-lb plate has 6 or more objects – there got to be at least one 1-lb object on it, which could be transferred.

Except for 1 or 2 minor problems here and there, this proof is OK. In fact I love this proof. I have a different proof which I'll post in future. But I am not sure if that would be more elegant than this.

However I am still looking for other and preferably better proofs. Is there anyone?

[Guest]

Here is a try.

since each object must have weight of possitive integer weight of each of them must be at least 1. So if we put them one next to another we would get something like this

1111111111

so we have 10 units left. Since we can not place all 10 remaining units on one place which would exceed the total weight of 10 units we can place maximum of 9 weight on one place which could look like

1

1

1

1

1

1

1

11

1111111111

So max weight we have for one object is 10 and we have one more unit to distribute among other weights.

Regardless where you distribute remaining 10 units you can always summ 1, 2 or more places with total weight of 10.