6. We call a finite set of natural numbers nice if in the decimal representation of these numbers, we need an even number of each represented digit to write them down $v$ times. Examples of nice sets include $\{11,13,31\},\{10,100,110\}$, and also the empty set. Determine how many nice subsets the set $\{1,2, \ldots, 2018\}$ has. (Patrik Bak)
SOLUTION. The set $M=\{1,2, \ldots, 2018\}$ from the problem statement will be divided into two parts

$$
A=\{1,2, \ldots, 9,10\}, \quad B=\{11,12, \ldots, 2018\}
$$

and we will show that the number of all beautiful subsets of the set $M$ is equal to the number of all subsets of the set $B$ (including the empty set). Since the set $B$ has $2018-10=2008$ elements, this number will be equal to $2^{2008}$, because generally any $n$-element set has exactly $2^n$ subsets (it suffices to apply the product rule to the fact that for each of the $n$ elements we have two options: either include it in the constructed subset or not).

We will verify the initial statement by showing that any beautiful subset $P$ of the given set $M$ is uniquely determined by its part lying in $B$, i.e., by the set $Q=P \cap B$, and that conversely, for any set $Q \subseteq B$ there exists a beautiful set $P \subseteq M$ such that $Q=P \cap B$. This will mean that there is a bijection (one-to-one correspondence) between the set of all beautiful subsets of $M$ and the set of all subsets of $B$, so both sets have the same number of elements.

Thus, let us describe how any fixed beautiful subset $P \subseteq M$ can be uniquely reconstructed from its part $Q=P \cap B$, i.e., determine its other part $P \cap A$. In other words, according to the known set $Q$, we need to decide which of the smallest numbers forming the set $A$ belong to the beautiful set $P$ and which do not. We will simply do this for each of the digits $c \in\{2,3, \ldots, 9\}$: since the number of occurrences of the digit $c$ in the notation of all numbers in $P$ is even, the number $c$ belongs to $P$ if and only if the number of digits $c$ in the notation of all numbers in the part $Q$ is odd (since the two mentioned counts can differ by at most 1). The same reasoning about the number of zeros can decide whether the number 10 belongs to $P$. Having this information about the number 10, we can (according to the number of ones) make the final decision, i.e., whether the number 1 is in $P$. This completes the reconstruction of the entire set $P$.

The procedure from the previous paragraph can apparently be successfully applied to any subset $Q$ of the set $B$ (even without knowing in advance that the corresponding beautiful set $P$ exists, so instead of reconstruction, it will be about its construction). We will thus construct a beautiful set $P \subseteq M$ that arises from the set $Q$ by adding some (precisely determined above) numbers from $A$ and for which the equality $Q=P \cap B$ will hold, as we wished. This completes the solution of the entire problem.

Answer. The number of beautiful subsets is $2^{2008}$.

SUPPLEMENTARY AND ADDITIONAL PROBLEMS:

In all problems, we are dealing with beautiful sets in the sense of the competition problem.

N1. An unknown beautiful set $P$ contains exactly the following multi-digit numbers: $13,21,34,55,89$. Find all single-digit numbers that belong to $P$. [Exactly the numbers $2,4,8$ and 9, each of the other digits is represented in the given five two-digit numbers in an even number of instances.]

N2. How many beautiful subsets does the set

$$
\{1,2,3,11,22,33,111,222,333\}
$$

have? $\left[4^{3}=64\right.$. Each of the three given triplets of numbers $\bar{c}, \overline{c c}, \overline{c c}$ has $\mathrm{v}$ in a beautiful set four possible representations: $\emptyset,\{\overline{c c}\},\{\bar{c}, \overline{c c}\}$ or $\{\bar{c}, \overline{c c}, \overline{c c c}\}$. Another solution: each of the given beautiful sets is determined by its multi-digit numbers, which can together form any of the $2^{6}$ subsets of the set $\{11,22,33,111,222,333\}$.]

N3. By which finite sets $Q$ of multi-digit numbers can we replace the set $\{13,21$, $34,55,89\}$ in the statement of $\mathrm{N} 1$ so that the problem has a solution? [In the notations of all numbers in $Q$, the digit 0 must be represented in an even number of instances, and this is the only condition on $Q$, because according to the parity of the number of occurrences of the other digits 1 to 9, we will then determine which of the numbers 1 to 9 will belong to the desired beautiful set and which will not.]

N4. How many beautiful subsets does the set

$$
\{1,3,5,7,9,11,13,15,17,19\}
$$

have? [32. The two-digit numbers from each of the given beautiful sets can form any of the $2^{5}$ subsets of the five-element set $\{11,13,15,17,19\}$.]

N5. How many beautiful subsets does the set

$$
\{1,2,3,10,11,12,13,20,21,22,23,30\}
$$

have? [256. The numbers greater than $10 \mathrm{z}$ from each of the given beautiful sets can form any of the $2^{8}$ subsets of the eight-element set

$$
\{11,12,13,20,21,22,23,30\} \text {. }
$$

(The number 10 will belong to a beautiful subset if and only if exactly one of the numbers 20 and 30 belongs to it.)]

[^0]:    1 Three dots mean lower powers of the base 10, generally different in both cases. The composition of these is not significant for further considerations.