Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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/
```
Associated Topics:
High School Number Theory
High School Polyhedra
Middle School Factoring Numbers
Middle School Polyhedra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search