2008 iTest Problems/Problem 93

Problem

For how many positive integers $n$ , $1 \le n \le 2008$ , can the set

${1, 2, 3, . . . , 4n}$

be divided into $n$ disjoint $4$ -element subsets such that every one of the $n$ subsets contains the element which is the arithmetic mean of all the elements in that subset?

Solution

Each $4$ element subset is of the form $\left\{a,b,c, \frac{a+b+c}{3}\right\}$ . The sum of the elements of this subset is $\frac{4(a+b+c)}{3}$ , which is divisible by $4$ . If $n$ is odd however, then the sum of the elements $1+2+3+ \cdots +4n$ is $\frac{4n(4n+1)}{2} = 2(n)(4n+1)$ , but $n$ and $4n+1$ are both odd, and so the sum is not divisible by $4$ . Hence $n$ may not be odd.

For $n=2$ , we note that the construction $\{1,5,6,8\},\{2,3,4,7\}$ works. For even $n$ greater than $2$ , we can divide each consecutive eight element subset using the same construction, eg, $\{8k+1,8k+5,8k+6,8k+8\},\{8k+2,8k+3,8k+4,8k+7\}$ for $0 \le k < \frac n8$ . Hence, the answer is all even $n$ , of which there are $\boxed{1004}$ .

Page

Toolbox

Search

2008 iTest Problems/Problem 93

Problem

Solution

See also