42nd Balkan Mathematical Olympiad

First we will solve the case $k=1$. Notice that a pair $(a,b)$ is 1-nice if $a\mid b+1$ and $b\mid a+1$. Assuming without loss of generality that $a\le b$ and setting $d=b-a$, we observe that since $b\mid a+1$ then $b\le a+1$, i.e. $d\le 1$. Since $a$ divides $(b-a)+1=d+1$, we conclude that $a\le 2$, and then that $b\le 3$, which means that only finitely many pairs are 1-nice.

Now, consider some integer $k\ge 2$. First, notice that the pair $(1,1)$ is $k$-nice. Now, given a $k$-nice pair $(a,b)$ such that $1\le a\le b$, let $c=(b^k+1)/a$. By construction, $c$ is a positive integer that divides $b^k+1$. Notice that we must have $\text{GCD}(a,b)=1$, because otherwise if some $p>1$ divides both $a$ and $b$, we have that $p$ divides $b^k+1$ as well, hence $p\mid 1$, contradiction.

Now we observe that $$c^k+1=\frac{(b^k+1{)}^k+a^k}{a^k},$$ and since $(b^k+1{)}^k+a^k\equiv 1+a^k\equiv 0(\mathrm{mod}b)$ and $\text{GCD}(a,b)=1$, we get that $b\mid c^k+1$, which means that $(b,c)$ is $k$-nice. Moreover, $c\ge \frac{b^2+1}{b}>b$ and so $b+c>a+b$.

Therefore, there is no $k$-nice pair $(a,b)$ whose sum $a+b$ is maximal, and since $(1,1)$ is $k$-nice, there must exist infinitely many $k$-nice pairs.

In conclusion, for all $k\ge 2$ there exist infinitely many $k$-nice pairs.