Let set $ T = \{1,2,3,4,5,6,7,8\}$. Find the number of all nonempty subsets $ A$ of $ T$ such that $ 3|S(A)$ and $ 5\nmid S(A)$, where $ S(A)$ is the sum of all the elements in $ A$.
Problem
Source: Problem 1 from CWMO 2007
Tags: combinatorics proposed, combinatorics
18.11.2007 11:42
There is no way to select a subset of $ T$ with at least $ 15$ elements, so you probably asked for $ S(A)$ to be the sum of the elements in $ A$ Pierre.
18.11.2007 11:44
pbornsztein wrote: There is no way to select a subset of $ T$ with at least $ 15$ elements, so you probably asked for $ S(A)$ to be the sum of the elements in $ A$ Pierre. Edited
19.11.2007 16:12
19.11.2007 16:17
I can't understand one thing,why there is always someone who post a hint? Tell me the reason.If you've solved it then post your complete proof,if not as you've already seen(i hope),i posted it in Proposed and Own Problems,hence i know solution,and if nobody will solve it during the week,i'll post a hint.OK?
19.11.2007 18:52
Sorry for the inconvenience. I ll post the complete solution: $ 1 \le S(A) \le 1 + 2 + \cdots + 8 = 36 \Rightarrow S(A) = 3,6,9,12,18,21,24,27,33,36$ Let $ \#An =$ the number of subsets of $ A$ with $ S(A) = n$ then $ \#A36 = 1, \#A(36 - i) = \#Ai$ $ \#A3 = \#A33 = 2$ $ \#A6 = 4$ $ \#A9 = \#A27 = 7$ $ \#A12 = \#A24 = 10$ $ \#A18 = 14$ $ \#A21 = 13$ $ \#A36 = 1$ $ TOTAL = 70$
19.11.2007 18:56
Yes,your proof is correct,but i think that you must show all subsets,that you have counted. There is one easier proof,that use much less counting,and i'll post it if nobody do it,until next week,OK?