1. (10 points) In the arithmetic class, children were studying some natural numbers and operations with them. The teacher gave the children many cards with the numbers 1, 2, 4, and 8 and asked them to arrange the cards in a circle using each of the numbers so that the sum of the numbers on any two adjacent cards is divisible by 3 but not by 9. How many cards could the children use to complete this task?
a) 8 ;
b) 9 ;
c) 10 ;
d) 11 .
Answer: a) and b).

First solution: It is sufficient to prove that the solutions to the problem are numbers of the form $6+2k$, where $k$ is a non-negative integer.

First, let's show that the minimum answer is 6. Next to the number 1, only the number 2 can be placed, and next to the number 8, only the number 4. Since the cards with the numbers 1 and 8 are used according to the condition, the final set must include the triplets 2-1-2 and 4-8-4. Therefore, fewer than 6 cards cannot be used. Since the cards with the numbers 2 and 4 can be adjacent, a set of these two triplets satisfies the condition.

Now, note that between the cards with the numbers 2 and 4, a pair 2-4 or 4-2 can be placed. Performing this operation $k$ times, we get that numbers of the form $6+2k$ satisfy the condition.

It remains to check that the number of cards is necessarily even. Let $A=\{2,8\}$ and $B=\{1,4\}$. Clearly, elements of set $A$ cannot be adjacent to each other; similarly, elements of set $B$ cannot be adjacent to each other. Thus, the number of cards from set $A$ used in the correct arrangement of cards is equal to the number of cards from set $B$. Therefore, the total number of cards is always even.

Second solution: We will consider that the vertices of the graph correspond to the numbers on the

![](https://cdn.mathpix.com/cropped/2024_05_06_9263b3ce8663e03b8a8fg-1.jpg?height=94&width=682&top_left_y=2243&top_left_x=687)

cards. We will connect vertices $p$ and $q$ with a directed edge if the card with the number $q$ can be placed after the card with the number $p$. We are interested in the length of a closed path that passes through all vertices. It is easy to notice that for the given graph, this value is $6+2k$ ($k$ - a non-negative integer).