Competition problem — Combinatorics

Library / /69 of 86

Combinatorics Difficulty 6.8 National olympiad Prove it Estonia

A fly farm contains $100001$ fruit flies. A research group wishes to buy some flies from the farm to perform (once) either experiment A or experiment B (but not both).

For experiment A, the research group needs a set of flies in which no fly is a descendant of any other. For such a set, the research group would pay the farm $505$ euros plus $5$ euros per fly bought.

For experiment B, the research group needs a set of flies in which among every two flies, one is a descendant of the other. For such a set, the research group would pay the farm $1000$ euros plus $10$ euros per fly bought.

Prove that there exists a set of flies in the farm for which the research group would pay at least $3010$ euros.

Solution

For $k = 1, 2, \dots$ , we call a fly a $k$ -th order parent, if the greatest suitable set for experiment B containing this fly as the oldest fly consists of exactly $k$ flies.

If there exists a suitable set for experiment B with at least $201$ flies, then the research group would pay at least $1000 + 10 \cdot 201 = 3010$ euros for it, which we wanted to show.

Now, assuming there is no such set, each suitable set for experiment B contains $200$ or fewer flies. Then each fly will be a parent of order at most $200$ . Since $100001 : 200 > 500$ , the pigeonhole principle implies that there exists a $k$ such that at least $501$ flies are parents of order exactly $k$ .

Out of two flies who are parents of the same order, one can clearly never be a descendant of the other, meaning the set of all parents of order exactly $k$ will be suitable for experiment A. For such a set, the research group would pay at least $505 + 5 \cdot 501 = 3010$ euros, which we wanted to show.

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 and solution reproduced as published; topic and difficulty added by this site.