Middle European Mathematical Olympiad 2020

Let $\mathbb{N}$ be the set of positive integers. Determine all positive integers $k$ for which there exist functions $f\colon \mathbb{N}\to \mathbb{N}$ and $g\colon \mathbb{N}\to \mathbb{N}$ such that $g$ assumes infinitely many values and such that

$$f^{g(n)}(n) = f(n) + k$$

holds for every positive integer $n$.

(Remark. Here, $f^i$ denotes the function $f$ applied $i$ times, i.e., $f^i(j) = \underbrace{f(f(\ldots f(f(j)) \ldots))}_{i \text{ times}}$.)

We call a positive integer $N$ contagious if there exist $1000$ consecutive non-negative integers such that the sum of all their digits is $N$. Find all contagious positive integers.

Let $ABC$ be an acute scalene triangle with circumcircle $\omega$ and incenter $I$. Suppose the orthocenter $H$ of $BIC$ lies inside $\omega$. Let $M$ be the midpoint of the longer arc $BC$ of $\omega$. Let $N$ be the midpoint of the shorter arc $AM$ of $\omega$.

Prove that there exists a circle tangent to $\omega$ at $N$ and tangent to the circumcircles of $BHI$ and $CHI$.

Find all positive integers $n$ for which there exist positive integers $x_1, x_2, \ldots, x_n$ such that

$$\dfrac{1}{x_1^2} + \dfrac{2}{x_2^2} + \dfrac{4}{x_3^2} + \cdots + \dfrac{2^{n-1}}{x_n^2} = 1.$$