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}$.

See Also

2008 iTest (Problems)
Preceded by:
Problem 92
Followed by:
Problem 94
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100