Can all non-negative integers be divided into 1968 non-empty classes such that each class contains at least one number and the following condition is met: if a number $m$ is obtained from a number $n$ by erasing two adjacent digits or identical groups of digits, then both $m$ and $n$ belong to the same class (for example, the numbers 7, 9339337, 93223393447, 932239447 belong to the same class)?
The first method. Let the symbol $\approx$ denote belonging to the same class. $\overline{M a b N} \approx \overline{M b b a b N} \approx \overline{M b a a b a b N} \approx \overline{M b a N}$. Thus, numbers obtained by swapping adjacent digits belong to the same class. Since any permutation can be represented as a sequence of swaps of adjacent digits, any two numbers whose digits differ only by a permutation belong to the same class. Therefore, if a digit appears in the number at least twice, any two of its occurrences can be erased, meaning that the information about which digits appear an odd number of times in the number completely determines the class to which the number belongs. Thus, the number of classes does not exceed $2^{10}=1024$.

The second method. Consider the semigroup of digit sequences with the operation of concatenation (appending) and the neutral element $\Lambda$ (the empty word). After factorization by the equivalence relation described in the condition, we obtain a semigroup with generators $0,1, \ldots, 9$ and relations of the form $X^{2}=\Lambda$ for each $X$. Due to these relations, the resulting semigroup will be a group. Since all groups of index 2 are commutative, the resulting group is commutative. Thus, we obtain a commutative group of index two with ten generators. The number of elements in it is 1024, meaning that the number of equivalence classes of the described equivalence relation does not exceed 1024.

## Answer

No.

Send a comment