Determine for which positive integers $k$, the set \[X=\{1990, 1990+1, 1990+2, \cdots, 1990+k \}\] can be partitioned into two disjoint subsets $A$ and $B$ such that the sum of the elements of $A$ is equal to the sum of the elements of $B$.
Problem
Source:
Tags:
06.11.2007 20:16
Let $ S(W)=$ The sum of the elements of $ W$ and $ \# W=$ the number of elements of $ W$ $ S(X)=1990 (k+1) +k(k+1)/2$ It is necessary that $ 2|S(X)$ then $ 2| k(k+1)/2$ then $ 4| k(k+1)$ then $ k \equiv 0,-1 (4)$ $ 1) k=4m+1$ $ X = \{1990,1990+4m+1,$ $ 1990+1 , 1990+4m,$ $ 1990+2 , 1990+4m-1,$ $ \cdots,$ $ 1990+2m, 1990+2m+1\}$ and pick the first column for the elements for $ A$ and we are done. $ 2) k=4m$ $ \#X=4m+1=\#A+\#B$ WLOG $ \#B=b \ge \#A=a$ then $ a=b-e$ with $ e \in \{0,1,2,\cdots \,b-1\}$ $ 4m+1=2b-e$ then $ e=2f-1$ with $ f \in \{1,2,\cdots \, 2m\}$ $ b=2m+f$, $ a=2m+1-f$ Let $ C=A-1990$ and $ D=B-1990$ then $ Y=\{0,1,2,\cdots ,4m\}$ is splitted in two sets $ C$ and $ D$ such as $ 1990 (2f-1) = S(D)-S(C)$ $ 4m(4m+1)/2= S(D)+S(C)$ $ 2m(4m+1)-1990 (2f-1) =2S(C)$ $ S(C) \ge (2m+1-f)(2m+2-f)/2$ $ 2m(4m+1) \ge (2m+1-f)(2m+2-f) +1990 (2f-1)$ $ 8m^2+2m +f (4m+3) \ge (2m+1)(2m+2)+f^2+1990 (2f-1)$ $ 8m^2+2m +f (4m+3) \ge 4m^2+6m+2+f^2+1990 (2f-1)$ $ 4m^2+f (4m+3) \ge 4m+2+f^2+1990 (2f-1)$ $ 4m^2-4m-2+ f (4m+3) \ge f^2+1990 (2f-1)$ Notice that $ f(4m+3-f) \ge 0$ and if $ 0 \le m \le 22$ then $ 4m^2-4m-2 \le 4 \times 22^2-4 \times 22 -2=1846 \le 1990$ contradiction then $ m \ge 23$ Let us analyze the case for $ k=23 \times 4=92$ for bigger $ k$ you can append any four numbers like: $ \{1990+92+1,1990+92+4\}$ and $ \{1990+92+2,1990+92+3\}$ $ S(X)=1990 \times 93+92 \times 93 /2=1990 \times 92+1990+4278=1990 \times 92+6268$ $ A=\{1990,1990+1,1990+2,\cdots,1990+44,1990+62,1990+92 \}$ $ \#A=1+44+1+1=47$ $ S(A)=1990 \times 47+44 \times 45/2+62+92=1990 \times 46+3134$ and $ 2 \times S(A)=S(X)$