Prove ten objects can be divided into two groups that balances each other when placed on the two pans of balance. [closed]

This result holds in the general case with 2ドルm$ objects of total weight 4ドルm,ドル with none of the weights exceeding 2ドルm$.

If a list P of positive integers sums to $n$ then P is called a partition of $n$. Let |P| denote the number of elements in P.

Let S' be the set of partitions P' of 2ドルn$ with |P'| = $n$ (i.e., each partition P' in S' has $n$ elements and P' sums to 2ドルn$) with no element of any P' exceeding $n$.

We can transform S' into a set S by subtracting 1 from each element of each P' in S'. S is then the set of all partitions P of $n$ except for the singleton partition [$n$], since we've reduced the sum of each P' by $n,ドル and each |P| $ \le n$. Conversely, given S we can recover S' by adding 1 to each existing element in each P and padding each P with extra ones to get the required length.

So we can attack the problem stated in the question by looking at the set of all partitions of 10 (except for the partition [10]), rather than the set of partitions of 20 of length 10 with no element exceeding 10.

Given a partition P of $n,ドル divide its elements into two lists A and B of approximately equal sums. Let $a$ be the sum of the elements of A, and $b$ be the sum of the elements of B; $a + b = n$. WLOG, assume $a \ge b$. We want to minimize the difference $d = a - b$. This can be achieved using a simple "greedy" algorithm.

• Sort P in descending order.
• For each $p$ in P, append $p$ to whichever of A and B currently has the lowest sum.
• When finished, swap A & B, if necessary to ensure $a \ge b$.

Proof that this algorithm does, in fact, minimize $d$ will be left as a exercise for the reader. :)

Now we just need to add $a$ ones to B and $b$ ones to A to get our balanced weights. But this step is only valid if $|A| \le b$ and $|B| \le a,ドル since we must add a one to each existing element in A and in B.

1ドル \le b \le n/2 \le a \lt n $
$n$ is even, so $n/2$ is an integer.

Clearly, for any P, the sum of its elements must be $ \ge |P|,ドル since each element in P is at least 1.

So $|B| \le b \le a,ドル thus $|B| \le a$. It only remains to show that $|A| \le b$.

If $d = 0$ then $a = b = n/2$ and so $|A| \le n/2 = b$.

We now look at the case where $d > 0$.

$a + b = n,ドル which is even, so $d = a - b$ is also even. And since it's non-zero in what follows, its minimum value is 2.

For any element $t$ in A, if $t < d$ we could swap $t$ over to B to reduce the difference:

$$\begin{align} \text{Let }& 0 < t < d\\ \text{Let }d' & = (a-t) - (b+t)\\ & = a - b - 2t\\ d' & = d - 2t\\ -d & < -t < 0\\ -2d & < -2t < 0\\ -d & < d-2t < d\\ -d & < d' < d\\ |d'| & < d \end{align}$$

But A and B have been constructed to minimize $d,ドル so all elements in A must be $ \ge d$.
If |A| were $\gt b,ドル it's minimal value would be $b+1,ドル and the minimal value of $a$ would thus be

$$\begin{align} (b + 1)d & = bd + d\\ & = bd + a - b\\ & = b(d-1) + a\\ \end{align}$$

But $d$ is an even integer> 0, so $b(d-1) + a \ge b + a = n > a,ドル and we have a contradiction.
Thus $|A| \le b$.

Update

That indirect proof that $|A| \le b$ has been annoying me. :) So here's a direct proof.

Each element of A is $ \ge d,ドル so $a \ge |A|d$

$$\begin{align} d & > 1\\ bd & > b\\ bd + d & > b + d = a \ge |A|d\\ (b + 1)d & > |A|d\\ b + 1 & > |A|\\ b & \ge |A|\\ \end{align}$$

I found some very efficient algorithms for generating partitions via this answer to the question Algorithm for generating integer partitions. You can see the original Python code for that partitioning algorithm on Jerome Kelleher's site, and his paper discussing the efficiency of various partitioning algorithms on arXiv Generating All Partitions: A Comparison Of Two Encodings. Most partitioning algorithms found on the Net are recursive, so it's nice to see some efficient iterative algorithms. :) According to Jerome's paper, the optimized algorithm listed on his website is the most efficient partitioning algorithm known.

 Balanced partitions for 10
 1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 0, [1, 1, 1, 1, 1] 5, [1, 1, 1, 1, 1] 5
[2, 2, 2, 2, 2], [2, 2, 2, 2, 2]
 2: [2, 1, 1, 1, 1, 1, 1, 1, 1]
 0, [2, 1, 1, 1] 5, [1, 1, 1, 1, 1] 5
[3, 2, 2, 2, 1], [2, 2, 2, 2, 2]
 3: [2, 2, 1, 1, 1, 1, 1, 1]
 0, [2, 1, 1, 1] 5, [2, 1, 1, 1] 5
[3, 2, 2, 2, 1], [3, 2, 2, 2, 1]
 4: [2, 2, 2, 1, 1, 1, 1]
 0, [2, 2, 1] 5, [2, 1, 1, 1] 5
