Problem

Source: South African Mathematics Olympiad 2020, Problem 6

Tags: combinatorics



Marjorie is the drum major of the world's largest marching band, with more than one million members. She would like the band members to stand in a square formation. To this end, she determines the smallest integer $n$ such that the band would fit in an $n \times n$ square, and lets the members form rows of $n$ people. However, she is dissatisfied with the result, since some empty positions remain. Therefore, she tells the entire first row of $n$ members to go home and repeats the process with the remaining members. Her aim is to continue it until the band forms a perfect square, but as it happens, she does not succeed until the last members are sent home. Determine the smallest possible number of members in this marching band.