South African Mathematical Olympiad Third Round

The answer is $1000977$. Let $M$ be the number of members of the marching band. We prove by induction that Marjorie's approach always yields a perfect square at some point, unless $M$ is of the form $M = (2^a + b)^2 + 2b + 1$ ($a, b$ nonnegative integers, $0 \le b < 2^a$) or $(2^a + b)^2 + 2^a + 3b + 2$ ($a, b$ nonnegative integers, $0 \le b < 2^a - 1$), in which case all members are eventually sent home.

This is true for $M = 1$ (which is not of either form), since the single member forms a $1 \times 1$ square, and for $M = 2$ (which is of the form $M = (2^a + b)^2 + 2b + 1$ with $a = b = 0$), in which case the two members form an incomplete $2 \times 2$ square and are sent home.

For the induction step, suppose that $M > 2$ and take $n$ to be the unique positive integer for which $(n-1)^2 < M \le n^2$. Then the $M$ members will stand in an $n \times n$ square, and if $M \ne n^2$, then $n$ members are sent home. We write $n - 1 = 2^a + b$, where $2^a$ is the greatest power of 2 less than or equal to $n-1$, and $0 \le b < 2^a$. We claim that the process reaches a perfect square if and only if neither $M = (2^a + b)^2 + 2b + 1$ nor $M = (2^a + b)^2 + 2^a + 3b + 2$ (the latter only for $b < 2^a - 1$).

Suppose first that $M \le n^2 - n + 1$, so that $M - n \le (n-1)^2 = (2^a + b)^2$. By the induction hypothesis, the process never reaches a perfect square if and only if $M - n = (2^a + b - 1)^2 + 2b - 1$ or $M - n = (2^a + b - 1)^2 + 2^a + 3b - 1$. The former equation is equivalent to $M = (2^a + b - 1)^2 + 2^a + 3b$. However, this is impossible since it gives

$$M = (2^a + b - 1)^2 + 2^a + 3b = (2^a + b)^2 - (2^a - b - 1) \le (n - 1)^2.$$

The latter equation yields
$$M = (2^a + b - 1)^2 + 2^{a+1} + 4b = (2^a + b)^2 + 2b + 1,$$
which is what we wanted to prove.

Likewise, if $M > n^2 - n + 1$, then $M - n > (n-1)^2$. So by the induction hypothesis, the process never reaches a perfect square if and only if either $M - n = (2^a + b)^2 + 2b + 1$ or $M - n = (2^a + b)^2 + 2^a + 3b + 2$. In the former case, we get
$$M = (2^a + b)^2 + 2^a + 3b + 2,$$
which is exactly the desired statement. Note, however, that $M \neq n^2$ (otherwise, the band forms a perfect square immediately) requires $b < 2^a - 1$. In the latter case, we obtain
$$M = (2^a + b)^2 + 2^{a+1} + 4b + 3 = (2^a + b + 1)^2 + 2(b + 1) > n^2,$$
which is impossible.

This completes the induction. Now note that $1000000 = 1000^2$ and $1000 = 2^9 + 488$, so the smallest number greater than $1000000$ that is of the form $(2^a + b)^2 + 2b + 1$ or $(2^a + b)^2 + 2^a + 3b + 2$ is $(2^9 + 488)^2 + 2 \cdot 488 + 1 = 1000977$.