6. Find the largest natural number in which all digits are different and any two adjacent digits differ by 6 or 7.
Answer: 60718293.

## Solution.

We will map each digit from 0 to 9 to a vertex in a graph and connect the vertices with an edge if the corresponding digits differ by 6 or 7.

![](https://cdn.mathpix.com/cropped/2024_05_06_6a3c59b5c78061150e51g-5.jpg?height=463&width=594&top_left_y=110&top_left_x=820)

We see that the vertices corresponding to the digits 4 and 5 are not connected to anything, so the maximum number that can be obtained will be 8 digits long. The vertices corresponding to the digits 3 and 6 can only be the first or last in the number. Since we need to find the maximum number, it is uniquely determined by moving along the edges of the graph and will be equal to 60718293.