All-Soviet-Union Mathematical Olympiad

Solution:
Obviously $11 = 36^{1} - 5^{2}$, and we guess that this is the best possible. We cannot have $36^{m} - 5^{n} = k$, where $2$, $3$ or $5$ divides $k$ (because then $2$ would divide $5^{n}$ and similarly in the other cases). So the only possible values of $k < 11$ are $1$, $7$.
We have $36^{m} - 5^{n} = 1 \pmod{5}$, so $k \neq 7$. Similarly, $36^{m} - 5^{n} = 3 \pmod{4}$, so $k \neq 1$.