8.1. Let $n=34000$. Among the vertices of a regular $n$-gon $A_{1} A_{2} \ldots A_{n}$, the vertices $A_{i}$ are painted red for which the number $i$ is a power of two, i.e., $i=1,2,4,8,16, \ldots$ In how many ways can 400 vertices of this $n$-gon be chosen so that they are the vertices of a regular 400-gon and none of them are red?
# Answer: 77

Solution. There are $\frac{34000}{400}=85$ ways to choose the correct 400-gon. Consider one of these options, where the vertex numbers of the 400-gon are of the form $a+85 k$ for a fixed $a \in\{1,2, \ldots, 85\}$. Let's see in which options the red vertices will be present.

Consider the powers of two not exceeding 34000: $1,2,4,8,16,32,64,128,256,512, \ldots$. They give remainders when divided by 85: $1,2,4,8,16,32,64,43,1,2, \ldots$ (starting from 1, the remainders repeat, as each subsequent remainder is obtained by multiplying the previous one by 2 and taking the remainder when divided by 85). Thus, red vertices are present in the considered 400-gon if and only if $a=1,2,4,8,16,32,64,43$, i.e., in 8 options. Therefore, the answer is $85-8=77$.