[3, 3, 2, 1, 1], [3, 2, 2, 2, 1]
 5: [2, 2, 2, 2, 1, 1]
 0, [2, 2, 1] 5, [2, 2, 1] 5
[3, 3, 2, 1, 1], [3, 3, 2, 1, 1]
 6: [3, 1, 1, 1, 1, 1, 1, 1]
 0, [3, 1, 1] 5, [1, 1, 1, 1, 1] 5
[4, 2, 2, 1, 1], [2, 2, 2, 2, 2]
 7: [3, 2, 1, 1, 1, 1, 1]
 0, [3, 1, 1] 5, [2, 1, 1, 1] 5
[4, 2, 2, 1, 1], [3, 2, 2, 2, 1]
 8: [3, 2, 2, 1, 1, 1]
 0, [3, 1, 1] 5, [2, 2, 1] 5
[4, 2, 2, 1, 1], [3, 3, 2, 1, 1]
 9: [3, 2, 2, 2, 1]
 0, [3, 2] 5, [2, 2, 1] 5
[4, 3, 1, 1, 1], [3, 3, 2, 1, 1]
10: [3, 3, 1, 1, 1, 1]
 0, [3, 1, 1] 5, [3, 1, 1] 5
[4, 2, 2, 1, 1], [4, 2, 2, 1, 1]
11: [3, 3, 2, 1, 1]
 0, [3, 2] 5, [3, 1, 1] 5
[4, 3, 1, 1, 1], [4, 2, 2, 1, 1]
12: [3, 3, 2, 2]
 0, [3, 2] 5, [3, 2] 5
[4, 3, 1, 1, 1], [4, 3, 1, 1, 1]
13: [4, 1, 1, 1, 1, 1, 1]
 0, [4, 1] 5, [1, 1, 1, 1, 1] 5
[5, 2, 1, 1, 1], [2, 2, 2, 2, 2]
14: [4, 2, 1, 1, 1, 1]
 0, [4, 1] 5, [2, 1, 1, 1] 5
[5, 2, 1, 1, 1], [3, 2, 2, 2, 1]
15: [4, 2, 2, 1, 1]
 0, [4, 1] 5, [2, 2, 1] 5
[5, 2, 1, 1, 1], [3, 3, 2, 1, 1]
16: [4, 3, 1, 1, 1]
 0, [4, 1] 5, [3, 1, 1] 5
[5, 2, 1, 1, 1], [4, 2, 2, 1, 1]
17: [4, 3, 2, 1]
 0, [4, 1] 5, [3, 2] 5
[5, 2, 1, 1, 1], [4, 3, 1, 1, 1]
18: [4, 4, 1, 1]
 0, [4, 1] 5, [4, 1] 5
[5, 2, 1, 1, 1], [5, 2, 1, 1, 1]
19: [5, 1, 1, 1, 1, 1]
 0, [5] 5, [1, 1, 1, 1, 1] 5
[6, 1, 1, 1, 1], [2, 2, 2, 2, 2]
20: [5, 2, 1, 1, 1]
 0, [5] 5, [2, 1, 1, 1] 5
[6, 1, 1, 1, 1], [3, 2, 2, 2, 1]
21: [5, 2, 2, 1]
 0, [5] 5, [2, 2, 1] 5
[6, 1, 1, 1, 1], [3, 3, 2, 1, 1]
22: [5, 3, 1, 1]
 0, [5] 5, [3, 1, 1] 5
[6, 1, 1, 1, 1], [4, 2, 2, 1, 1]
23: [5, 3, 2]
 0, [5] 5, [3, 2] 5
[6, 1, 1, 1, 1], [4, 3, 1, 1, 1]
24: [5, 4, 1]
 0, [5] 5, [4, 1] 5
[6, 1, 1, 1, 1], [5, 2, 1, 1, 1]
25: [5, 5]
 0, [5] 5, [5] 5
[6, 1, 1, 1, 1], [6, 1, 1, 1, 1]
26: [2, 2, 2, 2, 2]
 2, [2, 2, 2] 6, [2, 2] 4
[3, 3, 3, 1], [3, 3, 1, 1, 1, 1]
27: [3, 3, 3, 1]
 2, [3, 3] 6, [3, 1] 4
[4, 4, 1, 1], [4, 2, 1, 1, 1, 1]
28: [4, 2, 2, 2]
 2, [4, 2] 6, [2, 2] 4
[5, 3, 1, 1], [3, 3, 1, 1, 1, 1]
29: [4, 3, 3]
 2, [3, 3] 6, [4] 4
[4, 4, 1, 1], [5, 1, 1, 1, 1, 1]
30: [4, 4, 2]
 2, [4, 2] 6, [4] 4
[5, 3, 1, 1], [5, 1, 1, 1, 1, 1]
31: [6, 1, 1, 1, 1]
 2, [6] 6, [1, 1, 1, 1] 4
[7, 1, 1, 1], [2, 2, 2, 2, 1, 1]
32: [6, 2, 1, 1]
 2, [6] 6, [2, 1, 1] 4
