Baltic Way 2011 · Shortlist problem

We claim that $k = 3$. Obviously $k = 2$ is not enough: the numbers $1$, $2$ or $8$, $9$ have odd divisor sums.

Now suppose that the sum $\sigma(n)$ of all positive divisors of $n$ is odd. Consider a decomposition $n = 2^r \cdot m$, where $r \ge 0$ and $m$ is an odd positive integer. Then the set of odd divisors of $n$ coincides with the set of odd divisors of $m$. Hence $\sigma(n)$ has the same parity as $\sigma(m)$. Also, $\sigma(m)$ has the same parity as the number of divisors of $m$, since all of them are odd. But the divisors of $m$ can be grouped into pairs $(d, m/d)$, where $d \le \sqrt{m}$, except for the divisor $\sqrt{m}$ if it is an integer. It follows that the number of divisors of $m$ is odd if and only if $m$ is a perfect square. Hence the $\sigma(n)$ is odd if and only if $n$ is a perfect square or a perfect square multiplied by $2$.

Therefore, if three consecutive positive integers all have odd divisor sums, then each of them is either a perfect square or a perfect square multiplied by $2$. Thus at least two of these numbers are perfect squares or at least two are perfect squares multiplied by $2$. In both cases we obtain two distinct positive perfect squares with difference at most $2$, which is not possible. This proves that $k = 3$ has the required property.