(a) Determine if the set $ \{1,2,\ldots,96\}$ can be partitioned into 32 sets of equal size and equal sum. (b) Determine if the set $ \{1,2,\ldots,99\}$ can be partitioned into 33 sets of equal size and equal sum.
Problem
Source: China Girls Math Olympiad 2008, Problem 1
Tags: combinatorics unsolved, combinatorics
jgnr
29.08.2008 13:41
(a) No. Because $ 1+2+\ldots+96=\frac12\cdot96\cdot97$ is not divisible by 32.
(b) Yes: $ \{(1,99,50),(4,48,98),(7,96,47),\ldots,(97,51,2)\}$.
superacidduck
08.03.2009 06:47
China Girl's Mathematics Olympiad 2008 Problem 1
HamstPan38825
19.06.2022 00:28
A basic but informative exercise in combinatorial constructions When $n=2k+1$, the sum of the numbers is $(3k+2)(6k+3)$, and thus the sum per subset must be $9k+6$. Consider the following series of constructions: \begin{tabular}{c|c|c} 1 & $3k+2$ & $6k+3$ \\ 2 & $3k+3$ & $6k+1$ \\ $\vdots$ & $\vdots$ & $\vdots$ \\ $k+1$ & $4k+2$ & $4k+3$. \end{tabular}The remaining numbers are $k+2$ through $3k+2$ and the even numbers between $4k+4$ and $6k+2$, which we can divide as the following: \begin{tabular}{c|c|c} $k+2$ & $2k+2$ & $6k+2$ \\ $k+3$ & $2k+3$ & $6k$ \\ $\vdots$ & $\vdots$ & $\vdots$ \\ $2k+1$ & $3k+1$ & $4k+4$. \end{tabular}All the numbers are included in one of these two tables, so the construction works. When $n=2k$, the sum of all the elements is $\frac 12(3n)(3n+1)$ which is odd. But $n$ is even, so it is impossible to divide this quantity into $n$ integer sums. As a result, $n=32$ fails while $n=33$ works.