Maths Olympiad Prep

Library / /4 of 16

Combinatorics Difficulty 5.4 AIME, harder Prove it Bulgaria

Problem:

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?

Solution

Solution:

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 thief. So this distribution of the money gives (394)\binom{39}{4} poor groups. We shall prove that this is the required minimum.

Let rr 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 8r8r. Each group takes part in 8r/(405)8r / \binom{40}{5} divisions. Therefore each poor group is counted exactly 8r/(405)8r / \binom{40}{5} times and this gives at least rr. Therefore we have at least r(405)/8r=(394)r \binom{40}{5} / 8r = \binom{39}{4} poor groups.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.