Consider the set $A = \{1, 2, 3, ..., 2008\}$. We say that a set is of type $r, r \in \{0, 1, 2\}$, if that set is a nonempty subset of $A$ and the sum of its elements gives the remainder $r$ when divided by $3$. Denote by $X_r, r \in \{0, 1, 2\}$ the class of sets of type $r$. Determine which of the classes $X_r, r \in \{0, 1, 2\}$, is the largest.
Problem
Source: Indian Postal Coaching 2008 set 6 p6
Tags: combinatorics, number theory, remainder
jelena_ivanchic
27.02.2021 08:29
Really nice problem! It can be made more hard by making us to find the explicit cardinality stuff of each set . But then it's very hard to write stuff.
Consider set $B=\{1,2,\dots , 3k\}, k>1.$
Claim 1:$X_0$ is the largest for set $B.$
We can say by symmetry, $|X_1|=|X_2|.$ And we can show this by induction on $k.$
For base case take $k=2,$ we get $|X_1|=|X_2|=2$ and $|X_3|=3.$ So $X_3 $ is largest. Now if we add $\{4,5,6\}, $ we will get previous set using only
$E=\{1,2,3\}$ , sets using only $F=\{4,1,2,3\}$ , sets using only $G=\{5,1,2,3\}$ ,sets using only $H=\{6,1,2,3\}$, sets using only $I=\{4,5,1,2,3\}$, sets using only $J=\{4,6,1,2,3\}$, sets using only $K=\{5,6,1,2,3\}$, sets using only $L=\{4,5,6,1,2,3\}.$
For now sets $F,G,H,I,J,K,L$ will use at least two elements from there sets with $F$ must having $4$, $G$ having $5$, and so on.
Now initially we has $X_1=2,X_2=2, X_3=3$ . Now if we see sets, $\{4\},\{5\},\{6\},\{4,5\},\{4,6\}, \{5,6\}.$ Now $X_1=3,X_2=3,X_3=5.$
Now set $E's$ all non empty subset ahs been counted. Now consider set $F.$ Since $F's $ subsets will must have $4,$ it's same as having $E's$ subsets, but everything shifting to $1\mod 3,$ hence it will have $X_1=3,X_2=2,X_3=2.$
Similarly Since $G's $ subsets will must have $5,$ it's same as having $E's$ subsets, but everything shifting to $2\mod 3,$ hence it will have $X_1=2,X_2=3,X_3=2.$
And so on.. adding we get $X_1=20,X_2=20,X_3=23.$ For set $\{1,2,3,4,5,6\}.$
Now for $\{1,2,3,4,5,6,7,8,9\}, $ we will have $X_3$ and infact by this method, we get $|X_3| - |X_1|=2\cdot 3+1=7.$
For $\{1,2,3,4,5,6,7,8,9,10,11,12\}, $ we will have $X_3$ and we get $|X_3| - |X_1|=2\cdot 7+1.$
So this forming recurrence stuff. Clearly $K$ grows more, the difference between $X_3$ and $X_1$ grows very much too.
Now consider $C=\{1,2,\cdots,3k,3k+1\},$ It's just the set $B$ but we added ${3k+1}. $ So there are $3$ types of subsets,
Subset's of $B$, {3k+1}, D=Subsets must containing $3k+1.$
Claim2: $X_1$ is the largest for $C.$
Now if for $B,$ we have by our claim, $X_1=X_2=a$ and $X_3=b$ and $b>>a.$
Again, note that $D's$ subets are just $ B's$ subsets, but everything shifted with $1\mod 3.$
So $D's$ contribution to $X_1=b,X_2=a,X_3=a$ and the single set $\{3k+1\} $ contributes $1$ to $X_{1}.$
So for set $C,$ we get $X_1=a+b+1,X_2=a+a,X_3=a+b.$ Hence we get $X_1$ to be the largest.
Note that $2008=2007+1= 3l+1,$ so by our Claim2, we get $X_1$ to be the largest. And we are done!