There are 9 cards with numbers and 9. What is the maximum number of these cards that can be laid out in some order in a row so that on any two adjacent cards, one of the numbers is divisible by the other?
Problem 718
Official solution
2. Answer: 8.
Note that it is impossible to arrange all 9 cards in a row as required. This follows from the fact that each of the cards with numbers 5 and 7 can only have one neighbor, the card with the number 1. Therefore, both cards 5 and 7 must be at the ends, and the card with the number 1 must be adjacent to each of them, which is impossible. It is possible to select 8 cards and arrange them in a row according to the requirements of the problem, for example: .