Rectangular Solids from Blocks
Date: 09/25/98 at 02:43:32 From: David Purins Subject: Rectangular Solids made from "n" blocks? I am a mathematics teacher in Alice Springs (Central Australia). I have set a maths project, the solution to which evades me. How many rectangular solids can be made from "n" cube shaped blocks? For example, with 30 blocks there are: 1 x 1 x 30 1 x 2 x 15 1 x 3 x 10 1 x 5 x 6 2 x 3 x 5 We are looking for a formula. I'm thinking that it will be based on prime factors and combinations: Number of prime factors 1 2 3 4 Number of rectangular solids 1 2 5 14 I got these from using different prime numbers (2 x 3 x 5 x 7 for example) to produce numbers of blocks (210 in this case). Then put the prime numbers in to three different columns to represent the three dimensions.
Date: 09/25/98 at 10:57:19 From: Doctor Mitteldorf Subject: Re: Rectangular Solids made from "n" blocks? Dear David, Just a message before we begin. Even if you don't know the solution to a problem, you can still present your thinking process to the class - it's far more advanced and more sophisticated than theirs, and they can learn from the way you approach a problem and the way you follow a lead until it reaches a dead end, then go back and try another lead. Real mathematicians working on real problems are constantly trying this and that. They wouldn't get anywhere if they weren't allowed to make false starts. Students need to be encouraged to follow their thinking where it leads, constantly evaluating and re-evaluating to see if they are on the right track. On to prime factors. I'm going to take you through my thought process, and I've made some progress, but I don't have a complete solution for you. If a number has n prime factors, no duplicates, then each side of the rectangular solid can use none of these (length 1) or all of these (length p1*p2*...*pn) or any combination in between. The number of ways of doing this is the same as the answer to the question, "how many ways are there to apportion n objects among 3 separate bins?" Each bin may contain any number of the objects (including zero) but every one of the n objects must be in one of the bins. Well, the first object can be in any of the n bins, the second object can be in any of the n bins, etc - that's 3^n different ways of apportioning the objects. However, the bins themselves need to be regarded as indistinguishable - that corresponds to the fact that a block with dimension r*s*t is not different from a block s*t*r. So you need to divide by the number of orderings of 3 objects, namely 6. The answer this leads to is 3^n/6. But wait a minute, (thought I). 3^n isn't even divisble by 6. What's going on? I tried a simple example, (2 factors: 6 = 2*3) and saw what it was. Here's the problem: Even though I took care to say "all different" factors, there's still the possibility that there are two empty bins (two sides = 1), and these haven't really been counted six times, though we're dividing by 6 as if they had been. Fortunately, this case is easy to isolate: There are never 3 sides equal to 1. Two sides = 1 can happen in only 3 ways: each of the 3 sides can be the one that's not = 1. So there are 3 cases that should have been counted as 1 when instead they were divided by 6 and counted as 1/2. The solution is to add 1/2. So I get (3^n+3)/6 as an answer for the case where all the factors are different. This is an integer, and it seems to work for the case n = 2 and n = 3, so I have some confidence in it. Now let's jump to the case where all the n prime factors are the same - say, for example, 2^n or 7^n. This becomes the problem of apportioning n indistinguishable objects in 3 indistinguishable bins. I learned how to do this just the other day from one of Doctor Anthony's answers on this Web site: http://mathforum.org/dr.math/problems/chris9.16.98.html Think of putting your n objects on the belt at the grocery checkout, along with two dividers. ooo|oo|ooooooo There are n+2 objects on the belt, and they can be ordered in (n+2)! different ways. But the ordering of the n objects doesn't matter (remember - they're factors that are all the same). Also, the ordering of the 2 dividers doesn't matter. So you should divide by n!2!. The result is (n+2)(n+1)/2. But this isn't right either. We have the same ordering problem as above, which makes us want to divide by 6, but we can't divide by 6 because (n+2)(n+1)/2 isn't necessarily divisible by 6, and on closer inspection we see that we haven't overcounted all possibilities by a factor of 6, just the ones where all three sides are of different lengths. It's harder now to count which cases have two sides (or possibly 3 sides) that are the same. I'm going to go back now to try a different approach. Suppose we count ways to insert the dividers between the o's such that the number of o's is decreasing monotonically from left to right. For example, take n = 7 o's: then the first group could hold 3, 4, 5, 6, or 7. If it held 3, then the second group could only be 3; if it held 4, then the second group could be 3 or 2; if it held 5, the second group could be 2 or 1; if it held 6, the second group must be 1; and if it held 7 then the second group must be 0. This means that for 2^7 blocks, there are 7 different ways to make rectangular solids. But it's not clear to me yet what the pattern is, or how to generalize to 2^n blocks. Furthermore, when we've finished that, we still have to deal with those in-between cases where the prime factors aren't all different and aren't all the same. I'm going to stop here for now. For the present, I hope this has been as stimulating for you as it has been for me. - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum