Let n be a positive integer, and let S1,…,Sn be a collection of finite non-empty sets such that 1≤i<j≤n∑∣Si∣∣Sj∣∣Si∩Sj∣<1.
Prove that there exist pairwise distinct elements x1,…,xn such that xi is a member of Si for each index i.
Solution
A choice function or simply a choice for the collection S1,…,Sn is a function c from the first n positive integers to the union S1∪⋯∪Sn such that c(i) is a member of Si for each i. We must show that an injective choice is always possible under the conditions in the statement. To this end, we prove that the number of non-injective choices is strictly less than ∣S1∣⋯∣Sn∣, the total number of possible choices.
Indeed, a non-injective choice function sends some i and some j=i to the same element necessarily lying in Si∩Sj, so the number of non-injective choices does not exceed 1≤i<j≤n∑∣Si∩Sj∣∣S1∣⋯∣S^i∣⋯∣S^j∣⋯∣Sn∣=∣S1∣⋯∣Sn∣1≤i<j≤n∑∣Si∣∣Sj∣∣Si∩Sj∣<∣S1∣⋯∣Sn∣; where the hat over Si and Sj means that these sets are to be omitted. The conclusion follows.
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.