This puzzle is the twelfth puzzle from Matt Parker's Matt Parker's Maths Puzzles series.
You are creating a marching band. Your marching band must march in rows, but each row must have an equal number of performers in it. You want your marching band to be able to march in exactly 64 different formations.
Fix a marching band with n total players. If there is a valid formation with r
rows, then each row must have the same number of players, write c, and we have
.
Therefore r and c are factors of n.
Also, if r and c are factors of n, we can express n as
,
and we can produce a valid formation with r rows and c players in each row.
This shows us that the number of valid formations is exactly the number of ways
to choose two integers r and c such that
.
Since we can express c as
,
we have only a single degree of freedom in r for some fixed n.
Now the question becomes "What is the smalles number n such that n has exactly 64 factors?".
If
where pi is prime, then we know that n has
factors.
Therefore we are searching for the number
such that
.
This is a small search space, and checking it reveals our n to be 23335171 = 7560.
The facotrs of 7560 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 27, 28, 30, 35, 36, 40, 42, 45, 54, 56, 60, 63, 70, 72, 84, 90, 105, 108, 120, 126, 135, 140, 168, 180, 189, 210, 216, 252, 270, 280, 315, 360, 378, 420, 504, 540, 630, 756, 840, 945, 1080, 1260, 1512, 1890, 2520, 3780, and 7560. These numbers correspond to the possible numbers of rows that the marching band can play in.