Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
A fly farm contains 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 euros plus 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 euros plus euros per fly bought.
Prove that there exists a set of flies in the farm for which the research group would pay at least euros.
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 euros plus 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 euros plus euros per fly bought.
Prove that there exists a set of flies in the farm for which the research group would pay at least euros.
Solution
For , we call a fly a -th order parent, if the greatest suitable set for experiment B containing this fly as the oldest fly consists of exactly flies.
If there exists a suitable set for experiment B with at least flies, then the research group would pay at least euros for it, which we wanted to show.
Now, assuming there is no such set, each suitable set for experiment B contains or fewer flies. Then each fly will be a parent of order at most . Since , the pigeonhole principle implies that there exists a such that at least flies are parents of order exactly .
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 will be suitable for experiment A. For such a set, the research group would pay at least euros, which we wanted to show.
If there exists a suitable set for experiment B with at least flies, then the research group would pay at least euros for it, which we wanted to show.
Now, assuming there is no such set, each suitable set for experiment B contains or fewer flies. Then each fly will be a parent of order at most . Since , the pigeonhole principle implies that there exists a such that at least flies are parents of order exactly .
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 will be suitable for experiment A. For such a set, the research group would pay at least euros, which we wanted to show.
Techniques
Pigeonhole principleColoring schemes, extremal arguments