[7, 1, 1, 1], [3, 2, 2, 1, 1, 1]
33: [6, 2, 2]
 2, [6] 6, [2, 2] 4
[7, 1, 1, 1], [3, 3, 1, 1, 1, 1]
34: [6, 3, 1]
 2, [6] 6, [3, 1] 4
[7, 1, 1, 1], [4, 2, 1, 1, 1, 1]
35: [6, 4]
 2, [6] 6, [4] 4
[7, 1, 1, 1], [5, 1, 1, 1, 1, 1]
36: [7, 1, 1, 1]
 4, [7] 7, [1, 1, 1] 3
[8, 1, 1], [2, 2, 2, 1, 1, 1, 1]
37: [7, 2, 1]
 4, [7] 7, [2, 1] 3
[8, 1, 1], [3, 2, 1, 1, 1, 1, 1]
38: [7, 3]
 4, [7] 7, [3] 3
[8, 1, 1], [4, 1, 1, 1, 1, 1, 1]
39: [8, 1, 1]
 6, [8] 8, [1, 1] 2
[9, 1], [2, 2, 1, 1, 1, 1, 1, 1]
40: [8, 2]
 6, [8] 8, [2] 2
[9, 1], [3, 1, 1, 1, 1, 1, 1, 1]
41: [9, 1]
 8, [9] 9, [1] 1
[10], [2, 1, 1, 1, 1, 1, 1, 1, 1]

Let the weights be $x_1, x_2, ... x_{10},ドル such that $x_1 \neq x_2$ (otherwise all the weights would be equal, which is a trivial case). We need to find a subset of it such that the sum of its elements is 10ドル$.

Consider, $x_1, x_2, x_1+x_2, ..., x_1+x_2+x_3 + .. +x_9$. Note that if one of them is divisible by 10ドル,ドル then it must be exactly 10ドル,ドル as it must be smaller than 20ドル$. Thus if one of them is divisible by 10ドル,ドル we are done, if not, by pigeonhole principle, two of them have the same remainder$\mod10$.

If we subtract these two subsets, we have one subset whose sum is divisible by 10ドル,ドル but could neither be 0ドル$ or 20ドル,ドル so it must be 10ドル$. Note that these two can't be $x_2$ and $x_1,ドル as it would imply $x_2>10$.

• $\begingroup$ Your second paragraph is wrong: we are specifically told that $x_1+x_2+x_3 + .. +x_{10} = 20$. $\endgroup$

  TonyK

  – TonyK

  05/19/2015 15:39:34

  Commented May 19, 2015 at 15:39
• $\begingroup$ @TonyK Corrected. $\endgroup$

  Sawarnik

  – Sawarnik

  07/23/2015 16:52:26

  Commented Jul 23, 2015 at 16:52

I don't think that there is a standard procedure, similar to the "Master Theorem", that can be applied to your problem. (Maybe someone comes up with a pigeon-hole-principle solution.) This means that we have to play with the problem by looking at cases, in order to get the feel of it. The aim is to set everything up in such a way that a minimum of cases has to be discussed.

Update

An object of weight 1ドル$ has "underweight" 1ドル,ドル an object of weight 2ドル$ has normal weight, and any object with weight $w\geq3$ has overweight $w-2>0,ドル which has to be compensated by $w-2$ objects having weight 1ドル$.

If there is an object $A_0$ with weight $w\geq6$ then there are $\geq4$ objects $A_k$ of weight 1ドル$. Supplement$A_0$ with 10ドル-w\leq4$ of these $A_k$ in order to obtain 10ドル$.

From now on we may assume that all objects have weight $\leq 5$. If there are two objects $A_1,ドル $A_2$ of weight 3ドル,ドル 4ドル,ドル or 5ドル,ドル and of combined weight $w\geq7$ then their total overweight is $\geq3,ドル whence there are $\geq3$ objects $A_k$ of weight 1ドル$. Supplement $A_0\cup A_1$ with 10ドル-w\leq3$ of these $A_k$ in order to obtain 10ドル$.

The remaining weight patterns are of the form $$(5,2^6,1^3), \quad (4,2^7,1^2), \quad (3^\alpha,2^{10-2\alpha}, 1^\alpha)$$ with 0ドル\leq\alpha\leq5,ドル and are easy to deal with.

• $\begingroup$ Thanx , I will try to use pigeon hole principle and make cases $\endgroup$

  Murtuza Vadharia

  – Murtuza Vadharia

  05/15/2015 07:51:32

  Commented May 15, 2015 at 7:51
• $\begingroup$ @MurtuzaVadharia: Hopefully, you'll find my approach a little simpler. :) $\endgroup$

  PM 2Ring

  – PM 2Ring

  05/18/2015 14:12:57

  Commented May 18, 2015 at 14:12
• $\begingroup$ I did came up with that pigeonhole solution :D $\endgroup$

  Sawarnik

  – Sawarnik

  09/07/2016 08:16:56

  Commented Sep 7, 2016 at 8:16

• combinatorics
• proof-writing