# Problem involving combinations.

In how many ways can $42$ candies (all the same) be distributed among 6 different infants such that each infant gets an odd number of candies?

I seem to think that we have 42 different objects, and 6 choices. So it should be 42C6. However, I'm not factoring in the "odd number of candies" part of the question, so I'm sure it's wrong. Any help is appreciated.

• Candies should not be distributed to infants. Too much sugar isn't good for them, and the candies are a choking hazard. – MJD Mar 12 '13 at 3:43
• I'll be sure to let my math prof know that :) – chromozonex Mar 12 '13 at 3:44
• Note that 42C6 is quite far from the truth, even without the "odd number" constraint. You are not choosing a set of 6 specific candies from 42; furthermore all candies are the same, so there is really only one way to give 6 candies to a child. – Erick Wong Mar 12 '13 at 3:51

## 3 Answers

You are looking for compositions of $42$ into six odd parts. If you give each child one candy and put the rest in pairs, this will be the same as the weak compositions of 18 into six parts, which is given by ${23 \choose 5}=33649$. To prove the formula, put $24$ (pairs) in a row, then you select five places to split the row and remove one pair from each part. This allows for not giving any more candies to one or more infants.

• How did you know that you had to split them in pairs initially after giving out 1 candy? Is it just practice? – chromozonex Mar 12 '13 at 3:52
• @ChromoZoneX: I thought about how to make sure I didn't spoil the odd number for each infant. Handing out pairs solved that. – Ross Millikan Mar 12 '13 at 3:56
• Alright, why did you pick ${17 \choose 5}$. I would've picked ${18 \choose 6}$...? – chromozonex Mar 12 '13 at 3:59
• @ChromoZoneX: When you are doing a strong composition of 18 into six parts, you think of laying out all 18 items in order, then splitting the line into six pieces. This requires five splits out of 17 places you can split the line. However, I had overlooked that we want a weak composition-which means that pieces of zero are allowed. The easiest way to do that is to do a strong composition of 24 into 6 parts, then remove one item from each piece. Now we are picking five split points out of 23. – Ross Millikan Mar 12 '13 at 4:06

Each infant must get at least one candle, so you have 36 candles to give out in pairs to 6 infants. Hence you have 18 pairs to give out to 6 infants. Can you take it from there?

We will give out $2x_i+1$ candies to the $i$-th infant. Thus we want $2(x_1+\cdots+x_6)+6=42$, or equivalently $x_1+\cdots+x_6=18$.

Counting the number of solutions $(x_1,\dots,x_6)$ in non-negative integers of the equation $x_1+\cdots+x_6=18$ is a standard Stars and Bars problem.

Or else let's do the distribution cruelly. We will distribute $48$ candies to the infants, a positive even number of candies to each infant, and then take away a candy from each infant.

Tie the candies in bundles of $2$ each, and line up the bundles like this: $$\infty \quad\infty\quad\infty\quad \infty \quad\infty\quad\infty\quad\dots \quad\infty \quad\infty\quad\infty\quad\infty.$$ In the usual way, we want to choose $5$ intercandy gaps from the $23$ to put a separator into.