Track / Stage 5 / 384 of 400 #1464 of 2444

Problem 1464

AIME late

Combinatorics Difficulty 6.0 Prove it Saudi Arabian Mathematical Competitions · Saudi Arabia · 2012

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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.