Distribution of first $9$ natural numbers

combinationscombinatorics

The question states

The first $9$ natural numbers are to be divided in three groups $g_1$, $g_2$ and $g_3$ of equal size. In how many different ways can this be done if the sum of numbers in each group is odd?"

What I thought was to split it into cases. The three numbers chosen for one group should be of the following types:(for the sum to to be odd)

  1. $2$ even $1$ odd $\to$ $\binom{4}{2}$ $\binom{5}{1}$
  2. All $3$ odd $\to$ $\binom{5}{3}$

Summing this gives $40$ and I proceeded to choose for the next group by considering that case $1$ had occurred (for selection of first group) and with that new sample space tried forming the same cases. Similarly assuming that case $2$ has occurred I tried making cases for selection of group $2$. But this just lead to a lot of chaos. The given answer is $360$. How do I approach this question?

Best Answer

The first nine natural numbers contain exactly five odd numbers. Each group must contain an odd number of natural numbers if the sum of the numbers in each group is to be odd. The only way to do this is to have one group with three odd numbers and two groups with exactly one odd number.

Choose which three odd numbers are placed in the group with three odd numbers, which can be done in $\binom{5}{3}$ ways. Choose which two of the four even numbers will be placed in the group with the smaller of the two remaining odd numbers, which can be done in $\binom{4}{2}$ ways. The other two even numbers must be placed in the group with the remaining odd number. Hence, there are $$\binom{5}{3}\binom{4}{2}$$ unlabeled groups of three natural numbers, each having an odd sum, which can be formed from the first nine natural numbers. Since the groups are labeled, there are $$\binom{5}{3}\binom{4}{2}3!$$ labeled groups of three natural numbers, each of which has an odd sum, which can be formed from the first nine natural numbers.

Related Question