# Mathcounts 2013 state sprint round #14

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$?

• Hint: write out the prime factorizations of each number. Jun 17, 2013 at 22:06
• Good idea, but I still can't get the answer Jun 18, 2013 at 0:43

If $6$ precedes $4$, then we must have $1,?,?,6,4,12$. If $4$ precedes $6$, we must have $1,2,4,6,12$ with $3$ inserted anywhere to the left of $6$ (but of course to the right of $1$).

• But 4 isn't a divisor of 6, so that's where I got confused. But nice hint Jun 18, 2013 at 0:42
• @user82889: Correct, 4 is not a divisor of 6. That means they can go in either order, as he shows. Think carefully about this. In the second case, 2 has to come before 4, but why can 3 go anywhere? Jun 18, 2013 at 2:27

The following terminology is not required for the problem, but let me mention it anyway. Suppose you think of the numbers as nodes in a graph, with edges between node $a$‌ and node $b$ if $a$ is a divisor of $b$. Then you want to order the nodes in a line such that if there is an edge from node $a$ to node $b$, then node $a$ occurs to the left of $b$. In other words, you want to topologically sort the following graph:

(For simplicity I omitted the edges that don't affect the answer as they are implied by transitivity; the actual graph looks like

when all edges are drawn.)

In different terminology, you want to compute the number of linear extensions of the partial order given by the above relation.

Anyway, whatever terminology we use, we can throw it all away because the solution is the same as that of the other answers: consider any longest path in the graph, say $1 \rightarrow 3 \rightarrow 6 \rightarrow 12$. These must appear in that order. Further $2$ must appear before $6$ and after $1$, so it can appear either between $1$ and $3$, or between $3$ and $6$. Enumerating the possibilities:

• If $2$ appears between $1$ and $3$, so that we have the order $1, 2, 3, 6, 12$, then the valid choices for the remaining number $4$ are in the three "gaps" 2–3, 3–6 and 6–12:
• $1, 2, 4, 3, 6, 12$
• $1, 2, 3, 4, 6, 12$
• $1, 2, 3, 6, 4, 12$
• If $2$ appears between $3$ and $6$, so that we have the order $1, 3, 2, 6, 12$, then the choices for $4$ are in the gaps 2–6 or 6–12:
• $1, 3, 2, 4, 6, 12$
• $1, 3, 2, 6, 4, 12$

These are all the five (5) possibilities.

Hint: the first and last are fixed and should be easy to find. Now find the restrictions on the other four. Which numbers can go in the second slot? The fifth?

• Good hint, but I still can't get the answer :( Jun 18, 2013 at 0:42

Well one pretty much can tell that 1 and 12 are fixed and you can therefore start from there. One definite possible option is 1,2,3,4,6,12. You can also reverse the 2 and 3 because they are prime, making a second option of 1,3,2,4,6,12. The 6 and 4 can be switched because the only other multiple of 4 is 12, making a third possible combination of 1,2,3,6,4,12. This can also be used in making 1,2,4,3,6,12 for 3 is prime.I used the same rule for 6 and switched its place with the 4 making 1,3,2,6,4,12. This makes a total of 5 choices and I believe these are the correct options.