ManualCountingAndCasework Basic
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.

report an error