SMC 2015 Q24
24. Peter has 25 cards, each printed with a different integer from 1 to 25. He wishes to place \(N\) cards in a single row so that the numbers on every adjacent pair of cards have a prime factor in common.
What is the largest value of \(N\) for which this is possible?
- A 16
- B 18
- C 20
- D 22
- E 24
Senior Mathematical Challenge 2015, Question 24. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: C 20
There are five cards in Peter's set that are printed with an integer that has no prime factors in common with any other number from 1 to 25. The five numbers are 1 (which has no prime factors) and the primes 13, 17, 19 and 23. These cards cannot be placed anywhere in the row of \(N\) cards. One possible row is: 11, 22, 18, 16, 12, 10, 8, 6, 4, 2, 24, 3, 9, 21, 7, 14, 20, 25, 15, 5. So the longest row is of 20 cards.
Solution © UK Mathematics Trust, from the SMC 2015 solutions. Longer versions with investigations: Solutions and investigations (PDF).