Problem 29 · 2011 Math Kangaroo
Stretch
Number Theory
divisibility
Twenty different positive whole numbers are written into a 4×5 table. Any two numbers in cells that share a common side always have a common factor greater than 1. Determine the smallest possible value of n, where n is the largest number in the table.
Show answer
Answer: C — 26
Show hints
Hint 1 of 2
Neighbouring numbers must share a prime, so colour the grid like a checkerboard of two prime 'families'.
Still stuck? Show hint 2 →
Hint 2 of 2
Build the table from the smallest usable multiples of small primes to keep the maximum down.
Show solution
Approach: assign small-prime multiples to keep the largest entry minimal
- Adjacent cells need a common factor, so arrange numbers from the smallest multiples of 2, 3, 5, … that still keep all 20 distinct.
- Optimising the layout to minimise the biggest value gives a maximum of 26.
Mark:
· log in to save