Problem 29 · 2009 Math Kangaroo
Stretch
Number Theory
divisibility
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?
Show answer
Answer: D — 9
Show hints
Hint 1 of 2
Join two numbers when one divides the other; you want the longest chain of distinct numbers 1-10.
Still stuck? Show hint 2 →
Hint 2 of 2
Small numbers like 1 and 2 connect to many others - use them as bridges.
Show solution
Approach: find the longest divisibility chain in 1-10
- Make a chain where each neighbouring pair has one dividing the other, e.g. 4, 8, 1, 5, 10, 2, 6, 3, 9.
- That uses 9 distinct numbers below 11; all 10 is impossible because 7 cannot neighbour any of them.
- The maximum is 9 numbers.
Mark:
· log in to save