Adjacent Factors
Two numbers can be placed adjacent if one of them divides the other. Using only $1,...,10$, can you write the longest such list?
Age
11 to 14
Challenge level
Problem
Peter wrote down a list of different positive integers less than or equal to 10.
For each pair of adjacent numbers, one of the numbers was divisible by the other.
What is the longest list that Peter could have written?
If you liked this problem, here is an NRICH task which challenges you to use similar mathematical ideas.
Student Solutions
Answer: 9
Build up a long list
$6$
$2$ $6$ $3$
$4$ $2$ $6$ $3$ $9$
$8$ $4$ $2$ $6$ $3$ $9$ $1$
$8$ $4$ $2$ $6$ $3$ $9$ $1$ $5$ $10$
All numbers except $7$ used
Can we also use $7$?
$7$ should go at the end because it can only go next to $1$
$7$ $1$ $?$
$5$ will only fit if $5$ comes next (using the $1$) or if $5$ comes last, after $10$, which would come after $2$
$5$ next:
$7$ $1$ $5$ $10$ $2$ $?$
If $8$ or $4$ used next, $3$, $6$, $9$ won't fit
If $6$ used next, $8$ and $4$ won't fit
$5$ last:
$7$ $1$ $...$ $?$ $2$ $10$ $5$
Exactly the same problem as before now happens before the $2$
We can't use the $7$. We can only use 9 numbers.
The diagram below shows all of the possible connections that can be used.
Image
There are many other sequences of nine numbers that follow the rule. Can you find them all?