Marching Band problem
In this document I describe a solution to the ‘marchingband’ problem as stated on think-maths:
What is the fewest number of performers you require for your marching band to
have 64 marching options? (Only whole positive numbers will be accepted)
Where a ‘marchingband’ can march only in a rectangular shape.
Also, I present solutions in higher dimensions, and a solution with complex numbers, and a proof that the 2D case has a solution for all numbers of marching options.
Solution
Given marchingband of size N, where the prime factorization of N is:
N = product( p_i ^ n_i, i=0..k-1 )
Then, since each prime p_i will be one of: 0, 1, .. or n_i times in the width, the number of ways you can partition this in two numbers, ‘width times length’:
m = product( n_i+1, i=0..k-1 )
Now finding what set of values n will make 64 together:
2*2*2*2*2*2
4*2*2*2*2
8*2*2*2
4*4*2*2
8*4*2
4*4*4
8*8
64
Since we are looking for the smallest number, we use these values for exponents of the first couple of prime numbers from {2, 3, 5, 7, 11, 13}.
2*3*5*7*11*13 = 30030
2^3*3*5*7*11 = 9240
2^7*3*5*7 = 13440
2^3*3^3*5*7 = 7560
2^7*3^3*5 = 17280
2^3*3^3*5^3 = 27000
2^7*3^7 = 279936
2^63 = 9223372036854775808
So the smallest number is: 7560 people in a marching band.
Oeis A005179 lists the minimal groupsize for a specific number of arrangements, or, as OEIS puts it: The smallest number with exactly n divisors.
Can we proof that a solution always exists?
In two dimensions, take a groupsize of 2^(m-1), this will give the following possible arrangements, width * length:
2^0 * 2^(m-1)
2^1 * 2^(m-2)
...
2^(m-2) * 2^1
2^(m-1) * 2^0
Which makes a total of m different marchingband arrangements. This may not be the minimal groupsize, but
there clearly is a solution for an arbitrary m.
For three dimensions, a group of 1 has only one arrangement, while a prime-sized group will have three arrangements, with the group aligned to the x, y and z axis. I think this shows that getting two arrangements is impossible in 3D.
The OEIS table A007425 lists the number of arrangements for a given groupsize in three dimensions, or as OEIS puts it: The number of ordered factorizations of n as n = r s t.
Higher dimensional arrangements
Higher dimensional aliens would need a lot less individuals to have 64 different arrangements for their marchingband, In 4 dimensions, you would need 30 individuals, and in 6 dimensions you could do with just 6.
This table shows the minimum groupsize to get M different arrangements in n dimensions:
top-to-bottom is the number of arrangements, `left-to-right’ is the number of dimensions.
M, dim= 2 3 4 5 6 7 8 9
0 : 0 0 0 0 0 0 0 0
1 : 1 1 1 1 1 1 1 1
2 : 2 - - - - - - -
3 : 4 2 - - - - - -
4 : 6 - 2 - - - - -
5 : 16 - - 2 - - - -
6 : 12 4 - - 2 - - -
7 : 64 - - - - 2 - -
8 : 24 - - - - - 2 -
9 : 36 6 - - - - - 2
10 : 48 8 4 - - - - -
11 : 1024 - - - - - - -
12 : 60 - - - - - - -
13 : 4096 - - - - - - -
14 : 192 - - - - - - -
15 : 144 16 - 4 - - - -
16 : 120 - 6 - - - - -
17 : 65536 - - - - - - -
18 : 180 12 - - - - - -
19 :262144 - - - - - - -
20 : 240 - 8 - - - - -
21 : 576 32 - - 4 - - -
22 : 3072 - - - - - - -
23 : - - - - - - - -
24 : 360 - - - - - - -
25 : 1296 - - 6 - - - -
26 : 12288 - - - - - - -
27 : 900 30 - - - - - -
28 : 960 64 - - - 4 - -
29 : - - - - - - - -
30 : 720 24 - - - - - -
31 : - - - - - - - -
32 : 840 - - - - - - -
33 : 9216 - - - - - - -
34 :196608 - - - - - - -
35 : 5184 - 16 8 - - - -
36 : 1260 36 - - 6 - 4 -
37 : - - - - - - - -
38 :786432 - - - - - - -
39 : 36864 - - - - - - -
40 : 1680 - 12 - - - - -
41 : - - - - - - - -
42 : 2880 - - - - - - -
43 : - - - - - - - -
44 : 15360 - - - - - - -
45 : 3600 48 - - - - - 4
46 : - - - - - - - -
47 : - - - - - - - -
48 : 2520 - - - - - - -
49 : 46656 - - - - 6 - -
50 : 6480 - - - - - - -
51 :589824 - - - - - - -
52 : 61440 - - - - - - -
53 : - - - - - - - -
54 : 6300 60 - - - - - -
55 : 82944 512 - - - - - -
56 : 6720 - 32 - 8 - - -
57 : - - - - - - - -
58 : - - - - - - - -
59 : - - - - - - - -
60 : 5040 72 - - - - - -
61 : - - - - - - - -
62 : - - - - - - - -
63 : 14400 96 - - - - - -
64 : 7560 - 30 - - - 6 -
65 :331776 - - - - - - -
66 : 46080 1024 - - - - - -
67 : - - - - - - - -
68 :983040 - - - - - - -
69 : - - - - - - - -
70 : 25920 - - 16 - - - -
71 : - - - - - - - -
72 : 10080 - - - - - - -
73 : - - - - - - - -
74 : - - - - - - - -
75 : 32400 - - 12 - - - -
76 : - - - - - - - -
77 :746496 - - - - - - -
78 :184320 2048 - - - - - -
79 : - - - - - - - -
80 : 15120 - 24 - - - - -
81 : 44100 210 - - - - - 6
82 : - - - - - - - -
83 : - - - - - - - -
84 : 20160 192 64 - - 8 - -
85 : - - - - - - - -
86 : - - - - - - - -
87 : - - - - - - - -
88 :107520 - - - - - - -
89 : - - - - - - - -
90 : 25200 120 - - - - - -
91 : - 4096 - - - - - -
92 : - - - - - - - -
93 : - - - - - - - -
94 : - - - - - - - -
95 : - - - - - - - -
96 : 27720 - - - - - - -
97 : - - - - - - - -
98 :233280 - - - - - - -
99 :230400 - - - - - - -
100 : 45360 216 36 - - - - -
101 : - - - - - - - -
102 : - - - - - - - -
103 : - - - - - - - -
104 :430080 - - - - - - -
105 :129600 8192 - - - - - -
106 : - - - - - - - -
107 : - - - - - - - -
108 : 50400 180 - - - - - -
109 : - - - - - - - -
110 :414720 - - - - - - -
111 : - - - - - - - -
112 : 60480 - - - - - - -
113 : - - - - - - - -
114 : - - - - - - - -
115 : - - - - - - - -
116 : - - - - - - - -
117 :921600 - - - - - - -
118 : - - - - - - - -
119 : - - - - - - - -
120 : 55440 16384 128 - - - 8 -
121 : - - - - - - - -
122 : - - - - - - - -
123 : - - - - - - - -
124 : - - - - - - - -
125 :810000 - - 30 - - - -
126 :100800 288 - 32 12 - - -
127 : - - - - - - - -
128 : 83160 - - - - - - -
129 : - - - - - - - -
130 : - - - - - - - -
131 : - - - - - - - -
132 :322560 - - - - - - -
133 : - - - - - - - -
134 : - - - - - - - -
135 :176400 240 - - - - - -
136 : - 32768 - - - - - -
137 : - - - - - - - -
138 : - - - - - - - -
139 : - - - - - - - -
140 :181440 - 48 - - - - -
141 : - - - - - - - -
142 : - - - - - - - -
143 : - - - - - - - -
144 :110880 - - - - - - -
145 : - - - - - - - -
146 : - - - - - - - -
147 : - - - - - - - -
148 : - - - - - - - -
149 : - - - - - - - -
150 :226800 432 - - - - - -
151 : - - - - - - - -
152 : - - - - - - - -
153 : - 65536 - - - - - -
154 : - - - - - - - -
155 : - - - - - - - -
156 : - - - - - - - -
157 : - - - - - - - -
158 : - - - - - - - -
159 : - - - - - - - -
160 :166320 - 60 - - - - -
161 : - - - - - - - -
162 :352800 420 - - - - - -
163 : - - - - - - - -
164 : - - - - - - - -
165 : - 1536 256 - - - - 8
166 : - - - - - - - -
167 : - - - - - - - -
168 :221760 576 - - - - - -
169 : - - - - - - - -
170 : - - - - - - - -
171 : -131072 - - - - - -
172 : - - - - - - - -
173 : - - - - - - - -
174 : - - - - - - - -
175 : - - - 24 - - - -
176 :967680 - - - - - - -
177 : - - - - - - - -
178 : - - - - - - - -
179 : - - - - - - - -
180 :277200 360 - - - - - -
181 : - - - - - - - -
182 : - - - - - - - -
183 : - - - - - - - -
184 : - - - - - - - -
185 : - - - - - - - -
186 : - - - - - - - -
187 : - - - - - - - -
188 : - - - - - - - -
189 :705600 480 - - - - - -
190 : -262144 - - - - - -
191 : - - - - - - - -
192 :332640 - - - - - - -
193 : - - - - - - - -
194 : - - - - - - - -
195 : - - - - - - - -
196 : - - - - - 12 - -
197 : - - - - - - - -
198 : - 3072 - - - - - -
Complex arrangements
There may be another, even stranger race of aliens, where their marchingbands can be arranged in rectangles where the sides can be measured in complex numbers:
Now the minimum size, is a marching band of 150 aliens:
1 x 150
2 x 75
3 x 50
5 x 30
6 x 25
10 x 15
15 x 10
25 x 6
30 x 5
50 x 3
75 x 2
150 x 1
i x -150i
2i x -75i
3i x -50i
5i x -30i
6i x -25i
10i x -15i
15i x -10i
25i x -6i
30i x -5i
50i x -3i
75i x -2i
150i x -i
3+21i x 1-7i
15+45i x 1-3i
30+60i x 1-2i
75+75i x 1-i
15+30i x 2-4i
60+30i x 2-i
5+15i x 3-9i
10+20i x 3-6i
18+24i x 3-4i
25+25i x 3-3i
45+15i x 3-i
24+18i x 4-3i
30+15i x 4-2i
3+9i x 5-15i
6+12i x 5-10i
15+15i x 5-5i
5+10i x 6-12i
9+12i x 6-8i
20+10i x 6-3i
21+3i x 7-i
12+9i x 8-6i
6+8i x 9-12i
15+5i x 9-3i
3+6i x 10-20i
12+6i x 10-5i
8+6i x 12-9i
10+5i x 12-6i
1+3i x 15-45i
2+4i x 15-30i
5+5i x 15-15i
9+3i x 15-5i
3+4i x 18-24i
6+3i x 20-10i
4+3i x 24-18i
3+3i x 25-25i
1+2i x 30-60i
4+2i x 30-15i
3+i x 45-15i
2+i x 60-30i
1+i x 75-75i
Author
Willem Hengeveld itsme@xs4all.nl
