I like Russian problems! Answer: 4 Using four colors, we can done by the following way; 1122112211221122 1122112211221122 3344334433443344 3344334433443344 1122112211221122 1122112211221122 3344334433443344 3344334433443344 We show that it's impossible using 3 colors. Let the colors be A,B,C. WLOG we assume inner cell $L$ colored by A as in the diagram. Then, $L,P,Q$ and $L,P',Q'$ are of the different color since any two are position of knight or beaver. WLOG, $P=B$ and $Q=C$. There are two possibility that $P'=B, Q'=C$ or $P'=C, Q'=B$. In the former case, $R$ must be $C$ and $S$ must be $B$. Then, since $X$ and $Y$ are both knight-position with $R, S$, $X=Y=A$, acontradiction. In the later case, there are no color for $R$ since $P,A,P'$ are all beaver or knight-position. \begin{tabular}{|c|c|c|c|c|} \hline & P & & Q & \tabularnewline \hline & & X & & \tabularnewline \hline R & & L & & S\tabularnewline \hline & & Y & & \tabularnewline \hline & P' & & Q' & \tabularnewline \hline \end{tabular}