Solution:
Denote by $A_{1}, A_{2}, \ldots, A_{5}$ and $B_{1}, B_{2}, \ldots, B_{5}$ the countries on the respective sides of the sheet of paper. Let $S_{ij}$ be the area of the part of $A_{i}$ which belongs to the country $B_{j}$ on the other side of the sheet. (If $A_{i}$ and $B_{j}$ do not have a common area, then $S_{ij}=0$.) Then, setting the area of the sheet to be $1$, we have
$$\begin{aligned} S= & \left(S_{11}+S_{12}+S_{13}+S_{14}+S_{15}\right)+\left(S_{21}+S_{22}+S_{23}+S_{24}+S_{25}\right)+\cdots \\ & +\left(S_{51}+S_{52}+S_{53}+S_{54}+S_{55}\right)=1 \end{aligned}$$
since $S_{i1}+S_{i2}+S_{i3}+S_{i4}+S_{i5}$ equals the area of $A_{i}$.

The sum $S$ can be written also as follows:
$$\begin{aligned} S= & \left(S_{11}+S_{22}+S_{33}+S_{44}+S_{55}\right)+\left(S_{12}+S_{23}+S_{34}+S_{45}+S_{51}\right)+\cdots \\ & +\left(S_{15}+S_{21}+S_{32}+S_{43}+S_{54}\right) \end{aligned}$$
Hence at least one of the summands is greater than or equal to $0.2$ and let us assume that $S_{13}+S_{24}+S_{35}+S_{41}+S_{52} \geq 0.2$. We now color the countries $B_{1}, B_{2}, \ldots, B_{5}$ as follows: $B_{3}$ by the color of $A_{1}$, $B_{4}$ by the color of $A_{2}$, $B_{5}$ by the color of $A_{3}$, $B_{1}$ by the color of $A_{4}$ and $B_{2}$ by the color of $A_{5}$. Then every two countries are colored in different colors and at least $20\%$ of the sheet is colored in the same color on both sides.