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
SOLUTION
C
An integer can occur on a card in the row only if it shares a prime factor with at least one other integer on a card in the row. This rules out 1 , which has no prime factors, and the primes 13,17, 19 and 23 which are not factors of any other integers in the range from 1 to 25 .

With these five integers excluded, this leaves at most 20 cards that can be in the row. It is possible to arrange all these remaining cards in a row so as to meet the condition that integers on adjacent cards share a prime factor. In fact, there are lots of ways to do this. For example
$$
7,14,21,3,18,15,5,25,10,4,20,24,9,6,8,12,16,2,22,11 .
$$

It follows that the largest value of $N$ with the required property is 20 .
FOR INVESTIGATION
24.1 There are lots of different ways to arrange the cards carrying the 20 integers
$$
2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25
$$
in a row so that the integers on adjacent cards have a prime factor in common. Just one of these arrangements is given in the above solution.

One of these integers must occur at the end, either first or last, in any row of all these integers that meet the given condition. Which is it?
24.2 For which of the integers, $n$, of the 20 integers listed in Exercise 24.1, is it possible to arrange all 20 cards in a row so that $n$ is on the first card of the row, and so that every pair of adjacent integers in the row have a prime factor in common?
24.3 As we say above, there are lots of ways to arrange the 20 cards in a row so that every pair of adjacent integers has a prime number in common. Counting all the different possible solutions is rather hard. You can try this if you like, but we suggest that instead you consider the case where there are just 12 cards, each printed with a different integer from 1 to 12 .
(i) What is the largest value of $N$ such that $N$ of the 12 cards can be placed in a single row so that the numbers on every adjacent pair of cards have a prime factor in common?
(ii) For this value of $N$ how many different ways are there to arrange the $N$ cards in a row so as to meet the required condition?