The 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\ne 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$.