Skip to content

Instantly share code, notes, and snippets.

@nlitsme
Last active August 14, 2020 20:29
Show Gist options
  • Save nlitsme/d678e18ae9211585a98d01ec2ffab88c to your computer and use it in GitHub Desktop.
Save nlitsme/d678e18ae9211585a98d01ec2ffab88c to your computer and use it in GitHub Desktop.
mpmp12 Marchingband solution

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 8 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 Gaussian Integers ( complex numbers with integer coordinates ):

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment