Library / /93 of 120

, 2012

Combinatorics Difficulty 6.0 AIME, harder Prove it Saudi Arabia

A subset of $\{1, 2, 3, \dots, 30\}$ is called delicious if it does not contain elements $a$ and $b$ satisfying $a = 3b$ . A delicious subset is called super delicious if it is delicious and no delicious set has more elements than it has. Determine the number of super delicious subsets.

Solution

Partition the set $\{1, 2, 3, \dots, 30\}$ into 20 subsets as follows:
$\begin{aligned} & \{1, 3, 9, 27\}, \\ & \{2, 6, 18\}, \\ & \{4, 12\}, \{5, 15\}, \{7, 21\}, \{8, 24\}, \{10, 30\}, \\ & \{11\}, \{13\}, \{14\}, \{16\}, \{17\}, \{19\}, \{20\}, \\ & \{22\}, \{23\}, \{25\}, \{26\}, \{28\}, \{29\}. \end{aligned}$
A subset of $\{1, 2, 3, \dots, 30\}$ is delicious if and only if it does not contain two consecutive elements from any one of the 20 sets listed above. Thus, a delicious set contains at most 2 elements from each of the sets in the first two rows, and at most 1 element from each of the sets in the last two rows. It is possible for a delicious set to have exactly 2 elements from each of the sets in the first two rows, and exactly 1 element from each of the sets in the last two rows; therefore, a super delicious set must have this property. So there are
$3 \cdot 1 \cdot 2^5 \cdot 1^{13} = 96$
super delicious sets, because there are 3 ways to choose 2 non-consecutive elements from $\{1, 3, 9, 27\}$ , and 1 way to choose 2 non-consecutive elements from $\{2, 6, 18\}$ , and so on.

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.