Maths Olympiad Prep

Library / /19 of 70

Combinatorics Difficulty 8.0 Shortlist Prove it Romania

Given an integer k2k \ge 2, exhibit an infinite set A\mathcal{A} of sets of positive integers satisfying the two conditions below:
(a) The intersection of the members of every kk-element subset of A\mathcal{A} is a singleton set; and
(b) The intersection of the members of every (k+1)(k+1)-element subset of A\mathcal{A} is empty.

Solution

Biject the set of kk-element sets of positive integers with the set of positive integers to label the former S1,S2,,Sn,S_1, S_2, \dots, S_n, \dots. For every positive integer mm, set Am={n:mSn}A_m = \{n : m \in S_n\}.

If mm and mm' are distinct positive integers, there exist distinct positive integers nn and nn' such that mSnm \in S_n and mSnm' \in S_{n'}. Consequently, nAmAmn \in A_m \setminus A_{m'} and nAmAmn' \in A_{m'} \setminus A_m; in particular, AmAmA_m \neq A_{m'}, so the A\mathcal{A}'s form an infinite set A\mathcal{A}.

Next, if m1,m2,,mkm_1, m_2, \dots, m_k are distinct positive integers, then Am1Am2Amk={n}A_{m_1} \cap A_{m_2} \cap \dots \cap A_{m_k} = \{n\}, where nn is the index of the label of the set {m1,m2,,mk}\{m_1, m_2, \dots, m_k\} in the list S1,S2,S_1, S_2, \dots. Consequently, A\mathcal{A} satisfies (a).

Finally, if m1,m2,,mk,mk+1m_1, m_2, \dots, m_k, m_{k+1} are distinct positive integers, then {m1,m2,,mk}\{m_1, m_2, \dots, m_k\} and {m2,,mk,mk+1}\{m_2, \dots, m_k, m_{k+1}\} have different labels in the list S1,S2,S_1, S_2, \dots, so Am1Am2AmkAmk+1A_{m_1} \cap A_{m_2} \cap \dots \cap A_{m_k} \cap A_{m_{k+1}} is empty. Consequently, A\mathcal{A} satisfies (b).

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.