8
$\begingroup$

Friday writes different positive whole numbers that are all less than 11 next to each other in the sand. Robinson Crusoe looks at the sequence and notices with amusement that adjacent numbers are always divisible by each other. What is the maximum amount of numbers he could possibly have written in the sand?

Source: Question 19 of Kangaroo of Mathematics 2009 Level Junior (Grades 9 and 10)

My understanding is that this obviously doesn't mean that both adjacent numbers divide each other. It means that one of them divides the other. For example: 7 1 2 10 5 is a valid sequence.

Looking for an intuitive solution to the problem.

Bonus

Is there a general way to solve this problem? In other words, what's the largest sequence where all the numbers are less than n?

$\endgroup$
1

3 Answers 3

9
$\begingroup$

We work backwards from our constraints, starting from the most restrictive numbers.

7 can only go next to 1: 7 1

Next 5 and 9 only have 2 options, either 1 or 10 and 3, respectively. So one of these pairs must come after 1, the other must be at the other end of the string of numbers: 7 1 5 10 - 3 9 or 7 1 9 3 - 10 5

We have only one option each for what can be adjacent to 10 (2) and 3 (6): 7 1 5 10 2 - 6 3 9 or 7 1 9 3 6 - 2 10 5

Our remaining two numbers are 4 and 8, however neither of these are divisible by 6. So the largest sequence cannot be 10. It follows from @Weather Vane that 9 is the maximum length.

$\endgroup$
8
$\begingroup$

The "divisor" graph $G$ has node set $\{1,2,\dots,10\}$ and an edge $(i,j)$ if $i$ divides $j$ or $j$ divides $i$. Paths of length $9$ are easy to find. To show that $10$ is impossible, we want to show that $G$ has no Hamiltonian path. Equivalently, we want to show that the graph $H$ obtained from $G$ by adding a dummy node $0$ that is adjacent to all other $10$ nodes has no Hamiltonian cycle. Removing the $4$-node subset $\{0,1,2,3\}$ from $H$ leaves $5$ connected components: $\{4,8\},\{5,10\},\{6\},\{7\},\{9\}$. Because $4<5$, this subset yields a certificate that $H$ does not contain a Hamiltonian cycle and hence $G$ does not contain a Hamiltonian path.

For an even shorter certificate of non-Hamiltonicity of $H$, remove $3$ nodes $\{0,1,2\}$, leaving $4$ connected components: $\{3,6,9\},\{4,8\},\{5,10\},\{7\}$.

$\endgroup$
1
  • 1
    $\begingroup$ Forget hamiltonian paths. If you remove nodes 1 and 2 from {1..10} you get the same 4 disconnected subsets and you can connect at most 3 of them in a path by adding back nodes 1 and 2. $\endgroup$
    – Florian F
    Commented Jun 16 at 12:51
3
$\begingroup$

I can get nine of the ten numbers:

8 4 2 6 3 9 1 5 10
Missing number 7

Explanation:
I'm not aware of the exact mental process of how I found a solution, but this is the entire jotting of how it emerged:

enter image description here

My proof of the maximum:

Number 7 is the only one with no common multiples or factors with any other number. So 7 can only be joined to the sequence with 1, and 7 must be at an end.

The three primes 2, 3, and 5 form three groups of their multiples.
The 2 and 3 group, or the 2 and 5 group can be joined with 2.
But there is only one 2, and so the 1 is needed to join the other group.
So the 7 cannot be connected to the sequence.

$\endgroup$
2
  • 1
    $\begingroup$ Pls also show your method. More importantly, what's the proof that this is the largest? $\endgroup$ Commented Jun 15 at 23:16
  • 1
    $\begingroup$ There was no method apart from jotting on paper. It took about 10 seconds. $\endgroup$ Commented Jun 15 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.