Task 4. A pair of natural numbers is called good if one of the numbers is divisible by the other. Numbers from 1 to 30 were divided into 15 pairs. What is the maximum number of good pairs that could result?
Solution. Answer: 13.

First, let's prove that more than 13 good pairs could not have been formed. We will call a number bad if it is prime and not less than 15. There are only four bad numbers: \(17, 19, 23, 29\). None of the other numbers from 1 to 30 can be divisible by any bad number, and the bad numbers themselves can only be divisible by one (among the others). Consequently, at most one of the bad numbers can form a good pair with one, and the remaining at least three bad numbers will "ruin" at least 2 pairs.

Now let's consider the following 13 good pairs: \((1,27), (2,4), (3,6), (5,25), (7,21)\), \((8,16), (9,18), (10,20), (11,22), (12,24), (13,26), (14,28), (15,30)\). The remaining 4 numbers can be paired, for example, as follows: \((17,19), (23,29)\). In total, we have exactly 13 good pairs.

## Criteria

One of the largest suitable criteria is used:

7 points. Any complete solution to the problem.

4 points. An example consisting of 13 good pairs is constructed.

3 points. It is proven that there are no more than 13 good pairs.

1 point. The idea of considering "large" prime numbers (17, 19, 23, 29) is present, but there is no further progress.