Problem 19 · 2009 Math Kangaroo
Stretch
Number Theory
divisibilitycareful-counting
Friday writes several different positive whole numbers, 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?
Show answer
Answer: D — 9
Show hints
Hint 1 of 2
Among 1–10, each neighbour pair must have one number dividing the other.
Still stuck? Show hint 2 →
Hint 2 of 2
Treat numbers as dots and 'divides' as links, then find the longest chain of distinct numbers.
Show solution
Approach: build the longest chain of distinct numbers where each neighbour pair divides
- Among 1–10, the only number that 7 divides or that divides 7 is 1 (since 14 is too big), so 7 can sit next to 1 only — meaning 7 must be an end of the row, touching 1.
- If all ten numbers were used, 7 would need that single end spot, but then the rest of 1–10 still cannot all be chained, so 10 numbers is impossible.
- Drop 7 and a valid row of 9 exists: 9, 3, 6, 2, 4, 8, 1, 5, 10, where every neighbour pair has one dividing the other.
- So the most he could write is 9.
Mark:
· log in to save