Maths Olympiad Prep

Library / /16 of 16

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it United States

Problem:

We are given nn identical cubes, each of size 1×1×11 \times 1 \times 1. We arrange all of these nn cubes to produce one or more congruent rectangular solids, and let B(n)B(n) be the number of ways to do this. For example, if n=12n=12, then one arrangement is twelve 1×1×11 \times 1 \times 1 cubes, another is one 3×2×23 \times 2 \times 2 solid, another is three 2×2×12 \times 2 \times 1 solids, another is three 4×1×14 \times 1 \times 1 solids, etc. We do not consider, say, 2×2×12 \times 2 \times 1 and 1×2×21 \times 2 \times 2 to be different; these solids are congruent. You may wish to verify, for example, that B(12)=11B(12)=11.
Find, with proof, the integer mm such that 10m<B(2015100)<10m+110^{m}<B\left(2015^{100}\right)<10^{m+1}.

Solution

Solution:

The exact value of B(2015100)B\left(2015^{100}\right) is 921,882,251,894,177921,882,251,894,177. Thus m=14m=14.

Let us estimate B(n)B(n). First we note that the actual primes do not matter, just the exponents. Since 2015=513312015=5 \cdot 13 \cdot 31, we need to find B(p100q100r100)B\left(p^{100} q^{100} r^{100}\right), where p,q,rp, q, r are distinct primes.

Let's first try an easier case: n=p3q3r3n=p^{3} q^{3} r^{3}. For each divisor of nn, there will be one or more different "formations" of congruent rectangular solids. For example, we could take the divisor d=p2qrd=p^{2} q r and one possible formation would be dd solids, each with dimensions p×q×qr2p \times q \times q r^{2}.

So each formation is a sort of 4-tuple, where the first coordinate is dd, the number of solids, and the remaining three "coordinates" are the dimensions of the solid. In our example, the formation is the sort-of 4-tuple
(p2qr;{p,q,qr2}). \left(p^{2} q r ;\{p, q, q r^{2}\}\right) .
We call it a "sort-of" 4-tuple and use funny notation because the last three "coordinates" are an unordered trio, but the first coordinate—the number of solids—matters; it belongs in the first spot.

Making things even worse, each number paqbrcp^{a} q^{b} r^{c} in our pseudo-4-tuple corresponds to an ordered triple (a,b,c)(a, b, c) of exponents, where 0a,b,c30 \leq a, b, c \leq 3. The example above is thus represented by
((2,1,1);{(1,0,0),(0,1,0),(0,1,2)}). ((2,1,1) ;\{(1,0,0),(0,1,0),(0,1,2)\}) .
It is confusing, however, to combine ordered and non-ordered reasoning, so let us suppose, temporarily, that the order of the three dimension triples in the pseudo-4-tuple does matter. In fact, let's assume that the order matters for all 4 triples. Then our pseudo-4-tuple (of ordered triples) becomes a genuine ordered 4-tuple of ordered triples. Thus the following 4-tuples are considered to be different:
((2,1,1);(1,0,0),(0,1,0),(0,1,2))((2,1,1);(0,1,0),(0,1,2),(1,0,0))((0,1,0);(2,1,1),(1,0,0),(0,1,2)) \begin{aligned} & ((2,1,1) ;(1,0,0),(0,1,0),(0,1,2)) \\ & ((2,1,1) ;(0,1,0),(0,1,2),(1,0,0)) \\ & ((0,1,0) ;(2,1,1),(1,0,0),(0,1,2)) \end{aligned}
Notice that the first two actually represent the same formation, but the last one is different.

This makes the counting much easier. For the divisor dd with exponents (a,b,c)(a, b, c), the possible dimensions are the three vectors
(a1,b1,c1),(a2,b2,c2),(a3,b3,c3), \left(a_{1}, b_{1}, c_{1}\right),\left(a_{2}, b_{2}, c_{2}\right),\left(a_{3}, b_{3}, c_{3}\right),
where
a+a1+a2+a3=3,b+b1+b2+b3=3,c+c1+c2+c3=3 \begin{aligned} a+a_{1}+a_{2}+a_{3} & =3, \\ b+b_{1}+b_{2}+b_{3} & =3, \\ c+c_{1}+c_{2}+c_{3} & =3 \end{aligned}
Each of these three equations represents a solution to a classic ball-and-urn counting problem with four distinguishable urns (since there are four terms) and three balls (since the sums are all equal to 3). For example, the number of ordered solutions to the first equation is the number of ordered 4-tuples (a,a1,a2,a3)\left(a, a_{1}, a_{2}, a_{3}\right) with coordinates adding to 3, and there are (63)\binom{6}{3} such 4-tuples.

Since we can pick solution 4-tuples for each of the three equations independently, there are (63)3\binom{6}{3}^{3} different ordered solutions (ordered 4-tuples of ordered triples). For example, one solution may be
((2,1,1);(1,0,0),(0,1,0),(0,1,2)) ((2,1,1) ;(1,0,0),(0,1,0),(0,1,2))
However, we are currently counting each of the 4!4! permutations of these as different. We want to order the count by the first triple (after all, this first triple indicates the number of blocks in the formation), but we do not want to count order among the other three triples.

Consequently, we just divide our current count by 3!3!, getting
(63)36 \frac{\binom{6}{3}^{3}}{6}
This is not an exact value (in fact, it is not even an integer), because it improperly accounts for solids where two or more of the dimensions are equal. For example, suppose that the number of solids is prqp r q and the dimension of each of the solids is pr×pr×q2p r \times p r \times q^{2}. Thus the first triple (for the number of solids) is (1,1,1)(1,1,1), and the three next triples (for the dimension) are (1,0,1),(1,0,1)(1,0,1),(1,0,1), and (0,2,0)(0,2,0). These three triples do not have 6 different permutations, since two are equal; they have just 3 different permutations. Likewise, if the last three triples were the same (for example, if the dimensions of the solid was pq×pq×pqp q \times p q \times p q then there is only one ordering of these three triples.

In the more general case, where n=ptqtrtn=p^{t} q^{t} r^{t}, our approximation would yield the formula (t+33)3/6\binom{t+3}{3}^{3} / 6, which slightly misses the exact value. We say "slightly," because the formula is a degree-9 polynomial whose first term is t9/1296t^{9} / 1296, but the number of formations for which there are two equal dimensions would be a polynomial of degree 6 and the number of formations for which there are three equal dimensions is a polynomial of degree 33.

Thus for large values of tt, the first term t9/1296t^{9} / 1296 completely dominates. Plugging in t=100t=100 yields 1018/129610^{18} / 1296, which is approximately 101510^{15}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.