Let $P(A)$ be the arithmetic-means of all elements of set $A = \{ a_1, a_2, \ldots, a_n \}$, namely $P(A) = \frac{1}{n} \sum^{n}_{i=1}a_i$. We denote $B$ "balanced subset" of $A$, if $B$ is a non-empty subset of $A$ and $P(B) = P(A)$. Let set $M = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. Find the number of all "balanced subset" of $M$.
Problem
Source: CSEMO 2005-6
Tags: symmetry, induction, combinatorics unsolved, combinatorics
20.07.2005 15:21
the question means: how many ''balanced subsets'' does M have?
24.07.2005 12:44
Case 1: the subset doesn't include 5 Case 1.1: the subset includes 4,6. Now the numbers 4,5,6 don't affect the arithmetic means, so we find the subset M of {1,2,3,7,8,9} with P(M) = 5. We find that there are 8 of them. Case 1.2: the subset doesn't include 4,6. It is the same as case 1.1, because the numbers 4 and 6 doesn't affect the arithmetic means. Case 1.3: the subset includes 4, but not 6. We find that there are 5 of them. Case 1.4: the subset includes 6, but not 4. By symmetry, there are 5 as well. So there are 26 subsets Case 2: the subset includes 5. Since the number 5 doesn't affect the arithmetic mean, it is the same as case 1. But we've counted the empty set, so the actual total number is 51.
24.07.2005 14:14
I'd look at the numbers not as they are written down now, but at their difference with 5. So: 4, 3, 2, 1, 0, 1, 2, 3, 4 At both the left and the right part, the sum of the differences must be the same. D is the total difference at one side: If D = 0: One possibility at both sides: (empty) 1*1=1 If D = 1: One possibility at both sides: 4, 6 1*1=1 If D = 2: One possibility at both sides: 3, 7 1*1=1 If D = 3: Two possibilities at both sides: 3+4 / 2, 6+7 / 8 2*2=4 If D = 4: Two possibilities at both sides: 2+4 / 1, 6+8 / 9 2*2=4 If D = 5: Two possibilities at both sides: 1+4 / 2+3, 6+9 / 7+8 2*2=4 If D = 6: Two possibilities at both sides: 1+3 / 2+3+4, 7+9 / 6+7+8 2*2=4 If D = 7: Two possibilities at both sides: 1+2 / 1+3+4, 8+9 / 6+7+9 2*2=4 If D = 8: One possibility: no 3, 7 1*1=1 If D=9: One possibility: no 4,6 1*1=1 If D=10: all numbers: 1 Counting gives us 26. Multiplied by 2 for including or excluding 5 gives 52, minus the empty subset gives us 51 as well!
24.07.2005 15:36
Nice solution! Now try the case $M = \{1,2,3,...,k\}$
24.07.2005 15:50
I'm going away for a few days, but of course I already thought about this a little. Maybe, induction? If the answer for {1,2,3....k} is A(k): A(2a+1) = A(2a)*2+1 When k = 2a, the number of elemens in a subset must be even, since the mean is a+1/2. A(1) = 1 A(2) = 1 A(3) = 3 A(4) = 3 A(5) = 7 A(6) = 7 A(7) = 15 For these small numbers there is a pattern, but A(9) = 51 does not fit :'(. A(2a) >= A(2a-1) Maybe you can count by the number of elements in the subset you want to create. I'll check this topic later, arrivederci!
05.08.2005 09:36
Hmm... then it seems I can't solve this
11.06.2018 07:03
Can someone pls check my solution, I got 39 instead
Help pls Edit:I had a careless again whoops Edit: I just realized I think I have the shortest most elegant solution using complements