Problem 10.3. Forty thieves are to distribute 4000 euro amongst them. A group of five thieves is called poor if they have no more than 500 euro all together. What is the minimum number of poor groups amongst all possible groups of five thieves?

Ivailo Kortezov
10.3. If 39 thieves take 101 euro each and the last one takes 61 euro, then the only poor groups are those having as a member the last thieve. So this distribution of the money gives $\binom{39}{4}$ poor groups. We shall prove that this is the required minimum.

Let $r$ be the number of all possible divisions of the thieves in 8 groups of five thieves each. Any such division has at least one poor group. The total number of the groups in all divisions is $8 r$. Each group takes part in $8 r /\binom{40}{5}$ divisions. Therefore each poor group is counted exactly $8 r /\binom{40}{5}$ times and this gives at least $r$. Therefore we have at least $r\binom{40}{5} / 8 r=\binom{39}{4}$ poor groups.