2013
Problem - 1818
How many ways can all six numbers in the set $\{4, 3, 2, 12, 1, 6\}$ be ordered so that $a$ comes before $b$ whenever $a$ is a divisor of $b$?
Answer
$5$
This problem can be done manually. We know:
- $1$ divides all numbers. Therefore it must be the first
- $12$ is the multiple of all the rest, therefore it must be the last
- $2$ must be before $4$ and $6$
- $3$ must before $6$
- $4$ must be after $2$
- $6$ must after $3$
Having considered all the above constrains, we find only the following arrangments are legal:
- $\{1, 2, 3, 4, 6, 12\}$ (the base case)
- $\{1, 2, 3, 6, 4, 12\}$ (try to move $6$ forward)
- $\{1, 3, 2, 6, 4, 12\}$ (another legal. $6$ no longer can move further forward)
- $\{1, 2, 4, 3, 6, 12\}$ (starting from the base, now try to move $4$ forward)
- $\{1, 3, 2, 4, 6, 12\}$ (starting from the base, now try to move $3$ forward)
Therefore, the answer is $\boxed{5}$.
A note: though most counting problems in competitions involve some techniques, some in entry level may be solved by manually listing all the possibilities. In such cases, carefully enumerate in a systematic way is essential in order to ensure "no miss, no duplicate" counting.