4. (3 points) From the set of three-digit numbers that do not contain the digits 0, 6, 7, 8, 9 in their notation, several numbers were written on paper in such a way that no two numbers can be obtained from each other by swapping two adjacent digits. What is the maximum number of such numbers that could have been written?
Answer: 75

Solution:

Whether a number can be written or not depends only on numbers consisting of the same set of digits.

Suppose a number ABC, consisting of three different digits, is written. This means that the numbers BAC and ACB cannot be written. Among the numbers consisting of these same digits, BVA, VAB, and VBA remain. The first two can be written together, but the third cannot be written with any of the others. Therefore, among the six numbers consisting of the digits A, B, and V, a maximum of 3 can be written. There are 10 ways to choose the digits A, B, V from $1,2,3,4$ and 5. In total, this gives a maximum of 30 numbers.

Among the numbers AAB, ABA, BAA, a maximum of 2 can be written: AAB and BAA. The digit A can be chosen in five ways, and the digit B in four ways, so this results in 40 numbers.

Finally, all 5 numbers, each consisting of three identical digits, can be written.

In total, this gives 75 numbers.