SK 2017 Q14
14. The set \(S\) is given by \(S = \{1,\ 2,\ 3,\ 4,\ 5,\ 6\}\). A non-empty subset \(T\) of \(S\) has the property that it contains no pair of integers that share a common factor other than 1. How many distinct possibilities are there for \(T\)?
Senior Kangaroo 2017, Question 14. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 027
There are six subsets consisting of one element:
\(\{1\}, \{2\}, \{3\}. \{4\}, \{5\}, \{6\}\).
There are eleven subsets consisting of two elements:
\(\{1, 2\}, \{1,3\}, \{1,4\}, \{1, 5\}, \{1, 6\}; \{2, 3\}, \{2, 5\}; \{3, 4\}, \{3, 5\}{:}\ \{4, 5\}; \{5, 6\}\).
There are eight subsets consisting of three elements:
\(\{1, 2, 3\}, \{1, 2, 5\}; \{1, 3, 4\}, \{1, 3, 5\}; \{1, 4, 5\}; \{1, 5, 6\}; \{2, 3, 5\}; \{3, 4, 5\}\).
There are two subsets consisting of four elements:
\(\{1, 2, 3, 5\}; \{1, 3, 4, 5\}\).
Hence the answer is \(6 + 11 + 8 + 2 = 27\).
Solution © UK Mathematics Trust, from the SK 2017 solutions.